Phase Separation and the Ordering of Compilation Stages

A program that generates code has at least two stages: the stage that runs to produce the code, and the stage at which the produced code runs. Those stages cannot be interleaved freely, because the second one’s input does not exist until the first has finished. The rules that keep them apart are collectively called phase separation, and they are what makes the question “where is this macro defined” have an answer at all.

The distinction being enforced

The original phase distinction is between what a compiler can decide and what only the runtime can decide: types and scopes belong to the first, values and stores to the second. Macro expansion adds a third layer in front, because the code that performs the expansion is itself a program with its own bindings, and those bindings must be resolved before the expansion can happen.

The consequence is that the same name can exist at more than one phase. A function f exists at phase 0 — the phase of the compiled program. A macro m that expands to a call of f exists at phase 1 — it is used by the expander, which runs before phase 0 code exists. A macro that generates a macro exists at phase 2. A binding’s phase is part of its identity at the phase where it is referenced, and a reference that resolves to nothing at the phase in which it is used is an error of the same kind as referring to an unbound name.

This is not a notational detail. It determines the order in which a module’s dependencies must be compiled, and it determines what a module can see of another module.

Textual scope and its failure

The simplest enforcement is source order. In Rust, a macro_rules! definition occupies textual scope from the end of the definition to the end of the enclosing block or module, and not before:

fn main() {
    println!("{}", double(3));   // error: cannot find macro `double` in this scope
}

macro_rules! double {
    ($x:expr) => { $x * 2 };
}

The error is not about the macro being private or unexported; it is that the definition is not yet in the textual scope at the point where the invocation is collected. Expansion is a sequence of passes: the compiler collects invocations, resolves the names it can, expands what resolved, and repeats until no invocations remain, which is what lets an expansion that defines a macro satisfy an invocation later in the same file. What repetition does not do is reach backwards for a definition that appears after the invocation.

Two features soften this. #[macro_export] puts the macro at the crate root and makes it reachable by path from anywhere in the crate or from a dependent crate, which converts the ordering problem into a name-resolution problem. And a macro imported with use enters path-based scope, which the same resolution step consults for a name that textual scope did not supply. The result is that an exported or imported macro is usable above its textual definition, and a plain inline definition is usable only below it.

The textual rule exists because expansion consumes a partially built crate rather than a complete one. A system that resolved macro names the way it resolves function names — collecting all definitions first, then expanding — would allow forward references but would need to traverse the module before any expansion, and would still have to handle the case where a macro’s expansion defines another macro that a later invocation needs. That case is exactly what phase levels are for.

Phase levels in a module system

Racket makes the phase of every binding explicit. A module’s body is at phase 0; a begin-for-syntax form raises the phase of what it contains; and a require can be annotated to import at a higher phase:

#lang racket
(require (for-syntax racket/syntax))   ; format-id is needed while expanding, not at run time

(define-syntax (define-getter stx)
  (syntax-case stx ()
    [(_ name)
     (with-syntax ([getter (format-id #'name "get-~a" #'name)])
       #'(define (getter) 'name))]))

(define-getter size)     ; defines (get-size), which returns 'size

format-id is imported at phase 1 because the transformer of define-getter runs at phase 1 and calls it there. Without the for-syntax annotation the import would be at phase 0, and the transformer — which is not running at phase 0 — would not see the binding. The #'name argument is a syntax object, and format-id copies its lexical context onto the constructed identifier, which is what keeps the generated get-size hygienic with respect to the invocation site.

The rule that makes this composable is that phases shift transitively. If module A provides a macro whose expansion refers to a binding from module B, then B must be available at phase 1 when A is expanded. If A itself is imported at phase 1 by a module C, then everything A needs shifts to phase 2 for C’s expansion. A module that provides a macro therefore pulls its dependencies up by one phase for every consumer that uses the macro, and a chain of macro-providing modules shifts the chain’s dependencies by the length of the chain.

This is the mechanism that makes macro libraries composable across module boundaries, and it is the mechanism whose cost is the subject of the next section.

What transitive shifting costs

Each phase level is, in effect, a separate instantiation of the module. A module imported at phase 0 and phase 1 is run twice: once to produce the run-time bindings, once to produce the expand-time bindings. For a module that only defines functions, the second instantiation is cheap but not free — its body is evaluated again in a separate namespace. For a module that performs effects at initialisation, the second instantiation repeats them, which is why Racket’s phase system treats initialisation effects at higher phases as a thing to be declared rather than assumed.

The compilation cost is proportional to the number of (module, phase) pairs, not the number of modules. A dependency graph of depth d in which every level provides a macro yields up to d instantiations of the deepest module, and the work is multiplicative in the branching factor. Build systems that support this model therefore cache per phase, and the cache key includes the phase because the same module at two phases produces two different sets of bindings.

The benefit bought with that cost is that a macro’s expansion can be understood in isolation. If a macro’s transformer refers only to bindings imported at phase 1, then expanding it cannot depend on the run-time state of the program being compiled, because that state does not exist yet. The phase discipline is a guarantee about what expansion can observe, and it is the compile-time analogue of the guarantee that a pure function’s result depends only on its arguments.

Separate compilation and the bootstrapping order

Phase separation determines the order of a build graph. A crate that defines procedural macros must be compiled before any crate that uses them, and it must be compiled for the host rather than the target. A module that provides macros must be instantiated at the phase its consumers need. And a compiler that is written in the language it compiles must have a previous version of itself available to compile its own macro definitions.

The bootstrapping case is the sharpest illustration. A compiler’s source contains macros that the compiler itself defines; to build the compiler, an older compiler must expand them. The phase ordering is therefore not only within a build but across builds: the stage-0 compiler is a fixed point that must exist before the stage-1 compiler can be produced. Languages with heavy macro use in their own implementation tend to have an explicit bootstrap chain of two or three stages, and the chain’s length is determined by which features the earliest available compiler already supports.

Where the discipline leaks

Three failure modes are common enough to be recognised by their diagnostics.

The first is a macro whose expansion needs a binding that is only available at a lower phase. In Racket this is a phase mismatch error naming both the binding and the phase it was found at. In Rust the equivalent is a macro that expands to a reference to a local item that is not in scope at the expansion site, which surfaces as an ordinary unresolved-name error pointing into generated code.

The second is a circular phase dependency: module A provides a macro used by B, and B provides a binding that A’s transformer needs. Neither can be instantiated first. The usual resolution is to split the module so that the shared binding lives in a third module at the phase both need, which is a refactoring that the phase system forces and that a system without phases would not require.

The third is a macro whose expansion depends on the order in which other macros expanded. This is the same problem as the derive-ordering issue described in derive macros and structural recursion, raised to the level of modules: two macros that each expect the other’s output produce a module that compiles or does not depending on traversal order. Phase levels do not prevent this, because both macros are at the same phase; they only ensure that the phase is well-defined.

The general shape of the discipline is that a stage boundary is a commitment about what can be known when. Every facility that crosses the boundary — a macro referring to a function, a generated item referring to a type, a constant computed from a value — must be assigned a phase, and the assignment must be consistent along the whole dependency chain. The cost is the duplicate instantiation and the build ordering; the benefit is that expansion is decidable from the source alone. Systems that collapse the phases, expanding macros in the same pass that resolves their dependencies, gain convenience at the invocation site and lose the ability to say precisely what a macro can see.