Specialization

atoll-mono converts polymorphic HIR into the concrete function bodies and layouts required by MIR. It sits after semantic checking because generic calls must already be resolved and typed, and before MIR because frame and storage layout require concrete types.

Why specialize

A source function can quantify types and effects:

source scheme:       map[T, U, E](List[T], fn(T): U using E): List[U] using E
call-site instance:  map[int, string, {Suspend}](...)

The backend should not rediscover that substitution. Specialization gives the call site a concrete callee symbol whose body and signature already contain int, string, and the concrete effect row.

Reachability

The pass walks the call graph from roots. In the ordinary compiler path, roots are non-generic functions with bodies; unit-oriented queries can compute narrower reachable worklists.

For each reachable body, the walker visits call expressions and distinguishes:

• non-generic functions, which remain direct calls;
• generic functions with a concrete substitution, which need a specialization;
• closures or synthetic helper bodies introduced by an instance;
• drop, equality, hashing, or other compiler-required methods that become reachable through concrete layouts.

Discovery is transitive. A specialization can call another generic function, which adds another specialization to the worklist.

Canonical keys

Each function instance is identified by a specialization key:

(generic callee symbol,
 sorted [(quantified type variable, concrete type), ...],
 sorted [(effect-row variable, concrete effect row), ...])

Canonical sorting is load-bearing. Equivalent substitutions discovered from different call sites must compare equal regardless of map iteration or constraint-discovery order.

On a cache hit, the pass reuses the existing concrete symbol. On a cache miss, it:

1. allocates a fresh specialization symbol;
2. deep-clones the generic HIR body;
3. substitutes types and effects throughout the clone;
4. registers the concrete function and relevant side-table entries;
5. rewrites the call site to the concrete symbol;
6. schedules the new body for transitive discovery.

The cache prevents duplicate bodies and gives incremental queries a semantic identity more stable than “the next symbol allocated.”

Source and concrete bodies

After specialization, the project contains both:

• original generic source functions, still associated with their schemes; and
• concrete synthesized functions, with no generic scheme.

Keeping source functions supports diagnostics, tooling, and additional instances. MIR filters generic source functions so only concrete bodies enter backend lowering. Deleting or destructively rewriting the source scheme would make later call sites depend on discovery order.

Type substitution

Substitution must reach more than the function signature. It applies to every type-bearing location in the cloned body, including expression results, patterns, locals, closure captures, call arguments, error channels, and compiler-generated metadata.

A useful invariant is:

No type variable quantified by the source function remains free in its concrete specialization.

Variables owned by an enclosing or independently generic context need separate treatment; blindly replacing every inference variable would corrupt other schemes.

Effect substitution

Effects have their own substitution because a generic higher-order function can inherit an effect row from a callback. Two instances with identical value types but different concrete effect rows are not necessarily interchangeable: one may suspend while another remains pure.

The specialization key therefore distinguishes effect instances. Inherited effect witnesses are routed to the concrete function so diagnostics and later ABI selection can explain why an effect is present.

Generic types

Generic nominal types are not cloned into new source declarations. They remain Named types with concrete argument lists. The pass registers a layout for each used instantiation:

Pair[int, bool]
Pair[string, int]

These are distinct storage shapes even though they share one declaration. Layout registration must be deterministic and complete before MIR computes frames or codegen emits field offsets.

Mutation and ordering

Monomorphization currently mutates shared HIR arenas and tables while walking the worklist. That makes it a meaningful incremental and parallel boundary: discovery order, symbol allocation, nested generic calls, helper reachability, and layout registration interact.

The correctness rule is stronger than “the pass is deterministic on today’s fixture.” New parallel or per-key execution must separate local discovery from a canonical reduce, or otherwise prove that worker completion order cannot choose symbol IDs, cache keys, or emitted unit closure order.

Diagnostics

The specialization layer owns failures such as:

• a supposedly concrete call still contains an unresolved quantified type;
• a substitution does not satisfy a required trait;
• cloned HIR cannot be relocated consistently;
• inherited effect evidence cannot be routed;
• an instantiated layout cannot be registered;
• a required concrete body is absent.

These are reported through the Mono diagnostic layer. They must not be reclassified as codegen errors merely because emission triggered the specialization entry point.

Verification

Tests should cover:

• two call sites sharing an identical specialization;
• two distinct substitutions producing distinct symbols;
• nested generic calls and recursion;
• generic closures and methods;
• concrete struct and enum layouts;
• effect-row distinctions;
• stable specialization and diagnostic order across repeated compiles;
• parity between whole-project and per-key discovery paths.

The output contract is monomorphic HIR suitable for MIR Pipeline, not WebAssembly bytes.