M2compiler-V3/docs/analysis_generics.md

Analysis — adding generics to m2compiler-V3

Update 2026-10-08 (branch generics-inc1). Two things changed since this analysis: (1) V3 now has an AST and Lower emits from it, so the "V3 has no AST" premise in §3 is stale — though the substitution-scope re-parse is still the pragmatic route, because the AST stores resolved TypeIndex, not type names; (2) the chosen syntax is the ISO 10514-2 refinement form (GENERIC … MODULE + MODULE X = G(args)), per ../Generics/m2generic-syntaxe-analysis.md, not IMPORT X<T>.

Done (Increment 1, commit e1d0472): grammar recognition of the four module categories — GENERIC DEFINITION/IMPLEMENTATION MODULE with TYPE formals, and refining DEFINITION/IMPLEMENTATION MODULE X = G(actuals). Formals are entered as unresolved alias types (SymTab.EnterTypeParam); refinements are recorded. A refinement still produces an empty module.

Next (Increment 2): instantiate by re-parsing the generic source with a substitution scope, driven by a driver session pre-pass — record each generic's def/impl file path; on a refinement, re-open the generic, bind the formals to the actuals, name the module X, dedup, and lower it before the importer. Requires moving the normal body's BeginDef into the ; branch (so the refinement does not pre-register X), a SymTab.EnterTypeParamBound, a grammar instantiation context + accessors, and driver re-parse logic.

Study reviewed: ../Generics/ (the three m2-generics-coco-r-*.md analyses, the m2generic/ prototype: M2Generic.atg, gm2-gcc-0.2.atg → gm2-gcc-generics-0.3.atg, src/GenericGen.mod, templates/{Stack,List,Map}.g*).

Verdict in one line: the study's recommendation (integrate into the compiler, not a preprocessor) is right — but its plan is written for an AST-based compiler, and V3 has no AST, so the practical design is re-entrant template parsing with a type-substitution scope, not AST specialization.

1. What the study proposes

Two options, with a clear lean to the second:

1. Integrated preprocessor — the grammar accepts IMPORT Stack<INTEGER>; a tool instantiates templates, rewrites the user's source (IMPORT Stack<INTEGER> → IMPORT StackInteger), then gm2 compiles the result.
2. Fully in the compiler — the compiler understands X<T> natively, specializes internally, type-checks, and generates code; no gm2, no source rewriting.

m2generic is a competent option-1 prototype:

• M2Generic.atg (48 lines) parses a .gin file of INSTANTIATE Name<Type> FROM "x.gdef", "x.gmod";.
• GenericGen (Generate/Generate2) does lexical substitution of the identifier T (or K,V) outside strings/chars/comments, plus module renaming via MakeName/MakeName2 (Stack<INTEGER> → StackInteger), writing real .def/.mod.

• gm2-gcc-generics-0.3.atg adds the generic syntax to the full gm2 grammar's Import:

  GenericTypeActual       = Qualident.
  GenericTypeActualList   = GenericTypeActual { "," GenericTypeActual }.
  GenericModuleDesignator = Ident "<" GenericTypeActualList ">".
  ImportModule            = Ident | GenericModuleDesignator.
  ImportModuleList        = ImportModule { "," ImportModule }.
  Import = "FROM" ImportModule "IMPORT" IdentList ";" |
         "IMPORT" ImportModuleList ";".
  

Its README already flags the gap: parsing ≠ generation — the import-rewriting step (source→source) is still missing.

The supporting docs (analysis-0, analysis-1) survey Modula-2 generic techniques (ADDRESS + SYSTEM, code generation, generic modules, procedure parameters, opaque types) and conclude that for a custom compiler with OOP the in-compiler route is preferable, with a 3-level plan: type generics → multiple parameters → generics + OOP.

2. Assessment of the study

Strengths. Right conclusion for a custom compiler; good survey of the design space; a working prototype that pins the naming convention and the X<T> syntax; the 3-level staging is sensible.

Weaknesses (for the in-compiler path).

• Lexical T replacement is fragile — it can't tell the type parameter from a coincidentally-named user identifier, and it must special-case strings/comments/chars by hand. No nesting, no constraints, no shadowing discipline.
• Errors point at generated code, not the source.
• gm2 stays the type-checker — the whole point of having V3 is not to need it.
• Hard-wired arity — MakeName/MakeName2 bake in 1–2 parameters; Map<K,V> is a special case, not a general map.
• No instance dedup and no caching across instantiations.
• No AST to specialize — see below.

3. The critical mismatch: V3 has no AST

The study's recommended architecture is:

Generic AST → instantiation → specialized AST → type check → codegen

V3's frontend is a Coco/R grammar with inline semantic actions (M2.atg) that call SymTab/QbeGen while parsing — single-pass, declaration-before-use, no intermediate tree. So "specialize the AST" is not directly implementable. Two ways to read "integrate into the compiler":

• (A) Internal monomorphization via a substitution scope — when an instance is needed, re-parse the generic template with a scope that binds the type parameter(s) to the actual type(s), producing ordinary symbols + code under a mangled module name. No lexical replacement, no tree: the existing TypeIdent/Lookup path simply finds T as a type. This is V3's native analogue of the study's "specialized AST", and strictly better than GenericGen.
• (B) True type-parameterized symbols — carry T abstractly and specialize at instantiation. Much harder without an AST; a redesign.

(A) is the target.

4. Recommended design for V3 (option A)

Syntax (minimal, grammatical subset first):

GENERIC DEFINITION MODULE Stack<T>;
  TYPE Stack; PROCEDURE Push(VAR s : Stack; x : T); ...
END Stack.

GENERIC IMPLEMENTATION MODULE Stack<T>; ... END Stack.

Use:

IMPORT Stack<INTEGER>;
FROM Stack<INTEGER> IMPORT Stack, Push;

Mechanism, as a session-expansion pre-pass over the driver's unit list (reusing the fact that V3 already compiles several units — def + impl + program — per session):

1. Discover IMPORT Name<Args> / FROM Name<Args> IMPORT … in the inputs. (Cheap token scan, or fold it into the parser's import action.)
2. Synthesize each distinct instance Name<Args…> once (dedup cache), topologically ordered before its importer.
3. Parse the template (.gdef then .gmod) with a substitution scope live: push a scope binding T (or K,V) to the resolved actual type indices; the normal TypeIdent/Lookup path resolves T. Module/type names are mangled per instance (Stack<INTEGER> → StackInteger).
4. The importer then resolves StackInteger as an ordinary module: full type checking and real codegen, no source rewriting, no external tool, no gm2.

Naming: generalise the mangle to N parameters (Map<INTEGER,REAL> → MapIntegerReal) and to nested actuals (Stack<Stack<INTEGER>> → e.g. StackStackInteger, hashed if long).

Staging

• Increment 1 — single type parameter, module-level generics, def + impl, IMPORT X<T> / FROM X<T> IMPORT …, dedup, substitution-scope parse. (Stack<INTEGER>, Stack<REAL>.)
• Increment 2 — multiple parameters (Map<K,V>) — a map, not special cases.
• Increment 3 — nested generics, user types as actuals, caching.
• Increment 4 — constraints (e.g. T must be ordinal), then generics + OOP (GENERIC CLASS).

Difficulty, risk, guardrails

• Parser/scanner re-entrancy is the main new mechanism. Prefer the pre-pass (reuses the existing multi-file loop, avoids mid-parse re-entrancy); only make Parse callable from an action if the pre-pass proves insufficient.
• Fixpoint is the guard: the compiler uses no generics, so the image must stay byte-identical; the risk concentrates in driver/parser changes.
• First end-to-end increment is a moderate piece — of the order of the CLASS-lowering work (a focused day-plus).

Decisions to make up front

• Syntax for the generic definition/implementation and the import form.
• Mangling scheme for N parameters and nesting.
• Where instantiation happens (driver pre-pass vs parser action).
• Constraint model (even if none are implemented initially, leave room).
• Whether the generic source lives in .gdef/.gmod files or is recognised inside ordinary .def/.mod by the GENERIC keyword.

5. Concrete changes from the study

1. Drop lexical T replacement for the in-compiler path — use a substitution scope; keep GenericGen only as a test oracle.
2. Remove gm2 from the final pipeline (V3 type-checks).
3. Generalise mangling to N params / nesting; add instance dedup.
4. Decide the constraint model before implementing.
5. Scope the syntax to GENERIC … MODULE X<T>; + IMPORT X<T> first; FROM X<T> IMPORT … next.

6. Bottom line

The ../Generics study is a solid survey and its recommendation (in-compiler) is right for V3. Its concrete plan assumes an AST, which V3 doesn't have, so the realizable design is re-entrant template parsing with a type-substitution scope plus a session-expansion/dedup pre-pass — no AST rewriting, no textual substitution, no gm2. That is a genuine language feature of roughly CLASS-lowering scale, and it fits V3's architecture and self-hosting guard.