plum

#treesitter#compiler#wasm

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

ea186e4 — Peter John 2026-07-20T14:59:56+05:30 
docs: add design spec for generics monomorphization
Files changed (1) hide show
  1. docs/superpowers/specs/2026-07-20-generics-monomorphization-design.md +115 -0
docs/superpowers/specs/2026-07-20-generics-monomorphization-design.md ADDED
@@ -0,0 +1,115 @@
1
+ # Generics monomorphization
2
+
3
+ ## Problem
4
+
5
+ Generic type parameters (single lowercase letters: `a`, `b`, `c`, `d`) are supported today only
6
+ at the syntax and permissive-type-check level: `type Box(a) = value: a`, `trait Comparable(a: Ord)
7
+ = compareTo(other: a) -> Int`, and generic function params (`wrap(value: a) -> Bool`, `pair(first:
8
+ a, second: b) -> Bool`) all parse and type-check (`plum-checker` treats an unresolved generic
9
+ param permissively, the same way it treats any unmodeled/unknown type). `plum-wasm-codegen` has no
10
+ representation for a generic parameter at all — any attempt to compile a generic class/function
11
+ hits its permissive-fallback path (`ValType::I32` treated as "pointer to unmodeled type") without
12
+ ever resolving what concrete type is actually present at a given call site, so field
13
+ loads/stores and arithmetic on generic-typed values compile with the wrong width or fail outright.
14
+
15
+ This is the single largest remaining gap blocking `libs/std`'s actual `Option`/`Result`/`List`/
16
+ `Map` from compiling — **but fixing generics alone does not get there**: `libs/std/list.plum` and
17
+ `map.plum` also use syntax that doesn't exist in the grammar at all today (closures `|v| ...`,
18
+ `Nil`, `?.` optional chaining, `:=`, decorators like `@HasTrait`, colon-arrow return types). This
19
+ work targets **only** the currently-documented generic syntax (the shapes already exercised in
20
+ `examples/types.plum` and `examples/functions.plum`), not those std lib files.
21
+
22
+ ## Approach: monomorphization by specialization
23
+
24
+ Chosen over a type-erasure/boxed-uniform-representation approach because the rest of the compiler
25
+ already assumes every value has a statically-known concrete wasm type (`I32`/`I64`/`F64`) at
26
+ codegen time — monomorphization preserves that invariant everywhere, at the cost of compiling one
27
+ specialized copy per concrete instantiation actually used (standard Rust/C++-template-style
28
+ trade-off), rather than requiring a new runtime representation (boxed/tagged values, out-of-band
29
+ type metadata) that the rest of the codegen doesn't have anywhere else.
30
+
31
+ ### 1. Instantiation-site collection
32
+
33
+ Walk the whole program to determine every concrete `(generic item, concrete type argument list)`
34
+ combination actually needed:
35
+
36
+ - Explicit concrete type annotations naming a generic item with concrete arguments (`Box[Int]`,
37
+ `Box(Int)` — both bracket and paren syntax are already accepted per the grammar).
38
+ - Constructor calls where a generic class's field types resolve the class's generic parameters via
39
+ unification against the supplied argument types (`Box(value: 5)` → `a = Int`).
40
+ - Generic function/method calls where argument types resolve the function's generic parameters via
41
+ unification (`wrap(5)` → `a = Int`; `pair(1, "x")` → `a = Int, b = Str`).
42
+
43
+ This reuses `plum-checker`'s existing unification (`unify`, `infer_expr`) — extended so a generic
44
+ parameter name occurring in a declared type position is treated as a fresh unification variable
45
+ bound per call site, instead of being ignored/treated as an opaque unmodeled type name.
46
+
47
+ ### 2. Specialization mechanism
48
+
49
+ For each unique `(generic item, concrete type args)` pair, produce a substituted copy of the
50
+ `Class`/`Fn` AST item: every occurrence of a generic parameter name in a **declared type
51
+ position** (field types, param types, return types) is replaced by its concrete resolved
52
+ `ast::Type`, under an internal mangled name (e.g. `Box$Int`, `wrap$Int`, `pair$Int$Str` — `$`
53
+ joins the base name and each concrete type argument in declaration order). The substituted copy is
54
+ then run through the **existing, unmodified** non-generic checker (`build_global_tables`,
55
+ `check_fn`) and codegen (`compile_fn_body`, class field layout) pipeline — neither of those needs
56
+ to know or care that its input started out generic.
57
+
58
+ Mangled names are purely internal (`ClassEnv`/`MethodEnv`/`func_ids` keys, wasm export names where
59
+ relevant) — user source keeps calling `Box(...)`/`wrap(...)` normally; the compiler resolves which
60
+ specialization a given call site needs from its own already-inferred concrete argument types and
61
+ rewrites the call/construction internally to reference the matching mangled specialization.
62
+
63
+ A generic **method** (`get<List>(i: Int) -> a`) specializes alongside its receiver class: once
64
+ `List` is specialized as `List$Int`, every method declared with receiver `List` gets a
65
+ correspondingly substituted, separately-specialized copy keyed `List$Int::get`, following the
66
+ existing `MethodEnv` key shape (`(receiver type name, method name)`) with the receiver name being
67
+ the mangled one.
68
+
69
+ ### 3. Transitive/recursive generics — worklist to a fixed point
70
+
71
+ A freshly-specialized body can itself call another still-generic function/method — now with
72
+ concrete types known throughout that specialized body, so this is a new, fully-resolved
73
+ instantiation site. Processed as a worklist: seed it from every concrete instantiation site
74
+ reachable from non-generic code, specialize each, scan the newly-produced specialized bodies for
75
+ further instantiation sites they introduce, and repeat until no new specializations are added.
76
+
77
+ A recursion-depth guard bounds this (e.g. a hard cap on total specializations per compile, or on
78
+ nesting depth of a type argument list) so a pathological unbounded-expanding generic (a generic
79
+ type that embeds a larger instantiation of itself, with no concrete base case) fails with a clear
80
+ compile error rather than hanging or exhausting memory.
81
+
82
+ ## Out of scope
83
+
84
+ - Trait-bound enforcement (`trait Comparable(a: Ord)`'s `Ord` bound) — stays exactly as permissive
85
+ as it is today. Monomorphization only needs to substitute concrete types through, not verify
86
+ bounds are satisfied.
87
+ - Generic code with zero reachable concrete instantiation anywhere in the program is simply never
88
+ specialized or compiled — this tree-shaking falls out of the worklist approach for free, it
89
+ isn't a separate feature.
90
+ - `libs/std/list.plum` and `map.plum` compiling as-is — as established above, they need several
91
+ other unimplemented language features first (closures, `Nil`/optional chaining, decorators,
92
+ colon-arrow return syntax) that are unrelated to generics and out of scope here.
93
+ - A general, unbounded-generic-recursion *detector* beyond a simple depth/count cap — this is a
94
+ defensive backstop against a degenerate program, not a soundness analysis.
95
+
96
+ ## Testing plan
97
+
98
+ - **Checker tests** (`plum-checker/tests/checker_tests.rs`): a generic class instantiated at two
99
+ different concrete types in one program (`Box(Int)` and `Box(Str)`) resolves each usage's field
100
+ access to the correct concrete type; a generic function called with different concrete argument
101
+ types at different call sites infers correctly per site; a multi-param generic (`Pair`/`Map`-
102
+ shaped, two independent type params) resolves both params independently per call site.
103
+ - **Codegen tests** (`plum-wasm-codegen/tests/codegen_tests.rs`, compiled and executed via
104
+ `wasmtime` matching existing style): a generic class specialized at `Int` and at `Str` in the
105
+ same program, confirming the two specializations don't alias (distinct compiled bodies, correct,
106
+ independent field widths/offsets); a generic function called at multiple concrete types in one
107
+ program; a generic method dispatched on a specialized generic class; a transitively-generic call
108
+ chain (a specialized generic function itself calling another still-generic function) proving the
109
+ worklist reaches a correct fixed point; a deliberately-pathological unbounded-recursive generic
110
+ type, asserting `compile_source` returns a clear error rather than hanging or panicking.
111
+ - **Examples**: extend `examples/types.plum`/`examples/functions.plum` (currently declarations
112
+ only) with actual instantiations and a `main` that runs them end-to-end. Update README's Known
113
+ Gaps to drop the "user-defined generics aren't monomorphized" bullet, while adding/keeping a note
114
+ that this alone doesn't unblock `libs/std`'s actual `List`/`Map`/`Option`/`Result` (separate,
115
+ unrelated gaps remain there).