Lesson 4.8 — Syntax extension: token-based macros, AST-based macros and hygiene¶

Techniques: token-substitution macros (the C preprocessor; Clang's Preprocessor/TokenLexer), AST-based macros (Rust's macros by example with fragment specifiers, procedural macros; Swift macros), hygienic expansion (Kohlbecker, Friedman, Felleisen & Duba 1986; marks and syntax contexts, Dybvig, Hieb & Bruggeman 1992; sets of scopes, Flatt 2016; rustc's SyntaxContext) · Pebble implements: no macros (Pebble has no macro system); the lesson's examples run on Clang 23.1.2 and rustc 1.94.1 · Prerequisites: Lesson 1.1 (tokens), Lesson 4.7 (trees, lowering) · Time: 2 hours

A macro lets the programmer extend the syntax the parser accepts: a new name or form is rewritten, before or during parsing, into code the compiler already understands. Where the rewrite happens decides almost everything: on tokens, before the parser has seen any structure (C's #define), or on syntax trees and typed fragments (Rust, Scheme, Swift). And a rewrite that moves code from the macro's definition into the user's program can silently confuse the names of the two — the problem hygiene solves.

1. Problem and motivation¶

The problem. Given a program containing macro invocations and a set of macro definitions, produce an equivalent program without invocations, such that (a) the result's structure is what the macro author wrote (an argument that is an expression stays one expression), (b) names introduced by the macro and names written by the user do not capture each other unless the author asks for it, and (c) the process terminates and reports errors in terms of the source the user wrote.

Token-based macros¶

The C preprocessor (about 1973, standardized in C89 §3.8 / C23 §6.10) runs before parsing: #define DOUBLE(e) e * 2 replaces the tokens DOUBLE ( 1 + 2 ) by the tokens 1 + 2 * 2, and the parser sees the result. Tokens have no structure, so the argument's grouping is lost unless the author parenthesizes every use, and the GCC manual lists the pitfalls (operator precedence, swallowed semicolons, duplicated side effects, self-reference) [GCC-CPP]. Clang implements it in clang/lib/Lex (Preprocessor, TokenLexer) [CLANG-PPMacro]. It is still the macro system most C and C++ code uses, and C++ has no replacement for it apart from templates and constexpr.

AST-based macros¶

Lisp macros (1963 onwards) receive their arguments as data structures, not as text; Rust's macros by example (macro_rules!) match the argument token trees against patterns whose fragment specifiers ($e:expr, $t:ty, $i:ident) parse each fragment with the real parser, and paste the parsed fragment back as one opaque unit, so grouping is preserved [RUST-RefMBE, RUSTC-MBE]. Rust's procedural macros and Swift's macros (SE-0382 [SE0382]) go further: the macro is a program that receives a syntax tree (a token stream in Rust, a SwiftSyntax tree in Swift) and returns a new one, which the compiler parses and type-checks in place of the invocation.

Hygiene¶

A macro template that binds a name (let tmp = …) may capture a user's variable of the same name, and a template that refers to a name (std::io::_print) may be captured by a user's binding. Kohlbecker, Friedman, Felleisen and Duba [KFFD86] defined hygienic expansion for Scheme: identifiers introduced by one expansion step are renamed so they can only bind each other. Dybvig, Hieb and Bruggeman [DHB92] made it efficient with lazily propagated marks (the syntax-case system of R6RS Scheme), and Flatt [Fla16] reformulated it as sets of scopes (Racket). rustc attaches a syntax context (a chain of expansion marks) to every identifier's span and resolves local variables by name and context [RUSTC-Hygiene].

2. Definitions and algorithms¶

Token-based macros¶

Definition 4.8.1 (Token-substitution macro, expansion, disabled macro)

A token-substitution macro is either object-like, $M \mapsto \beta$, or function-like, $M(p_1, \dots, p_k) \mapsto \beta$, where $\beta$ is a token sequence (the replacement list) in which the parameters $p_j$ may occur. An invocation of a function-like $M$ is the token $M$ followed by a parenthesized, comma-separated list of arguments $\alpha_1, \dots, \alpha_k$ (commas inside nested parentheses do not separate). Expansion replaces the invocation by $\beta[p_1 := \alpha'_1, \dots, p_k := \alpha'_k]$, where $\alpha'_j$ is $\alpha_j$ fully expanded, and then rescans the result together with the rest of the input. While the replacement of $M$ is being rescanned, $M$ is disabled: an occurrence of $M$ produced by it is not expanded, and is marked so that it is never expanded later (C's "painted blue" tokens; Clang's Token::DisableExpand).

Losing and keeping grouping

With #define DOUBLE(e) e * 2, the invocation DOUBLE(1 + 2) has $\alpha_1$ = 1 + 2 and expands to the tokens 1 + 2 * 2, which the parser groups as $1 + (2 \cdot 2) = 5$. With #define DOUBLE2(e) ((e) * 2) it expands to ((1 + 2) * 2) $= 6$. With #define foo (4 + foo), foo expands to (4 + foo) and the inner foo is disabled, so expansion stops there.

Algorithm 4.8.2 (Macro expansion with rescanning and disabled macros)

Input: a token sequence $t$; a table of macro definitions; a set $A$ of disabled macro names (initially empty).
Output: the fully expanded token sequence.
Precondition: every function-like invocation has balanced parentheses.
Postcondition: no token of the output is an enabled macro name that could be expanded at its position (Theorem 4.8.7 shows the loop terminates).
Invariant: each output token is either a token of $t$, or of a replacement list, and is marked "disabled" if it names a macro that was in $A$ when it was produced.

function Expand(t, A):
    out ← []
    while t is not empty:
        x ← pop first token of t
        if x names a macro M, x is not marked disabled, and M ∉ A:
            if M is function-like and the next token of t is not '(':
                out.append(x);  continue                 # a function-like name without '(' is not an invocation
            args ← ReadArguments(t) if M is function-like else []   # consumes '(' ... ')'
            args' ← [Expand(α, A) for α in args]           # argument prescan
            body ← Substitute(M.β, M.params, args')         # plus # and ## (stringize, paste) on the raw args
            t ← Expand(body, A ∪ {M}) ++ t                  # rescan with M disabled
            # Expand's output is prepended to the remaining input, which is rescanned;
            # this is how a function-like macro name at the end of a replacement meets its '(' in the source.
        else if x names a macro M ∈ A:
            out.append(x marked disabled)                   # painted blue: never expanded again
        else:
            out.append(x)
    return out
function Substitute(β, params, args'):
    return β with each parameter token p_j replaced by the token sequence args'_j
function ReadArguments(t):
    pop '('; split the tokens up to the matching ')' at depth-0 commas; pop ')'

The C preprocessor loses the argument's grouping

Reproduce (clang 23.1.2):

cat > dbl.c <<'EOF'
#include <stdio.h>
int foo = 1;
#define foo (4 + foo)
#define DOUBLE(e) e * 2
#define DOUBLE2(e) ((e) * 2)
int main(void) {
  printf("%d %d %d\n", DOUBLE(1 + 2), DOUBLE2(1 + 2), foo);
  return 0;
}
EOF
clang-23 -E -P dbl.c | tail -4
clang-23 -o dbl dbl.c && ./dbl

Output (complete):

int main(void) {
  printf("%d %d %d\n", 1 + 2 * 2, ((1 + 2) * 2), (4 + foo));
  return 0;
}
5 6 5

What to notice: -E shows the token stream the parser receives: DOUBLE(1 + 2) became 1 + 2 * 2, so the program prints 5, while the fully parenthesized DOUBLE2 gives 6 (Theorem 4.8.8). foo expanded once to (4 + foo) and stopped — the inner foo is disabled and refers to the global variable, so it prints $4 + 1 = 5$. In Clang, Preprocessor::HandleIdentifier (clang/lib/Lex/Preprocessor.cpp) expands only if !Identifier.isExpandDisabled() && MI->isEnabled(), TokenLexer::Init calls Macro->DisableMacro(), and PPMacroExpansion.cpp sets Token::DisableExpand on a name whose macro is disabled [CLANG-PPMacro].

AST-based macros¶

Definition 4.8.3 (Macro by example, fragment, opaque substitution)

A macro by example is an ordered list of rules $(\pi_1 \Rightarrow \tau_1), \dots, (\pi_r \Rightarrow \tau_r)$. A matcher $\pi$ is a sequence of literal tokens, metavariables $\$x{:}F$ with a fragment specifier $F$ (a nonterminal of the language: expr, ty, pat, ident, tt = one token tree, …) and repetitions $\$( \dots ) \mathit{sep}\ {*}$. Matching $\pi$ against the argument token trees binds each $\$x{:}F$ to a fragment: the result of running the parser for $F$ on the input at that point. A transcriber $\tau$ is a token sequence with metavariables; opaque substitution inserts each bound fragment of kind $F \ne$ tt (and ident, lifetime) as a single unit — in rustc, a token group with invisible delimiters — which the parser treats like a parenthesized $F$. The result is then parsed as the nonterminal the invocation stands for (expression, statement, item).

double! with expr and with tt

macro_rules! double { ($e:expr) => { $e * 2 }; }: on double!(1 + 2), the expression parser consumes 1 + 2 and binds $\$e$ to the expression node; transcription gives ⟦1 + 2⟧ * 2, where ⟦ ⟧ are the invisible delimiters, which parses as $(1+2) \cdot 2 = 6$. With ($($t:tt)*) => { $($t)* * 2 } the fragments are three single token trees 1, +, 2, pasted without grouping: 1 + 2 * 2 $= 5$, the C behavior.

Algorithm 4.8.4 (Expanding a macro by example, after rustc's expand_macro)

Input: a macro invocation m!(args) in a position expecting nonterminal $N$; the rules of m.
Output: the syntax tree for $N$ that replaces the invocation, or an error "no rules expected this token".
Precondition: args is a token tree (balanced delimiters, as produced by the lexer).
Postcondition: the output is an $N$ tree in which every fragment bound to a non-tt metavariable appears as one subtree (Theorem 4.8.9).
Invariant: rules are tried in order; the first whose matcher matches all of args wins.

function ExpandMBE(m, args, N):
    for i in 1..r:
        β ← Match(π_i, args)                           # rustc: try_match_macro
        if β ≠ fail:
            ts ← Transcribe(τ_i, β, fresh mark μ)      # marks identifiers of τ_i with μ (Algorithm 4.8.6)
            return Parse(N, ts)                        # the fragment groups parse as units
    error "no rules expected this token in macro call"
function Match(π, input):                             # rustc: an NFA over matcher positions; fragments call the real parser
    for each element of π in order:
        literal token  → input must start with it; consume it
        $x:F           → run the parser for F on input; bind x ↦ (F, fragment); fail if it errors
        $( … ) sep *   → match the group repeatedly, binding x ↦ list of fragments
    succeed iff input is fully consumed
function Transcribe(τ, β, μ):
    replace each $x by β(x): a tt as raw tokens, any other F as Group(Invisible(F), tokens);
    expand repetitions per β's lists; apply mark μ to every identifier written in τ

Rust keeps an expr fragment's grouping, and loses it for raw token trees

Reproduce (rustc 1.94.1; -Zunpretty is unstable, so RUSTC_BOOTSTRAP=1 enables it on a stable toolchain):

cat > dbl.rs <<'EOF'
macro_rules! double { ($e:expr) => { $e * 2 }; }
macro_rules! double_tt { ($($t:tt)*) => { $($t)* * 2 }; }
fn main() { println!("{} {}", double!(1 + 2), double_tt!(1 + 2)); }
EOF
rustc -o dblr dbl.rs && ./dblr
RUSTC_BOOTSTRAP=1 rustc -Zunpretty=expanded dbl.rs | sed -n '/^fn main/,$p'

Output (complete):

6 5
fn main() {
    { ::std::io::_print(format_args!("{0} {1}\n", (1 + 2) * 2, 1 + 2 * 2)); };
}

What to notice: the same macro body gives 6 with an expr fragment and 5 with tt fragments: the pretty-printer shows the invisible group of the expr fragment as parentheses, (1 + 2) * 2. compiler/rustc_expand/src/mbe/transcribe.rs (transcribe_pnr) wraps every non-tt fragment in Delimiter::Invisible(InvisibleOrigin::MetaVar(kind)) "to maintain parsing priorities" [RUSTC-MBE]; tt fragments "are emitted into the output stream directly as raw tokens" — a token-based macro inside an AST-based system.

Hygiene¶

Definition 4.8.5 (Capture, hygiene condition, marks, syntax context)

Consider one expansion step that replaces an invocation by a template instance. An identifier occurrence in the result is user-written if it comes from the invocation's arguments and macro-introduced if it comes from the template. Capture happens when a binding occurrence of one kind binds a reference occurrence of the other kind that it would not bind in the unexpanded program. Expansion is hygienic [KFFD86] if generated bindings bind only generated references of the same step, and user bindings bind only user references (free template references resolve at the macro's definition site). A mark is a fresh token $\mu$ created per expansion step; a syntax context is the sequence (or set) of marks applied to an identifier. Two identifiers $(n_1, c_1)$ and $(n_2, c_2)$ refer to the same local binding iff $n_1 = n_2$ and $c_1 = c_2$ (the Rust rule for local variables, labels and $crate, "mixed-site hygiene" [RUST-RefMBE]).

SWAP in C and in Rust

SWAP(tmp, other) with the template { int tmp = a; a = b; b = tmp; } gives { int tmp = tmp; tmp = other; other = tmp; }: the template's tmp binding captures the user's tmp (the right-hand tmp, and both tmp in the assignments), so the macro swaps nothing. With marks, the template's binder is $(\texttt{tmp}, \mu)$ and the user's variable is $(\texttt{tmp}, \varnothing)$: let tmp#μ = tmp; tmp = other; other = tmp#μ; — a correct swap.

Algorithm 4.8.6 (Hygienic expansion with marks, after Kohlbecker et al. and Dybvig et al.)

Input: a program tree with macro invocations; each identifier carries a name and a context (initially empty).
Output: the expanded program in which every reference is resolved to a binding.
Precondition: macro definitions are known when their invocations are expanded (definition before use, or a fixed point over items).
Postcondition: the hygiene condition of Definition 4.8.5 holds (Theorem 4.8.10).
Invariant: an identifier's context records exactly the expansion steps that introduced it: a template identifier of step $s$ carries $\mu_s$ (plus the marks it had in the macro definition); a user identifier carries only the marks it had in the invocation.

function ExpandHygienic(tree):
    while tree contains an invocation m!(args):
        μ ← FreshMark()
        inst ← template of the matching rule with fragments of args substituted
        for each identifier x in inst that came from the template: x.ctx ← x.ctx ++ [μ]
        replace the invocation by inst                     # user identifiers are untouched
    Resolve(tree)
function Resolve(tree):                                     # lexical scoping on (name, ctx)
    for each reference r:
        bind r to the innermost binding b in scope with b.name = r.name and b.ctx = r.ctx
        if none: resolve r.name at the site recorded in r.ctx's last mark (the macro definition), or error

C's SWAP captures the user's variable; Rust's is hygienic

Reproduce (clang 23.1.2):

cat > swap.c <<'EOF'
#include <stdio.h>
#define SWAP(a, b) { int tmp = a; a = b; b = tmp; }
int main(void) {
  int tmp = 1, other = 2;
  SWAP(tmp, other);
  printf("tmp=%d other=%d\n", tmp, other);
  return 0;
}
EOF
clang-23 -E -P swap.c | tail -6
clang-23 -o swap swap.c && ./swap

Output (complete):

int main(void) {
  int tmp = 1, other = 2;
  { int tmp = tmp; tmp = other; other = tmp; };
  printf("tmp=%d other=%d\n", tmp, other);
  return 0;
}
tmp=1 other=2

What to notice: the inner int tmp shadows the user's tmp from its own initializer on (int tmp = tmp even reads the uninitialized inner variable), so the block assigns other to itself through the inner tmp and the outer tmp is never touched: no swap, and no diagnostic without -Wall. Token substitution has no way to tell the two tmps apart.

rustc's syntax contexts keep the two tmps apart

Reproduce (rustc 1.94.1):

cat > hyg.rs <<'EOF'
macro_rules! swap {
    ($a:ident, $b:ident) => { let tmp = $a; $a = $b; $b = tmp; };
}
fn main() {
    let mut tmp = 1;
    let mut other = 2;
    swap!(tmp, other);
    println!("tmp={tmp} other={other}");
}
EOF
rustc -o hyg hyg.rs && ./hyg
RUSTC_BOOTSTRAP=1 rustc -Zunpretty=expanded,hygiene hyg.rs | sed -n '/^fn main/,/^}/p'

Output (complete):

tmp=2 other=1
fn main /* 1303#0 */() {
    let mut tmp /* 2535#0 */ = 1;
    let mut other /* 1540#0 */ = 2;
    let tmp /* 2535#4 */ = tmp /* 2535#0 */;
    tmp /* 2535#0 */ = other /* 1540#0 */;
    other /* 1540#0 */ = tmp /* 2535#4 */;
    ;
    {
        ::std /* 0#5 */::io /* 2558#5 */::_print /* 2675#5
                */(format_args!("tmp={0} other={1}\n", tmp /* 2535#0 */,
                other /* 1540#0 */));
    };
}

What to notice: each identifier is printed as symbol#context: the user's tmp is 2535#0, the macro's tmp is 2535#4 — the same symbol, a different syntax context — so let tmp#4 = tmp#0 binds a new variable and the swap works. The full dump (after the code) lists context #4 as outer_mark: (crate0::{{expn2}}, SemiOpaque) with expn2 of kind Macro(Bang, "swap"): one fresh mark per expansion step, as in Algorithm 4.8.6. SemiOpaque is macro_rules!'s mixed-site hygiene (compiler/rustc_span/src/hygiene.rs, enum Transparency [RUSTC-Hygiene]): locals, labels and $crate resolve at the definition site, everything else at the call site; println!'s ::std::io::_print carries context #5 of its own expansion.

3. Worked example¶

One source line, three macro systems. The input is DOUBLE(a + b) / double!(a + b) with a = 1, b = 2, and the SWAP of §2.

step	C preprocessor (Algorithm 4.8.2)	`macro_rules!` with `$e:expr` (Algorithm 4.8.4)
1	see identifier `DOUBLE`, enabled, next token `(`	see invocation `double!(…)` in expression position
2	read arguments: $\alpha_1$ = `a + b` (3 tokens)	rule 1: matcher `$e:expr`; run the expression parser on `a + b`: tree $+(a, b)$, input fully consumed
3	prescan $\alpha_1$: no macros, $\alpha'_1$ = `a + b`	bind $e \mapsto$ (expr, $+(a,b)$)
4	substitute: `a + b * 2`; rescan with `DOUBLE` disabled: nothing to expand	transcribe: `⟦a + b⟧ * 2`, mark $\mu$ on template identifiers (none here)
5	parser: $a + (b \cdot 2) = 5$	parser: $\langle a+b \rangle \cdot 2 = 6$

Hygiene trace for swap!(tmp, other) (Algorithm 4.8.6), the contexts as rustc prints them:

occurrence	origin	context	resolves to
`let mut tmp` (line 5)	user	`#0`	binding $B_1$
`let tmp` in the template	macro, mark of `expn2`	`#4`	new binding $B_2$
`= $a` → `tmp`	user (fragment)	`#0`	$B_1$ (not $B_2$: contexts differ)
`$a = $b` → `tmp = other`	user	`#0`	$B_1$, `other`
`$b = tmp` → `other = tmp`	`other` user, `tmp` macro	`#0`, `#4`	`other`, $B_2$

Result: $B_2 \leftarrow 1$, $B_1 \leftarrow 2$, other $\leftarrow 1$ — the output tmp=2 other=1.

Try it

Predict, then check with clang-23 -E -P: #define SQ(x) x * x applied to SQ(1 + 1) and to SQ(i++). In Rust, write macro_rules! sq { ($x:expr) => { $x * $x }; } and run sq!({ println!("hi"); 2 }): how many times does it print, and why is that the same pitfall as C's even though the grouping is right?

4. Invariants and correctness¶

Token-based macros¶

Theorem 4.8.7 (Expansion with disabled macros terminates)

For a finite set of $m$ macro definitions and a finite input, Algorithm 4.8.2 terminates.

Proof

By induction on $m - |A|$, the number of macros not yet disabled. Call $\mathrm{Expand}(t, A)$ and consider the recursive calls it makes. Calls on arguments ($\mathrm{Expand}(\alpha, A)$) are on sequences strictly shorter than the remaining input and with the same $A$; calls on bodies are $\mathrm{Expand}(\beta', A \cup \{M\})$ with $M \notin A$, so $|A \cup \{M\}| = |A| + 1$ and they terminate by the induction hypothesis (when $|A| = m$ no macro can be expanded and the loop just copies its input). It remains to show that the loop of $\mathrm{Expand}(t, A)$ itself makes finitely many iterations. Each iteration either moves one token of $t$ to the output, or replaces an invocation (at least one token) by $\mathrm{Expand}(\beta', A \cup \{M\})$, a fully expanded sequence with respect to $A \cup \{M\}$: rescanning it at level $A$ can only expand occurrences of $M$ that are not marked — but every occurrence of $M$ produced inside that call was marked disabled (the third branch). The only tokens that can still trigger an expansion are a function-like macro name at the end of the expansion meeting a ( from $t$; each such expansion consumes at least the ( and ) of $t$. So the length of the unprocessed part of the original input strictly decreases every time an expansion at level $A$ starts, except that each expansion's result is scanned once, which is finite by the induction hypothesis. Hence finitely many iterations. The output can still be exponentially long: $M_1 \mapsto M_2\,M_2$, $M_2 \mapsto M_3\,M_3$, …, $M_m \mapsto x$ gives $2^{m-1}$ tokens from one.

Theorem 4.8.8 (Full parenthesization preserves grouping)

Let an expression grammar have the rule $\mathit{primary} \to (\ \mathit{expr}\ )$, and let a function-like macro's replacement list be $(\beta)$ where every parameter occurrence in $\beta$ is written $(p)$. If every argument $\alpha_j$ is a token sequence derivable from $\mathit{expr}$ and $\beta[p_j := x_j]$ (with fresh names $x_j$) derives from $\mathit{expr}$, then the expansion parses as $\beta$'s tree with each $x_j$ replaced by $\alpha_j$'s tree; in particular the value does not depend on the operators inside the arguments or around the invocation.

Proof

Each $(\alpha_j)$ is derivable from $\mathit{primary}$, and a primary is a leaf of every operator-precedence decision: the precedence parser (any of Lesson 4.1's four algorithms, which agree by Theorem 4.1.14) treats a parenthesized group as an atom, exactly like the identifier $x_j$. So the parse of $\beta[p_j := (\alpha_j)]$ has the same shape as that of $\beta[p_j := x_j]$ with the atoms $x_j$ replaced by the subtrees of $(\alpha_j)$. The outer parentheses make the whole expansion a primary as well, so the operators around the invocation cannot take part of it as an operand. The hypothesis on the arguments matters: an argument such as 1) + (2 is not derivable from $\mathit{expr}$ and breaks the argument. Parenthesization does not fix repeated evaluation: SQ(i++) still duplicates i++.

AST-based macros¶

Theorem 4.8.9 (Fragments are substituted as subtrees)

In the output of Algorithm 4.8.4, every fragment bound to a metavariable of kind $F \notin \{\texttt{tt}, \texttt{ident}, \texttt{lifetime}\}$ is a single subtree of kind $F$, identical to the tree the $F$-parser built during matching.

Proof

Transcription inserts the fragment as one token group with invisible delimiters tagged with $F$. When the result is parsed, the parser sees the group at a point where it expects some nonterminal; the group can be consumed only as a whole (its delimiters are balanced tokens, and nothing outside can match inside them), and the parser, on meeting an invisible group tagged $F$, returns the stored $F$ node (rustc's parse_nonterminal path) — just as a parenthesized expression is consumed only as a primary. So it becomes exactly one subtree, the one built during matching; the surrounding operators are parsed around it as around an atom, which is the argument of Theorem 4.8.8 with the parentheses made invisible and automatic. For tt fragments no group is inserted, which is why double_tt! loses grouping.

Hygiene¶

Theorem 4.8.10 (Marking prevents capture)

If identifiers are resolved by (name, context) as in Algorithm 4.8.6, then no binding introduced by an expansion step binds a user-written reference, and no user-written binding binds a reference introduced by an expansion step.

Proof

Consider expansion step $s$ with fresh mark $\mu_s$. By the invariant, every identifier the template introduces carries $\mu_s$ as its last mark, while every user-written identifier of the invocation's arguments carries only marks it had before step $s$; $\mu_s$ is fresh, so none of those contains $\mu_s$. Later steps append marks to their own template identifiers only, and apply the same append to identifiers of the step-$s$ output that pass through them as template identifiers, so the two groups remain distinguishable: their contexts differ in whether $\mu_s$ occurs at the position where step $s$ put it. Resolution binds a reference to a binding only when name and context are equal. A binding introduced at step $s$ has $\mu_s$ in its context and a user reference does not, so they are never equal; symmetrically for user bindings and introduced references. References that find no equal binding resolve at the macro definition site, which is what "free template references refer to the definition's environment" requires. Kohlbecker et al. [KFFD86] prove the corresponding result for their renaming algorithm; Flatt [Fla16] gives the set-of-scopes version, where marks become scopes and "equal context" becomes "the binding's scope set is a subset of the reference's".

5. Complexity¶

Let $n$ be the size of the program before expansion, $N$ its size after, $m$ the number of macros, and $d$ the nesting depth of expansions.

Technique	Time	Space	Notes
Token-based (C preprocessor)	$O(N \cdot d)$ token copies: each token of the output is rescanned once per enclosing expansion level	$O(N)$	$N$ can be $2^{m-1} n$ (Theorem 4.8.7's example); Clang avoids copying by lexing from macro bodies through `TokenLexer`
AST-based (macros by example)	per invocation: matching runs an NFA over matcher positions, $O(\ell \cdot \lvert \pi \rvert)$ thread steps for $\ell$ argument tokens when no fragment is involved, plus the fragment parsers (which commit: no backtracking into a fragment); `macro_parser.rs` notes its pathological cases are worse than an NFA's; plus parsing the transcription	$O(N)$	rustc tries rules in order: $r$ rules cost up to $r$ matching attempts
Hygiene, eager renaming (Kohlbecker et al.)	$O(N^2)$: every expansion step walks and renames its whole output [DHB92]	$O(N)$	the original algorithm
Hygiene, lazy marks (Dybvig et al.; rustc)	$O(N)$ amortized: marks are applied to a subtree lazily and pushed down when it is taken apart [DHB92]; rustc interns contexts, so a span carries one 32-bit context id	$O(N + \text{\#contexts})$	a syntax context lookup is a table access

Pathological cases. Token macros can blow up exponentially (#define X2(a) a a nested $k$ times, $2^k$ tokens), and the recursion limits of real preprocessors bound only nesting, not size. For macros by example, a matcher with nested repetitions and an ambiguous separator is rejected by rustc ("local ambiguity") instead of backtracking; the follow-set rules of the reference ($e:expr may only be followed by =>, , or ;) keep matching deterministic. Recursive macro_rules! that peel one token per step are quadratic in the input length and hit rustc's recursion_limit (128 by default).

Token-based macros¶

Stringizing and token pasting (#x, a ## b): operate on the unexpanded argument tokens — trade-off: code generation power (X-macros) with no structure at all.
Template-based substitutes (C++ templates, constexpr, if consteval): typed and scoped — trade-off: no new syntax, only new functions and types.

AST-based macros¶

Procedural macros (Rust proc_macro, Swift macros [SE0382]): arbitrary code transforms a token stream or syntax tree — trade-off: full power, but the macro is a separate program (a compiler plugin), and IDEs must run it.
Type-checked arguments (Swift): arguments are type-checked before expansion [SE0382] — trade-off: better diagnostics and IDE support without expansion, but a macro cannot accept code that is not already well-typed.

Hygiene¶

Mixed-site hygiene (Rust macro_rules!: locals, labels and $crate at definition site, other names at the call site [RUST-RefMBE]): trade-off: items and methods behave as if written at the call site, which is convenient but not fully hygienic.
Unique names instead of hygiene (Swift's makeUniqueName [SE0382], Common Lisp's gensym): the macro author requests fresh names by hand — trade-off: simple implementation, but hygiene depends on the author's discipline.
Sets of scopes [Fla16] (Racket): contexts as sets instead of sequences — trade-off: a simpler model that also handles definition contexts and modules.

7. In real compilers¶

Token-based macros¶

Clang: clang/lib/Lex/Preprocessor.cpp (HandleIdentifier), PPMacroExpansion.cpp (HandleMacroExpandedIdentifier, Token::DisableExpand), TokenLexer.cpp (DisableMacro) at llvmorg-23.1.2 [CLANG-PPMacro]; GCC's libcpp with its manual's pitfalls chapter [GCC-CPP]. The box after Algorithm 4.8.2 shows Clang's -E output.

AST-based macros¶

rustc: compiler/rustc_expand/src/mbe/macro_rules.rs (expand_macro, try_match_macro) and transcribe.rs (transcribe_pnr) at 1.94.1 [RUSTC-MBE]; Swift expression and attached macros [SE0382]; Scheme's syntax-rules. The box after Algorithm 4.8.4 shows rustc's expansion.

Hygiene¶

rustc compiler/rustc_span/src/hygiene.rs (SyntaxContext, ExpnData, enum Transparency) [RUSTC-Hygiene]; Racket's expander (sets of scopes [Fla16]); R6RS syntax-case [DHB92]. The boxes after Algorithm 4.8.6 show C's capture and rustc's contexts.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Token-based macros	Any token rewrite, no structure; `DOUBLE(1 + 2)` = 5	$O(N \cdot d)$ · fast, before parsing	Errors point into expansions ("expanded from macro"); no grouping, no scoping	Low	C, C++, assembly, `#include` guards
AST-based macros	Rewrites of parsed fragments; `double!(1 + 2)` = 6	matching per rule, parsing per expansion	Errors in terms of fragments; "no rules expected this token"	Medium (by example) to high (procedural)	Rust, Scheme, Swift, Elixir
Hygiene	Prevents capture both ways (Theorem 4.8.10)	$O(N)$ with lazy marks, $O(N^2)$ eager	Correct programs by default (`tmp=2 other=1`)	Medium: contexts on every identifier, resolution by context	Rust, Racket, Scheme; not C or Swift

Choose token macros when you must interoperate with C or need conditional compilation before parsing. Choose AST-based macros when the extension must respect the language's grammar and give good errors. Require hygiene whenever templates bind names — without it every macro author must invent unique names by hand.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Token-based macros	`cpp-double`, `cpp-self-ref`	—	`token-macros`	—
AST-based macros	`mbe-expr-vs-tt`, `mbe-fragment-subtree`	—	`ast-macros`	—
Hygiene	`hygiene-swap`, `hygiene-contexts`	—	`hygiene`	—

Pebble has no macros, so this lesson has no exercise; its outcomes are checked by the quiz and flashcards, whose answers come from the runs above.

References¶

See the chapter references.

step	C preprocessor (Algorithm 4.8.2)	`macro_rules!` with `$e:expr` (Algorithm 4.8.4)
1	see identifier `DOUBLE`, enabled, next token `(`	see invocation `double!(…)` in expression position
2	read arguments: \(\alpha_1\) = `a + b` (3 tokens)	rule 1: matcher `$e:expr`; run the expression parser on `a + b`: tree \(+(a, b)\), input fully consumed
3	prescan \(\alpha_1\): no macros, \(\alpha'_1\) = `a + b`	bind \(e \mapsto\) (expr, \(+(a,b)\))
4	substitute: `a + b * 2`; rescan with `DOUBLE` disabled: nothing to expand	transcribe: `⟦a + b⟧ * 2`, mark \(\mu\) on template identifiers (none here)
5	parser: \(a + (b \cdot 2) = 5\)	parser: \(\langle a+b \rangle \cdot 2 = 6\)

Technique	Time	Space	Notes
Token-based (C preprocessor)	\(O(N \cdot d)\) token copies: each token of the output is rescanned once per enclosing expansion level	\(O(N)\)	\(N\) can be \(2^{m-1} n\) (Theorem 4.8.7's example); Clang avoids copying by lexing from macro bodies through `TokenLexer`
AST-based (macros by example)	per invocation: matching runs an NFA over matcher positions, \(O(\ell \cdot \lvert \pi \rvert)\) thread steps for \(\ell\) argument tokens when no fragment is involved, plus the fragment parsers (which commit: no backtracking into a fragment); `macro_parser.rs` notes its pathological cases are worse than an NFA's; plus parsing the transcription	\(O(N)\)	rustc tries rules in order: \(r\) rules cost up to \(r\) matching attempts
Hygiene, eager renaming (Kohlbecker et al.)	\(O(N^2)\): every expansion step walks and renames its whole output [DHB92]	\(O(N)\)	the original algorithm
Hygiene, lazy marks (Dybvig et al.; rustc)	\(O(N)\) amortized: marks are applied to a subtree lazily and pushed down when it is taken apart [DHB92]; rustc interns contexts, so a span carries one 32-bit context id	\(O(N + \text{\#contexts})\)	a syntax context lookup is a table access

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Token-based macros	Any token rewrite, no structure; `DOUBLE(1 + 2)` = 5	\(O(N \cdot d)\) · fast, before parsing	Errors point into expansions ("expanded from macro"); no grouping, no scoping	Low	C, C++, assembly, `#include` guards
AST-based macros	Rewrites of parsed fragments; `double!(1 + 2)` = 6	matching per rule, parsing per expansion	Errors in terms of fragments; "no rules expected this token"	Medium (by example) to high (procedural)	Rust, Scheme, Swift, Elixir
Hygiene	Prevents capture both ways (Theorem 4.8.10)	\(O(N)\) with lazy marks, \(O(N^2)\) eager	Correct programs by default (`tmp=2 other=1`)	Medium: contexts on every identifier, resolution by context	Rust, Racket, Scheme; not C or Swift

Lesson 4.8 — Syntax extension: token-based macros, AST-based macros and hygiene¶

1. Problem and motivation¶

Token-based macros¶

AST-based macros¶

Hygiene¶

2. Definitions and algorithms¶

Token-based macros¶

AST-based macros¶

Hygiene¶

3. Worked example¶

4. Invariants and correctness¶

Token-based macros¶

AST-based macros¶

Hygiene¶

5. Complexity¶

6. Variants and refinements¶

Token-based macros¶

AST-based macros¶

Hygiene¶

7. In real compilers¶

Token-based macros¶

AST-based macros¶

Hygiene¶

8. Comparison¶

9. Assessment¶

References¶