Part of a multi-episode project
quote was the whole game all along, and how quasiquote (`), unquote (,) and unquote-splicing (,@) turn "code as data" from a slogan into a template language;defmacro to last episode's evaluator with barely a dozen new lines, and how evalList decides to expand before it decides to apply;when and unless as three-line macros rather than hard-wired Zig;&rest, so a macro body can accept any number of forms;gensym and a hygienic swap fix it for good;Interpreter;quote special form we met last episode;Learn Zig Series):Last episode we finished the evaluator, and we ended on an itch that I promised we would scratch. Remember it? Every special form -- if, quote, define, let -- was hard-wired into evalList in Zig. To teach the language a new piece of syntax, you had to edit the interpreter's source and recompile it. And I said that felt wrong for Lisp of all languages, the one language whose entire reputation is that it grows from the inside. Today we make good on that. By the end, when and unless will not be Zig code at all -- they will be three-line definitions written in the Lisp itself, and the interpreter will not have the faintest idea they exist. That is the magic of macros, and it is genuinely one of the most beautiful ideas in all of programming. Here we go!
The whole thing rests on a single sentence, so let me put it up front and then spend the rest of the episode earning it: a function takes values and returns a value; a macro takes code and returns code. A function runs when your program runs. A macro runs earlier, at the moment the evaluator first meets the call, and its job is not to compute an answer but to rewrite the call into different code -- which the evaluator then goes on to run as if you had typed it yourself. That one shift in when and on what a thing operates is the entire subject.
Back in the reader (episode 150) we did something that looked like a small convenience and was secretly the foundation of everything: 'foo became the two-element list (quote foo). And in the evaluator quote did the laziest thing imaginable -- it handed back its argument without evaluating it. (quote (+ 1 2)) gives you a three-element list, NOT the number 3. That is the hinge the whole language swings on: in Lisp, a program is a Value tree, and Value trees are things your program can build, inspect, and hand back. Code is data. Data is code. There is no wall between them the way there is in Zig, where a function body is a fundamentally different kind of thing from a slice.
If code is just data, then a function that produces code is just a function that produces a list. And a "macro" is nothing more mysterious than: take the raw argument forms (as data), run some code that builds a new form (a new list), and then evaluate that. The only genuinely new machinery we need is (a) a way to build code conveniently, and (b) a way to tell the evaluator "expand this before you run it." Let us take those in order.
You can build code with list, cons and quote. To construct (if c a b) by hand you would write (list 'if c a b), quoting the bits that are literal and leaving the bits that are computed. That works, but it gets unreadable fast once the template is bigger than a couple of elements. So every Lisp ships a template syntax: quasiquote. You write a backtick ` in stead of a quote, and inside it everything is literal except the parts you mark with a comma. A comma , means "stop quoting, evaluate this one thing and drop the result in." A comma-at ,@ means "evaluate this, which had better be a list, and splice its elements in here." So `(if ,c ,a ,b) reads almost exactly like the code it builds.
First we teach the reader those three sigils, right next to the ' we already had. Each one just wraps the next form in a two-element tagged list, exactly like quote did:
fn readForm(self: *Reader) ReadError!Value {
self.skipWs();
const c = self.peek() orelse return error.UnexpectedEof;
switch (c) {
'(' => return self.readList(),
')' => return error.UnexpectedRParen,
'\'' => { self.pos += 1; return self.wrap("quote", try self.readForm()); },
'`' => { self.pos += 1; return self.wrap("quasiquote", try self.readForm()); },
',' => {
self.pos += 1;
if (self.peek() == @as(u8, '@')) {
self.pos += 1;
return self.wrap("unquote-splicing", try self.readForm());
}
return self.wrap("unquote", try self.readForm());
},
'"' => return self.readString(),
else => return self.readAtom(),
}
}
So `(a ,x) parses to (quasiquote (a (unquote x))). Pure data, no evaluation yet -- the reader never evaluates anything, it only recognises shapes. All the interesting behaviour lives in a new special form, quasiquote, whose handler walks the template and decides, element by element, what is literal and what must be evaluated:
fn quasi(self: *Interpreter, env: *Env, template: Value) EvalError!Value {
if (template != .list) return template;
const items = template.list;
if (items.len == 2 and items[0] == .symbol and std.mem.eql(u8, items[0].symbol, "unquote")) {
return self.eval(env, items[1]);
}
var acc = std.ArrayList(Value).empty;
for (items) |item| {
if (item == .list and item.list.len == 2 and item.list[0] == .symbol and
std.mem.eql(u8, item.list[0].symbol, "unquote-splicing"))
{
const spliced = try self.eval(env, item.list[1]);
if (spliced != .list) return error.TypeError;
for (spliced.list) |s| try acc.append(self.arena, s);
} else {
try acc.append(self.arena, try self.quasi(env, item));
}
}
return .{ .list = try acc.toOwnedSlice(self.arena) };
}
Read it against the three cases. An atom (a number, a symbol, anything that is not a list) is literal -- return it untouched. A whole template that is an (unquote x) means evaluate x and use that. Otherwise we are looking at a list, and we walk it building a new one: any element that is itself (unquote-splicing xs) gets its list-value evaluated and its elements poured in one by one; everything else is recursively quasiquoted and appended as a single element. That recursion is what lets templates nest. Nota bene: ,@ is the reason you can build a form of unknown length -- a macro body with any number of statements -- which is precisely what when needs in a moment. Wire it into evalList beside the other forms and the reader shorthand just works:
if (std.mem.eql(u8, s, "quote")) return items[1];
if (std.mem.eql(u8, s, "quasiquote")) return self.quasi(env, items[1]);
Now the star of the show. A macro is, structurally, almost identical to a lambda -- it has parameters and a body and a defining environment. The only difference is when and how it is called: a lambda receives evaluated arguments and its result is the answer; a macro receives raw, unevaluated argument forms and its result is more code to evaluate. That near-sameness is a gift in a language with tagged unions, because we can reuse the Lambda struct entirely and just add one more variant to Value to mark the difference:
pub const Value = union(enum) {
nil,
boolean: bool,
number: f64,
symbol: []const u8,
string: []const u8,
list: []const Value,
builtin: *const fn (*Interpreter, []const Value) EvalError!Value,
lambda: *Lambda,
macro: *Lambda, // same shape as a lambda -- different treatment
};
(defmacro name (params...) body...) builds one of these. The handler is a near-copy of sfDefine's function branch, except it tags the result as .macro in stead of .lambda:
fn sfDefmacro(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
// (defmacro name (params...) body...)
if (items.len < 4 or items[1] != .symbol or items[2] != .list) return error.BadSpecialForm;
const lam = try self.makeLambda(env, items[2].list, items[3..]);
const m = Value{ .macro = lam.lambda };
try env.define(items[1].symbol, m);
return m;
}
The interesting part is not defining a macro, it is using one, and that happens in evalList. After we have ruled out the built-in special forms, but before we treat the head as an ordinary call, we ask a new question: is this head a symbol bound to a macro? If so, we do not evaluate the arguments. We expand:
fn evalList(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
const head = items[0];
if (head == .symbol) {
const s = head.symbol;
if (std.mem.eql(u8, s, "quote")) return items[1];
if (std.mem.eql(u8, s, "quasiquote")) return self.quasi(env, items[1]);
if (std.mem.eql(u8, s, "if")) return self.sfIf(env, items);
if (std.mem.eql(u8, s, "define")) return self.sfDefine(env, items);
if (std.mem.eql(u8, s, "set!")) return self.sfSet(env, items);
if (std.mem.eql(u8, s, "lambda")) return self.sfLambda(env, items);
if (std.mem.eql(u8, s, "let")) return self.sfLet(env, items);
if (std.mem.eql(u8, s, "begin")) return self.evalSequence(env, items[1..]);
if (std.mem.eql(u8, s, "defmacro")) return self.sfDefmacro(env, items);
// is the head a macro? expand, then evaluate the expansion.
if (env.lookup(s)) |v| {
if (v == .macro) {
const expanded = try self.expandMacro(v.macro, items[1..]);
return self.eval(env, expanded);
}
}
}
const callee = try self.eval(env, head);
const args = try self.arena.alloc(Value, items.len - 1);
for (items[1..], 0..) |arg, i| args[i] = try self.eval(env, arg);
return self.apply(callee, args);
}
Stare at those two lines in the macro branch, because they are the whole idea distilled. We call expandMacro with items[1..] -- the raw argument forms, exactly as written, nothing evaluated -- and then we take whatever comes back and hand it straight to eval. Expansion produces code; eval runs that code. Two phases, clearly separated. And expandMacro itself is just the lambda-call machinery pointed at the raw forms:
fn expandMacro(self: *Interpreter, m: *Lambda, args: []const Value) EvalError!Value {
const local = try self.arena.create(Env);
local.* = Env.init(self.arena, m.env);
try self.bindInto(local, m, args);
return self.evalSequence(local, m.body);
}
Notice it binds the parameters to the arguments and runs the body -- same as calling a function -- but the arguments it binds are unevaluated forms, and the "answer" it computes is a Value we intend to interpret as code. Nothing in Zig marks that intent; it is the same Value type either way. That is the deep trick, and it is only comfortable because code and data share one representation.
Let me make the difference concrete, because reading about it is one thing and seeing it is another. This tiny macro throws its first argument away entirely:
_ = try ip.evalStr("(defmacro second (a b) b)");
// 'a' is never defined anywhere; a *function* would crash evaluating it.
const v = try ip.evalStr("(second (car nil) 99)");
// v.number == 99
(car nil) is a guaranteed error -- you cannot take the car of an empty list. If second were an ordinary function, the argument (car nil) would be evaluated before the call, the error would fire, and we would never get anywhere. But second is a macro, so it receives the raw form (car nil) as data, quietly ignores it, and returns the form 99. The dangerous code was never run because it was never asked to be. THIS is the power if needed last episode and could only get by being hard-wired -- and now any user can write forms with that same control over evaluation, without touching the interpreter.
There is a practical gap to close before the good macros are writable. when should accept a condition and then any number of body forms: (when c a b c d). But our lambdas from episode 151 demanded an exact argument count. So we add a small variadic convention: a trailing &rest name in the parameter list soaks up all the leftover arguments as a single list. It lives in makeLambda, and because macros reuse Lambda, they get it for free too:
fn makeLambda(self: *Interpreter, env: *Env, params: []const Value, body: []const Value) EvalError!Value {
var fixed_end = params.len;
var rest: ?[]const u8 = null;
for (params, 0..) |p, i| {
if (p == .symbol and std.mem.eql(u8, p.symbol, "&rest")) {
if (i + 2 != params.len or params[i + 1] != .symbol) return error.BadSpecialForm;
fixed_end = i;
rest = params[i + 1].symbol;
break;
}
}
const names = try self.arena.alloc([]const u8, fixed_end);
for (params[0..fixed_end], 0..) |p, i| {
if (p != .symbol) return error.BadSpecialForm;
names[i] = p.symbol;
}
const lam = try self.arena.create(Lambda);
lam.* = .{ .params = names, .rest = rest, .body = body, .env = env };
return Value{ .lambda = lam };
}
The binding side pairs with it. I pulled the parameter-binding out of apply into a shared bindInto, so lambdas, macros, and apply all bind arguments the same way -- fixed params one-to-one, and any surplus gathered into the rest list:
fn bindInto(self: *Interpreter, local: *Env, lam: *Lambda, args: []const Value) EvalError!void {
if (lam.rest == null) {
if (args.len != lam.params.len) return error.WrongArgCount;
} else {
if (args.len < lam.params.len) return error.WrongArgCount;
}
for (lam.params, 0..) |p, i| try local.define(p, args[i]);
if (lam.rest) |rname| {
const extra = args[lam.params.len..];
const slice = try self.arena.alloc(Value, extra.len);
@memcpy(slice, extra);
try local.define(rname, .{ .list = slice });
}
}
Small change, big payoff -- &rest body is now a legal macro parameter, and inside the macro body is a plain list you can splice with ,@.
Here is the moment the episode has been building toward. when -- "if the condition holds, run all these forms" -- is a piece of syntax most languages bake into their compiler. In our Lisp it is three lines, written in the language, that the interpreter has never heard of:
_ = try ip.evalStr("(defmacro when (cond &rest body) `(if ,cond (begin ,@body) nil))");
const v = try ip.evalStr("(when (< 1 2) 10 20 30)"); // -> 30
const w = try ip.evalStr("(when (< 2 1) 10 20 30)"); // -> nil
Read the template: `(if ,cond (begin ,@body) nil). When you call (when (< 1 2) 10 20 30), cond is bound to the form (< 1 2) and body to the list (10 20 30). The quasiquote drops cond in after the if, splices the three body forms into a begin, and leaves nil as the else branch. Out comes (if (< 1 2) (begin 10 20 30) nil) -- real code, which then evaluates to 30. The interpreter runs if and begin, both of which it does know; when itself vanished the instant it expanded. unless is its mirror image and just as short:
_ = try ip.evalStr("(defmacro unless (cond &rest body) `(if ,cond nil (begin ,@body)))");
const v = try ip.evalStr("(unless (< 2 1) 42)"); // -> 42
Sit with what just happened, because it is the entire reason people fall in love with Lisp. We extended the language's syntax without extending the language's implementation. In Zig, adding new syntax means changing the compiler. Here, adding when means writing a three-line definition at the REPL, and it composes with everything else exactly as if it had been built in. That is the itch from last episode, finally scratched.
Now the sharp edge, because I would be doing you a disservice to show macros without the trap that catches everyone once. To demonstrate it we need mutation, so I have added a set! special form -- it assigns to an existing binding, walking the scope chain to find it (an unbound name is a clean UnboundSymbol error, not a silent new global):
fn sfSet(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len != 3 or items[1] != .symbol) return error.BadSpecialForm;
const val = try self.eval(env, items[2]);
try env.set(items[1].symbol, val);
return val;
}
With set! in hand, here is a swap macro that exchanges two variables. The obvious version uses a temporary called tmp:
// The NAIVE, buggy version -- do not ship this:
// (defmacro swap (a b)
// `(let ((tmp ,a)) (set! ,a ,b) (set! ,b tmp)))
For (swap p q) this expands to (let ((tmp p)) (set! p q) (set! q tmp)), which is perfect. But watch what happens the day someone writes (swap tmp other) -- a variable that just happens to be named tmp. Now the expansion is (let ((tmp tmp)) (set! tmp other) (set! other tmp)), and the macro's private tmp has collided with the user's tmp. The inner let shadows the real one, the swap silently does the wrong thing, and nothing errors. This is unhygienic macro expansion, and the bug is nasty precisely because it only shows up for particular variable names the macro author never imagined.
The fix is to never invent a name that could clash. We ask the interpreter for a guaranteed-fresh symbol -- one no source code could ever have typed -- via a gensym builtin backed by a counter on the interpreter:
fn biGensym(ip: *Interpreter, args: []const Value) EvalError!Value {
_ = args;
ip.gensym_counter += 1;
const name = try std.fmt.allocPrint(ip.arena, "g__{d}", .{ip.gensym_counter});
return .{ .symbol = name };
}
Now the hygienic swap: generate a fresh symbol at expand time, and unquote it into the template everywhere the temporary is needed. Because the name is unique, it cannot collide with anything the caller wrote:
_ = try ip.evalStr(
\\(defmacro swap (a b)
\\ (let ((tmp (gensym)))
\\ `(let ((,tmp ,a)) (set! ,a ,b) (set! ,b ,tmp))))
);
_ = try ip.evalStr("(define tmp 100)");
_ = try ip.evalStr("(define other 200)");
_ = try ip.evalStr("(swap tmp other)");
// tmp -> 200, other -> 100. Correct, even though the user's variable is literally called tmp.
Notice the macro body now has two layers: an ordinary let that runs during expansion to grab a gensym, wrapped around a quasiquote that builds the code. The ,tmp splices the generated symbol (something like g__1) into the output, so the expansion becomes (let ((g__1 tmp)) (set! tmp other) (set! other g__1)). No collision is possible, because no human ever types g__1. Real Schemes automate this with fully hygienic macro systems and Rust does it in its macro_rules!, but doing it by hand with gensym is how the whole industry did it for decades, and it is worth feeling the problem with your own fingers before a system hides it from you.
As always in this series, the tests are the spec, and the two I care most about are the ones that pin down the behaviour words can only gesture at -- that when expands correctly, and that hygiene actually holds:
test "when macro expands to if-begin" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
_ = try ip.evalStr("(defmacro when (cond &rest body) `(if ,cond (begin ,@body) nil))");
try std.testing.expectEqual(@as(f64, 30), (try ip.evalStr("(when (< 1 2) 10 20 30)")).number);
try std.testing.expect((try ip.evalStr("(when (< 2 1) 10 20 30)")) == .nil);
}
test "swap still works when a user variable is named tmp" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
_ = try ip.evalStr(
\\(defmacro swap (a b)
\\ (let ((tmp (gensym)))
\\ `(let ((,tmp ,a)) (set! ,a ,b) (set! ,b ,tmp))))
);
_ = try ip.evalStr("(define tmp 100)");
_ = try ip.evalStr("(define other 200)");
_ = try ip.evalStr("(swap tmp other)");
try std.testing.expectEqual(@as(f64, 200), (try ip.evalStr("tmp")).number);
try std.testing.expectEqual(@as(f64, 100), (try ip.evalStr("other")).number);
}
Nine tests cover the new ground: quasiquote assembles a list with an unquote and a splice in the right places, when and unless expand and run, set! mutates an existing binding, the hygienic swap works even against a hostile tmp, a macro ignores an argument that would crash a function, &rest gathers surplus arguments, and last episode's (+ 1 (* 2 3)) still evaluates to 7. On my machine zig test runs all nine green against Zig 0.16. The language now extends itself.
A word on speed, since macros have an unusual performance story. The good news is that a macro's work happens at expand time, once per site, and produces plain code -- so a well-written macro imposes zero runtime cost over having typed the expansion by hand. when is not slower than if; after expansion it is if. That is a genuinely lovely property: you get new syntax for free at runtime.
The honest news is that our particular implementation re-expands every single time it meets the call, because evalList expands and immediately evaluates, keeping nothing. In a tight loop that re-runs the macro expander over and over for no reason. The standard cure is a separate expansion pass: walk the whole program once, replacing every macro call with its expansion, then hand the fully-expanded tree to the evaluator (or to the bytecode compiler we built for the calculator back in episodes 148 and 149). That is exactly how real Lisps are structured -- read, macro-expand, compile, run, as four distinct stages -- and it is the natural next refactor if you wanted to make this fast. For a teaching interpreter I have kept expansion inline because it makes the two-phase idea impossible to miss: you can see expand-then-eval sitting right there in evalList. Optimise when you have measured a reason to, not before -- and here the clarity is worth more than the microseconds.
The cross-language contrast is unusually revealing for macros, because it is a feature the three comparison languages handle in three completely different ways.
In C, "macros" means the preprocessor, and the preprocessor operates on text, not on parsed code. #define SQUARE(x) x*x is a blind textual substitution, which is why SQUARE(a+b) famously expands to a+b*a+b and computes the wrong thing -- the preprocessor has no idea x is an expression, it just pastes characters. Our Lisp macros operate on the parsed Value tree, so (square (+ a b)) sees (+ a b) as a structured argument and can never mangle it that way. That structural-versus-textual gap is the single biggest reason C macros are treated as a last resort while Lisp macros are treated as a crown jewel.
In Rust, macro_rules! is much closer to what we built -- it matches on the token tree and is hygienic by default, meaning the compiler automatically renames a macro's internal identifiers so the tmp-collision bug we hit simply cannot happen; you get for free what we bought with gensym. Rust also has procedural macros, which are literally Rust functions that take a token stream and return a token stream -- that is our "code in, code out" definition almost word for word, just at compile time and over tokens in stead of Value lists. The price is real complexity: proc macros live in a separate crate and lean on heavy libraries to parse and rebuild syntax.
In Go, there are no macros at all, on purpose -- the language designers consider metaprogramming a readability hazard and would rather you wrote the code out or ran go generate to emit source ahead of time. That is a defensible position (you always know exactly what runs), but it means patterns that are a three-line macro here become either repetition or an external code generator there. Zig, interestingly, splits the difference with comptime (episode 9): it has no read-time macro system like this, but it lets ordinary code run at compile time, which covers a big slice of what macros are used for -- generating types and unrolling logic -- while keeping everything in one language with no separate expansion phase to reason about. Different philosophies, and building this Lisp is the best way I know to feel why each language landed where it did.
Step back and look at what these three episodes have become. Text goes into the reader and comes out a tree (150). The evaluator walks that tree and computes with it -- variables, if, closures, recursion (151). And now the language rewrites its own code before running it, so when, unless and a hygienic swap are written in Lisp, not in Zig, and the interpreter never knew (152). Read, expand, eval -- the three classic layers of a Lisp, each one small, each one resting on "code is data." Nine more tests, all green against Zig 0.16.
But run your eye over the vocabulary we actually have and it is thin. We can add, subtract, compare, cons, car, cdr -- and that is about it. There is no map, no filter, no fold, no length, no not, no way to append two lists. A language is not just its evaluator; it is also the library of useful things you can reach for without rebuilding them each time. And here is the satisfying part: with macros and lambdas both in hand, an awful lot of that library can be written in the language itself, no more Zig required. That is the thread we pull next -- turning this bare evaluator into something you would actually want to compute with. Thanks for reading, and de groeten! ;-)
@scipio