Skip to content

Flatten deeply-nested non-Effect/ST do-blocks#107

Merged
Unisay merged 5 commits into
mainfrom
issue-104/flatten-deep-binds
Jun 22, 2026
Merged

Flatten deeply-nested non-Effect/ST do-blocks#107
Unisay merged 5 commits into
mainfrom
issue-104/flatten-deep-binds

Conversation

@Unisay

@Unisay Unisay commented Jun 22, 2026

Copy link
Copy Markdown
Collaborator

Fixes #104.

Problem

A straight-line do/>>= chain desugars to a right-nested tree of continuation closures, bind m1 (\x1 -> bind m2 (\x2 -> … last)). Past roughly 200 nesting levels Lua's parser refuses to load the chunk at all (chunk has too many syntax levels, LUAI_MAXCCALLS). On the JS/ES backends deep nesting is only a performance cost; on Lua it is a correctness failure, because the file never loads.

#46 fixed this for Effect/ST via magic-do: their computations are thunks, so a chain lowers to a flat statement sequence. That cannot work for an arbitrary monad, where bind m k is an opaque call whose control flow lives inside bind (Maybe short-circuits, lists call k zero or more times, State threads context). #104 is the general case.

The fix: flattenDeepBinds

A new IR pass, wired into optimizedUberModule right after magicDo (so by the time it runs, every Effect/ST chain is already a Let thunk and only other monads remain). It lambda-lifts a long bind chain: the chain is split into fixed-size segments, and each segment's continuation becomes a small named $kontN helper whose free continuation variables are passed as explicit parameters. The result is a flat let of helpers wrapping a shallow body, so nesting no longer grows with chain length.

This relocates closures and forwards their environment, but it never reorders, drops, or duplicates a bind/k call, so it is semantics-preserving for any monad, strict Lua included: the helper calls pass only variables, and binding a helper does not run its body. Recognition precision therefore only decides which expressions get restructured, not correctness.

Two properties make the De Bruijn bookkeeping disappear:

  • The pass runs after renameShadowedNames, so every local is uniquely named. A helper reuses the chain's own binder names as its parameters, so references stay at index 0 with no shifting.
  • The transitive live set falls out of countFreeRefs on the built helper bodies: because a helper's call site passes its live variables explicitly, those variables show up as free references one level up and propagate through the chain automatically.

When a cut's live set would exceed Lua's 60-upvalue cap (LUAI_MAXUPVALUES) the pass bails and leaves the chain nested rather than emit a function that also will not load. Packing the environment into a single table to cut that to one upvalue is a possible later upgrade.

Safety net: NestingCheck

A post-codegen check in Backend.compileModules measures the chunk's maximum nesting depth and rejects it with a clear NestingTooDeep error when it crosses a conservative threshold, instead of writing out Lua that no interpreter can load. The metric mirrors the recursive-descent parser: it counts function bodies, call arguments, and operators, but not the iterative spine of a curried call. This catches whatever flattenDeepBinds bails on, plus the deep-nesting shapes that are not flattened yet (see Scope below).

Tests

  • Golden.LongMaybeBind: a runnable 300-step Maybe do block whose final result reads the first bound variable, forcing it through every lifted helper. The eval oracle is (Just 301). Without the fix the generated Lua fails to load; with it, stock Lua 5.1 runs it.
  • Golden.LongMaybeBindModule: the same chain in module mode (no main), which exercises the IR/Lua goldens.
  • Unit specs for the pass (free-reference preservation, length-independent output nesting, idempotence) and for the detector (depth metric, threshold, the curried-spine case).

The generated golden.lua loads and runs under stock Lua 5.1.5; max nesting is 43 against the ~200 cap. No existing golden changed.

Scope

This handles do/bind chains. Still not flattened, and now reported by the detector instead of silently breaking: applicative chains (ado/apply, bindFlipped), chains whose live set exceeds the upvalue budget, and deep nesting from non-bind constructs (large case trees, long <> concatenations, wide literals). A general Lua-AST-level nesting breaker covering those is filed separately.

Unisay added 4 commits June 22, 2026 10:58
A straight-line `do`/`>>=` chain desugars to a right-nested tree of
continuation closures. Past ~200 nesting levels Lua's parser refuses to
load the chunk (`chunk has too many syntax levels`, LUAI_MAXCCALLS) — a
correctness failure unique to the Lua backend. magic-do (#46) already
fixes Effect/ST; this handles every other monad.

New IR pass `flattenDeepBinds` (runs right after `magicDo`, so only
non-Effect/ST chains remain): it lambda-lifts long bind chains, splitting
them into segments and turning each segment's continuation into a small
named `$kont` helper whose free continuation variables are passed
explicitly. This relocates closures and forwards their environment but
never reorders, drops, or duplicates a bind/k call, so it is
semantics-preserving for any monad. Running after `renameShadowedNames`
makes every local unique, so helpers reuse the chain's own binder names
as parameters and no De Bruijn shifting is needed. When a cut's live set
would exceed Lua's 60-upvalue cap the pass bails and leaves the chain
nested.

Safety net `Language.PureScript.Backend.Lua.NestingCheck`: a post-codegen
check (in `Backend.compileModules`) that rejects a chunk nesting beyond a
conservative threshold with a clear `NestingTooDeep` error instead of
emitting unloadable Lua. Catches whatever `flattenDeepBinds` bails on,
plus not-yet-flattened deep constructs (ado/apply, case/concat/literal).

Tests: golden fixtures Golden.LongMaybeBind (runnable, 300+ Maybe binds
with transitive liveness; eval oracle `(Just 301)`) and
Golden.LongMaybeBindModule (module mode); unit specs for both the pass
(free-ref preservation, bounded nesting, idempotence) and the detector.

Docs: docs/QUIRKS.md updated to describe the flattening and the remaining
unfixed cases.

Fixes #104
NestingCheck previously exercised only call arguments and the curried
spine. Add metric + threshold coverage for the constructs the detector is
the sole safety net for (FlattenDeepBinds does not flatten them): operator
chains, if-ladders, nested table constructors, and field-access chains.

FlattenDeepBinds previously tested only pristine bind chains. Add a chain
interleaved with discard (unused-binder) steps — the shape a real do block
produces once discardUnit.discard collapses to bind — asserting it still
flattens while preserving the bind count and free-reference set.
flattenDeepBinds only flattened pure bind chains built on a literal Bind
dictionary (Maybe, Either). It missed two shapes, so any do block that
interleaves statement lines — most importantly a State block of get/put —
failed to flatten and hit Lua's parser nesting cap (chunk has too many syntax
levels):

- A statement line is a discard, whose Discard Unit instance is discard = bind;
  the optimizer leaves the head as (dict.discard) dictInner, a literal-dict
  field projection wrapping a beta-redex.
- A monad-transformer bind reduces to Control.Bind.bind <dict>, but
  Control.Bind.bind is itself a top-level binding after linking, so the old
  peelAlias-based check resolved through it (into \dict -> dict.bind) and never
  matched the name.

Replace the recognition with a MagicDo-style normaliser (headReducesToBind)
that resolves aliases, projects literal-dictionary fields, and beta-reduces,
but checks the Control.Bind.bind / Control.Bind.discard names before resolving
so they act as stops. The literal-dictionary dict.bind path (Maybe/Either) is
unchanged.

Add runnable golden tests for a long State (get/put) and Either chain, and
replace the synthetic discard unit test with one using the real discard-alias
shape. Maybe/Either goldens are byte-identical; the full suite stays green.

This closes the #104 acceptance gap for State.
Strengthen the recognition's coverage and pin the load-bearing correctness
invariant, after the State surprise showed recognition was undertested.

Monad matrix (runnable goldens, all flatten and load under stock Lua 5.1):
- LongReaderBind:  Reader (single-layer transformer, all bind)
- LongWriterBind:  Writer (all tell -> discard, monoid threading)
- LongExceptBind:  Except (short-circuit monad)
- LongStackBind:   StateT Int (Except String) -- a two-layer transformer
  stack, whose bind dictionary is itself built from nested instances; this is
  the multi-layer head shape no prior test exercised.

Property tests (Hedgehog, 200 examples each) over randomly generated bind/
discard chains of varying length: free references preserved, bind/discard step
count preserved, idempotence, and -- for long chains -- flattening fires and
nesting drops. These guard the invariant the pass rests on (recognition only
governs which chains are restructured, never correctness), independent of any
particular monad's dictionary shape.

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 addresses Lua 5.1’s parser nesting limit by (1) flattening deeply nested non-Effect/ST do/>>= chains at the IR level via lambda-lifting and (2) adding a post-codegen nesting-depth safety check that fails compilation with a clear error instead of emitting unloadable Lua.

Changes:

  • Add IR.FlattenDeepBinds pass to lambda-lift long bind/discard chains into bounded-depth $kontN helper segments.
  • Add Lua.NestingCheck to detect excessive syntactic nesting in generated chunks and throw NestingTooDeep.
  • Add new goldens and specs covering long bind chains across several monads plus unit tests for both the flattener and the nesting detector.

Reviewed changes

Copilot reviewed 43 out of 59 changed files in this pull request and generated 7 comments.

Show a summary per file
File Description
test/ps/spago.dhall Adds PS deps needed by new golden modules (Either/Transformers/Tuples).
test/ps/output/Golden.LongWriterBind.Test/golden.lua New golden Lua output for long Writer bind chain.
test/ps/output/Golden.LongWriterBind.Test/eval/golden.txt Expected runtime output for Writer eval golden.
test/ps/output/Golden.LongWriterBind.Test/eval/.gitignore Ignores eval actual output for Writer golden.
test/ps/output/Golden.LongStateBind.Test/eval/golden.txt Expected runtime output for State eval golden.
test/ps/output/Golden.LongStateBind.Test/eval/.gitignore Ignores eval actual output for State golden.
test/ps/output/Golden.LongStackBind.Test/eval/golden.txt Expected runtime output for stacked StateT/Except eval golden.
test/ps/output/Golden.LongStackBind.Test/eval/.gitignore Ignores eval actual output for stacked golden.
test/ps/output/Golden.LongReaderBind.Test/golden.lua New golden Lua output for long Reader bind chain.
test/ps/output/Golden.LongReaderBind.Test/eval/golden.txt Expected runtime output for Reader eval golden.
test/ps/output/Golden.LongReaderBind.Test/eval/.gitignore Ignores eval actual output for Reader golden.
test/ps/output/Golden.LongMaybeBind.Test/eval/golden.txt Expected runtime output for Maybe eval golden.
test/ps/output/Golden.LongMaybeBind.Test/eval/.gitignore Ignores eval actual output for Maybe golden.
test/ps/output/Golden.LongExceptBind.Test/golden.lua New golden Lua output for long Except bind chain.
test/ps/output/Golden.LongExceptBind.Test/eval/golden.txt Expected runtime output for Except eval golden.
test/ps/output/Golden.LongExceptBind.Test/eval/.gitignore Ignores eval actual output for Except golden.
test/ps/output/Golden.LongEitherBind.Test/eval/golden.txt Expected runtime output for Either eval golden.
test/ps/output/Golden.LongEitherBind.Test/eval/.gitignore Ignores eval actual output for Either golden.
test/ps/golden/Golden/LongWriterBind/Test.purs New golden PS module exercising long Writer do block.
test/ps/golden/Golden/LongStateBind/Test.purs New golden PS module exercising long State do block.
test/ps/golden/Golden/LongStackBind/Test.purs New golden PS module exercising long StateT-over-Except do block.
test/ps/golden/Golden/LongReaderBind/Test.purs New golden PS module exercising long Reader do block.
test/ps/golden/Golden/LongMaybeBindModule/Test.purs New module-mode golden to exercise IR/Lua output for long Maybe chain.
test/ps/golden/Golden/LongMaybeBind/Test.purs New runnable golden for long Maybe do block.
test/ps/golden/Golden/LongExceptBind/Test.purs New runnable golden for long Except do block.
test/ps/golden/Golden/LongEitherBind/Test.purs New runnable golden for long Either do block.
test/Main.hs Wires new specs into the test runner.
test/Language/PureScript/Backend/Lua/NestingCheck/Spec.hs Adds unit tests for chunk depth metric and thresholding behavior.
test/Language/PureScript/Backend/IR/FlattenDeepBinds/Spec.hs Adds unit + property tests for free-ref preservation, depth bounding, idempotence.
pslua.cabal Exposes new library modules and includes new test modules.
lib/Language/PureScript/Backend/Lua/NestingCheck.hs Implements nesting-depth measurement and limit check for Lua chunks.
lib/Language/PureScript/Backend/Lua.hs Adds NestingTooDeep to the Lua backend error type.
lib/Language/PureScript/Backend/IR/Optimizer.hs Inserts flattenDeepBinds into the optimized IR pipeline after magicDo.
lib/Language/PureScript/Backend/IR/MagicDo.hs Updates docs to reference FlattenDeepBinds for the general case.
lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs New IR pass implementing segmented lambda-lifting of deep bind/discard chains.
lib/Language/PureScript/Backend.hs Runs nesting check post-codegen and throws Lua.NestingTooDeep on overflow.
exe/Main.hs Adds CLI error rendering for NestingTooDeep.
docs/QUIRKS.md Updates docs for long do blocks, remaining unflattened shapes, and new failure mode.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Comment thread lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs Outdated
Comment thread lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs
Comment thread lib/Language/PureScript/Backend/Lua/NestingCheck.hs Outdated
Comment thread lib/Language/PureScript/Backend/Lua/NestingCheck.hs Outdated
Comment thread lib/Language/PureScript/Backend/Lua/NestingCheck.hs Outdated
Comment thread docs/QUIRKS.md Outdated
Comment thread exe/Main.hs Outdated
- FlattenDeepBinds.hs — index all group members (not just Standalone) in
  topLevel & letLocals so RecursiveGroup-bound bind/discard aliases resolve
  (r3452746991, r3452747082); + RecursiveGroup tests
- NestingCheck.hs — parenthesise `1 + (a `max` b)` in IfThenElse/BinOp/VarIndex
  for clarity (already correct: max binds tighter than +) (r3452747127,
  r3452747161, r3452747188); + deeper-on-right guard test
- docs/QUIRKS.md — correct the live-set bail threshold to ~15, not ~50
  (r3452747232)
- exe/Main.hs — broaden NestingTooDeep message beyond do/>>= chains, link #108
  (r3452747267)
@Unisay Unisay merged commit 4ff1d4b into main Jun 22, 2026
2 checks passed
@Unisay Unisay deleted the issue-104/flatten-deep-binds branch June 22, 2026 15:09
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.

Generic fallback: flatten deeply-nested do-blocks for non-Effect/ST monads

2 participants