Multi-Stage Programming and Cross-Stage Persistence

A macro expands once, at a point in the source, and its output is compiled as if it had been written there. Multi-stage programming generalises this: a program is annotated with levels, an expression at level n+1 constructs a piece of a level-n program, and the compiler enforces that a level-n+ expression cannot depend on a level-n value. The result is a typed notion of code generation in which the generator and the generated are both ordinary expressions in the same language.

Brackets and escapes

The two constructs are usually written as a quotation and a splice. In MetaOCaml, .< ... >. and .~e are the brackets and the escape; in Scala 3, '{ ... } and ${ ... } are quotes and splices; in a Lisp, the corresponding pair is backquote and comma. The syntax differs but the typing rule is the same.

(* MetaOCaml: build a function that adds a constant to its argument *)
let add_n n = .<fun x -> x + .~n>.

The outer brackets delay the fun expression: it is not a function value, it is a piece of code that will become one when the brackets are removed. The inner escape removes the delay from n, so the value of n is inserted into the delayed expression as a literal. The type of add_n records the level: it takes an int and returns a value of the code type int -> int code, not int -> int.

The compiler’s job is to ensure that an escape is only applied to something whose level is exactly one below the enclosing bracket. An escape of a code value at the same level is a type error; an escape of a run-time value into a bracket is precisely the operation that cross-stage persistence permits or forbids, depending on the language.

What run does

Removing the brackets is an explicit operation, usually called run or eval. It takes a code value and produces the value the code denotes, by compiling and executing it. The essential point is that run is not the identity: between the brackets and the run, the program is data. In MetaOCaml the function is Runcode.run, and it is defined in the user-level library rather than as a special form; it composes a step that closes the code value with run_bytecode or run_native.

.< 1 + 2 >.                  (* a code value; nothing has been computed *)
Runcode.run .< 1 + 2 >.      (* 3, computed by executing the generated code *)

A staged program that builds code and then runs it can therefore be optimized at the moment the code is constructed, because the constructor is ordinary code that the compiler already knows how to optimize. This is the source of staging’s main benefit: the generator can specialize the generated program on values known at generation time, and the generated program contains no trace of the decisions that produced it.

The cost is that the generated code is compiled at run time, which means a compiler — or at least an evaluator — must be present in the running program. MetaOCaml’s run compiles the code value to native code through the OCaml compiler’s own backend, so a program that uses it carries that backend. A language that stages only at compile time avoids the run-time compiler entirely, at the price of never being able to generate code from run-time data.

The level discipline

The typing rule is a single constraint applied recursively. Inside a quote at level n, the body is code at level n+1, and within it a name may refer only to bindings of that same stage — other level-n+1 bindings — unless it is escaped. A level-0 binding from the enclosing program is not visible inside the quote at all, which is the whole point: the generated program runs later, in an environment that does not contain the generator’s locals.

An escape consumes one level of delay. Inside a level-n+1 body, an escape admits a value at level n: a code value of level n is spliced in as a piece of the program under construction, and a value of a cross-stage-persistent type is admitted as a literal. A quote inside a quote raises the level again, and escapes must be counted accordingly — the same nesting rule as quasiquotation and nesting depth, but enforced by the type system rather than by a reader.

The enforcement is what distinguishes staging from string-based code generation. In a system that builds source text and hands it to a compiler, a variable captured from the enclosing scope is interpolated as text, and whether it is a literal or an identifier is decided by how it was printed. In a staged system, the level of the variable is known, and the compiler can reject a program that would require a run-time value to be present in generated code.

Cross-stage persistence

The rule that makes staging usable is that some values can cross a stage boundary. A literal integer can be embedded in generated code; a string can be; a function cannot, because a function value is a closure with an environment that exists only in the generating process.

A language that permits an arbitrary value to cross is said to have cross-stage persistence for that value’s type. The permissive choice is to allow anything, which means the generated code must be able to refer to the generating process’s heap — and that only works if the generated code runs in the same process, which is true for Runcode.run but false for a code value that is written to a file and compiled later.

The restrictive choice is to allow only types that have a representation in the generated program: integers, floating-point numbers, strings, and possibly references to top-level definitions. Whether a function is excluded depends on the system. MetaOCaml refuses to persist a local function literal through the escape, because its environment has no counterpart in the generated code; a reference to a top-level function, whose body is independently available, can cross. The restriction is expressed as a syntactic condition on the escape — MetaOCaml lifts serialisable types to literals and rejects what cannot be lifted — and its effect is that a staged program must be written so that every value crossing a boundary is representable as code.

(* the escape of a local closure is rejected: the environment has no code representation *)
let bad f = .< f 0 >.        (* error: the free variable f has no persistent value *)

(* the escape of a literal is accepted *)
let good n = .< n + 1 >.     (* n is embedded as an integer literal *)

The practical consequence is a design pressure toward generating code from data rather than from behaviour. A generator that wants to specialize on a function’s behaviour must either inline the function — copying its body into the generated code, which requires access to its syntax — or represent the decision as a data value that the generated code branches on. Both are workarounds for the fact that behaviour does not cross stages.

Staging and partial evaluation

The relationship to partial evaluation is direct: a partial evaluator takes a program and some of its inputs and produces a residual program specialized on those inputs. Staging is the annotation language that makes the specialization explicit and checkable.

The difference is who decides what is static. In an automatic partial evaluator, the binding-time analysis infers which parts of the program depend only on known inputs, and the evaluator specializes accordingly. The analysis is conservative, and its decisions are not visible to the programmer. In a staged language, the brackets and escapes are the programmer’s declaration of binding time, and the type checker verifies consistency.

The trade is expressiveness against predictability. An automatic evaluator can specialize code the programmer did not think about, and can fail to specialize code the programmer expected it to. An explicitly staged program specializes exactly what is bracketed, and a mistake in the annotation is a type error rather than a missed optimization. The second is easier to reason about and requires more writing.

The cost of explicit staging is that the generator must be written twice: once as the staged program that builds code, and once as the generated program that the code denotes. The two are different programs with different types, and the staging annotations are what connect them. A change to the generated program’s interface requires a matching change in the generator, and nothing but the type checker connects the two.

Where staging stops

Three limitations bound what a staged program can express.

The first is the shape of the generated code. A quote’s body is written as source, so the structure of the generated program is fixed at the point the generator is written. Generating a program whose control flow depends on a run-time value requires either a branch in the generated code — with both paths present — or a second stage that constructs the branch. A generator cannot produce a program with a loop count that is not known when the generator is compiled, unless the loop is in the generated program rather than the generator.

The second is the compilation boundary. A code value can be run in the same process, or written out and compiled separately. The second requires the code value to be serialisable as source or as an intermediate representation, and it requires the generating program’s types to be available to the later compiler. Most staged systems support only the first, which is why they are used for run-time specialization rather than for offline code generation.

The third is the phase ordering of the language’s own macros. A staged expression is not a macro: it is compiled by the ordinary compiler with an extra level annotation, so it does not have the expansion-order problems described in phase separation and compilation stages. What it does have is the same requirement that the generating code be compiled before the generated code exists, which for a same-process run means the generator’s output is compiled during the program’s execution. The compiler must therefore be part of the runtime, and the language’s implementation must support compiling at run time — a requirement that most ahead-of-time implementations do not meet.

The position staging occupies is therefore narrow but exact: it is the only facility in this cluster that makes code a first-class value with a type that says which stage it belongs to. Macros rewrite syntax before the program exists; reflection inspects types after it exists; staging sits between them, constructing the program from within a program that is already running.