Skip to content

Uncurry data constructor applications - #278

Merged
Unisay merged 4 commits into
mainfrom
issue-201/uncurry-ctors
Jul 15, 2026
Merged

Uncurry data constructor applications#278
Unisay merged 4 commits into
mainfrom
issue-201/uncurry-ctors

Conversation

@Unisay

@Unisay Unisay commented Jul 14, 2026

Copy link
Copy Markdown
Collaborator

Closes #201.

What

The IR Ctor node now carries its field argument expressions and is saturated by construction, instead of being a childless leaf whose currying materialized only at codegen:

-- before: a childless leaf; codegen wraps it in one closure per field
Ctor ann algTy modName tyName ctorName [FieldName]
-- after: the field arguments live in the node, count always equals arity
Ctor ann algTy modName tyName ctorName [RawExp ann]

Translation emits a constructor of arity n as a manifest chain of n unary lambdas over the saturated node, the same shape a user-written curried function has, so the worker/wrapper split from #24 covers constructors with no special case:

-- data Shape = ... | Tri Int Int Int   translates to
Abs v0 (Abs v1 (Abs v2 (Ctor SumType "M" "Shape" "Tri" [Ref v0, Ref v1, Ref v2])))
  • A saturated application of an arity-≥2 constructor compiles to a single n-ary worker call that builds the table with no intermediate closures (from the Golden.UncurryCtor golden, prefixes abbreviated):

    -- before                          -- after
    local Tri = function(value0)       local Tri_S_w = function(value0, value1, value2)
      return function(value1)            return { "M∷Shape.Tri", value0, value1, value2 }
        return function(value2)        end
          return { "M∷Shape.Tri",
            value0, value1, value2 }   -- site: Tri(a)(b)(c)  ~>  Tri_S_w(a, b, c)
        end
      end
    end
  • A saturated arity-1 application inlines to a direct in-place table build that makes no calls at all:

    -- before                          -- after
    Data_Maybe_Just(add(x, 1))         { "Data.Maybe∷Maybe.Just", (add(x, 1)) }
  • Partial applications and constructors used as first-class values (map Just xs) keep going through the curried wrapper, unchanged:

    M.Tri = function(p1)
      return function(p2)
        return function(p3) return Tri_S_w(p1, p2, p3) end
      end
    end

How

  • IR.Types: Ctor carries [RawExp ann]; it is traversed by subexpressions (so DCE, uniquify, substitution and CSE handle the arguments generically) and gets an explicit alphaEq case (the == fallback is over-strict once arguments contain binders). The invariant is written down in Note [Constructor applications are saturated].
  • Optimizer: the case-of-known-constructor family (Fold ReflectCtor and DataArgumentByIndex over known constructor applications (case-of-known-constructor) #177/Budgeted call-site inlining of dictionary methods to collapse non-Effect/ST monadic chains #180/Case-of-known-constructor through a let-bound scrutinee #214/Graduated @inline directives: arity=N, accessor forms, and a directives file #232) matches the bare node, and a shared resolveKnownCtorApp recognizes every reference shape a constructor value takes across the pipeline: the in-place node, the n-ary worker call the early uncurry run leaves (unwindApp does not flatten AppN, so missing this shape would silently stop the folds from firing on monadic chains), the curried unary spine, and the wrapper-to-worker delegate hop.
  • Lua codegen: the Ctor case emits the positional table directly from the compiled arguments. A multi-valued expression in the final positional row (a call or ...) is wrapped in explicit parens so it adjusts to one value instead of splicing extra results into the table: Ctor … [f x] renders as { "M∷T.C", (f(x)) }, never { "M∷T.C", f(x) }.
  • Linter: WellApplied additionally rejects any AppN whose head is a Ctor: the node is a value now, and a pass that forgot would emit a call on a table.
  • No changes to Uncurry, DCE, FloatIn, MagicDo, Linker, Uniquify or FlattenDeepBinds: the manifest lambda chain is exactly the shape they already handle.

Measurement

New Bench.CtorBuild anchor (hot build+match loop over a three-field constructor), committed with pre-change oracles first so the diff shows the movement:

  • Wall-clock on the linked artifact, same driver, old vs new compiler: LuaJIT 0.336s to 0.082s (4.1x), PUC Lua 5.1 1.048s to 0.302s (3.5x).
  • LuaJIT trace report: the hot map/fold loops go from blacklisted to compiled once per-element construction stops executing FNEW. Blacklisted spots drop from 6 to 2 and compiled traces rise from 6 to 10.
  • The issue names bench/micro/ctor_match.lua as the anchor; that file does not exist, so this PR adds bench/micro/ctor_build.lua (current/ideal pair) and bench/macro/ctor_build.lua instead.

Verification

  • The new Golden.UncurryCtor module pins every shape the change touches (saturated arity-3 sum, arity-2 product, arity-1, nullary singletons, stored partial application, higher-order use, newtype, recursive Cons spine). Its first commit records the old curried output; the diff to the accepted state demonstrates the red-to-green movement.
  • Every eval/golden.txt oracle across all 75 golden modules is byte-identical, so the change is semantics preserving end to end.
  • New unit tests cover the translation shapes (lambda chain, nullary, newtype erasure), the resolveKnownCtorApp recognition shapes including the n-ary worker call and the wrapper hop, the unsaturated-application declines, and the codegen paren guard.

Known tradeoff

Inlined arity-1 sum-constructor sites each embed a copy of the "Module∷Type.Ctor" tag string, so constructor-heavy chunks grow: LongMaybeBind/golden.lua goes from 667 to 1576 lines while dropping one call per construction. The string itself is interned by Lua at load time, so the cost is chunk size, not per-value memory. Hoisting shared tags into a chunk local is a possible follow-up.

@Unisay
Unisay requested a review from Copilot July 14, 2026 20:08
@Unisay Unisay self-assigned this Jul 14, 2026
@Unisay
Unisay marked this pull request as ready for review July 14, 2026 20:11
Add the UncurryCtor golden and the CtorBuild bench anchor with the current
compiler, so the demonstrate-red baseline records today's curried
closure-per-field construction. The golden covers every shape the uncurrying
change touches: a saturated arity-3 sum constructor, a saturated arity-2
product constructor, an arity-1 constructor, nullary singletons, a partial
application stored and reused, a constructor passed higher-order, newtype
construction, and a recursive Cons spine folded back. eval/golden.txt is the
semantic oracle across the change.

The bench anchor (Bench.CtorBuild, bench/macro/ctor_build.lua,
bench/micro/ctor_build.lua) drives a hot build+fold loop; its FNEW census
pins the intermediate closures the worker/wrapper split will remove.

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

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 implements issue #201 by changing the IR representation of data constructors so Ctor carries its field argument expressions and is always saturated, enabling the existing worker/wrapper uncurrying machinery (#24) to optimize saturated constructor applications without Lua-backend special-casing. It updates the optimizer, linter, Lua codegen, tests, goldens, and benchmarks to preserve semantics while significantly reducing closure allocations and calls in hot constructor-building code.

Changes:

  • IR: make Ctor a saturated value node carrying [Exp], add traversal and alpha-equivalence support, and update constructor translation to emit a manifest curried lambda chain over the saturated node.
  • Optimizer/linter/codegen: teach folds and well-applied checks about the new constructor shapes (in-place Ctor, curried wrapper spines, n-ary worker calls, wrapper→worker hop), and emit constructor tables directly with a paren-guard for multi-valued final fields.
  • Tests/benchmarks: add a new golden module, extend unit/spec coverage for translation + codegen + optimizer recognition shapes, and add ctor-build benchmark anchors plus updated benchmark goldens.

Reviewed changes

Copilot reviewed 71 out of 82 changed files in this pull request and generated 2 comments.

Show a summary per file
File Description
test/ps/src/Golden/UncurryCtor/Test.purs New golden source module exercising constructor shapes affected by the change end-to-end.
test/ps/src/Bench/CtorBuild.purs New PureScript benchmark artifact for hot constructor build+match loops.
test/ps/output/Golden.UncurryCtor.Test/golden.lua New Lua golden output for the new UncurryCtor golden module.
test/ps/output/Golden.UncurryCtor.Test/eval/golden.txt New eval oracle for UncurryCtor (expected stdout).
test/ps/output/Golden.UncurryCtor.Test/eval/.gitignore Golden eval actual output ignore entry.
test/ps/output/Golden.UncurriedLift.Test/golden.lua Updated Lua golden reflecting ctor/call-shape changes flowing through output.
test/ps/output/Golden.UncurriedLift.Test/golden.ir Updated IR golden reflecting ctor representation changes.
test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua Updated Lua golden reflecting ctor lowering updates.
test/ps/output/Golden.TailRecM2Shadow.Test/golden.ir Updated IR golden reflecting ctor nodes now carrying arguments.
test/ps/output/Golden.STDoBlock.Test/golden.lua Updated Lua golden reflecting ctor lowering updates.
test/ps/output/Golden.STDoBlock.Test/golden.ir Updated IR golden reflecting ctor representation changes.
test/ps/output/Golden.RecDataDefs.Test/golden.lua Updated Lua golden for recursive data definitions with in-place ctor tables.
test/ps/output/Golden.RecDataDefs.Test/golden.ir Updated IR golden showing constructor bindings translated as lambda chains + saturated Ctor.
test/ps/output/Golden.PatternMatching.Test2/golden.lua Updated Lua golden reflecting constructor wrapper/worker and in-place ctor builds.
test/ps/output/Golden.PatternMatching.Test2/golden.ir Updated IR golden reflecting new ctor translation and fold shapes.
test/ps/output/Golden.PatternMatching.Test1/golden.lua Updated Lua golden reflecting constructor wrapper changes.
test/ps/output/Golden.PatternMatching.Test1/golden.ir Updated IR golden reflecting ctor-as-lambda-chain translation.
test/ps/output/Golden.NumberIsNaN.Test/golden.lua Updated Lua golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.NumberIsNaN.Test/golden.ir Updated IR golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.MixedEffectSTDo.Test/golden.lua Updated Lua golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.MixedEffectSTDo.Test/golden.ir Updated IR golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.MaybeChainModule.Test/golden.lua Updated Lua golden showing in-place ctor tables in chained Maybe code.
test/ps/output/Golden.MaybeChainModule.Test/golden.ir Updated IR golden showing in-place Ctor nodes replacing ctor-app spines in some sites.
test/ps/output/Golden.MaybeChain.Test/golden.lua Updated Lua golden showing in-place ctor tables and adjusted formatting.
test/ps/output/Golden.MaybeChain.Test/golden.ir Updated IR golden showing ctor nodes with embedded args.
test/ps/output/Golden.LongReaderBind.Test/golden.lua Updated Lua golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.LongReaderBind.Test/golden.ir Updated IR golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.LongEitherBind.Test/golden.ir Updated IR golden showing constructor reads folding through the new ctor value shapes.
test/ps/output/Golden.LongBindFlipped.Test/golden.ir Updated IR golden reflecting ctor nodes and constructor-reference folding behavior.
test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua Updated Lua golden showing more in-place ctor table construction.
test/ps/output/Golden.DirectiveArity.Test/golden.ir Updated IR golden reflecting constructor binding translation as lambda chain over saturated Ctor.
test/ps/output/Golden.DerivedFunctor.Test/golden.lua Updated Lua golden showing direct worker-style ctor builds and reduced curried chains.
test/ps/output/Golden.DerivedFunctor.Test/golden.ir Updated IR golden reflecting ctor workers/wrappers and saturated ctor nodes.
test/ps/output/Golden.DataDeclarations.Test1/golden.lua Updated Lua golden for data declarations to match new ctor translation.
test/ps/output/Golden.DataDeclarations.Test1/golden.ir Updated IR golden showing ctor bindings as manifest lambda chains.
test/ps/output/Golden.CSE.Test/golden.lua Updated Lua golden reflecting in-place ctor tables and altered CSE-visible shapes.
test/ps/output/Golden.CaseStatements.Test/golden.lua Updated Lua golden reflecting ctor translation changes.
test/ps/output/Golden.CaseStatements.Test/golden.ir Updated IR golden reflecting ctor binding translation changes.
test/ps/output/Golden.BugListGenericEq.Test/golden.lua Updated Lua golden reflecting ctor translation changes.
test/ps/output/Golden.ArrayOfUnits.Test/golden.lua Updated Lua golden (primarily regenerated identifiers/shapes).
test/ps/output/Golden.ArrayOfUnits.Test/golden.ir Updated IR golden (primarily regenerated identifiers/shapes).
test/Language/PureScript/Backend/Lua/Spec.hs Adds codegen regression test for parenthesizing multi-valued final ctor fields; updates ctor expression helper.
test/Language/PureScript/Backend/IR/Spec.hs Adds unit tests for constructor translation (lambda chain, nullary ctor, newtype erasure) and helper to translate with datatype registry.
test/Language/PureScript/Backend/IR/Optimizer/Spec.hs Expands optimizer tests to cover folding through wrapper spines, n-ary worker calls, and wrapper→worker delegate hops; updates existing ctor-fold tests to new ctor representation.
test/Language/PureScript/Backend/IR/Gen.hs Updates generators to produce saturated Ctor nodes with embedded argument expressions and adjusts “leaf ctor” generation to nullary only.
test/Language/PureScript/Backend/IR/CSE/Spec.hs Updates CSE tests to treat Ctor as an in-place node (and partial applications as ref-headed calls).
lib/Language/PureScript/Backend/Lua.hs Emits constructor tables directly from compiled ctor args and adds parenLastMultiValued guard for the final positional field.
lib/Language/PureScript/Backend/IR/Types.hs Redefines Ctor to carry argument expressions, adds invariant note, includes ctor args in subexpressions, and adds alphaEq handling.
lib/Language/PureScript/Backend/IR/Optimizer.hs Updates known-constructor folds for new ctor representation, adds resolveKnownCtorApp/ctorFunctionShape, and updates let-propagation logic to use arity rather than field-name lists.
lib/Language/PureScript/Backend/IR/Linter.hs Extends WellApplied lint to reject AppN whose head is a Ctor value (CtorApplied).
lib/Language/PureScript/Backend/IR/CSE.hs Updates CSE ctor handling to treat Ctor as a saturated node with effect-free args.
lib/Language/PureScript/Backend/IR.hs Updates mkConstructor translation to emit a manifest curried lambda chain over a saturated Ctor node.
changelog.d/20260714_150000_unisay_uncurry_ctors.md Adds changelog entry describing the constructor uncurrying change and its tradeoffs.
bench/micro/ctor_build.lua Adds a micro benchmark spec comparing a manually-curried “current” variant vs an “ideal” direct table build loop.
bench/macro/ctor_build.lua Adds a macro benchmark spec comparing the compiled Bench.CtorBuild artifact to an ideal direct-build loop.
bench/goldens/trace_ctor_build.txt Adds LuaJIT trace-report golden for ctor_build benchmark.
bench/goldens/trace_bind_chain.txt Updates bind_chain trace-report golden (line/site shifts from regenerated output).
bench/goldens/fnew_Bench.CtorBuild.txt Adds FNEW-site golden for Bench.CtorBuild chunk.
bench/goldens/fnew_Bench.BindChain.txt Updates FNEW-site golden for Bench.BindChain chunk (counts/sites shifted).

Comment thread test/ps/src/Bench/CtorBuild.purs Outdated
Comment thread bench/macro/ctor_build.lua Outdated
Unisay added 2 commits July 14, 2026 22:17
)

The Ctor node now carries its field argument expressions directly —
saturated by construction (argument count equals declared arity) — instead
of being a childless leaf whose currying materialized only at codegen.
Translation emits a constructor of arity n as a manifest chain of n unary
lambdas over the saturated node, the same shape a user-written curried
function has, so the existing worker/wrapper split handles constructors
with no special case: an arity-≥2 constructor becomes an n-ary worker
(one call, one table build, no intermediate closures) plus a curried
wrapper for partial and higher-order uses, and an arity-1 constructor is
pasted at saturated sites, beta-reducing to an in-place table build.

Details:

* IR.Types: Ctor carries [RawExp ann]; traversed by subexpressions
  (DCE/uniquify/substitution/CSE work generically); explicit alphaEq case
  (the ==-fallback is over-strict once arguments contain binders); the
  invariant is documented in Note [Constructor applications are saturated].
* Optimizer: the case-of-known-constructor family (#177/#180/#214/#232)
  matches the bare node; the shared resolveKnownCtorApp recognizes every
  reference shape a constructor value takes across the pipeline — the
  in-place node, the n-ary worker call the early uncurry run leaves
  (invisible to unwindApp, which does not flatten AppN), the curried
  unary spine, and the wrapper-to-worker delegate hop.
* Lua codegen: the Ctor case emits the positional table directly from the
  compiled arguments; a multi-valued final row (call/vararg) is wrapped in
  explicit parens so it adjusts to one value instead of splicing.
* Linter: WellApplied additionally rejects any AppN with a Ctor head — a
  constructor value is a table, never a function.
* CSE: saturatedCtorApp collapses to a direct node match.

Structural goldens are accepted in the follow-up commit; every
eval/golden.txt oracle is byte-identical across the change.
Structural goldens for 30 modules move to the new constructor codegen:
saturated arity-≥2 constructors compile to one n-ary worker call
(Tri_S_w(a, b, c) — previously a closure allocation and a call per field),
saturated arity-1 sites inline to a direct in-place table build, and
partial or higher-order uses keep the curried wrapper. Every
eval/golden.txt oracle is byte-identical — the change is semantics
preserving across all 75 golden modules.

Bench oracles: the CtorBuild trace report shows the hot map/fold loops
going from blacklisted to compiled (blacklisted 6 → 2, compiled traces
6 → 10) once per-element construction stops executing FNEW; wall-clock
on the linked artifact improves 4.1x under LuaJIT and 3.5x under PUC
Lua 5.1. Known tradeoff, visible in the Long*Bind goldens: each inlined
sum-constructor site embeds its own copy of the tag string, so
constructor-heavy chunks grow (LongMaybeBind 667 → 1576 lines); hoisting
shared tags is a potential follow-up.
@Unisay
Unisay force-pushed the issue-201/uncurry-ctors branch from 0702b14 to 2fbc51b Compare July 14, 2026 20:21
- test/ps/src/Bench/CtorBuild.purs — reword the header to a timeless
  workload description instead of asserting the curried-chain codegen
  this PR replaces
  (#278 (comment))
- bench/macro/ctor_build.lua — likewise describe the linked-vs-ideal
  gap without pinning a codegen shape
  (#278 (comment))
- bench/goldens/trace_ctor_build.txt — re-accepted: the trace report
  pins the macro spec's source lines, which shifted with the header edit
@Unisay
Unisay merged commit f84e2b0 into main Jul 15, 2026
2 checks passed
@Unisay
Unisay deleted the issue-201/uncurry-ctors branch July 15, 2026 08:26
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.

Uncurry data constructor applications

2 participants