Generalise deep-nesting breaker to any monad + applicative spines (#108)#110
Merged
Conversation
…es (#108) FlattenDeepBinds recognised deep chains by instance name (Control.Bind.bind/discard or a Bind dictionary shape). That was precise but brittle: the State-transformer miss fixed in #107 was exactly a recognition gap, and applicative (ado/apply, =<<) chains were never covered. Replace name-anchored recognition with structure-anchored recognition, and add a second strategy for the application-spine shape. Strategy A (continuation lambda-lifting) now fires on any `f action (\x -> ...)` chain, not just a recognised bind: drop the `isBindHead` guard from `asStep` and delete the whole recogniser/resolution machinery (`isBindHead`, `headReducesToBind`, `denotes`, `isBindDict`, `peelAlias`, the Control.Bind name constants, `mkResolve`/`topLevel`/`letLocals`, the threaded `resolve` parameter). Existing bind goldens are unchanged (same structural shape → identical lambda-lift). This covers do-blocks of any monad plus non-bind CPS / bracket / with-style nesting. Strategy B (application-spine sequentialisation, new) handles chains whose depth lives in a value-argument position rather than a trailing lambda — ado/apply (`apply (apply ... ) ...`), =<</bindFlipped, deep left-associated <>, and any other nested call spine (all contiguous App trees at the IR level). It peels the deepest application path and rebuilds it bottom-up (Lua's evaluation order for these spines), sealing the accumulator into a fresh $tmp local every `segmentSize` frames. This bounds both Lua 5.1 per-function limits at once: parser nesting (~200 levels) and locals (200) — a naive full A-normalisation flattens nesting but overflows the 200-local cap, so segmentation is required. Dispatch tries A first; a bind chain hides its depth under lambdas, so its application-spine depth is tiny and B only ever sees the remaining deep App spines. MagicDo (Effect/ST imperative lowering) and NestingCheck (post-codegen backstop) are unchanged. Deep case trees (nested if/then/else) remain on NestingCheck as a residual follow-up. Tests: structural-recognition unit (non-bind head now flattens), Strategy-B units + 200-example properties (free-ref preservation, idempotence, depth reduction for left- and right-nested spines), and three runnable goldens whose generated Lua loads and evaluates under stock Lua 5.1: LongCallbackChain (A, recursive-guarded CPS combinator → 300), LongApplyChain (B, *> spine → Just 300), LongBindFlipped (B, =<< spine → Just 301).
There was a problem hiding this comment.
Pull request overview
This PR generalizes the Lua backend’s “deep nesting breaker” so more deeply-nested PureScript expression shapes compile into Lua 5.1-loadable code, extending beyond name-gated monadic bind chains to structural continuation chains and deep application spines (e.g. applicative chains and =<<).
Changes:
- Replace name/dictionary-shape recognition in
FlattenDeepBindswith structural recognition for continuation chains (f action (\x -> ...)) and add a second strategy for deepAppspines using$tmpsegmentation. - Expand/adjust test coverage with new unit + property tests, plus new runnable goldens for callback chains, applicative chains, and
=<<chains. - Update user-facing docs and error messaging to reflect the broadened flattening behavior.
Reviewed changes
Copilot reviewed 17 out of 23 changed files in this pull request and generated 4 comments.
Show a summary per file
| File | Description |
|---|---|
| lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs | Implements structural Strategy A and new Strategy B for deep App spines. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Updates optimizer pipeline comment to describe both strategies. |
| test/Language/PureScript/Backend/IR/FlattenDeepBinds/Spec.hs | Adds/updates unit + property tests for both strategies. |
| test/ps/golden/Golden/LongCallbackChain/Test.purs | New golden source for non-bind CPS continuation chain (Strategy A). |
| test/ps/golden/Golden/LongApplyChain/Test.purs | New golden source for deep applicative spine via *> (Strategy B). |
| test/ps/golden/Golden/LongBindFlipped/Test.purs | New golden source for deep =<< chain (Strategy B). |
| test/ps/output/Golden.LongCallbackChain.Test/golden.lua | New generated Lua golden for callback-chain runnable golden. |
| test/ps/output/Golden.LongCallbackChain.Test/eval/golden.txt | Expected runtime output for callback-chain golden. |
| test/ps/output/Golden.LongCallbackChain.Test/eval/.gitignore | Ignores eval harness actual output. |
| test/ps/output/Golden.LongApplyChain.Test/golden.lua | New generated Lua golden for applicative-spine runnable golden. |
| test/ps/output/Golden.LongApplyChain.Test/eval/golden.txt | Expected runtime output for applicative-spine golden. |
| test/ps/output/Golden.LongApplyChain.Test/eval/.gitignore | Ignores eval harness actual output. |
| test/ps/output/Golden.LongBindFlipped.Test/golden.lua | New generated Lua golden for =<< runnable golden. |
| test/ps/output/Golden.LongBindFlipped.Test/eval/golden.txt | Expected runtime output for =<< golden. |
| test/ps/output/Golden.LongBindFlipped.Test/eval/.gitignore | Ignores eval harness actual output. |
| exe/Main.hs | Updates the NestingTooDeep user hint text. |
| docs/QUIRKS.md | Documents the newly-flattened shapes (Strategy A + Strategy B). |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
- FlattenDeepBinds module header: correct the Strategy B description to segmented A-normalisation (a $tmp every segmentSize frames, not per App) and state the real soundness argument — data flow is preserved exactly; operand evaluation order may shift for argument-position-deep spines, which is sound because strict full evaluation makes divergence order-independent and the off-spine operands of non-Effect/ST monadic spines are pure and total. - sequentialiseSpine haddock + the "bounds output spine depth" test comment: drop the inaccurate "every application / spine depth 1" wording (it is segmented). - docs/QUIRKS.md: describe the spine breaker as segmented, noting it keeps the local count under Lua's 200-per-function cap. - exe/Main.hs NestingTooDeep hint: mention that a single bind chain forwarding too many variables can still bail (upvalue cap), so it is not always flattened. Documentation/comment-only; generated Lua is unchanged.
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 #108.
Problem
FlattenDeepBindsflattens deep nesting that would otherwise overflow Lua 5.1's parser-nesting cap (~200 levels). It recognised deep chains by instance name —Control.Bind.bind/discard, or aBinddictionary shape. That recognition is precise but brittle and incomplete:ado/apply,=<</bindFlipped) carry their depth in a value-argument position rather than a trailing lambda, and were never covered — they fell through to aNestingTooDeepcompile error where they could compile.Change
Replace name-anchored recognition with structure-anchored recognition, and add a second strategy dispatched by where the depth lives.
Strategy A — continuation lambda-lifting (existing, name-gate removed). Fires on any
f action (\x -> ...)chain, not just a recognised bind. This deletes the entire recogniser/resolution machinery (isBindHead,headReducesToBind,denotes,isBindDict,peelAlias, theControl.Bindname constants,mkResolve/topLevel/letLocals, and the threadedresolveparameter — ~200 lines). Existing bind goldens are unchanged: same structural shape → identical lambda-lift. Now also covers non-bindCPS /bracket/with-style nesting.Strategy B — application-spine sequentialisation (new). Handles contiguous
Appspines whose depth is in a value-argument position:ado/apply,=<</bindFlipped, deep left-associated<>, any nested call spine. It peels the deepest application path and rebuilds it bottom-up — Lua's evaluation order for these spines — sealing the accumulator into a fresh$tmplocal everysegmentSizeframes.Segmentation (not full A-normalisation) is required because there are two Lua 5.1 per-function limits: a naive full ANF flattens the parser nesting but then overflows the 200-local cap (~300 locals for a 300-deep spine). Segmenting every
segmentSizeframes bounds both at once: each segment nests ≤segmentSizedeep and the local count is ≈depth / segmentSize.Dispatch tries A first; a bind chain hides its depth under lambdas, so its application-spine depth is tiny and B only ever sees the remaining deep
Appspines — the two are naturally disjoint.What is not replaced
Effect/STimperative lowering) is a different kind of solution (local x = m()is only valid where computations are thunks); kept, still runs first, still consumes Effect/ST chains before the general breaker sees them.casetrees (nestedif/then/else) need branch- and laziness-aware hoisting; left onNestingCheckas a residual follow-up.Soundness
Lua is strict, so every
Appcallee and argument is evaluated regardless of use. Strategy B sequentialises strict positions in evaluation order and never hoists acrossAbs/branch boundaries, so it preserves evaluation order and divergence. Strategy A only relocates continuations and forwards live variables by name — it never reorders, drops, or duplicates a call. The pass runs afterrenameShadowedNames, so the freshly-named$kont/$tmpbinders shift no de Bruijn index.Tests
LongCallbackChain(A) — recursive-guarded non-bindCPS combinator, ~300 deep →300.LongApplyChain(B) —*>applicative spine, ~300 deep →(Just 300).LongBindFlipped(B) —=<<spine, ~300 deep →(Just 301).Full suite green (313 examples, 0 failures); no existing golden churned.
fourmolu/hlintclean.