Learn Zig Series (#150) - Mini Project: Lisp - Reader

Part of a multi-episode project

What will I learn?

What the "read" in Read-Eval-Print-Loop actually means, and why in Lisp it is a genuinely separate stage from evaluation;
How to represent every Lisp datum -- numbers, symbols, strings, booleans, nil, and nested lists -- with a single tagged union, the way we learned back in episode 6;
How to write a tokenizer that is barely twenty lines because Lisp's syntax is almost non-existent (that is the whole point of Lisp);
How to turn that flat stream of tokens into a tree with a tiny recursive-descent reader, one that calls itself to read nested lists;
How to handle the quote shorthand 'x, and see for the first time why "code is just data" is more than a slogan;
How to write the reader's mirror image -- a printer -- so we can round-trip source text through the data model and prove nothing was lost;
How to report malformed input (a stray ), an unclosed string, a missing )) as typed errors in stead of a crash;
How one arena allocator makes the whole memory story for a parsed tree collapse into a single deinit.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org) -- the code here is written and tested against Zig 0.16;
Tagged unions from episode 6, allocators (especially the arena) from episode 7, and error unions from episode 4;
It helps to have the calculator lexer/parser from episode 146 and the recursive-descent detour from episode 132 somewhere in the back of your mind;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#150) - Mini Project: Lisp - Reader

We just spent four episodes building a calculator, and we ended with a real bytecode VM you could step through with a debugger. That project taught us the full spine of an interpreter -- lexer, parser, tree-walker, bytecode, stack machine. So why on earth start another language project now? Because the calculator, for all its machinery, could only ever do one thing: compute a single arithmetic expression. It had no variables you could define, no functions you could write, no way to grow. Lisp is where we fix that, and it is the perfect next step, because Lisp is the language that famously has almost no syntax at all. That sounds like a weakness. It is the opposite. It means the parser -- our subject today -- is small enough to hold in your head, and it means we get to meet, for real, one of the deepest ideas in programming: that in Lisp, code and data are the same thing.

Before a Lisp can evaluate anything, it has to read. In the classic Read-Eval-Print-Loop, "read" is a genuinely distinct phase that takes source text and produces a data structure -- not an abstract syntax tree in the calculator's sense, but ordinary Lisp data: numbers, symbols, and lists. The evaluator (that is next episode's job) then walks that data and gives it meaning. Today we build only the reader, and by the end we will have a thing that turns (+ 1 (* 2 3)) into a tree of Zig values, and turns that tree back into (+ 1 (* 2 3)) again, losing nothing. Here we go!

One type to represent everything

In the calculator we had a Token type and, separately, an Expr tree -- two different shapes for two different jobs. Lisp collapses that. The reader's output is Lisp's universal data type, and it has to represent every kind of datum the language knows: a number, a symbol (like + or foo), a string, the booleans, the empty-ish nil, and -- recursively -- a list of any of those. This is exactly the job a tagged union was born to do, the same tool we reached for back in episode 6.

const std = @import("std");

pub const Value = union(enum) {
    nil,
    boolean: bool,
    number: f64,
    symbol: []const u8,
    string: []const u8,
    list: []const Value,
};

Look at that list variant for a second, because it is where the magic lives: a Value can be a slice of Value. The type is recursive, which means the data is a tree, which means a Lisp program and a Lisp data structure are described by one and the same Zig type. When the evaluator later sees (+ 1 2), it is not looking at some special parsed "call node" -- it is looking at a plain three-element list whose first element happens to be the symbol +. That is homoiconicity, and it is why Lisp macros (a couple of episodes down the line) are so absurdly powerful: a macro is just a function that takes this data and returns more of it. Having said that, let us not get ahead of ourselves -- first we have to build one of these trees.

Notice too what is not here. We store symbols and strings as []const u8 slices. Numbers are plain f64 -- a real Lisp would carry integers and rationals as well, but a single float keeps us focused on the reader. And nil carries no payload at all; it is a bare tag, the Lisp equivalent of "nothing to see here."

The tokenizer: almost embarrassingly small

A tokenizer chops raw text into the smallest meaningful pieces. For most languages this is a chunky bit of code -- think back to episode 131, where the simple-language lexer had to recognise keywords, operators, and multi-character punctuation. Lisp's lexer is a different animal entirely, because Lisp has essentially four pieces of punctuation: (, ), ' (the quote shorthand), and " for strings. Everything else -- +, foo, 42, -3.5, hello-world -- is just an atom, a run of characters bounded by whitespace or one of those delimiters. So first, the token shape and the error set:

pub const ReadError = error{
    UnexpectedRParen,
    UnbalancedParen,
    UnterminatedString,
    UnexpectedEof,
    OutOfMemory,
};

const TokTag = enum { lparen, rparen, quote, atom, string, eof };

const Token = struct {
    tag: TokTag,
    text: []const u8,
    pos: usize,
};

Every token remembers its pos, the byte offset where it started. We do not lean on that heavily in this first cut, but it is the hook a real implementation uses to say "unclosed paren on line 12" in stead of just "unclosed paren." Now the lexer itself. It walks a cursor over the source, first skipping whitespace and ; comments (Lisp comments run to end of line), then classifying whatever it lands on:

const Lexer = struct {
    src: []const u8,
    pos: usize = 0,

    fn isDelim(c: u8) bool {
        return c == '(' or c == ')' or c == '\'' or c == '"' or std.ascii.isWhitespace(c);
    }

    fn skipSpaceAndComments(self: *Lexer) void {
        while (self.pos < self.src.len) {
            const c = self.src[self.pos];
            if (std.ascii.isWhitespace(c)) {
                self.pos += 1;
            } else if (c == ';') {
                while (self.pos < self.src.len and self.src[self.pos] != '\n') self.pos += 1;
            } else break;
        }
    }

    fn next(self: *Lexer, arena: std.mem.Allocator) ReadError!Token {
        self.skipSpaceAndComments();
        const start = self.pos;
        if (self.pos >= self.src.len) return .{ .tag = .eof, .text = "", .pos = start };
        const c = self.src[self.pos];
        switch (c) {
            '(' => {
                self.pos += 1;
                return .{ .tag = .lparen, .text = "(", .pos = start };
            },
            ')' => {
                self.pos += 1;
                return .{ .tag = .rparen, .text = ")", .pos = start };
            },
            '\'' => {
                self.pos += 1;
                return .{ .tag = .quote, .text = "'", .pos = start };
            },
            '"' => return self.readString(arena),
            else => {
                while (self.pos < self.src.len and !isDelim(self.src[self.pos])) self.pos += 1;
                return .{ .tag = .atom, .text = self.src[start..self.pos], .pos = start };
            },
        }
    }

That else branch is the entire "reader syntax" of atoms: from where we are, keep walking until you hit a delimiter, and hand back everything in between as one atom token. hello-world, +, 42, <=, list? -- all of them are read by that one loop, no special cases. This is why Lisp lets you name a function list->vector while most languages would choke on the >: to the lexer it is just non-delimiter characters. The text of an atom token is a slice into the source -- no copying, we just remember where it starts and ends.

Strings are the one case that needs real work, because of escape sequences. A "\n" in the source is two characters that must become one newline in the value, so we cannot just slice -- we have to build the unescaped bytes into a buffer:

    fn readString(self: *Lexer, arena: std.mem.Allocator) ReadError!Token {
        const start = self.pos;
        self.pos += 1; // skip the opening quote
        var buf: std.ArrayList(u8) = .empty;
        while (self.pos < self.src.len) {
            const c = self.src[self.pos];
            if (c == '"') {
                self.pos += 1;
                return .{ .tag = .string, .text = try buf.toOwnedSlice(arena), .pos = start };
            } else if (c == '\\' and self.pos + 1 < self.src.len) {
                self.pos += 1;
                try buf.append(arena, switch (self.src[self.pos]) {
                    'n' => '\n',
                    't' => '\t',
                    '\\' => '\\',
                    '"' => '"',
                    else => |other| other,
                });
                self.pos += 1;
            } else {
                try buf.append(arena, c);
                self.pos += 1;
            }
        }
        return error.UnterminatedString;
    }
};

Here is the first place the arena earns its keep. The unescaped string bytes are allocated from an arena allocator that the reader owns, so we never have to track and free this buffer by hand -- when the whole parse is done, one arena.deinit() reclaims every string, every list, everything. If the source runs out before we ever see a closing ", we fall out of the loop and return error.UnterminatedString -- a named failure, not a silent truncation. (That else => |other| other captures whatever character followed the backslash and passes it through unchanged, so \q becomes a literal q in stead of blowing up. Real Lisps are stricter; we are being forgiving.)

The reader: from a flat stream to a tree

Now the heart of it. The lexer gives us a flat sequence of tokens; the reader turns that into the recursive Value tree. This is recursive descent, exactly the technique from episode 132, but Lisp makes it almost suspiciously simple because the grammar is so tiny. Our reader keeps a one-token lookahead (a peeked slot) so it can look at the next token without consuming it -- the same trick the calculator parser used to decide what to do next.

pub const Reader = struct {
    lexer: Lexer,
    arena: std.mem.Allocator,
    peeked: ?Token = null,

    pub fn init(arena: std.mem.Allocator, src: []const u8) Reader {
        return .{ .lexer = .{ .src = src }, .arena = arena };
    }

    fn peek(self: *Reader) ReadError!Token {
        if (self.peeked == null) self.peeked = try self.lexer.next(self.arena);
        return self.peeked.?;
    }

    fn advance(self: *Reader) ReadError!Token {
        const t = try self.peek();
        self.peeked = null;
        return t;
    }

    pub fn read(self: *Reader) ReadError!?Value {
        const t = try self.advance();
        switch (t.tag) {
            .eof => return null,
            .rparen => return error.UnexpectedRParen,
            .lparen => return try self.readList(),
            .quote => return try self.readQuote(),
            .string => return Value{ .string = t.text },
            .atom => return try self.atomToValue(t.text),
        }
    }

The read function is the public entry point, and its return type tells the whole story: ReadError!?Value. It can fail (the error union), and it can legitimately return nothing (the optional) when we have reached the end of input -- that is how a caller knows to stop reading. A stray closing paren ) at the top level is an immediate error.UnexpectedRParen: you cannot close a list you never opened. An opening paren hands off to readList; a quote to readQuote; a string token becomes a string value directly; and an atom goes to atomToValue to be classified. Five short arms, and that is the entire dispatch.

The recursion lives in readList. When we have consumed a (, we keep reading values -- each of which may itself be a nested list, calling straight back into read -- until we meet the matching ):

    fn readList(self: *Reader) ReadError!Value {
        var items: std.ArrayList(Value) = .empty;
        while (true) {
            const t = try self.peek();
            switch (t.tag) {
                .eof => return error.UnbalancedParen,
                .rparen => {
                    _ = try self.advance();
                    return Value{ .list = try items.toOwnedSlice(self.arena) };
                },
                else => {
                    const v = (try self.read()) orelse return error.UnbalancedParen;
                    try items.append(self.arena, v);
                },
            }
        }
    }

Read that loop carefully, because it is the entire parser in miniature. We peek at the next token without consuming it. If it is ), we consume it and hand back the accumulated items as a list value -- done. If it is end-of-input, we ran off the edge without ever finding our closing paren, so we report error.UnbalancedParen. Otherwise we recurse into read, which happily deals with a nested (, and append whatever it gives us. Because read calls readList and readList calls read, arbitrary nesting -- (a (b (c))) -- just works, the call stack mirroring the paren depth. This is the payoff of recursive descent: the shape of the code follows the shape of the grammar.

Quote: the first taste of code-as-data

The single-quote shorthand is where Lisp starts to show its hand. Writing 'foo is defined to mean exactly the same thing as writing (quote foo) -- the reader expands the punctuation into an ordinary two-element list. That is a remarkable little fact: a piece of syntax turns into plain data that the evaluator will later interpret. We build that list right here in the reader:

    fn readQuote(self: *Reader) ReadError!Value {
        const quoted = (try self.read()) orelse return error.UnexpectedEof;
        const pair = try self.arena.alloc(Value, 2);
        pair[0] = Value{ .symbol = "quote" };
        pair[1] = quoted;
        return Value{ .list = pair };
    }

We read the thing being quoted (recursively -- you can quote a whole list, '(1 2 3)), then allocate a two-slot list from the arena: the symbol quote followed by whatever we just read. If there is nothing after the quote (' at end of input), that is an error.UnexpectedEof. When we print this back later, 'foo will come out as (quote foo) -- and that is not a bug, that is the truth: they are the same data. Nota bene: this is precisely the mechanism that, several episodes from now, lets macros rewrite code, because "rewriting code" turns out to be nothing more than building lists like this one.

The last reader piece is atom classification. An atom's characters could spell a number, a boolean, nil, or -- failing all of those -- a symbol. We decide by trying to parse a float and falling back:

    fn atomToValue(self: *Reader, text: []const u8) ReadError!Value {
        if (std.mem.eql(u8, text, "nil")) return .nil;
        if (std.mem.eql(u8, text, "true")) return .{ .boolean = true };
        if (std.mem.eql(u8, text, "false")) return .{ .boolean = false };
        if (std.fmt.parseFloat(f64, text)) |n| {
            return .{ .number = n };
        } else |_| {
            return .{ .symbol = try self.arena.dupe(u8, text) };
        }
    }
};

The order matters: we check the reserved words first, then try parseFloat, and only if that fails do we conclude the atom is a symbol. This is why + is a symbol (parseFloat rejects it) while -3.5 is a number (parseFloat accepts it) -- the numeric parser itself is our classifier, and we do not have to hand-write the rules for what a valid number looks like. For symbols we call arena.dupe to copy the characters into the arena, so that the finished tree owns all its bytes and no longer points back into the original source buffer. That is a deliberate design choice: after the read, you can throw the source text away and the Value tree still stands on its own.

Printing it back: proving the round-trip

A parser you cannot inspect is a parser you cannot trust. The cleanest way to check that we read something correctly is to print it back and see if we get the same text -- a round-trip. So we write the reader's mirror image: a function that walks a Value and renders it as Lisp source into a byte buffer.

const WriteError = std.mem.Allocator.Error || error{NoSpaceLeft};

pub fn writeValue(a: std.mem.Allocator, out: *std.ArrayList(u8), v: Value) WriteError!void {
    switch (v) {
        .nil => try out.appendSlice(a, "nil"),
        .boolean => |b| try out.appendSlice(a, if (b) "true" else "false"),
        .number => |n| {
            var buf: [64]u8 = undefined;
            try out.appendSlice(a, try std.fmt.bufPrint(&buf, "{d}", .{n}));
        },
        .symbol => |s| try out.appendSlice(a, s),
        .string => |s| {
            try out.append(a, '"');
            for (s) |c| switch (c) {
                '"' => try out.appendSlice(a, "\\\""),
                '\\' => try out.appendSlice(a, "\\\\"),
                '\n' => try out.appendSlice(a, "\\n"),
                '\t' => try out.appendSlice(a, "\\t"),
                else => try out.append(a, c),
            };
            try out.append(a, '"');
        },
        .list => |items| {
            try out.append(a, '(');
            for (items, 0..) |item, i| {
                if (i != 0) try out.append(a, ' ');
                try writeValue(a, out, item);
            }
            try out.append(a, ')');
        },
    }
}

The printer is recursive for the same reason the reader is: a list can contain lists. The .string arm re-escapes on the way out -- a real newline in the value becomes the two characters \n in the output -- so that what we print could be read back in again. The .list arm puts a single space between elements but not before the first or after the last, which is how you get (+ 1 2) and not ( + 1 2 ). And that WriteError set, combining Zig's allocator error with bufPrint's NoSpaceLeft, is a small but honest detail: formatting a float into a fixed 64-byte buffer can in principle overflow, and Zig makes us acknowledge that in the type in stead of pretending it cannot happen.

One convenience before we test. A source file is usually many top-level forms, not just one, so a helper that reads them all into a slice is handy:

pub fn readAll(arena: std.mem.Allocator, src: []const u8) ReadError![]Value {
    var reader = Reader.init(arena, src);
    var forms: std.ArrayList(Value) = .empty;
    while (try reader.read()) |v| try forms.append(arena, v);
    return forms.toOwnedSlice(arena);
}

That while (try reader.read()) |v| loop is Zig's optional-payload capture doing exactly what it was made for: keep going as long as read returns a value, stop the moment it returns null (end of input). Feed it 42 -3.5 true false nil hello and you get back six values; feed it a whole program and you get every top-level form in order.

Testing the reader

As always in this series, the tests are the specification. The most satisfying ones are the round-trips: read text into a tree, print the tree back, assert we got the original text. I wrap that in a small helper that spins up an arena, reads one form, and renders it with the outer test allocator (so the result survives the arena being torn down):

fn roundTrip(a: std.mem.Allocator, src: []const u8) ![]u8 {
    var arena = std.heap.ArenaAllocator.init(a);
    defer arena.deinit();
    const aa = arena.allocator();
    var reader = Reader.init(aa, src);
    const v = (try reader.read()).?;
    var out: std.ArrayList(u8) = .empty;
    try writeValue(a, &out, v);
    return out.toOwnedSlice(a);
}

test "round-trips nested lists" {
    const a = std.testing.allocator;
    const s = try roundTrip(a, "(+ 1 (* 2 3))");
    defer a.free(s);
    try std.testing.expectEqualStrings("(+ 1 (* 2 3))", s);
}

test "quote expands to (quote x)" {
    const a = std.testing.allocator;
    const s = try roundTrip(a, "'foo");
    defer a.free(s);
    try std.testing.expectEqualStrings("(quote foo)", s);
}

That second test is the whole quote idea captured in one assertion: we typed 'foo, and the data model contains (quote foo). The reader kept its promise. Next, the classifier -- proving that atoms sort themselves into the right variants, and that nil, true, and false are recognised in stead of being treated as symbols:

test "atoms classify into numbers, booleans, nil, symbols" {
    const a = std.testing.allocator;
    var arena = std.heap.ArenaAllocator.init(a);
    defer arena.deinit();
    const aa = arena.allocator();
    const forms = try readAll(aa, "42 -3.5 true false nil hello");
    try std.testing.expectEqual(@as(usize, 6), forms.len);
    try std.testing.expectEqual(@as(f64, 42), forms[0].number);
    try std.testing.expectEqual(@as(f64, -3.5), forms[1].number);
    try std.testing.expectEqual(true, forms[2].boolean);
    try std.testing.expectEqual(false, forms[3].boolean);
    try std.testing.expect(forms[4] == .nil);
    try std.testing.expectEqualStrings("hello", forms[5].symbol);
}

And the part that separates a toy from a tool: malformed input has to fail cleanly, with a name, not a crash. A truncated list, a stray closing paren, an unterminated string -- each is a distinct typed error the caller can catch and report:

test "unbalanced and stray parens are typed errors" {
    const a = std.testing.allocator;
    var arena = std.heap.ArenaAllocator.init(a);
    defer arena.deinit();
    const aa = arena.allocator();
    {
        var r = Reader.init(aa, "(+ 1 2");
        try std.testing.expectError(error.UnbalancedParen, r.read());
    }
    {
        var r = Reader.init(aa, ")");
        try std.testing.expectError(error.UnexpectedRParen, r.read());
    }
    {
        var r = Reader.init(aa, "\"oops");
        try std.testing.expectError(error.UnterminatedString, r.read());
    }
}

There is also the small matter of comments and whitespace, which the lexer is supposed to make disappear entirely. A leading comment line and a trailing one should have zero effect on what we read:

test "comments and whitespace are skipped" {
    const a = std.testing.allocator;
    const s = try roundTrip(a,
        \\; a leading comment
        \\(list 1 2) ; trailing
    );
    defer a.free(s);
    try std.testing.expectEqualStrings("(list 1 2)", s);
}

On my machine zig test runs all six of these green against Zig 0.16. That is the whole reader, verified: nested lists round-trip, quote expands, atoms classify, strings escape and unescape, bad input fails with named errors, and comments vanish. Not bad for a parser you can read in one sitting.

How this compares elsewhere

If you have written a JSON parser you have already met most of these ideas, and the contrast with other languages is instructive. In C, this same reader is where the pain of manual memory management concentrates: every list needs an allocation, every allocation needs a matching free, and a parse error halfway through a nested structure means carefully unwinding everything you allocated so far or leaking it. Our arena makes that entire category of bug evaporate -- read succeeds or fails, and either way one deinit cleans up. In Rust, the Value type would be an enum much like our union, and you would likely reach for Rc or an arena crate to handle the recursive ownership; the borrow checker keeps you honest but asks more of you up front, where Zig lets the arena carry the burden with almost no ceremony. In Go, an interface{} or a tagged struct plus the garbage collector would get you a reader in twenty minutes, at the cost of the GC deciding when your memory goes away in stead of you -- fine for a script, less fine for the kind of predictable systems code this series is about. The Lisp-specific lesson cuts across all of them though: because the syntax is so minimal, the parser is the easy part. In most languages the grammar is the hard bit and the data model is obvious; in Lisp it is the reverse, and that inversion is exactly what makes the language so malleable.

Where we go next

Step back and see what we have. A reader that takes the character string (+ 1 (* 2 3)) and produces a tree of Values -- and that same tree prints back to the same string, byte for byte. Along the way we built a tokenizer small enough to embarrass a C compiler's lexer, met homoiconicity face to face when 'foo quietly became (quote foo), and let a single arena allocator make the whole memory story a non-event. Six tests, all green against Zig 0.16, covering the happy path and the ugly one alike.

But reading is only the R in REPL. Right now (+ 1 2) is just data -- a three-element list sitting inertly in memory. It does not add anything, because nothing has yet given the symbol + any meaning. That is the difference between a data structure and a program, and closing that gap -- walking this tree and actually computing with it, with an environment that maps symbols to values -- is the whole job waiting for us next. We have taught the machine to read; soon we teach it to understand. Bedankt voor het lezen, en tot de volgende! ;-)

@scipio

Learn Zig Series (#150) - Mini Project: Lisp - Reader

Learn Zig Series (#150) - Mini Project: Lisp - Reader

What will I learn?

Requirements

Difficulty

Curriculum (of the Learn Zig Series):

Learn Zig Series (#150) - Mini Project: Lisp - Reader

One type to represent everything

The tokenizer: almost embarrassingly small

The reader: from a flat stream to a tree

Quote: the first taste of code-as-data

Printing it back: proving the round-trip

Testing the reader

How this compares elsewhere

Where we go next

Curriculum (of the `Learn Zig Series`):