scalus.uplc.transform

Replace nested Apply with Case/Constr

For example, replace (apply (apply (apply f a) b) c) with (case (constr 0 [a, b, c]) f). This is more memory/cpu efficient than nested Apply at least in Plutus V3 Plomin HF, protocol version 10.

With current machine costs, Apply costs 100 memory and 16000 cpu, same for Case/Constr. Hence (case (constr 0 [a, b, c]) f) costs 200 memory and 32000 cpu, while (apply (apply (apply f a) b) c) costs 300 memory and 48000 cpu.

Common Context Extraction (CCE) for UPLC terms.

Generalizes CSE by extracting common contexts (subtrees differing in exactly one position) into shared lambda-abstractions. While CSE handles identical subexpressions, CCE handles cases where repeated structures differ in a single "hole" at '''any''' child position:

// Right-spine (original):
headList(tailList(sndPair(unConstrData(x)))) + headList(tailList(sndPair(unConstrData(y))))
→ let f = \a -> headList(tailList(sndPair(unConstrData(a)))) in f(x) + f(y)

// Left-spine (new): f(x, z) + f(y, z)
→ let g = \a -> f(a, z) in g(x) + g(y)

// Case scrutinee (new): case x of [...] and case y of [...]
→ let h = \a -> case a of [...] in h(x) + h(y)

This reduces on-chain script code size (CBOR bytes), which directly affects transaction fees.

==Algorithm==

1. '''Collect pass''': Traverse the term. For each non-leaf node, generate all single-hole decompositions via CommonContextExtraction.decompose. Record templates with termBits >= [[CommonContextExtraction.MinTemplateBits]] along with their paths. Track path IDs at evaluation boundaries (LamAbs, Delay, Case), same as CSE.
2. '''Group & filter pass''': Group by TemplateKey. For each group:
   • Require >= 2 distinct leaves (identical leaves are handled by CSE)
   • Profitability check: CommonContextExtraction.extractionSavingBits > 0
   • Compute bind path as longest common prefix of occurrence paths
   • Scope safety: free vars of template (excluding HOLE) in scope at bind path
   • Shadowing safety: no re-binding between bind and occurrence paths
   • Conditional boundary safety: no hoisting shape-partial builtins across Case/Delay
3. '''Substitute pass''': For each candidate (largest template first):
   • Re-count in (possibly modified) term via CommonContextExtraction.matchTemplate
   • Create fresh name __cce_[_N] (e.g. __cce_HeadList, __cce_SndPair_1)
   • Replace each matching occurrence with Apply(Var(lambdaName), leaf)
   • Insert at bind path: Apply(LamAbs(lambdaName, body), LamAbs(param, templateBody))

Share repeated expressions by introducing a strict UPLC binding, using Plutus 1.63.0.0's ancestor-or-self rule. In the examples below, let x = e in body means [(lam x body) e]; e is evaluated before body, even when the uses of x are delayed. For example, let x = Error in Delay(x) fails immediately, whereas Delay(Error) is a value.

// When sharing pays, keep one copy of e and replace its uses with variables:
Constr(0, [e, e])  =>  let x = e in Constr(0, [x, x])

// An existing strict occurrence can also supply a deferred use:
Constr(0, [e, Delay(e)])  =>  let x = e in Constr(0, [x, Delay(x)])

// No strict occurrence outside the delays: do not move e out of them.
Constr(0, [Delay(e), Delay(e)])

==Safety: where may the binding go?== Lambda bodies, delayed bodies and individual Case branches are separate evaluation regions. Other children inherit their parent's region, including the body of an immediately applied lambda (a strict let). A group must contain an occurrence in its outermost region; occurrences in descendant regions can join it. Sibling regions alone cannot justify an outer binding. Otherwise extracting, for example, a failing e from an unused delay would make a successful program fail. The same placement rule applies to every candidate, including constants:

LamAbs(a, Constr(0, [e(a), e(a)]))
 => LamAbs(a, let x = e(a) in Constr(0, [x, x]))  // stay inside the lambda

let a = e in Constr(0, [a, e])
 => let x = e in (let a = x in Constr(0, [a, x])) // applied lambda is strict

Case(tag, [e, e, 0])  // no outer occurrence of e; selecting branch 2 must not run e
Constr(0, [Delay(largeConstant), Delay(largeConstant)])
 // No special constant-hoisting exception: the two constant uses stay in separate regions.
 // Sharing the whole Delay values is allowed; that does not evaluate their bodies.

Like Plutus CSE, this preserves results and success/failure, not trace multiplicity, trace order, failure messages or exact budgets. A region is not an evaluation-order barrier: sharing may move work earlier within it. For example, with e = trace("B", 1) and a = trace("A", 0), sharing e in Constr(0, [a, e, e]) can change logs from ["A", "B", "B"] to ["B", "A"] while returning the same constructor. If a and e both fail, moving e first can change which failure is reported, but still fails. Even sharing a constant adds Apply/LamAbs/Var work, so exact budgets are not preserved.

No builtin-totality or name-prefix assumptions are needed: divideInteger n d can be a candidate even when d might be zero, provided placement is safe and sharing pays. Renaming n to __partial_n does not change that decision.

==Profitability: should we introduce the binding?== Safe placement alone is insufficient. SharingCost prices estimated reference-script bits saved minus the extra binding's execution fee for values. Repeated computations such as f(xs) are also shared when that estimate is negative: the callee's avoided work is unknown, so this is a runtime-sharing preference, not a prediction of lower total fees. Each round takes the greatest eligible estimate, then recollects on the changed tree. For example, three uses of a 54-bit constant save (3 - 1) * 54 - 3 * 12 - 8 = 64 estimated bits: remove two copies, insert three variables, and pay the Apply/LamAbs tags. The default fee estimate subtracts about 20.77 lovelace of binding work from 120 lovelace of reference-size savings. Two uses of an 18-bit integer constant instead save 18 - 24 - 8 = -14 bits and are rejected. See docs/design/cse-placement.md for the contract and pricing assumptions.

Performs eta-reduction on a term.

Eta-reduction is the process of removing redundant lambda abstractions from a term. For example, the term λx. f x can be eta-reduced to f but only if

• x is not free in f
• f is a pure expression

Purity checking is handled by TermAnalysis.isPure. A term is pure if it does not contain any side effects, such as Error, Force of non-delayed terms, or saturated builtin applications. See TermAnalysis.isPure for comprehensive documentation on purity semantics.

On top of the syntactic purity check, the pass tracks a value-arity environment for [(lam x body) rhs] let-bindings: when rhs provably evaluates to a lambda of arity n (counting the self-application fixpoint encoding [(lam f [f f]) (lam f (lam a ... body))] produced for recursive functions), a partial application x a1 ... ak with k < n pure arguments is itself a pure expression, so multi-argument eta-wrappers like λa. λb. f a b reduce to f. This removes the wrapper the compiler emits around a multi-parameter recursive entry point ([(lam f (lam a (lam b [f a b]))) fix] becomes [(lam f f) fix], which the Inliner then collapses to fix). The same wrapper in the case-constr application encoding — (lam a (lam b (case (constr 0 a b) f))) as produced by CaseConstrApply — reduces too, see caseConstrEtaRedex.

'''Precondition: named terms only.''' Every analysis here — the arities environment, the capture checks via TermAnalysis.freeVars, and the field matching in caseConstrEtaRedex — identifies variables by NAME and ignores NamedDeBruijn.index, so scope is whatever the binder nesting says it is. That is the representation the compiler pipeline produces: UplcPipeline hands optimizers a named term and de Bruijn indices are only assigned later, at Program.deBruijnedProgram. Do not run this pass on an already-de-Bruijned term (one whose Var indices are meaningful — the CEK requires that form, see lookupVarName, which rejects index 0): there, two distinct binders may share a name, and name-based scoping would conflate them.

Extract forced builtins to top level

For example, replace (force (force (builtin fstPair))) with (lam FstPair (FstPair (pair true false)) (! (! __FstPair))). This is more memory/cpu efficient than nested Force at least in Plutus V3 Plomin HF, protocol version 10.

With current machine costs, Force costs 100 memory and 16000 cpu, same for Builtin. Hence (lam FstPair (FstPair (pair true false)) (! (! __FstPair))) costs 200 memory and 32000 cpu, while (force (force (builtin fstPair))) costs 300 memory and 48000 cpu.

Companion object providing convenient factory methods for the Inliner.

Optimizer that performs function inlining, beta-reduction, and dead code elimination.

The Inliner performs several transformations:

• '''Beta-reduction''': Replaces function application with direct substitution when safe
• '''Identity function inlining''': Eliminates identity functions like λx.x
• '''Dead code elimination''': Removes unused lambda parameters when the argument is pure
• '''Profitable value inlining''': Inlines variables, constants, and builtins when duplication is profitable
• '''Force/Delay elimination''': Simplifies Force(Delay(t)) to t
• '''Partial evaluation''': Evaluates closed subexpressions at compile time via the CEK machine (e.g., addInteger 2 3 → 5, (λx. addInteger x 1) 2 → 3)

==Inlining Strategy==

The inliner uses occurrence counting and purity analysis to decide what is safe to inline:

• Variables, builtins, and constants are duplicated only when sharing is unprofitable
• Other values are only inlined if used once
• Pure unused arguments are eliminated entirely

==Example==

// Input: (λx. λy. x) 42 100
// After inlining identity and dead code elimination:
// Output: 42

val inliner = new Inliner()
val optimized = inliner(term)
// Check what was optimized
println(inliner.logs.mkString("\n"))

==Implementation Details==

The inliner performs capture-avoiding substitution to prevent variable capture during beta-reduction.

Re-associates a chain of nested lets into multi-argument applications.

A let is [(lam x body) rhs], so a chain of them nests to the right. Bindings that do not depend on each other can be applied as one argument list instead:

// before: three nested lets — 3 Apply + 3 LamAbs = 6 machine steps
[(lam a [(lam b [(lam c body) ec]) eb]) ea]

// after: one three-argument application — same step count on its own...
[[[(lam a (lam b (lam c body))) ea] eb] ec]

// ...but [[CaseConstrApply]] then encodes it as Case + Constr + 3 LamAbs = 5 steps
(case (constr 0 [ea, eb, ec]) [(lam a (lam b (lam c body)))])

A group of N bindings therefore saves N - 2 machine steps per execution of the chain. This pass only re-associates — the case/constr encoding is left to CaseConstrApply, which already fires on any application chain with 3+ arguments and must stay the single place that decision is made (Case/Constr are illegal before Plutus V3).

==Why the threshold is five, not three==

Steps are not the whole fee: the encoding also changes the script's size, and the two pull in opposite directions below N = 7.

In the flat encoding an application chain is pure tags, 4N bits. The case-constr form pays fixed framing first — Case tag 4, Constr tag 4, constructor index 8, field-list framing N+1 (one bit per field plus a terminator), branch-list framing 2 — so 19 + N bits. The difference is therefore

Δbits = (19 + N) - 4N = 19 - 3N

which is '''larger''' below N = 7 and smaller from N = 7 up (verified against the encoder for N = 1..12). On mainnet a script byte costs 15 lovelace of reference-script fee in every transaction using the script, while a machine step costs 6.92 lovelace (100 mem * 0.0577 + 16,000 cpu * 0.0000721) per ''execution''. So the break-even depends on how often the chain runs: for a script executed once per transaction it sits just under N = 4; at N = 3 the grouping loses about 12 lovelace, and only turns positive from roughly three executions per transaction.

MinRunSize is 5 rather than 4 because the theoretical N = 4 margin (+0.72 lovelace) does not survive measurement: flat is bit-packed, so a group's 7 theoretical bits round up to a whole byte in the encoded script. Measured over the ten example validators: a threshold of 4 nets +511 lovelace for +19 bytes and still makes one of them worse, while 5 nets +533 for no extra bytes at all and makes none worse.

All of this is conservative for chains that run more than once per transaction (inside a loop, or a script spending several inputs), where the step saving multiplies but the bytes are paid once.

==Grouping rule==

The chain is split into '''maximal contiguous runs'''. A binding joins the current run when

• its right-hand side does not mention any binder already in the run, and
• its name does not repeat a binder already in the run.

Bindings are never reordered. Aiken's split_body_lambda moves bindings between groups to grow them, which changes the order effects happen in; Scalus preserves source evaluation order.

==Why no purity guard is needed==

The CEK machine evaluates [f a] function-first, then argument. So [[[F ea] eb] ec] evaluates F (a lambda — effect-free), then ea, then the beta-reduction yields the next lambda (effect-free), then eb, then ec — exactly the order of the nested form. Under the subsequent case (constr 0 [...]) encoding the fields are also evaluated left to right. A right-hand side that errors, traces or diverges therefore does so at the same point relative to the others in both forms, so this pass applies to effectful bindings (a require(...) lowers to a binding with no uses) as readily as to values.

Moving a right-hand side out of the scope of the earlier binders cannot capture or free a name either: in the input it sits under those binders, so a free occurrence of one of them refers to the let, which is exactly what the dependency test rejects.

That argument covers ordering '''within''' the chain. It does not by itself cover a chain in the function position of an enclosing Apply, where CaseConstrApply would otherwise merge the enclosing arguments into the same constr and hoist them ahead of the chain body; rebuild leaves the outermost run nested in that case, which keeps the two forms identical. See rebuild.

No-op optimizer that returns the term unchanged without any optimizations.

This is useful as a default when optimization is disabled or as a placeholder in testing.

Base trait for UPLC term optimizers.

An optimizer transforms a UPLC (Untyped Plutus Core) term into an equivalent but more efficient term. Optimizers can perform various transformations such as:

• Dead code elimination
• Function inlining and beta-reduction
• Eta-reduction (removing redundant lambda abstractions)
• Constant folding
• Conversion of lazy evaluation to strict evaluation when safe

==Usage==

Optimizers are typically used in optimization pipelines (see V1V2Optimizer and V3Optimizer) where multiple optimization passes are applied sequentially:

val optimizer = new StrictIf()
val optimizedTerm = optimizer(term)
println(s"Optimizations applied: ${optimizer.logs.mkString(", ")}")

==Implementation Notes==

Optimizer implementations should:

• Accept a scalus.uplc.eval.Logger as constructor parameter for logging optimizations
• Be deterministic: applying the same optimizer to the same term should always produce the same result
• Preserve semantics: the optimized term must be equivalent to the original term
• Log all applied optimizations for debugging and analysis

Compile-time partial evaluator for UPLC terms.

Evaluates closed subexpressions (no free variables) at compile time using the CEK machine and replaces them with their result. This covers saturated builtin applications, lambda applications with constant arguments, case/constr elimination on known constructors, and any composition of the above.

==Safety==

A budget cap prevents expensive computations from slowing the compiler. Failed evaluations (runtime errors, budget exceeded) leave the original term unchanged, preserving semantics.

Prepares a UPLC term for flat serialization by replacing BLS12-381 constants that cannot be directly flat-encoded with equivalent runtime expressions.

Standalone BLS constants become uncompress(compressed_bytes):

• Const(BLS12_381_G1_Element(v)) → Apply(Builtin(Bls12_381_G1_uncompress), Const(ByteString(compress(v))))

List constants containing BLS elements are unrolled into MkCons chains:

• Const(List(G1, [v1, v2])) → MkCons(uncompress(compress(v1)), MkCons(uncompress(compress(v2)), Const(List(G1, [])))) The empty List[G1Element] at the end is flat-serializable because the stub Flat instance for BLS types is never invoked for empty lists.

Applied automatically before flat encoding in DeBruijnedProgram.flatEncoded.

Optimizes if-then-else expressions by converting lazy branches to strict evaluation when safe.

==Background==

UPLC (Untyped Plutus Core) uses strict evaluation: all function arguments are evaluated before the function is applied. However, for conditional expressions using IfThenElse, we need lazy evaluation to avoid evaluating both branches.

The standard compilation generates:

Force(Apply(Apply(Apply(Force(Builtin(IfThenElse)), condition), Delay(thenBranch)), Delay(elseBranch)))

This pattern has a cost:

• 2 Delay nodes to suspend branch evaluation
• 1 Force node to evaluate the selected branch
• Total: '''3 extra term node evaluations per if-then-else'''

==The Optimization==

When both branches are "simple values" that evaluate to exactly 1 term, we can safely evaluate them strictly, removing the Delay/Force overhead:

Apply(Apply(Apply(Force(Builtin(IfThenElse)), condition), thenBranch), elseBranch)

This saves 3 term node evaluations, improving performance without changing semantics.

==Simple Values (Single-Term Evaluation)==

A term is considered "simple" if it evaluates to exactly 1 term:

• Var: Variable lookup (1 term)
• Const: Constant value (1 term)
• LamAbs: Lambda abstraction - not executed until applied (1 term)
• Builtin: Builtin function reference - not executed until applied (1 term)
• Delay: Suspended computation - not executed (1 term)
• Constr(_, Nil): Empty constructor (1 term)

Terms that are NOT simple (multi-term evaluation):

• Apply: Requires evaluating function + argument (3+ terms)
• Force: Requires evaluating the forced term (2+ terms)
• Case: Requires evaluating scrutinee + pattern matching (2+ terms)
• Constr(_, args) with args: Requires evaluating each argument (1 + n terms)
• Error: Will fail immediately

==Example==

// Original: if condition then 42 else 100
Force(Apply(Apply(Apply(Force(Builtin(IfThenElse)), condition), Delay(Const(42))), Delay(Const(100))))
// Cost: 5 term evaluations (Force + Apply + Apply + Apply + Force + 2 Delay + selected Const)

// Optimized: both branches are constants (simple values)
Apply(Apply(Apply(Force(Builtin(IfThenElse)), condition), Const(42)), Const(100))
// Cost: 2 term evaluations (Force + Apply + Apply + Apply + selected Const)
// Savings: 3 term evaluations (2 Delay + 1 Force)

Static analysis utilities for UPLC terms.

Provides analysis methods for determining properties of UPLC terms that are useful for optimization and transformation passes.