Skip to content

Remove unsound eta reduction to fix the stack overflow in generic instances#45

Merged
Unisay merged 2 commits into
mainfrom
issue-32/fix-recursive-instance-stack-overflow
Jun 12, 2026
Merged

Remove unsound eta reduction to fix the stack overflow in generic instances#45
Unisay merged 2 commits into
mainfrom
issue-32/fix-recursive-instance-stack-overflow

Conversation

@Unisay

@Unisay Unisay commented Jun 12, 2026

Copy link
Copy Markdown
Collaborator

Closes #32. Supersedes #33 by including its test module, extended with a main so the generated code is actually executed.

What was wrong

eq x y = genericEq x y on a recursive data type overflowed the Lua stack as soon as a comparison was attempted. The instance dictionary referenced itself eagerly: calling eqList dictEq rebuilt the dictionary chain, which contained eqList dictEq as a strict argument, and so on without a base case. The user's eta-expanded method definition is the documented PureScript idiom for breaking exactly this cycle, and the upstream JS backend preserves it. pslua's optimizer destroyed it: the eta reduction rule rewrites λx. M x to M, which moves the evaluation of M from every call of the lambda to the point where the lambda was constructed. In a strict target that is not semantics preserving.

There were two reasons #33 could not reproduce this. Its golden test only checked compilation and luacheck, never running the code, so this PR adds a main and an eval golden to exercise the runtime path. And with a single generic type in the module, the generic machinery is used once, so the inliner inlines it and the self-reference happens to land under another lambda. The new GenericEqTwoTypes module defines two generic-derived Eq instances, which keeps the machinery multiply used and reproduces the overflow on current main.

The fix

The eta reduction rule is removed rather than restricted, because every shape of M worth reducing is unsafe in its own way: an application may diverge (the case above); a reference turns a recursive group member f = λx. g x into the value binding f = g, which the laziness analysis ran too early to see, so nothing wraps it in runtime-lazy and g may be uninitialized; an abstraction is already covered by beta reduction. The full argument lives in Note [Eta reduction is unsound] in the optimizer.

Removing the rule surfaced a latent gap in renameShadowedNames: it only processed exports, not bindings. Eta reduction used to collapse the nested same-named lambdas that now survive into codegen, so luacheck started flagging shadowed upvalues, and a shadowed reference with a non-zero index inside a binding would crash the Lua code generator with UnexpectedRefBound. The renaming pass now covers bindings as well.

Tests

  • Golden/BugListGenericEq: the module from Test generic list equality #33 plus a main; its eval golden locks list equality at runtime.
  • Golden/GenericEqTwoTypes: the red test for this fix. Stack overflow before, correct output after.
  • Golden/DerivedFunctor: locks the derived Functor symptom from the issue comments (map over an Either-like and a recursive Tree type). It already behaves correctly on main; the golden keeps it that way.
  • A unit test pins down that the optimizer leaves λx. M x intact.
  • Golden diffs across the seven affected modules change shape only: lambdas that used to be eta-reduced are now preserved. All eval goldens pass.

The remaining symptom from the issue comments, a long do block failing with "chunk has too many syntax levels", has a different root (lexical nesting of bind continuations against Lua's hard parser limit) and is tracked in #46.

Unisay added 2 commits June 12, 2026 14:44
Three eval-golden modules exercising the symptoms reported in #32:

- BugListGenericEq: the original repro from PR #33, extended with a
  main function so the generated Lua is actually executed (the PR
  only checked compilation and luacheck, which is why the runtime
  stack overflow went unnoticed).
- DerivedFunctor: derived Functor instances mapped over an Either-like
  and a recursive Tree type.
- GenericEqTwoTypes: two generic-derived Eq instances in one module.
  The duplication keeps the generic machinery multiply-used, so the
  inliner does not mask the eager self-reference in the instance
  dictionary: evaluation overflows the Lua stack until the optimizer
  stops eta-reducing user code.

golden.ir/golden.lua files are intentionally not included: they are
generated on first test run, and the fix in the next commit changes
their shape anyway.
In a strict language, rewriting (λx. M x) to M moves the evaluation
of M from every call of the lambda to the point where the lambda was
constructed. When M transitively references the binding being defined,
as it does in instance dictionaries deriving Eq via Generic for
recursive data types, the eagerly evaluated self-reference recurses
without a base case and overflows the Lua stack at dictionary
construction time. Eta-expanding the method by hand is the documented
PureScript idiom for breaking exactly this cycle, and the upstream JS
backend preserves it; pslua's optimizer destroyed it.

The rule is removed rather than restricted: every shape of M worth
reducing is unsafe in its own way. Details are in the new
Note [Eta reduction is unsound].

Removing eta reduction surfaced a latent gap in renameShadowedNames:
it only processed uberModuleExports, leaving shadowed locals in
uberModuleBindings unrenamed. Previously eta reduction happened to
collapse the offending nested lambdas; without it, luacheck flags the
shadowing, and a shadowed reference with a non-zero index inside a
binding would crash the Lua code generator with UnexpectedRefBound.
The renaming pass now covers bindings as well.

Golden files change shape only: lambdas that used to be eta-reduced
are now preserved. All eval goldens, including the new repros, pass.
@Unisay Unisay self-assigned this Jun 12, 2026
@Unisay Unisay added the bug Something isn't working label Jun 12, 2026
@Unisay Unisay mentioned this pull request Jun 12, 2026
@Unisay Unisay merged commit 160f3c5 into main Jun 12, 2026
1 check passed
@Unisay Unisay deleted the issue-32/fix-recursive-instance-stack-overflow branch June 12, 2026 14:29
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

bug Something isn't working

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Stack overflow in Prelude generic tests

1 participant