Part of a multi-episode project
if and quote and define can NOT be ordinary functions, and how to dispatch to them;lambda so that a function remembers the environment it was born in -- a real closure, exactly the upvalue idea from episode 137;+, <, car, cons, ...) as plain Zig function pointers;Value tagged union, the Reader, readAll) -- we build straight on top of it;Learn Zig Series):Last episode we built a reader, and we ended it on a slightly frustrating note: we had taught the machine to turn (+ 1 (* 2 3)) into a tidy tree of Values, and we could print that tree back out again byte for byte -- but the thing just sat there. It did not add anything. It was data, inert data, a three-element list whose first element happened to be the symbol + and which meant absolutely nothing to nobody. That gap, between a data structure and a program, is the whole subject of today. We are going to write the E in Read-Eval-Print-Loop, and by the end that same list will actually evaluate to 7, we will have variables, we will have if, and -- the part I genuinely love teaching -- we will have real closures, functions that remember where they were born.
If you have followed the calculator project (episodes 146 through 149) you already met a tree-walking evaluator once, in episode 147. This is the same idea, grown up. The calculator could only ever compute one arithmetic expression; there were no names, no scopes, no way to define something and reuse it. Lisp fixes all of that, and it does so with an evaluator that is shockingly small -- the entire core is maybe a hundred lines. That smallness is not an accident. It is the famous Lisp insight, the one people write poems about: because code and data are the same shape (a Value tree), the evaluator only has to know how to walk one kind of thing. Here we go!
Before a single line of code, get the mental model straight, because everything hangs off it. When the evaluator looks at a Value, there are exactly three cases, and knowing which case you are in tells you what to do:
nil. 42 means 42, full stop. Nothing to compute.x or + is a name, and a name has to be looked up in the current environment to find what it refers to. x on its own does not mean the three letters -- it means "whatever x is bound to right now."(f a b) means "work out what f is, work out what a and b are, and apply the one to the others." This is where all the action lives, and it splits again into special forms versus ordinary function calls.That is the entire theory of evaluation. Having said that, before we can look anything up we need somewhere to look, so let us build the environment first.
An environment is a mapping from names to values, plus a pointer to its enclosing environment. That parent pointer is the crucial bit -- it is what makes nested scope work. When you ask for x and this scope does not have it, you walk up to the parent, and its parent, and so on, until you either find x or run out of scopes (an unbound-variable error). We store the local bindings in a std.StringHashMap, the same hash map we met in episode 22.
pub const Env = struct {
table: std.StringHashMap(Value),
parent: ?*Env,
pub fn init(a: std.mem.Allocator, parent: ?*Env) Env {
return .{ .table = std.StringHashMap(Value).init(a), .parent = parent };
}
pub fn lookup(self: *Env, name: []const u8) ?Value {
var e: ?*Env = self;
while (e) |env| : (e = env.parent) {
if (env.table.get(name)) |v| return v;
}
return null;
}
pub fn define(self: *Env, name: []const u8, v: Value) EvalError!void {
try self.table.put(name, v);
}
};
Look at lookup. It is a plain loop up the parent chain, and it returns an optional -- ?Value -- because a name genuinely might not be there. That while (e) |env| : (e = env.parent) is Zig's optional-capture loop with a continue-expression, walking the linked list of scopes one hop at a time. The parent being ?*Env (an optional pointer) is what terminates the walk: the global environment has parent = null, so when we reach it and still have not found the name, the loop ends and we hand back null. Nota bene: this single struct, a hash map plus a parent pointer, is the entire scoping mechanism of the language. Blocks, function calls, let -- they all boil down to "make a new Env whose parent is the current one."
For the values themselves we have to extend last episode's Value union a little, because now the language can produce two things the reader never could: builtin functions (like +) and user-defined functions (lambda). So we add two variants:
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,
};
pub const Lambda = struct {
params: []const []const u8,
body: []const Value,
env: *Env,
};
A builtin is nothing more exotic than a pointer to a Zig function -- give it the interpreter (so it can allocate) and a slice of already-evaluated arguments, and it hands back a Value or an error. A lambda, the user-defined kind, is a small struct: the parameter names, the body forms to run, and -- pay attention, because THIS is the whole closures idea from episode 137 -- the env the lambda was defined in. That captured environment is what makes a closure a closure. We will see it bite in a moment.
Now the function all of this exists to support. I wrap the state in an Interpreter struct that carries an arena allocator (so, just like the reader, we never free anything by hand -- one deinit at the end reclaims the lot) and a pointer to the global environment. The eval method is the three-questions model translated directly into a switch:
pub fn eval(self: *Interpreter, env: *Env, v: Value) EvalError!Value {
switch (v) {
.nil, .boolean, .number, .string, .builtin, .lambda => return v,
.symbol => |name| return env.lookup(name) orelse error.UnboundSymbol,
.list => |items| {
if (items.len == 0) return .nil;
return self.evalList(env, items);
},
}
}
Read the three arms against the three questions. Self-evaluating things -- numbers, strings, booleans, nil, and also already-built functions -- just return themselves; the first arm groups all of them. A symbol becomes env.lookup(name) orelse error.UnboundSymbol, and that orelse is Zig doing something beautiful: lookup returns an optional, and if it is null we convert it, right there, into a named error the caller can catch. No sentinel values, no -1, no crash -- an honest, typed UnboundSymbol. And the empty list () we treat as nil (a common Lisp convention), while a non-empty list goes off to evalList, which is where things get interesting.
Here is a subtlety that trips up everyone the first time, so let me be very explicit about it. Most lists are function calls: (+ 1 2) evaluates +, 1, and 2, then applies. But some lists must NOT evaluate their arguments. Consider (if condition then-branch else-branch): if we eagerly evaluated both branches before choosing, if would be useless -- worse, (if (safe?) (do-thing) (crash)) would crash every time even when it should not. And (define x 10): we must not evaluate x, because x is not defined yet, that is the whole point. Forms that control whether and when their arguments get evaluated are called special forms, and they cannot be ordinary functions. So evalList checks for them first, by name, before falling through to the general call machinery:
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 self.sfQuote(items);
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, "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..]);
}
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);
}
The shape is: if the head is a symbol naming a special form, dispatch to the hand-written handler that decides for itself what to evaluate. Otherwise -- and this is the ordinary-call path that handles the vast majority of lists -- we evaluate the head to get the thing we are calling, evaluate every argument, collect the results into a freshly-allocated slice, and hand off to apply. That for (items[1..], 0..) loop is where "arguments are evaluated left to right before the call" actually happens; it is a decision every language makes, and here it is, four lines, right in the open.
quote is the simplest special form and also the most philosophically loaded one. (quote x) returns x without evaluating it -- it is the escape hatch that lets you talk about code as data. We met the reader shorthand 'x last episode; this is the thing it expands into:
fn sfQuote(self: *Interpreter, items: []const Value) EvalError!Value {
_ = self;
if (items.len != 2) return error.BadSpecialForm;
return items[1];
}
fn sfIf(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len != 4) return error.BadSpecialForm;
const cond = try self.eval(env, items[1]);
if (isTruthy(cond)) return self.eval(env, items[2]);
return self.eval(env, items[3]);
}
sfQuote literally just hands back items[1] -- the thing after quote -- untouched. No evaluation. That is the entire trick, and it is exactly why (quote (+ 1 2)) gives you back a three-element list in stead of the number 3. sfIf is where you see lazy evaluation earn its keep: we evaluate the condition, and then -- depending on the result -- we evaluate only one of the two branches. The other branch is never touched. This is impossible to do as a normal function, because a normal function receives its arguments already evaluated; by the time it runs, the "crash" branch would already have crashed. Truthiness we keep dead simple, the Scheme way: everything is true except false and nil.
fn isTruthy(v: Value) bool {
return switch (v) {
.nil => false,
.boolean => |b| b,
else => true,
};
}
define binds a name in the current environment. I support two shapes: the plain (define x 10), and the sugar (define (square x) (* x x)), which is just a shorter way of writing (define square (lambda (x) (* x x))). Handling both is a matter of looking at what comes after define:
fn sfDefine(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len < 3) return error.BadSpecialForm;
switch (items[1]) {
.symbol => |name| {
if (items.len != 3) return error.BadSpecialForm;
const val = try self.eval(env, items[2]);
try env.define(name, val);
return val;
},
.list => |sig| {
if (sig.len == 0 or sig[0] != .symbol) return error.BadSpecialForm;
const lam = try self.makeLambda(env, sig[1..], items[2..]);
try env.define(sig[0].symbol, lam);
return lam;
},
else => return error.BadSpecialForm,
}
}
If the second element is a bare symbol, we evaluate the third element and bind it -- variable definition, done. If it is a list like (square x), we treat the first element as the function name and the rest as parameters, build a lambda from them and the body, and bind that. Notice we do NOT evaluate items[1] in either branch -- that is the special-form discipline again, because the name being defined does not have a value to look up yet. Now the lambda itself:
fn sfLambda(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len < 3 or items[1] != .list) return error.BadSpecialForm;
return self.makeLambda(env, items[1].list, items[2..]);
}
fn makeLambda(self: *Interpreter, env: *Env, params: []const Value, body: []const Value) EvalError!Value {
const names = try self.arena.alloc([]const u8, params.len);
for (params, 0..) |p, i| {
if (p != .symbol) return error.BadSpecialForm;
names[i] = p.symbol;
}
const lam = try self.arena.create(Lambda);
lam.* = .{ .params = names, .body = body, .env = env };
return Value{ .lambda = lam };
}
Everything in makeLambda is bookkeeping except the last two lines, and those two lines are the point of the whole episode. We allocate a Lambda, and we store env in it -- the environment that was current at the moment the lambda was written. That is the closure. When this function is later called, from wherever, it will run with access to the variables that were in scope where it was DEFINED, not where it was called. This is precisely the upvalue capture we studied in episode 137, except here we get it almost for free, because an environment is just a struct with a parent pointer and we already have one lying around.
let introduces a handful of local bindings and runs a body inside them. It is sugar you could technically build out of lambda, but writing it directly is clearer:
fn sfLet(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len < 3 or items[1] != .list) return error.BadSpecialForm;
const bindings = items[1].list;
const local = try self.arena.create(Env);
local.* = Env.init(self.arena, env);
for (bindings) |b| {
if (b != .list or b.list.len != 2 or b.list[0] != .symbol) return error.BadSpecialForm;
const val = try self.eval(env, b.list[1]);
try local.define(b.list[0].symbol, val);
}
return self.evalSequence(local, items[2..]);
}
We make a fresh Env whose parent is the current one, evaluate each binding's value in the outer environment (so the bindings cannot see each other -- that is the difference between let and let*, a nicety I am mentioning but not implementing today), stuff them into the local scope, and run the body there. Running a "body" -- possibly several forms in a row, keeping only the last result -- is common enough that I factor it out:
fn evalSequence(self: *Interpreter, env: *Env, forms: []const Value) EvalError!Value {
var result: Value = .nil;
for (forms) |f| result = try self.eval(env, f);
return result;
}
This is also exactly what begin needs, which is why evalList routes begin straight here. A sequence with no forms is nil; otherwise you get the value of the last form, every earlier one evaluated purely for its side effects (like a define).
Back in evalList, once we have an evaluated callee and an evaluated argument slice, we call apply. It has to handle both flavours of callable -- the builtin Zig function and the user lambda:
fn apply(self: *Interpreter, callee: Value, args: []const Value) EvalError!Value {
switch (callee) {
.builtin => |f| return f(self, args),
.lambda => |lam| {
if (args.len != lam.params.len) return error.WrongArgCount;
const local = try self.arena.create(Env);
local.* = Env.init(self.arena, lam.env);
for (lam.params, 0..) |p, i| try local.define(p, args[i]);
return self.evalSequence(local, lam.body);
},
else => return error.NotCallable,
}
}
A builtin is trivial: just call the Zig function pointer. The lambda case is the mirror image of makeLambda, and it is where the closure comes alive. We check the argument count (a WrongArgCount error if it is off). Then -- and this is THE line -- we make the call's local environment with parent = lam.env, the captured definition environment, not the environment we happen to be calling from. We bind each parameter to its argument in that local scope, and evaluate the body there. That one choice of parent is the difference between lexical scope (what almost every sane language uses) and dynamic scope (what almost nobody wants). And the else arm means that trying to call a number, (3 4 5), is a clean NotCallable error rather than undefined behaviour.
An interpreter with no builtins can compute nothing -- + has to come from somewhere. Builtins are just Zig functions matching the signature we put in the Value union: take the interpreter and the evaluated args, return a Value. Arithmetic first, with a small helper that insists an argument really is a number (and returns a typed TypeError if not):
fn wantNumber(v: Value) EvalError!f64 {
return switch (v) {
.number => |n| n,
else => error.TypeError,
};
}
fn biAdd(_: *Interpreter, args: []const Value) EvalError!Value {
var sum: f64 = 0;
for (args) |a| sum += try wantNumber(a);
return .{ .number = sum };
}
fn biSub(_: *Interpreter, args: []const Value) EvalError!Value {
if (args.len == 0) return error.WrongArgCount;
var acc = try wantNumber(args[0]);
if (args.len == 1) return .{ .number = -acc };
for (args[1..]) |a| acc -= try wantNumber(a);
return .{ .number = acc };
}
fn biLt(_: *Interpreter, args: []const Value) EvalError!Value {
if (args.len != 2) return error.WrongArgCount;
return .{ .boolean = (try wantNumber(args[0])) < (try wantNumber(args[1])) };
}
Because these are ordinary Zig, they are variadic in the Lisp sense for free: biAdd folds over however many arguments it gets, so (+ 1 2 3 4) is 10 and (+) is 0. biSub has the classic Lisp twist where one argument means negation ((- 5) is -5). And every place a non-number could sneak in, wantNumber turns it into a named error in stead of a wrong answer. The list operations are the other half of a Lisp's soul -- car, cdr, cons, list -- and these DO need the interpreter, because building a new list means allocating from the arena:
fn biList(ip: *Interpreter, args: []const Value) EvalError!Value {
const items = try ip.arena.alloc(Value, args.len);
@memcpy(items, args);
return .{ .list = items };
}
fn biCons(ip: *Interpreter, args: []const Value) EvalError!Value {
if (args.len != 2 or args[1] != .list) return error.TypeError;
const tail = args[1].list;
const items = try ip.arena.alloc(Value, tail.len + 1);
items[0] = args[0];
@memcpy(items[1..], tail);
return .{ .list = items };
}
fn biCar(_: *Interpreter, args: []const Value) EvalError!Value {
if (args.len != 1 or args[0] != .list or args[0].list.len == 0) return error.TypeError;
return args[0].list[0];
}
list gathers its arguments into a new slice; cons prepends one element to a list; car returns the first element (and cdr, which I have left off here for space but is in the full source, returns everything after the first). This is the vocabulary you build data structures out of in a Lisp -- there are no arrays or structs, there are only these cons-style lists, and yet it is enough to build anything. Wiring them into the global scope is one function, and it is deeply unglamorous in the best way:
fn installBuiltins(self: *Interpreter) EvalError!void {
try self.global.define("+", .{ .builtin = biAdd });
try self.global.define("-", .{ .builtin = biSub });
try self.global.define("*", .{ .builtin = biMul });
try self.global.define("/", .{ .builtin = biDiv });
try self.global.define("<", .{ .builtin = biLt });
try self.global.define("=", .{ .builtin = biEq });
try self.global.define("list", .{ .builtin = biList });
try self.global.define("cons", .{ .builtin = biCons });
try self.global.define("car", .{ .builtin = biCar });
try self.global.define("cdr", .{ .builtin = biCdr });
try self.global.define("null?", .{ .builtin = biNullp });
}
Each line binds a name to a builtin value. So + really is just a variable in the global environment whose value happens to be a function -- which means, delightfully, that you could rebind it, or pass it to another function, or return it from one. Functions are values here, no asterisks, no caveats.
The interpreter's init builds the global environment and installs the builtins, and a small evalStr helper reads a source string and evaluates every top-level form, using last episode's readAll:
pub fn evalStr(self: *Interpreter, src: []const u8) RunError!Value {
const forms = try readAll(self.arena, src);
var result: Value = .nil;
for (forms) |f| result = try self.eval(self.global, f);
return result;
}
That RunError is ReadError || EvalError -- the union of "the parse went wrong" and "the evaluation went wrong", so evalStr can surface either kind of failure through one honest return type. As always in this series, the tests are the specification, and the most convincing test in the whole project is the closure one:
test "lambda closes over its environment" {
const a = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(a);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
_ = try ip.evalStr("(define (make-adder n) (lambda (x) (+ x n)))");
_ = try ip.evalStr("(define add5 (make-adder 5))");
const v = try ip.evalStr("(add5 10)");
try std.testing.expectEqual(@as(f64, 15), v.number);
}
Sit with that for a second, because it is the forementioned magic made concrete. make-adder is called with 5, returns a lambda, and then make-adder has completely returned -- its call is over. Yet add5 still remembers that n was 5, because the lambda captured the environment where n lived. Call it with 10 and you get 15. The n outlived the function call that created it. That is a closure, and the arena is what lets it work without ceremony: the environment holding n is arena memory, so it stays alive as long as the interpreter does. And recursion falls out for free, because a defined function can look its own name up in the global scope:
test "recursion via define" {
const a = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(a);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
_ = try ip.evalStr(
\\(define (fact n)
\\ (if (< n 2) 1 (* n (fact (- n 1)))))
);
const v = try ip.evalStr("(fact 5)");
try std.testing.expectEqual(@as(f64, 120), v.number);
}
Nine tests in total cover the ground: arithmetic nesting evaluates, variables define and resolve, if picks the right branch on truthiness, closures capture, recursion computes 5! as 120, let scopes locally, the list builtins build and dismantle, quote returns data unevaluated, and an unbound symbol comes back as a catchable error.UnboundSymbol. On my machine zig test runs all nine green against Zig 0.16. We have a language.
A word on speed, because a tree-walker like this is the slowest respectable way to run a language, and it is worth knowing why. Every time we evaluate (+ x n) we walk the list, string-compare the head against every special-form name, hash-look-up + and x and n up a chain of scopes, allocate an argument slice from the arena... that is a lot of work to add two numbers. This is exactly the motivation for the bytecode compiler and VM we built for the calculator in episodes 148 and 149 -- compile the tree once into flat instructions, resolve variables to slots ahead of time, and the per-operation cost collapses. The obvious low-hanging fruit here would be to replace the string comparisons for special forms with an interned-symbol integer check, and to resolve variable lookups to (depth, index) pairs so we skip the hashing. But a tree-walker's virtue is that it is obvious -- you can read it and see exactly what the language means -- and for a teaching interpreter (or a config language, or a scripting layer that runs occasionally) that clarity beats raw speed every day of the week. Optimise when you have measured a reason to; not before.
The cross-language contrast is instructive too. In C, this same evaluator is a minefield of manual memory: every environment, every argument array, every consed list needs an allocation and, in a naive version, a matching free -- and closures make it genuinely hard, because you cannot free a function's environment when it returns if a lambda escaped with a pointer into it. That is the classic "upward funarg problem", and C solutions reach for reference counting or a garbage collector. Our arena sidesteps the whole thing: environments live until the interpreter dies, so an escaped closure is never a dangling pointer. In Rust, the Value would be an enum much like our union, but the recursive, shared, escaping ownership of closure environments fights the borrow checker hard -- most Rust Lisps end up wrapping environments in Rc<RefCell<...>>, paying runtime reference-counting to model exactly what our arena gives us for nearly nothing. In Go, the garbage collector makes closures effortless and you would have a working evaluator in an afternoon, at the cost of the GC deciding when memory goes away in stead of you -- fine for a script, less ideal for the predictable systems code this series is about. Zig's arena sits in a sweet spot for an interpreter: closures just work, there is no GC pausing your program, and the entire memory story is "one deinit at the end." That is a genuinely nice place to be.
Step back and look at what we have built across two episodes. Source text comes in, the reader turns it into a tree, and now the evaluator walks that tree and computes with it: numbers add up, if chooses, let scopes, define remembers, and lambda captures its birthplace so closures and recursion just work -- all of it on top of a hundred-odd lines and a single arena that makes the memory management a non-event. (+ 1 (* 2 3)) finally, actually, equals 7. Nine tests, all green against Zig 0.16.
But look again at the special forms, and notice something itching. if, quote, define, let -- every one of them is hard-wired into evalList in Zig. We can only add new syntax by editing the interpreter's source and recompiling. That feels wrong for Lisp, of all languages, the language whose entire reputation is that you can grow it from the inside. What if the language could define its own special forms? What if let were not Zig code at all, but something written in the Lisp itself, a function that takes code as data and returns new code? Remember how 'foo quietly became (quote foo) back in the reader -- code as data was staring at us the whole time. That thread, the one that turns "code is data" from a slogan into a power tool, is what we pull next. Thanks for reading, and tot de volgende keer! ;-)
@scipio