Section 2: Complete Type Inference

Goal: Full Hindley-Milner type inference

SPEC: spec/08-types.md, spec/09-properties-of-types.md

Status: Complete — Full Hindley-Milner inference with actionable type error messages. 4,078 Rust tests in workspace (all pass), 101 Ori spec tests across inference/bindings/lambdas/collections (all pass), all 11 compile-fail tests pass including 5 conversion hint tests (int(x), float(x), str(x), byte(x), [x]).

2.1 Unification Algorithm

• Implement: Occurs check — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/unify/mod.rs — occurs_check_detects_infinite_type (prevents T = [T])
  • Ori Tests: tests/spec/inference/unification.ori — 25 tests (all pass)

• Implement: Substitution application via resolve() — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/unify/mod.rs — path_compression, error_propagates, never_unifies_with_anything
  • Ori Tests: tests/spec/inference/unification.ori — substitution verified through unification tests

• Implement: Generalization (let-polymorphism) — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/unify/mod.rs — generalize_identity_function, generalize_monomorphic, generalize_does_not_generalize_outer_vars, let_polymorphism_example
  • Ori Tests: tests/spec/inference/polymorphism.ori — 8 tests (all pass)
  • Verified: Polymorphic identity @id (x) = x works with both int and str

• Implement: Instantiation — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/unify/mod.rs — instantiate_identity_scheme, instantiate_non_scheme, instantiate_twice_gives_different_vars
  • Ori Tests: tests/spec/inference/polymorphism.ori

2.2 Expression Type Inference

• Implement: Local variable inference — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/infer/expr.rs — 85+ expression inference tests
  • Ori Tests: tests/spec/expressions/bindings.ori — 17 tests (all pass)
  • Verified: let x = 42 infers int, let x = x + 1 chains correctly

• Implement: Lambda parameter inference — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/infer/expr.rs — lambda inference tests
  • Ori Tests: tests/spec/expressions/lambdas.ori — 29 tests (all pass)
  • Verified: apply(x -> x + 1, 41) correctly infers x: int from context

• Fix: Closure-returning-closure inference bug

  • (n: int) -> (int) -> int = { (x: int) -> int = base + n + x } — infers () return instead of (int) -> int when outer closure returns inner closure (test_aot_closure_capturing_closure)

• Implement: Generic type argument inference — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/infer/ — generic inference tests
  • Ori Tests: tests/spec/inference/generics.ori — 22 tests (all pass)

• Implement: Collection element type inference — spec/08-types.md § Type Inference [done] (2026-02-10)

  • Rust Tests: ori_types/src/infer/expr.rs — collection inference tests
  • Ori Tests: tests/spec/types/collections.ori — 35 tests (all pass)
  • Verified: [1, 2, 3] infers [int], {"a": 1} infers {str: int}

2.3 Type Error Improvements

• Implement: Expected vs found messages — spec/08-types.md § Type Errors [done] (2026-02-10)

  • Rust Tests: ori_types/src/ — 20+ type error tests
  • Ori Tests: tests/compile-fail/type_mismatch_arg.ori — 1 test (passes)

• Implement: Type conversion hints — spec/08-types.md § Type Errors [done] (2026-02-16)

  • Implement: Edit-distance typo suggestions (“did you mean?”) [done] (2026-02-10)
  • Rust Tests: ori_types/src/infer/env.rs — 21 tests including edit distance for typo suggestions
  • Ori Tests: tests/compile-fail/type_hints.ori — 5 non-skipped tests pass
  • Implement: Conversion function suggestions in type mismatch errors (int(x), float(x), str(x), byte(x), [x]) [done] (2026-02-16)
  • Ori Tests: tests/compile-fail/type_hints.ori — all 10 tests pass (5 conversion hints + 5 existing) [done] (2026-02-16)

• Implement: Source location in errors — spec/08-types.md § Type Errors [done] (2026-02-10)

  • Ori Tests: tests/compile-fail/return_type_mismatch.ori — 1 test (passes)
  • Verified: All type errors include span information

Compile-fail test harness: Implemented via #compile_fail("expected_error") attribute. All 11 compile-fail tests pass: cargo st tests/compile-fail/

2.4 Section Completion Checklist

• All 2.1 items complete — unification, occurs check, generalization, instantiation [done] (2026-02-10)
• All 2.2 items complete — local variable, lambda, generic, collection inference (reopened: closure-returning-closure inference bug)
• All 2.3 items complete — expected/found, hints, source locations [done] (2026-02-10)
• 3,792 Rust unit tests pass (ori_types) [done] (2026-02-10)
• Spec and compile-fail tests pass — 101 Ori spec tests + 11 compile-fail [done] (2026-02-10)
• Run full test suite: ./test-all.sh — all pass [done] (2026-02-10)

Exit Criteria Met: Complete type inference with error messages and hints.