Remove unsound eta reduction to fix the stack overflow in generic instances#45
Merged
Merged
Conversation
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Closes #32. Supersedes #33 by including its test module, extended with a
mainso the generated code is actually executed.What was wrong
eq x y = genericEq x yon a recursive data type overflowed the Lua stack as soon as a comparison was attempted. The instance dictionary referenced itself eagerly: callingeqList dictEqrebuilt the dictionary chain, which containedeqList dictEqas 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 xtoM, which moves the evaluation ofMfrom 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
mainand 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 newGenericEqTwoTypesmodule 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
Mworth reducing is unsafe in its own way: an application may diverge (the case above); a reference turns a recursive group memberf = λx. g xinto the value bindingf = g, which the laziness analysis ran too early to see, so nothing wraps it in runtime-lazy andgmay be uninitialized; an abstraction is already covered by beta reduction. The full argument lives inNote [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 withUnexpectedRefBound. The renaming pass now covers bindings as well.Tests
Golden/BugListGenericEq: the module from Test generic list equality #33 plus amain; 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.λx. M xintact.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.