# Analysis — adding generics to m2compiler-V3

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):

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

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

Use:

```modula-2
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.