How Residual Code Is Built

The previous chapter treated code generation as a black box: staged operations “emit themselves”. This chapter opens the box. None of it is needed to use staging, but Part III reads differently once the shape of the generated programs is familiar.

Let-insertion

The generator keeps an open block — a list of statements emitted so far. When an operation residualizes, it does not build an expression tree in place; it appends the operation to the block as a statement and returns a fresh residual variable standing for the result. When the enclosing scope closes, the block is drained into a chain of lets ending in the final expression.

(+ (lift 1) (lift 2)) therefore compiles not to the expression (+ 1 2) but to

(let x0 (+ 1 2)
  x0)

— five nodes, matching the count the printer reported. Every intermediate result gets a name; compound expressions never nest. The output is in administrative normal form (ANF), and the discipline buys two things: generated programs never duplicate work (a shared result is a shared variable, not a recomputed expression), and effects in generated code stay in the order they were emitted, since statement position is evaluation order.

The fresh-variable counter and the open block are the staging state — what base.scm keeps in globals and narju keeps in the evaluator context. The floor REPL’s :ctx command shows both.

Reify scopes

Some constructs need a complete program for a subterm, not a variable into an open block: both branches of a staged if, the body of run, the body of a staged function. These open a reify scope — save the staging state, start an empty block, evaluate the subterm, drain the new block into a let-chain around the result, restore the state. A staged if reifies each branch this way, so branches keep their effects to themselves; run 0 reifies its operand to get the closed program it executes.

Scopes nest arbitrarily — a staged if inside a staged function inside run is three saved-and-restored staging states — and the machine keeps them on its own explicit stack, so nesting depth is bounded by memory, not by the Rust call stack.

Lifting a closure

lift on numbers and symbols makes literals. On a closure there is nothing syntactic to copy — a closure is a captured environment and a body, not source — so lift η-expands: it opens a reify scope, applies the closure to a fresh code variable, and lets the body generate itself. Whatever the body does with an ordinary argument, it now does with code, emitting its operations into the new block; the drained result becomes the body of a residual lambda.

This is the move that makes an interpreter compilable in Part III: the interpreter is a function, functions are lifted by running them on code, and running an interpreter on code is compiling.

Memoization, or why recursion terminates

η-expansion of a recursive function looks like it should diverge: the body of fact contains a call to fact, generating that call re-enters the closure, and so on. The generator memoizes instead — the reference’s stFun registry. Before η-expanding, lift checks whether a structurally identical closure has already been lifted in this scope; if so, it reuses the existing residual definition rather than expanding again.

The recursive call inside fact’s body is a call to the same closure, so the check fires on the first recursion and the unfolding stops at depth one. The result is a single residual lambda that calls itself:

(lift (lambda fact n
  (if (eq? n (lift 0))
      (lift 1)
      (* n (fact (- n (lift 1)))))))
;=> #<code 25 nodes>

as an expression tree, roughly

(lambda f x0
  (let x1 (eq? x0 0)
    (if x1
        1
        (let x2 (- x0 1)
          (let x3 (f x2)
            (let x4 (* x0 x3)
              x4))))))

— the let-chains inside each if branch being the drained blocks of their reify scopes. Matching is structural, following base.scm, so two separately constructed but identical closures reaching different lift sites also share one residual definition.

Residual variables are positions

Generated variables x0, x1, … are, internally, environment indices like every other variable — the names above are for reading. The fresh counter allocates the next index; scope save/restore keeps indices from leaking between reify scopes. A corollary worth knowing: code values are only meaningful within the staging context that made them, and run closes one off into a self-contained program before executing it.