Token Substitution and Tree Substitution in Macro Expansion

Two facilities are both called macro expanders and share almost nothing else. One matches an identifier against a flat sequence of preprocessing tokens and splices in a replacement sequence, with no notion of what the tokens mean. The other receives a form that has already been parsed into a tree, runs ordinary code over that tree, and returns another tree for the compiler to continue with. The choice between these two designs determines which bugs the macro system can have, whether malformed invocations are diagnosed, and whether expansion is guaranteed to finish.

A preprocessor sees tokens, not structure

A C macro definition binds a name to a replacement list of preprocessing tokens. When the name appears later in the translation unit and is followed by a (, the preprocessor collects arguments by splitting at commas that are not enclosed in parentheses, substitutes each argument for the corresponding parameter in the replacement list, and continues. Brackets, braces, and string literals carry no special weight during this split; only parenthesis depth is tracked. A comma inside square brackets therefore still separates arguments, which is why array subscripts in macro arguments require an extra pair of parentheses or a variadic form.

Because the substitution is textual at the token level, the macro body cannot see the shape of what it was given. Two classic consequences follow directly.

#define SCALE(x) x * 2
#define TWICE(x) ((x) + (x))

int a = SCALE(1 + 3);   /* 1 + 3 * 2, evaluates to 7 */
int b = TWICE(i++);     /* i modified twice without a sequence point: undefined behaviour */

SCALE is wrong because the argument’s internal structure is invisible: the multiplication binds tighter than the addition that arrived as part of x. TWICE is wrong in a different way, because the parameter appears twice in the replacement list, so the argument’s side effect is executed twice. Wrapping every parameter in parentheses fixes the first class of error and does nothing for the second. The usual mitigation is to make the parameter evaluate exactly once, by binding it to a temporary inside a statement expression or by using a function instead.

Two operators exist precisely because the preprocessor has no syntax to work with. # stringises an argument without expanding it first, producing a string literal from the argument’s spelling, and ## concatenates two adjacent tokens into one. Both suppress the normal argument expansion, since expanding first would destroy the spelling that the operator is defined to capture. The result of ## must be a single valid preprocessing token; if it is not, the standard does not define what happens, and implementations differ.

Rescanning, argument prescan, and the rule that stops recursion

Expansion has two phases that are easy to conflate. First, each argument is fully macro-expanded on its own, unless the corresponding parameter is adjacent to # or ##. Second, the replacement list is substituted and then rescanned together with the tokens that follow the invocation, so a macro that expands to the name of another macro triggers that macro in turn.

The indirection idiom exists because of the prescan rule. Writing CAT(A, B) where A and B are themselves macros produces the concatenation of the unexpanded spellings, because ## suppresses expansion of its operands. Routing through an extra macro layer forces the arguments to expand before they reach the pasting operator:

#define CAT_(a, b) a##b
#define CAT(a, b) CAT_(a, b)     /* arguments expand here, then paste in CAT_ */

Rescanning is bounded by a rule that has no analogue in tree-based macro systems: a macro name encountered while its own replacement list is being rescanned is not expanded again. Implementations enforce this by attaching to each token a set of macro names that are ineligible for further expansion. A definition such as #define f(x) f(x) + 1 therefore turns f(1) into f(1) + 1: the occurrence of f in the replacement carries the mark that suppresses it, so it survives into the output as a call that the preprocessor has already declined to expand. A pair of definitions that expand into each other likewise collapses to one of the two names instead of diverging. The practical effect is that preprocessor expansion always terminates, whatever the definitions say.

The standard also sets minimum capacities that a conforming implementation must provide: 4095 macro identifiers defined simultaneously in one translation unit, 127 parameters in a single macro definition, and 127 arguments in a single invocation. A macro library that exceeds these bounds is outside what the standard promises, even though most compilers accept far more.

Macros over parsed forms

A Lisp macro is a function whose arguments are unevaluated forms and whose result is a form to be compiled in place of the call. The reader has already built lists, symbols, and literals, so the macro body can destructure its input, test it, walk it, and construct output with the same operations any other program uses.

(defmacro unless (test &body body)
  `(if ,test nil (progn ,@body)))

Three properties come from operating on trees rather than tokens. Argument boundaries are the structure itself, so there is no comma-splitting rule to get wrong. The macro’s ordinary parameter list performs destructuring, which means an invocation with the wrong number of arguments is rejected at expansion time, with a message naming the macro. And because the macro body is arbitrary code, it can inspect an argument’s shape — for example, checking that a binding clause is a two-element list — instead of merely pasting it into a template.

The cost of that power is that expansion is a general computation. A macro whose body does not terminate hangs the compiler, and no rule analogous to the preprocessor’s self-reference restriction prevents it. Compilers that support tree macros therefore impose resource limits of their own rather than relying on the language definition: a step count, an expansion depth, or a wall-clock budget, each of which turns a non-terminating macro into a diagnostic.

Where the two models meet

Rust occupies the middle ground, and the compromise is instructive. macro_rules! matches token trees: the input is grouped by matched delimiters into a nested structure, so the matcher can require that a fragment be an expression, a type, or a statement, and the parser classifies the fragment before substitution. Precedence bugs of the SCALE kind cannot occur, because $x:expr captures a complete expression node rather than a run of tokens. Yet the expansion is still token-level: the replacement is a token sequence that is parsed afterwards, and a macro can produce syntactically invalid output that is only rejected once the surrounding parser sees it.

macro_rules! unless {
    ($cond:expr, $body:block) => { if !$cond $body };
}

The $cond:expr fragment is parsed and re-emitted with the parentheses the parser recorded, so unless!(a == b, { ... }) behaves as written. The $body:block fragment must be a braced block; passing an unbraced expression is a match failure rather than a confusing parse error later. What the fragment specifier buys is early classification, and what it costs is a fixed grammar of fragment kinds that the macro author cannot extend.

What neither model decides

Substitution strategy says nothing about which identifiers the expansion’s names refer to. A macro that introduces a local variable named tmp will shadow a caller’s tmp in a tree-based system just as readily as in a token-based one, because both splice the name into the caller’s scope. Preventing that requires a separate mechanism that tracks the origin of each identifier, treated in macro hygiene and identifier capture.

Nor does substitution strategy say how a macro builds output containing holes. Both families need a notation for “this part is literal, that part is substituted”, and both arrive at some form of quotation: backquote in Lisp, the replacement list itself in C, and $name interpolation in Rust. The depth rules that govern nested quotation are a distinct problem, covered in quasiquotation and nesting depth.

The useful summary is that token substitution is cheap, total, and blind, while tree substitution is expensive, partial, and structure-aware. A preprocessor cannot report a malformed invocation because it never learns what an invocation means; a Lisp macro can, because it runs in the compiler and receives the parsed argument. A preprocessor’s expansion is guaranteed to terminate because the language forbids the only unbounded case; a Lisp macro’s is not, and the compiler must add the limit that the semantics does not provide. Every later macro system is a position on the line between those two sets of properties, and most of them, including the procedural macro systems examined in procedural macros over token streams, choose token trees as the compromise: enough structure to classify fragments, not enough to make the macro body a compiler of its own.