Part of a multi-episode project
null?, pair?, eq?, cons, car, cdr) and why everything else can be bootstrapped on top of them;define function shorthand so the prelude reads like Lisp instead of a wall of lambdas;map, filter and fold in the language itself -- three lines each, no Zig required;cond, and and or become recursive macros written in Lisp, not special forms hard-wired in Zig;Interpreter;defmacro from last episode;Learn Zig Series):Last episode ended on a confession. We had built a language that could evaluate, close over variables, recurse, and even rewrite its own syntax with macros -- and yet when I actually reached for the vocabulary, it was embarrassingly thin. We can add, subtract, compare, cons, car, cdr, and that is very nearly the whole list. No map. No filter. No fold. No length, no reverse, no append. An evaluator is not a language you would want to use; a language you want to use also has a standard library, the pile of small useful things you reach for without rebuilding them each time. Today we build that pile, and the satisfying part -- the part that makes this whole three-episode arc pay off -- is that almost none of it needs to be written in Zig. We write the library in the Lisp itself. Here we go!
There is a single design idea sitting underneath everything in this episode, and if you take nothing else away, take this: a real language is two languages stacked on top of each other. At the bottom is a tiny core of primitives that genuinely cannot be expressed in the language -- they touch the host machine, the raw data representation, the arithmetic unit. On top of that core sits a much larger library written in the language itself, defined in terms of the primitives and of each other. The whole art of language design is drawing that line in the right place: put too much in the core and your implementation bloats and every feature costs you Zig code; put too little and the language is unusable until someone writes a mountain of it. Lisp is famous for drawing the line extremely low, and that is exactly what lets a ten-line reader plus a small evaluator blossom into something expressive. Let us feel that firsthand.
The honest question to start with is: what genuinely cannot be written in Lisp itself, given what episode 151 already gives us? Arithmetic and comparison are already builtins -- they have to be, since Zig is the only thing here that can add two f64s. cons, car and cdr are already in from the evaluator -- they touch the list representation directly. What is missing is a small set of predicates and identity tests: is this thing empty (null?), is it a non-empty list (pair?), are these two values the same (eq?), and the humble not. These have to be primitives because they inspect the tagged union itself, which Lisp code has no other way to see. Here they are, in the same builtin shape episode 151 established -- fn (ip, args) EvalError!Value:
fn biNullp(ip: *Interpreter, args: []const Value) EvalError!Value {
_ = ip;
if (args.len != 1) return error.WrongArgCount;
return .{ .boolean = args[0] == .nil };
}
fn biPairp(ip: *Interpreter, args: []const Value) EvalError!Value {
_ = ip;
if (args.len != 1) return error.WrongArgCount;
return .{ .boolean = args[0] == .list and args[0].list.len > 0 };
}
fn biNot(ip: *Interpreter, args: []const Value) EvalError!Value {
_ = ip;
if (args.len != 1) return error.WrongArgCount;
return .{ .boolean = isFalsy(args[0]) };
}
isFalsy is a one-liner that encodes the language's notion of truth -- only nil and the boolean false count as false, everything else (including 0 and the empty string, deliberately) is true. That is the Scheme convention rather than the C one, and it is a choice, the kind you get to make when you build a language. eq? is slightly more work because it must compare across variants, so I write a small valuesEqual helper and expose it:
fn valuesEqual(a: Value, b: Value) bool {
if (@as(std.meta.Tag(Value), a) != @as(std.meta.Tag(Value), b)) return false;
return switch (a) {
.nil => true,
.boolean => a.boolean == b.boolean,
.number => a.number == b.number,
.symbol => std.mem.eql(u8, a.symbol, b.symbol),
.string => std.mem.eql(u8, a.string, b.string),
else => std.meta.eql(a, b), // lists/lambdas: identity by pointer/slice
};
}
fn biEq(ip: *Interpreter, args: []const Value) EvalError!Value {
_ = ip;
if (args.len != 2) return error.WrongArgCount;
return .{ .boolean = valuesEqual(args[0], args[1]) };
}
Nota bene: eq? here compares atoms by value and compound things by identity, which is precisely the distinction real Schemes draw between eq?, eqv? and equal?. I am collapsing them into one for teaching purposes, but it is worth knowing the family exists. While we are down here I also add a variadic list primitive -- (list 1 2 3) builds a list from already-evaluated arguments, which is different from quote because the arguments are evaluated first:
fn biList(ip: *Interpreter, args: []const Value) EvalError!Value {
const slice = try ip.arena.alloc(Value, args.len);
@memcpy(slice, args);
return if (args.len == 0) Value.nil else .{ .list = slice };
}
That is the entire core we add today -- five little builtins. Everything else in the standard library is going to be written upstairs, in the language.
One small reader chore before we go up a floor. Our library wants honest boolean literals, so the atom reader from episode 150 learns two new words. This is a three-line change to readAtom, slotting in beside the nil recognition it already had:
fn readAtom(self: *Reader) ReadError!Value {
const tok = self.readToken();
if (std.mem.eql(u8, tok, "nil")) return .nil;
if (std.mem.eql(u8, tok, "#t")) return .{ .boolean = true };
if (std.mem.eql(u8, tok, "#f")) return .{ .boolean = false };
if (parseNumber(tok)) |n| return .{ .number = n };
return .{ .symbol = tok };
}
Tiny, but it means (not #t) and (if #f 1 2) now read the way you would expect. Small quality-of-life fixes like this are most of what a standard-library pass actually is -- a hundred little conveniences, none of them clever, all of them necessary.
Here is a papercut we should fix before writing a page of definitions. In episode 152, defining a function meant (define map (lambda (f xs) ...)) -- the lambda and the name spelled out separately every single time. Every Lisp on earth offers a shorthand where (define (map f xs) ...) means the same thing, and since our whole prelude is about to be forty function definitions, that shorthand earns its keep instantly. It is a small enhancement to sfDefine: if the second element is a list rather than a symbol, treat its head as the name and its tail as the parameters, and build the lambda for the user:
fn sfDefine(self: *Interpreter, env: *Env, items: []const Value) EvalError!Value {
if (items.len < 3) return error.BadSpecialForm;
// (define (name params...) body...) -- function shorthand
if (items[1] == .list) {
const spec = items[1].list;
if (spec.len == 0 or spec[0] != .symbol) return error.BadSpecialForm;
const lam = try self.makeLambda(env, spec[1..], items[2..]);
try env.define(spec[0].symbol, lam);
return lam;
}
// (define name value)
if (items[1] != .symbol) return error.BadSpecialForm;
const val = try self.eval(env, items[2]);
try env.define(items[1].symbol, val);
return val;
}
Notice this reuses makeLambda from last episode untouched -- including its &rest support, so the shorthand handles variadic functions for free. This is the kind of change I like: it adds zero new concepts, it just makes the concepts we have pleasant to type. And pleasantness is not a luxury when you are about to write the library, it is the difference between a prelude you will maintain and one you will abandon.
Now the mechanism that ties it together. The standard library is just a string of Lisp source that we evaluate once, at startup, into the global environment -- before the user ever types anything. That string is the prelude. We store it as a Zig multiline string literal and load it in init:
const PRELUDE =
\\(define (not2 x) (if x #f #t))
\\(define (fold f acc xs)
\\ (if (null? xs) acc (fold f (f acc (car xs)) (cdr xs))))
\\(define (map f xs)
\\ (if (null? xs) nil (cons (f (car xs)) (map f (cdr xs)))))
\\(define (filter pred xs)
\\ (if (null? xs)
\\ nil
\\ (if (pred (car xs))
\\ (cons (car xs) (filter pred (cdr xs)))
\\ (filter pred (cdr xs)))))
\\(define (length xs) (if (null? xs) 0 (+ 1 (length (cdr xs)))))
\\(define (append a b) (if (null? a) b (cons (car a) (append (cdr a) b))))
\\(define (reverse xs) (fold (lambda (acc x) (cons x acc)) nil xs))
\\(define (member x xs)
\\ (if (null? xs) #f (if (eq? x (car xs)) xs (member x (cdr xs)))))
;
fn loadPrelude(self: *Interpreter) EvalError!void {
var reader = Reader.init(self.arena, PRELUDE);
while (try reader.next()) |form| {
_ = try self.eval(&self.global, form);
}
}
The only genuinely new plumbing is reader.next() -- episode 150's reader read a single form, but a prelude is many forms in a row, so next() returns the next top-level form each call and null at end of input. That is a five-line loop wrapped around the readForm we already have. Once loadPrelude runs, the global environment is furnished: map, filter, fold and the rest are ordinary bindings, indistinguishable from what a user would define, because that is exactly what they are. This is how CPython ships os and itertools, how a Scheme ships its (scheme base) library -- a body of code in the language, loaded before your program. The line between "language" and "library" is administrative, not fundamental.
Let us actually read the three definitions from the prelude, because they are the heart of the episode and each is only a few lines. Start with fold, the most general of the three -- give it a combining function, a starting accumulator and a list, and it walks left to right folding each element into the accumulator:
// (fold f acc xs) written in Lisp:
// (if (null? xs) acc (fold f (f acc (car xs)) (cdr xs)))
_ = try ip.evalStr("(fold (lambda (a x) (+ a x)) 0 (list 1 2 3 4))"); // -> 10
_ = try ip.evalStr("(fold (lambda (a x) (* a x)) 1 (list 1 2 3 4))"); // -> 24
Read the recursion: empty list, return the accumulator; otherwise recurse on the tail with the accumulator updated by folding in the head. Sum is fold + from 0, product is fold * from 1, and -- here is the lovely part -- reverse is also just a fold, consing each element onto the front of a growing list, which naturally flips the order. One three-line primitive, three derived operations. map and filter follow the same shape but build lists instead of scalars:
_ = try ip.evalStr("(map (lambda (x) (* x x)) (list 1 2 3 4))"); // -> (1 4 9 16)
_ = try ip.evalStr("(filter (lambda (x) (< x 3)) (list 1 2 3 4))"); // -> (1 2)
_ = try ip.evalStr("(length (map (lambda (x) (+ x 1)) (list 5 6)))"); // -> 2
map conses (f (car xs)) onto the mapped tail; filter conses the head only when the predicate holds, otherwise skips it and keeps going. Both bottom out at nil for the empty list. And every one of these is written in the language, calling only null?, car, cdr, cons and each other. No Zig was harmed. That is the standard-library principle made real: a tiny core, and a rich vocabulary grown on top of it entirely from within.
Now the moment last episode was secretly setting up. Nested if gets ugly fast; every language has a multi-branch cond. In most languages cond is a hard-wired piece of the compiler. In ours it is a macro, written in Lisp, and -- this is the part I love -- a recursive one, which expands into a chain of ifs by expanding itself on the rest of the clauses:
_ = try ip.evalStr(
\\(defmacro cond (&rest clauses)
\\ (if (null? clauses)
\\ nil
\\ (let ((clause (car clauses)))
\\ `(if ,(car clause)
\\ (begin ,@(cdr clause))
\\ (cond ,@(cdr clauses))))))
);
const v = try ip.evalStr(
\\(cond ((< 5 1) 100)
\\ ((< 5 3) 200)
\\ (#t 300))
); // -> 300
Follow the expansion once and it clicks. (cond (test1 body1) (test2 body2) ...) expands to (if test1 (begin body1) <expansion of cond on the rest>), and that inner cond expands the same way, peeling one clause per step until the clause list is empty and it produces nil. The `(...) quasiquote, the , unquotes and the ,@ splice are all exactly the tools from episode 152, and (cond ,@(cdr clauses)) is the recursive call: the macro emits another cond form, which the evaluator will expand in turn. A macro that expands into a call to itself -- if that does not make you grin, check your pulse. and and or are the same trick, short-circuiting by expanding into nested ifs:
_ = try ip.evalStr(
\\(defmacro and (&rest xs)
\\ (if (null? xs)
\\ #t
\\ (if (null? (cdr xs))
\\ (car xs)
\\ `(if ,(car xs) (and ,@(cdr xs)) #f))))
);
_ = try ip.evalStr("(and (< 1 2) (< 2 3) (< 3 4))"); // -> #t (last value)
_ = try ip.evalStr("(and (< 1 2) (< 9 3) (car nil))"); // -> #f, and car-nil never runs
Look closely at that second example, because it is the whole reason and has to be a macro and not a function. The third argument (car nil) is a guaranteed error -- but and short-circuits at the second clause, which is false, and because the expansion is a chain of ifs, the dangerous form is never evaluated. A function and would evaluate all its arguments before it ran, blow up on (car nil), and never get the chance to short-circuit. This is the same control-over-evaluation power we first met with if in episode 151, now available to ordinary library authors. The macro system we built last episode was not a party trick -- it is load-bearing infrastructure for the standard library, and cond/and/or are the receipt.
As throughout this series, I trust the tests over my own prose, and the ones that matter most pin down the two claims that words can only gesture at: that the self-hosted list functions actually compute the right thing, and that cond's recursive expansion selects the right branch. Because the prelude loads in init, a fresh Interpreter already knows all of this:
test "fold, map, filter are available from the prelude" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
try std.testing.expectEqual(@as(f64, 10), (try ip.evalStr("(fold (lambda (a x) (+ a x)) 0 (list 1 2 3 4))")).number);
try std.testing.expectEqual(@as(f64, 2), (try ip.evalStr("(length (filter (lambda (x) (< x 3)) (list 1 2 3 4)))")).number);
try std.testing.expectEqual(@as(f64, 3), (try ip.evalStr("(length (map (lambda (x) x) (list 7 8 9)))")).number);
}
test "cond selects the first true clause" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var ip = try Interpreter.init(arena.allocator());
_ = try ip.evalStr(
\\(defmacro cond (&rest clauses)
\\ (if (null? clauses) nil
\\ (let ((clause (car clauses)))
\\ `(if ,(car clause) (begin ,@(cdr clause)) (cond ,@(cdr clauses))))))
);
try std.testing.expectEqual(@as(f64, 300), (try ip.evalStr(
\\(cond ((< 5 1) 100) ((< 5 3) 200) (#t 300))
)).number);
}
Twelve tests cover the new ground: each of null?, pair?, eq? and not in isolation, the (define (f x) ...) shorthand producing a callable, map/filter/fold computing correctly, reverse as a fold, append joining two lists, member finding and failing, cond picking a branch, and and/or short-circuiting past a form that would otherwise crash. On my machine zig test runs all twelve green against Zig 0.16. And here is the quiet triumph: the ratio flipped. Last episode almost every new feature was Zig code. This episode, four of the twelve tests exercise behaviour that has no Zig implementation at all -- it is Lisp, evaluated by the Lisp, defined in the prelude. The language is now big enough to grow itself.
Honesty time, because self-hosting is not free. When map is written in the language and runs through the same eval loop as user code, every single step -- every cons, every car, every recursive call -- pays the interpreter's per-node overhead. A native Zig map would be a tight for loop over a slice; ours is a tree-walk that allocates an Env per recursive call. For a teaching interpreter that is exactly the right trade (clarity over microseconds, as always), but it is real, and on a million-element list you would feel it.
There is a sharper problem lurking in these definitions, and I want to name it rather than hide it. Look at length: (+ 1 (length (cdr xs))). That is not tail-recursive -- the + 1 has to happen after the recursive call returns, so every element adds a frame to the call stack. map and append have the same shape. On a long enough list, these overflow the Zig call stack and crash. fold, by contrast, is tail-recursive -- the recursive call is the last thing it does -- but our evaluator does not yet turn tail calls into loops, so it grows the stack too. Real Schemes are required by their standard to implement proper tail calls, which is exactly what lets you write loops as recursion without fear. Adding tail-call optimisation to eval (detect a call in tail position, reuse the current frame instead of recursing in Zig) is the natural next investment if you wanted this Lisp to be practical, and it pairs beautifully with the bytecode-VM approach we built for the calculator back in episodes 148 and 149. I am flagging it, not fixing it -- optimise when you have measured a reason to, and a teaching Lisp's reason is "the reader learned the idea," which it now has.
The core-versus-library question is one every language answers, and comparing the answers is unusually illuminating.
In C, the line is drawn brutally low and the "standard library" is a separate thing you #include and link -- libc. The language proper has no map, no lists, not even a string type; a C string is a convention (a char* with a \0), and everything from strlen to qsort lives in library functions written in C themselves, exactly mirroring our prelude-in-Lisp. The difference is that C's library cannot be as generic as ours -- qsort takes a void* and a comparator function pointer and casts blindly, because C had no generics for decades. Our Lisp map works on any list of anything for free, because dynamic typing is doing the work C's void* gymnastics were straining to do.
In Rust, the line is drawn cleverly. map, filter and fold are not language keywords -- they are methods on the Iterator trait, defined in the standard library in Rust itself, precisely like our prelude. But Rust's version is zero-cost: the compiler monomorphises and inlines the closure so that v.iter().map(|x| x*x).filter(...).sum() compiles down to the same tight loop you would have written by hand, no per-element overhead, no heap allocation. That is the dream our tree-walker can only point at -- the same expressiveness, none of the runtime tax -- and it is bought with a heavy compile-time machinery (traits, generics, lifetimes) that our forty lines of Lisp did not need. Different place to pay the bill.
In Go, the answer for years was "you do not get map, write the for loop." Go's designers deliberately kept the core tiny and were suspicious of generic library functions as readability hazards, so len and append were magic built-ins and everything else was hand-rolled loops. Generics arrived in Go 1.18 and a slices package now offers some of this, but the culture still leans toward writing the loop out. That is a coherent philosophy -- you always see exactly what runs, no hidden dispatch -- and it is the opposite pole from Lisp, where hiding the loop behind map is considered a virtue. Zig, interestingly, sits closer to Go here: no map built into the language, but comptime (episode 9) lets you write generic library functions that specialise at compile time, so you can have a zero-cost generic map if you want one, without a trait system. Four languages, four different heights for the same line, and building this Lisp is the clearest way I know to feel why each one chose where to draw it.
Step all the way back and look at what these four episodes became. Text goes in and a tree comes out (150). The evaluator walks the tree and computes -- variables, if, closures, recursion (151). Macros let the language rewrite its own code before running it (152). And now a standard library, written in the language itself, turns that bare evaluator into something with an actual vocabulary -- map, filter, fold, cond, and, or, all bootstrapped on a five-primitive core (153). Read, expand, eval, and a library on top: that is a language, small but complete, and every layer rested on the same idea that code is data. Twelve more tests, all green against Zig 0.16, and four of them testing behaviour that lives in no Zig at all.
That closes the Lisp project. We have now built, across this series, a calculator and a full little language of our own -- interpreters are firmly in the bag. Next I want to turn away from parsing and evaluating and point us back at the machine itself: the kind of low-level, from-scratch engine work where you are pushing bytes and building a data structure that does one focused thing very fast. It is a different flavour of mini project, closer to the metal, and a good change of pace after four episodes of thinking about thinking. Bring the tagged-union and allocator habits with you -- they never stop paying off. Bedankt voor het lezen, en tot de volgende keer! ;-)
@scipio