صفحهٔ اصلی گشت‌و‌گذار راهنما
ورود
eric
/
M2compiler-V3
1
0
انشعاب 0
پرونده‌ها مشکلات 0 درخواست واکشی 0 ویکی
درخت: cb97d17ade
شاخه‌ها تگ‌ها
M2compiler-V3
/
docs
/
analysis_generics.md

analysis_generics.md 12 KB
تاريخچه خام

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.

Done (Increment 3 — 2026-10-16): value (constant) parameters and actual-kind constraints. A generic formal may now be a value rather than a type: GENERIC DEFINITION MODULE Buf (size : CARDINAL); TYPE T = ARRAY [0..size] OF CHAR; … instantiated by MODULE X = Buf(10);. Grammar: GenericFormal collects its names then accepts : TYPE (type formal) or : TypeIdent (value formal); Actual accepts an integer, charConst or an identifier (type name = type actual, CONST name = value actual). Refinement actuals now carry a kind (type/value) and a value text (refKind/refVal, instKind/instVal + InstActualKind/InstActualVal/RefineActualKind/RefineActualVal). On instantiation a value formal becomes a CONST bound to the actual value; in the abstract template it is a CONST with a placeholder value ("0"), so template parsing succeeds — templates are never lowered, so only instances matter. Constraints: the actual's kind must match the formal (a type formal needs a type actual, a value formal a value one) — otherwise 233; tested by g_badbuf. Suite 210/210, fixpoint OK, corpus unchanged.

Still open for inc3+: a constraint model beyond kind-matching (e.g. "T must be ordinal"), and GENERIC CLASS.

Done (Increment 3 — 2026-10-16, continued): procedure parameters. A formal may be a procedure:

> GENERIC DEFINITION MODULE Sort
>   (Element : TYPE; Compare : PROCEDURE(a, b : Element) : INTEGER);
> PROCEDURE Smaller(x, y : Element) : Element;
> END Sort.
> DEFINITION/IMPLEMENTATION MODULE IntSort = Sort(INTEGER, Cmp.IntCompare);
> ```
> The formal's type is an inline `ProcType`.  The **actual is a
> *qualified* procedure name** (`Cmp.IntCompare`) — the refinement form
> parses its actuals before any import, so a qualified name is the only
> way to reach a procedure without one.  In the **abstract template** the
> formal is entered as a proc-typed callable (KindVar + proc type), so
> the body type-checks (calls are indirect there); at **instantiation**
> it is aliased to the actual procedure:
> - `SymTab.AliasProc(formal, mod, actual)` clones the actual's
>   `SymNode` under the formal's name (keeps `uid`/`mod`/`sym`), so
>   name resolution and argument checks see the actual;
> - `Lower.AliasProc(formal, uid, res, depth, ext)` adds a **proc-table
>   entry** (without disturbing the scope stack) so `Lower`'s call
>   emission targets the actual;
> - `SymTab.ProcBaseByUid` + a uid→base map let `QbeGen.Mangled` recover
>   the actual's base name after the instance scope has been popped.
>
> Verified end-to-end: `Smaller(7, 3)` through `IntSort` (with
> `IntCompare` in a separate module) returns 3.  Suite **211/211**
> (`SortProg`), fixpoint OK, corpus unchanged.

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:

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.