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