plum

# Generics monomorphization

## Problem

Generic type parameters (single lowercase letters: `a`, `b`, `c`, `d`) are supported today only
at the syntax and permissive-type-check level: `type Box(a) = value: a`, `trait Comparable(a: Ord)
= compareTo(other: a) -> Int`, and generic function params (`wrap(value: a) -> Bool`, `pair(first:
a, second: b) -> Bool`) all parse and type-check (`plum-checker` treats an unresolved generic
param permissively, the same way it treats any unmodeled/unknown type). `plum-wasm-codegen` has no
representation for a generic parameter at all — any attempt to compile a generic class/function
hits its permissive-fallback path (`ValType::I32` treated as "pointer to unmodeled type") without
ever resolving what concrete type is actually present at a given call site, so field
loads/stores and arithmetic on generic-typed values compile with the wrong width or fail outright.

This is the single largest remaining gap blocking `libs/std`'s actual `Option`/`Result`/`List`/
`Map` from compiling — **but fixing generics alone does not get there**: `libs/std/list.plum` and
`map.plum` also use syntax that doesn't exist in the grammar at all today (closures `|v| ...`,
`Nil`, `?.` optional chaining, `:=`, decorators like `@HasTrait`, colon-arrow return types). This
work targets **only** the currently-documented generic syntax (the shapes already exercised in
`examples/types.plum` and `examples/functions.plum`), not those std lib files.

## Approach: monomorphization by specialization

Chosen over a type-erasure/boxed-uniform-representation approach because the rest of the compiler
already assumes every value has a statically-known concrete wasm type (`I32`/`I64`/`F64`) at
codegen time — monomorphization preserves that invariant everywhere, at the cost of compiling one
specialized copy per concrete instantiation actually used (standard Rust/C++-template-style
trade-off), rather than requiring a new runtime representation (boxed/tagged values, out-of-band
type metadata) that the rest of the codegen doesn't have anywhere else.

### 1. Instantiation-site collection

Walk the whole program to determine every concrete `(generic item, concrete type argument list)`
combination actually needed:

- Explicit concrete type annotations naming a generic item with concrete arguments (`Box[Int]`,
  `Box(Int)` — both bracket and paren syntax are already accepted per the grammar).
- Constructor calls where a generic class's field types resolve the class's generic parameters via
  unification against the supplied argument types (`Box(value: 5)` → `a = Int`).
- Generic function/method calls where argument types resolve the function's generic parameters via
  unification (`wrap(5)` → `a = Int`; `pair(1, "x")` → `a = Int, b = Str`).

This reuses `plum-checker`'s existing unification (`unify`, `infer_expr`) — extended so a generic
parameter name occurring in a declared type position is treated as a fresh unification variable
bound per call site, instead of being ignored/treated as an opaque unmodeled type name.

### 2. Specialization mechanism

For each unique `(generic item, concrete type args)` pair, produce a substituted copy of the
`Class`/`Fn` AST item: every occurrence of a generic parameter name in a **declared type
position** (field types, param types, return types) is replaced by its concrete resolved
`ast::Type`, under an internal mangled name (e.g. `Box$Int`, `wrap$Int`, `pair$Int$Str` — `$`
joins the base name and each concrete type argument in declaration order). The substituted copy is
then run through the **existing, unmodified** non-generic checker (`build_global_tables`,
`check_fn`) and codegen (`compile_fn_body`, class field layout) pipeline — neither of those needs
to know or care that its input started out generic.

Mangled names are purely internal (`ClassEnv`/`MethodEnv`/`func_ids` keys, wasm export names where
relevant) — user source keeps calling `Box(...)`/`wrap(...)` normally; the compiler resolves which
specialization a given call site needs from its own already-inferred concrete argument types and
rewrites the call/construction internally to reference the matching mangled specialization.

**Generic enums** (`enum Option = | Some(a) | None` — matching `libs/std`'s real `Option`) are in
scope alongside classes/functions/traits. Unlike `Class`/`Trait`, `ast::Enum` has no explicit
`generics: Vec<GenericParam>` field, and neither does `ast::Fn` — both are detected as generic
implicitly, the same way: a variant's field type name (`EnumVariant.fields: Vec<String>`, for
enums) or a function's param/return type name (for `Fn`) that is a single lowercase letter (`a`,
`b`, `c`, `d` — the grammar's only legal generic-parameter spelling) is treated as an implicit
generic parameter, exactly like a `Class`'s explicit `generics` list entry. Specialization,
mangling, and the worklist apply identically regardless of which item kind introduced the generic
parameter.

A generic **method** (`get<List>(i: Int) -> a`) specializes alongside its receiver class: once
`List` is specialized as `List$Int`, every method declared with receiver `List` gets a
correspondingly substituted, separately-specialized copy keyed `List$Int::get`, following the
existing `MethodEnv` key shape (`(receiver type name, method name)`) with the receiver name being
the mangled one.

### 3. Transitive/recursive generics — worklist to a fixed point

A freshly-specialized body can itself call another still-generic function/method — now with
concrete types known throughout that specialized body, so this is a new, fully-resolved
instantiation site. Processed as a worklist: seed it from every concrete instantiation site
reachable from non-generic code, specialize each, scan the newly-produced specialized bodies for
further instantiation sites they introduce, and repeat until no new specializations are added.

A recursion-depth guard bounds this (e.g. a hard cap on total specializations per compile, or on
nesting depth of a type argument list) so a pathological unbounded-expanding generic (a generic
type that embeds a larger instantiation of itself, with no concrete base case) fails with a clear
compile error rather than hanging or exhausting memory.

## Out of scope

- Trait-bound enforcement (`trait Comparable(a: Ord)`'s `Ord` bound) — stays exactly as permissive
  as it is today. Monomorphization only needs to substitute concrete types through, not verify
  bounds are satisfied.
- Generic code with zero reachable concrete instantiation anywhere in the program is simply never
  specialized or compiled — this tree-shaking falls out of the worklist approach for free, it
  isn't a separate feature.
- `libs/std/list.plum` and `map.plum` compiling as-is — as established above, they need several
  other unimplemented language features first (closures, `Nil`/optional chaining, decorators,
  colon-arrow return syntax) that are unrelated to generics and out of scope here.
- A general, unbounded-generic-recursion *detector* beyond a simple depth/count cap — this is a
  defensive backstop against a degenerate program, not a soundness analysis.

## Testing plan

- **Checker tests** (`plum-checker/tests/checker_tests.rs`): a generic class instantiated at two
  different concrete types in one program (`Box(Int)` and `Box(Str)`) resolves each usage's field
  access to the correct concrete type; a generic function called with different concrete argument
  types at different call sites infers correctly per site; a multi-param generic (`Pair`/`Map`-
  shaped, two independent type params) resolves both params independently per call site.
- **Codegen tests** (`plum-wasm-codegen/tests/codegen_tests.rs`, compiled and executed via
  `wasmtime` matching existing style): a generic class specialized at `Int` and at `Str` in the
  same program, confirming the two specializations don't alias (distinct compiled bodies, correct,
  independent field widths/offsets); a generic function called at multiple concrete types in one
  program; a generic method dispatched on a specialized generic class; a transitively-generic call
  chain (a specialized generic function itself calling another still-generic function) proving the
  worklist reaches a correct fixed point; a deliberately-pathological unbounded-recursive generic
  type, asserting `compile_source` returns a clear error rather than hanging or panicking.
- **Examples**: extend `examples/types.plum`/`examples/functions.plum` (currently declarations
  only) with actual instantiations and a `main` that runs them end-to-end. Update README's Known
  Gaps to drop the "user-defined generics aren't monomorphized" bullet, while adding/keeping a note
  that this alone doesn't unblock `libs/std`'s actual `List`/`Map`/`Option`/`Result` (separate,
  unrelated gaps remain there).