Skip to content

Generalise deep-nesting breaker to any monad + applicative spines (#108)#110

Merged
Unisay merged 2 commits into
mainfrom
issue-108/general-nesting-breaker
Jun 22, 2026
Merged

Generalise deep-nesting breaker to any monad + applicative spines (#108)#110
Unisay merged 2 commits into
mainfrom
issue-108/general-nesting-breaker

Conversation

@Unisay

@Unisay Unisay commented Jun 22, 2026

Copy link
Copy Markdown
Collaborator

Closes #108.

Problem

FlattenDeepBinds flattens deep nesting that would otherwise overflow Lua 5.1's parser-nesting cap (~200 levels). It recognised deep chains by instance nameControl.Bind.bind/discard, or a Bind dictionary shape. That recognition is precise but brittle and incomplete:

  • The State-transformer miss fixed in Flatten deeply-nested non-Effect/ST do-blocks #107 was exactly a recognition gap.
  • Applicative chains (ado/apply, =<</bindFlipped) carry their depth in a value-argument position rather than a trailing lambda, and were never covered — they fell through to a NestingTooDeep compile 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, the Control.Bind name constants, mkResolve/topLevel/letLocals, and the threaded resolve parameter — ~200 lines). Existing bind goldens are unchanged: same structural shape → identical lambda-lift. Now also covers non-bind CPS / bracket / with-style nesting.

Strategy B — application-spine sequentialisation (new). Handles contiguous App spines 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 $tmp local every segmentSize frames.

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 segmentSize frames bounds both at once: each segment nests ≤ segmentSize deep 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 App spines — the two are naturally disjoint.

What is not replaced

  • MagicDo (Effect/ST imperative 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.
  • NestingCheck (post-codegen backstop) is unchanged.
  • Deep case trees (nested if/then/else) need branch- and laziness-aware hoisting; left on NestingCheck as a residual follow-up.

Soundness

Lua is strict, so every App callee and argument is evaluated regardless of use. Strategy B sequentialises strict positions in evaluation order and never hoists across Abs/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 after renameShadowedNames, so the freshly-named $kont/$tmp binders shift no de Bruijn index.

Tests

  • Structural-recognition unit: a chain whose head is not a bind now flattens (proves the name-gate is gone).
  • Strategy-B units + 200-example Hedgehog properties for both left- and right-nested spines: free-reference preservation, idempotence, nesting-depth reduction.
  • Three runnable goldens whose generated Lua loads and evaluates under stock Lua 5.1 (eval oracle):
    • LongCallbackChain (A) — recursive-guarded non-bind CPS 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/hlint clean.

…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).

Copilot AI left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 FlattenDeepBinds with structural recognition for continuation chains (f action (\x -> ...)) and add a second strategy for deep App spines using $tmp segmentation.
  • 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.

Comment thread lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs
Comment thread exe/Main.hs Outdated
Comment thread docs/QUIRKS.md
Comment thread test/Language/PureScript/Backend/IR/FlattenDeepBinds/Spec.hs
- 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.
@Unisay Unisay merged commit 96c5dae into main Jun 22, 2026
2 checks passed
@Unisay Unisay deleted the issue-108/general-nesting-breaker branch June 22, 2026 19:54
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

General monad-agnostic nesting breaker: drop bind/discard name-gating in flattenDeepBinds

2 participants