Skip to content

fix: lower De Bruijn indices when a binder is removed (#56)#70

Merged
Unisay merged 1 commit into
mainfrom
issue-56/beta-reduce-unshift
Jun 14, 2026
Merged

fix: lower De Bruijn indices when a binder is removed (#56)#70
Unisay merged 1 commit into
mainfrom
issue-56/beta-reduce-unshift

Conversation

@Unisay

@Unisay Unisay commented Jun 14, 2026

Copy link
Copy Markdown
Collaborator

Closes #56.

Compiling Data.Array aborted with Unexpected bound reference: Ref Nothing (Local (Name "b")) 1, which blocked the purescript-lua-arrays port entirely. The single declaration Data.Array.foldRecM was enough to trigger it.

Root cause

The IR addresses locals with per-name De Bruijn indices: Ref (Local n) k means the k-th enclosing binder named n, counting from the innermost. When an optimizer pass removes a binder, every reference that pointed past that binder (index ≥ 1, because it was skipping over it) has to drop by one. Two passes removed a binder and skipped that repair:

  • betaReduce drops the applied lambda. In foldRecM f b array = tailRecM2 go b 0, the outer parameter b collides with tailRecM2's own third parameter b. Inlining tailRecM2 (a single-use dictionary accessor) beta-reduces under that inner b; capture avoidance shifts the outer reference up to index 1, and removing the inner binder left it stranded there instead of lowering it back to 0.
  • dead-code elimination blanks an unused named binder to ParamUnused. If an inner lambda's parameter is unused but its body still references an outer binder of the same name (at index 1, skipping the inner one), blanking the binder must lower that reference to 0. This is the same class of bug; the well-scopedness property below found it.

Both sites now repair the survivors with a new unshift, the inverse of shift 1. To keep the two from drifting apart, shift is refactored to share its scope-tracking traversal (overFreeIndex) with unshift; the strict minIndex < index guard leaves genuine inner references alone and keeps the Natural index from underflowing.

Tests

There was no unit coverage for the De Bruijn primitives at all, so the original bug could only surface as an integration crash. This adds a layer that exercises them directly:

  • Types spec: round-trip unshift . shift 1 ≡ id and a substitute-identity law as properties, plus the classic capture-avoiding substitution examples (capture under a same-named binder, pass-through of an unrelated binder, a shadowing binder stopping the substitution, a reference reaching past one).
  • Optimizer spec: a well-scopedness invariant (optimizing a well-scoped expression must never produce an unbound local) run over a generator of well-scoped terms through the full pipeline. This is what surfaced the DCE sibling bug. Deterministic regressions pin both passes: the foldRecM shape for beta reduction, a shadowing unused binder for DCE.
  • Golden: Golden.TailRecM2Shadow, an eval golden over a tailRecM2-based foldRecM paraphrase whose accumulator parameter is named b to reproduce the original collision.

Verified: cabal test is green, and pslua --entry Data.Array now compiles purescript-lua-arrays to luacheck-clean Lua.

The IR uses per-name De Bruijn indices: a `Ref (Local n) k` selects the
k-th enclosing binder named `n`. Two optimizer passes removed a binder
without lowering the references that had skipped over it, leaving them
pointing one binder too far out -- an unbound local that the Lua backend
rejects with `UnexpectedRefBound`. This aborts `Data.Array` compilation
(`foldRecM`, #56):

  * beta reduction drops the applied lambda;
  * dead-code elimination blanks an unused named binder to `ParamUnused`.

Both now repair the survivors with a new `unshift`, the inverse of
`shift 1`. `shift` is refactored to share its scope-tracking traversal
(`overFreeIndex`) with `unshift` so the two cannot drift apart.

Tests: property and example coverage for shift/unshift/substitute,
including the classic capture-avoiding cases (Types spec); a
well-scopedness invariant over a well-scoped expression generator (this
found the DCE sibling bug) plus deterministic regressions for both
passes (Optimizer spec); and an eval golden `Golden.TailRecM2Shadow`
over the `foldRecM` shape that triggered #56.

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

Fixes a scoping bug in the IR optimizer where removing a binder (via beta reduction or DCE blanking) could leave same-named local references with De Bruijn indices pointing past the remaining binders, causing Lua codegen to abort (e.g. Data.Array.foldRecM, issue #56).

Changes:

  • Introduces unshift (inverse of shift 1) and refactors shift/unshift to share a single scope-tracking traversal (overFreeIndex).
  • Applies unshift when beta-reducing away a named lambda binder and when DCE blanks an unused named binder to ParamUnused.
  • Adds direct De Bruijn primitive property tests + optimizer well-scopedness invariant tests, plus a golden regression reproducing the original tailRecM2/b-name collision shape.

Reviewed changes

Copilot reviewed 13 out of 13 changed files in this pull request and generated no comments.

Show a summary per file
File Description
test/ps/spago.dhall Adds tailrec dependency needed by the new PureScript golden regression.
test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua New golden Lua output for the regression case.
test/ps/output/Golden.TailRecM2Shadow.Test/golden.ir New golden IR output for the regression case.
test/ps/output/Golden.TailRecM2Shadow.Test/eval/golden.txt Expected eval output for the golden regression.
test/ps/output/Golden.TailRecM2Shadow.Test/eval/.gitignore Ignores eval runner’s actual.txt.
test/ps/output/Golden.TailRecM2Shadow.Test/corefn.json New golden CoreFn input for the regression case.
test/ps/golden/Golden/TailRecM2Shadow/Test.purs Adds a PureScript repro mirroring the original shadowing/capture scenario.
test/Language/PureScript/Backend/IR/Types/Spec.hs Adds laws/examples for shift/unshift and capture-avoiding substitution.
test/Language/PureScript/Backend/IR/Optimizer/Spec.hs Adds a well-scopedness invariant property + deterministic regressions for beta-reduce and DCE.
test/Language/PureScript/Backend/IR/Gen.hs Adds scopedExp generator to produce well-scoped terms for optimizer invariants.
lib/Language/PureScript/Backend/IR/Types.hs Refactors shift and adds unshift via shared overFreeIndex traversal.
lib/Language/PureScript/Backend/IR/Optimizer.hs Fixes beta reduction to unshift after substitution when removing a binder.
lib/Language/PureScript/Backend/IR/DCE.hs Fixes DCE binder-blanking to unshift outer references when removing a name slot.

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

@Unisay Unisay self-assigned this Jun 14, 2026
@Unisay Unisay merged commit 94c13ce into main Jun 14, 2026
2 checks passed
@Unisay Unisay deleted the issue-56/beta-reduce-unshift branch June 14, 2026 15:00
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.

Codegen: 'Unexpected bound reference Local b index 1' compiling Data.Array.foldRecM (index inflated by optimizer)

2 participants