js-hindley-milner-let-polymorphism-checker
Done. The solution is built, verified, and written up in ~/SOLUTION.md.
| File | Contents |
|---|---|
SOLUTION.md |
Self-contained markdown: problem statement, root-cause analysis, the exact fix (both source files embedded verbatim), and verification. |
hm-checker.js |
Full Damas–Milner checker (lexer, recursive-descent parser, union–find unification with occurs check, schemes, let generalization, fix, precise error reporting, CLI). |
test.js |
Hand-built suite — 57 cases (well over the ~30 required), all passing. |
\f. f f or fix (\f. \x. f [x]) build cyclic a := a -> b / a = [a] bindings that loop forever. Fix: occurs check on every var binding; rejects with infinite type: cannot unify a with (a -> b) … in subterm \f f``.let desugared to lambda → let id = x => x in (id 1, id true) is wrongly monomorphic. Fix: a native let rule — type RHS in the outer env, quantify into a scheme, re-instantiate fresh variables per use — while f => (f 1, f true) stays rejected.\y. let x = y in (x 1, x true) would be accepted as (int, bool). Fix: quantify exactly FV(τ) \ FV(Γ), subtracting each scheme's quant set when computing FV(Γ).let x = x in x must fail as unbound, not as an infinite type; recursion is only legal through monomorphic fix : (a -> a) -> a.cannot unify int with bool (while unifying (int -> a) with (bool -> b)) in subterm \x true``.node test.js → 57/57 cases passed, exit 0.let chain deriving (int, bool) in ~0.2 s, and occurs-check rejection in <1 ms; naive-alternative regressions (desugared let, unguarded unify corruption) documented with actual outputs.# Evidence - Problem class: js-hindley-milner-let-polymorphism-checker - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T04:23:14.912Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "In JavaScript (Node), implement Hindley-Milner type inference for a small lambda calculus whose terms are int/bool literals, variables, lambda abstractions, applications, let-bindings, and an explicit fix primitive. Use union-find unification with a proper occurs check, generalize only type variables absent from the environment when typing let, and keep recursion monomorphic: accept let id = x => x in (id 1, id true) with principal type, reject f => (f 1, f true), and reject any ill-scoped self-reference that lacks fix. Return the principal type or a precise error naming the conflicting types and the subterm where unification failed, and validate against a hand-built suite of ~30 positive and negative cases covering deep let-generalization, occurs-check cycles (x = [x]-style), and generalization under a non-empty environment.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "js-hindley-milner-let-polymorphism-checker", "provider": "openrouter", "solved_at": "2026-09-05T04:23:14.912Z", "version": "20"}Done. The solution is built, verified, and written up in ~/SOLUTION.md.
| File | Contents |
|---|---|
SOLUTION.md |
Self-contained markdown: problem statement, root-cause analysis, the exact fix (both source files embedded verbatim), and verification. |
hm-checker.js |
Full Damas–Milner checker (lexer, recursive-descent parser, union–find unification with occurs check, schemes, let generalization, fix, precise error reporting, CLI). |
test.js |
Hand-built suite — 57 cases (well over the ~30 required), all passing. |
\f. f f or fix (\f. \x. f [x]) build cyclic a := a -> b / a = [a] bindings that loop forever. Fix: occurs check on every var binding; rejects with infinite type: cannot unify a with (a -> b) … in subterm \f f``.let desugared to lambda → let id = x => x in (id 1, id true) is wrongly monomorphic. Fix: a native let rule — type RHS in the outer env, quantify into a scheme, re-instantiate fresh variables per use — while f => (f 1, f true) stays rejected.\y. let x = y in (x 1, x true) would be accepted as (int, bool). Fix: quantify exactly FV(τ) \ FV(Γ), subtracting each scheme's quant set when computing FV(Γ).let x = x in x must fail as unbound, not as an infinite type; recursion is only legal through monomorphic fix : (a -> a) -> a.cannot unify int with bool (while unifying (int -> a) with (bool -> b)) in subterm \x true``.node test.js → 57/57 cases passed, exit 0.let chain deriving (int, bool) in ~0.2 s, and occurs-check rejection in <1 ms; naive-alternative regressions (desugared let, unguarded unify corruption) documented with actual outputs.# Evidence - Problem class: js-hindley-milner-let-polymorphism-checker - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T04:23:14.912Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "In JavaScript (Node), implement Hindley-Milner type inference for a small lambda calculus whose terms are int/bool literals, variables, lambda abstractions, applications, let-bindings, and an explicit fix primitive. Use union-find unification with a proper occurs check, generalize only type variables absent from the environment when typing let, and keep recursion monomorphic: accept let id = x => x in (id 1, id true) with principal type, reject f => (f 1, f true), and reject any ill-scoped self-reference that lacks fix. Return the principal type or a precise error naming the conflicting types and the subterm where unification failed, and validate against a hand-built suite of ~30 positive and negative cases covering deep let-generalization, occurs-check cycles (x = [x]-style), and generalization under a non-empty environment.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "js-hindley-milner-let-polymorphism-checker", "provider": "openrouter", "solved_at": "2026-09-05T04:23:14.912Z", "version": "20"}