Section 04B: Polymorphic Lambda Monomorphization

Status: Complete — all implementation work done. TPR-04B-013 crash fixed 2026-04-04. All 14 TPR findings resolved. Impl-hygiene clean. 1 verification item externally blocked by roadmap Section 21A (LLVM generic stdlib monomorphization — assert_eq import can’t be monomorphized for codegen). (2026-04-06) Goal: Polymorphic lambda bodies (like a -> b -> a + b with type forall t14. t14 -> t14 -> t14) compile through LLVM with concrete types. Lambda-specific LCFails resolved. The broader 2639 LCFail issue has multiple root causes tracked separately as BUG-04-030.

Context: The JIT EH work (Sections 01-03) expanded LLVM spec test coverage from ~1800 to ~4400 tests via ori test --backend=llvm. This exposed a pre-existing monomorphization gap: polymorphic lambda bodies are lowered to ARC IR with generalized Scheme types (forall t14) instead of concrete types. The LLVM codegen can’t map these to LLVM types, causing 2639 LCFails (60% of spec tests).

Root cause chain:

Type checker generalizes polymorphic lambda types into Schemes: forall t14. t14 -> t14 -> t14
Canonical expression arena stores the Scheme type on the lambda expression node
ARC lowering in lower_lambda (lambda.rs:56) calls pool.resolve_fully(ty) — returns Scheme unchanged (resolve_fully has no Scheme handling)
Line 57 checks pool.tag(resolved_ty) == Tag::Function — FALSE for Scheme, so all params default to Idx::UNIT
Lambda ARC function gets params typed as forall t14 (BoundVar) instead of int
ARC classifier sees BoundVar → Triviality::Unknown → ArcClass::PossibleRef → needs_rc() = true
RC operations inserted for scalar values using wrong LLVM types
LLVM IR verification fails: call void @ori_rc_dec(i64 %cap.0, ptr @"_ori_drop$206")

Why BoundVars can’t be resolved by resolve_fully: During type generalization (unify/generalization.rs), inference Vars are converted to VarState::Generalized and their link to concrete types is severed. BoundVars in the Scheme body reference quantified variables, not pool VarState entries. The concrete types only exist at call-site instantiation (where fresh Vars ARE linked to concrete types via VarState::Link).

Reference implementations:

Lean 4 src/Lean/Compiler/LCNF/ToMono.lean: Type erasure — all type-former params erased before codegen. Closures carry only concrete runtime types.
Rust compiler/rustc_monomorphize/src/collector.rs: Closures are always concrete by MIR — polymorphism resolved in earlier phases. Instance::resolve_closure() produces monomorphic closure instances.
Swift lib/SILOptimizer/IPO/ClosureSpecializer.cpp: Per-specialization cloning at SIL level — generic closures cloned with concrete types at call sites.

Depends on: Section 03 (LLVM emission infrastructure). Does NOT depend on Section 04 bug fixes (orthogonal code paths).

04B.1 Scheme Unwrapping in ARC Lowering

File(s): compiler/ori_arc/src/lower/calls/lambda.rs

The immediate bug: line 57 checks Tag::Function but fails for Tag::Scheme. The Scheme wraps a Function type accessible via pool.scheme_body(). Unwrapping before the tag check allows parameter extraction to proceed.

Note: This alone doesn’t fix the problem — BoundVar params inside the unwrapped Function still aren’t concrete. But it’s a prerequisite for Part 2 and fixes the Idx::UNIT fallback that corrupts ALL params.

Add Scheme unwrapping after resolve_fully: (2026-04-03)

let resolved_ty = self.pool.resolve_fully(ty);
// Unwrap Scheme to reach the inner Function type.
// Scheme types arise from polymorphic lambdas (e.g., `a -> b -> a + b`
// with type `forall t14. t14 -> t14 -> t14`). The inner body is
// Function([BoundVar(0)], Function([BoundVar(0)], BoundVar(0))).
let fn_ty = if self.pool.tag(resolved_ty) == Tag::Scheme {
    self.pool.scheme_body(resolved_ty)
} else {
    resolved_ty
};
let fn_param_types = if self.pool.tag(fn_ty) == Tag::Function {
    // ... existing parameter extraction logic (lines 58-71)

Similarly unwrap Scheme for body_ty at line 117 and return type at line 158: (2026-04-03)

let raw_body_ty = self.expr_type(body);
let body_ty = if self.pool.tag(raw_body_ty) == Tag::Scheme {
    self.pool.scheme_body(raw_body_ty)
} else {
    raw_body_ty
};

Add use ori_types::Tag; if not already imported — already imported (2026-04-03)
Verify: ORI_DUMP_AFTER_ARC=1 ori build /tmp/test_curried.ori shows Function params (Tag::Var, not Idx::UNIT) (2026-04-03)

04B.2 BoundVar Substitution in LLVM Codegen

File(s): compiler/ori_llvm/src/codegen/function_compiler/define_phase.rs

After Part 1, lambda ARC functions have BoundVar-typed params. These must be resolved to concrete types before LLVM emission. The concrete types are available in the parent function’s ARC IR: the parent has a variable with the concrete instantiation type (e.g., %4: (int) -> (int) -> int).

Strategy: In emit_arc_function, before calling compile_lambda_arc, scan the parent’s ARC IR to find the concrete instantiation of each lambda’s Scheme type. Build a BoundVar→concrete substitution map and rewrite the lambda’s var_types.

Add resolve_all_lambda_bound_vars to define_phase.rs: (2026-04-03) Implemented as iterative resolution with global BoundVar/Var map, fallback to Idx::INT for unresolvable types.
```
/// For each lambda with BoundVar-typed params, find the concrete
/// instantiation from the parent function's var_types and rewrite
/// the lambda's param/var types to concrete types.
fn resolve_lambda_bound_vars(
    &self,
    parent_func: &ori_arc::ArcFunction,
    lambda: &mut ori_arc::ArcFunction,
) { ... }
```
Implementation approach:
1. Check if any lambda param has Tag::BoundVar — if not, skip (fast path)
2. Find the PartialApply instruction in parent_func that references this lambda by name
3. Get the PartialApply result variable’s type from parent_func.var_type(dst)
4. If still a Scheme, scan parent for a downstream variable that copies the PartialApply result with a concrete type (the %4: (int) -> ... = %0 pattern)
5. Structurally compare the lambda’s Scheme body (Function with BoundVars) with the concrete Function type to build BoundVar(N) → ConcreteType mapping
6. Walk all lambda.var_types entries: replace any that match a BoundVar in the map
7. Also update lambda.params[i].ty and lambda.return_type
Call resolve_lambda_bound_vars in emit_arc_function before the lambda compile loop: (2026-04-03) Called at line 134 as resolve_all_lambda_bound_vars(&arc_func, &mut lambdas, self.pool) — batch resolution before any individual compilation.
Handle nested lambdas: inner lambda’s parent IS the outer lambda. The resolve must happen transitively — outer lambda resolved first, then inner lambda uses the resolved outer as its parent. (2026-04-03) Implemented via batch resolution: all lambdas resolved together with a global BoundVar→concrete map. Sibling lambdas searched for PartialApply references.
Handle the case where the concrete type can’t be found (fully polymorphic call — no concrete instantiation). In this case, fall back to type erasure: treat all BoundVars as Idx::INT (i64) for LLVM type and ArcClass::Scalar for RC classification. (2026-04-03) Implemented via fallback_bound_vars_to_int() as final pass.
Verify: ORI_DUMP_AFTER_LLVM=1 ori build /tmp/test_curried.ori shows concrete i64 params in lambda LLVM IR (2026-04-03) Note: ARC dump shows pre-resolution types; LLVM IR dump confirms resolution worked — lambda_main_0 takes (i64, i64) -> i64.
Verify: ori run --backend=llvm /tmp/test_curried.ori produces 7 — matches interpreter (2026-04-03)

04B.3 Capture Type Resolution

File(s): compiler/ori_arc/src/lower/calls/lambda.rs

Captures in nested lambdas inherit types from the outer scope’s variable table. For polymorphic outer lambdas, these types may be BoundVars. The same substitution from 04B.2 must apply to capture types.

The resolve_lambda_bound_vars function from 04B.2 already rewrites lambda.params[i].ty — captures ARE params (leading params in the lambda ARC function). Verify that the capture params are also covered by the rewrite. (2026-04-03) Verified: apply_bound_var_map iterates ALL lambda.params including leading capture params. Tested with string-capturing closure — produces correct output.

Add an assertion in compile_lambda_arc: (2026-04-03) Added debug_assert! checking no BoundVar-typed params remain. Assertion passes on all 16,513 tests.

// Verify no BoundVar types remain after resolution.
debug_assert!(
    !lambda.params.iter().any(|p| matches!(self.pool.tag(p.ty), ori_types::Tag::BoundVar)),
    "lambda {} has unresolved BoundVar params after resolution",
    self.interner.lookup(lambda.name),
);

Verify the closure env drop function (in closures.rs) correctly handles the now-concrete types — the existing tag-based dispatch should work since types are no longer BoundVar/Scheme (2026-04-03) Verified: string-capturing closure name -> \{greeting} {name}`produces correct output andORI_CHECK_LEAKS=1` reports zero leaks.

04B.4 Test Matrix

Matrix dimensions:

04B.R Third Party Review Findings

04B.N Completion Checklist

Exit Criteria: ori test --backend=llvm tests/spec/expressions/lambda_mono.ori passes all tests (0 LCFails). Curried/nested polymorphic lambda tests pass through LLVM. No new test failures introduced. ORI_CHECK_LEAKS=1 clean on all RC-typed capture tests. Note: the broader 2639 LCFail issue (BUG-04-030) has 4 distinct root causes; this section addresses Root Cause A (lambda Scheme/BoundVar/Var types).