Part of a multi-episode project
f64 literals, and a small name pool for variables;Expr tree from episode 146 that emits bytecode instead of computing a number;pi at compile time, and reject sqrt(1, 2) before the program ever runs;Expr tree those two produced;Learn Zig Series):At the end of last episode I made you a promise. We had a real, tested, tree-walking evaluator -- it read an Expr and handed you a number, with typed errors for every failure and even a constant-folding pass. And I closed by pointing at the one thing it was not: fast. Every node cost a switch on the union tag, a pointer chase to a child that lives who-knows-where on the heap, another function call, and back up again. For a calculator a human types into, that is nothing. For a tree evaluated a million times, those scattered pointer chases start to bite. Today we do something about it. We stop walking the tree and start compiling it -- flattening that pointer-chasing structure into a tidy array of bytecode the machine can march straight through. Here we go!
Let me be precise about the word, because it gets thrown around loosely. Compiling, in our little world, means a one-time translation: we take the Expr tree the parser built and we walk it once, emitting a flat sequence of simple instructions as we go. After that, the tree can be thrown away. The instructions -- the bytecode -- are what we keep, and they are what actually runs. If you evaluate the same expression a thousand times (plotting a curve, recomputing a spreadsheet column), you pay the tree-walk cost once at compile time and then run a cache-friendly flat array a thousand times. That is the entire trade, and it is the same trade a real language compiler makes at a much grander scale.
The target we compile to is a stack machine. If episodes 135 and 136 are ringing a bell, good -- this is where that theory earns its place in the project. A stack machine is dead simple: there is one stack of values, and every instruction either pushes a value onto it or pops some values, does something, and pushes the result back. add pops two numbers and pushes their sum. negate pops one and pushes its negation. That is the whole model. The cleverness is that any expression tree, no matter how deeply nested, flattens into a linear list of these push-and-pop instructions -- and the order that list must be in is postfix, also called reverse Polish notation.
Here is the tree we have been carrying since episode 146. I reproduce it so the compiler below has something concrete to walk:
const BinOp = enum { add, sub, mul, div, mod, pow };
const Expr = union(enum) {
number: f64,
ident: []const u8,
unary: struct { op: enum { neg }, operand: *Expr },
binary: struct { op: BinOp, lhs: *Expr, rhs: *Expr },
call: struct { name: []const u8, args: []*Expr },
};
Now think about 1 + 2 * 3. As a tree it is an add whose left child is 1 and whose right child is a mul of 2 and 3. To evaluate add, a stack machine needs both its operands already sitting on the stack. So the instructions have to be: push 1, push 2, push 3, mul (which consumes the 2 and 3 and leaves 6), then add (which consumes 1 and 6 and leaves 7). Written out: CONST 1, CONST 2, CONST 3, MUL, ADD. Notice the operators come after their operands -- that is postfix, and it is exactly what you get if you emit a node's children before you emit the node itself. The recursive walk that produces this is almost eerily simple, as we will see. The tree's shape, which the parser already built to encode precedence, translates directly into the order of the flat instruction stream. We are not re-deciding precedence; we are just reading the tree out loud in the right order.
Let us name our opcodes. Each is a single byte -- that is why it is called _byte_code -- and some are followed by a one-byte operand. I keep the set small on purpose; a calculator does not need two hundred instructions:
const OpCode = enum(u8) {
constant, // operand: index into the constant pool; pushes that f64
get_var, // operand: index into the name pool; pushes a variable's value
add,
sub,
mul,
div,
mod,
pow, // each pops two, pushes the result
negate, // pops one, pushes its negation
call, // operands: function id, argument count
ret, // stop; the top of the stack is the answer
};
The enum(u8) backing is deliberate: an OpCode is a byte, so @intFromEnum and @enumFromInt convert for free with no lookup table. Most opcodes carry no operand -- add is just the byte 2. But constant cannot carry an f64 in a single byte, so instead it carries a one-byte index into a side table of constants. Same story for get_var, which carries an index into a table of variable names. And call carries two operand bytes: which function, and how many arguments were pushed for it. This split -- opcodes in one flat byte array, bulky data in side tables -- is the classic bytecode layout, and it is what makes the code stream so compact and cache-friendly.
A compiled program is more than its instructions; it also needs the constant pool and name pool those instructions point into. Bundle all three together and you get what every bytecode system calls a chunk:
const Chunk = struct {
code: std.ArrayList(u8) = .empty,
constants: std.ArrayList(f64) = .empty,
names: std.ArrayList([]const u8) = .empty,
fn deinit(self: *Chunk, a: std.mem.Allocator) void {
self.code.deinit(a);
self.constants.deinit(a);
self.names.deinit(a);
}
};
Nota bene the = .empty default and the fact that every list method now takes the allocator explicitly -- that is the Zig 0.16 unmanaged ArrayList, the same style we have been using since the standard library moved to it. The code list is the raw instruction bytes. constants holds every literal f64 the program mentions, so an instruction can refer to 3.14159 by a one-byte index in stead of embedding eight bytes inline. names does the same for variable names. One deinit frees all three -- the chunk owns its data outright, which will matter a great deal the moment we start passing compiled programs around.
Now the heart of the episode. First the error set: compilation can fail in exactly four ways, and -- just like the evaluator's EvalError last episode -- naming them makes every failure a typed value the caller cannot forget:
const CompileError = error{
UnknownFunction, // a name like frobnicate(2)
BadArgCount, // sqrt(1, 2) -- wrong number of arguments
TooManyConstants, // more than 256 distinct literals
TooManyNames, // more than 256 distinct variable names
} || std.mem.Allocator.Error;
The compiler itself is a small struct holding the allocator and the chunk it is filling, plus a handful of emit helpers. The helpers are boring on purpose -- boring is good in code that runs for every single node:
const Compiler = struct {
a: std.mem.Allocator,
chunk: *Chunk,
fn emit(self: *Compiler, op: OpCode) !void {
try self.chunk.code.append(self.a, @intFromEnum(op));
}
fn emitByte(self: *Compiler, b: u8) !void {
try self.chunk.code.append(self.a, b);
}
fn addConstant(self: *Compiler, v: f64) !u8 {
const idx = self.chunk.constants.items.len;
if (idx > 255) return error.TooManyConstants;
try self.chunk.constants.append(self.a, v);
return @intCast(idx);
}
fn nameIndex(self: *Compiler, name: []const u8) !u8 {
for (self.chunk.names.items, 0..) |n, i| {
if (std.mem.eql(u8, n, name)) return @intCast(i);
}
const idx = self.chunk.names.items.len;
if (idx > 255) return error.TooManyNames;
try self.chunk.names.append(self.a, name);
return @intCast(idx);
}
};
Two details worth flagging. First, addConstant and nameIndex return a u8 and guard against overflowing 255 -- our operands are single bytes, so a program with more than 256 distinct constants is a real (if unlikely for a calculator) error, and we name it rather than let it wrap silently. Second, nameIndex de-duplicates: reference x five times and it lands in the name pool once. That is a small courtesy now and a genuine optimization in a bigger compiler.
And here is the walk itself -- the piece that turns a tree into postfix bytecode. Read it against the eval from last episode and you will see they are siblings: same five arms, same recursion, but where eval returned a number, compile emits an instruction:
fn compile(self: *Compiler, e: *const Expr) CompileError!void {
switch (e.*) {
.number => |v| {
const idx = try self.addConstant(v);
try self.emit(.constant);
try self.emitByte(idx);
},
.ident => |name| {
if (lookupConst(name)) |v| {
// pi, e, tau: resolved to a literal at compile time
const idx = try self.addConstant(v);
try self.emit(.constant);
try self.emitByte(idx);
} else {
const idx = try self.nameIndex(name);
try self.emit(.get_var);
try self.emitByte(idx);
}
},
.unary => |u| {
try self.compile(u.operand); // children first...
try self.emit(.negate); // ...then the operator
},
.binary => |b| {
try self.compile(b.lhs);
try self.compile(b.rhs);
try self.emit(binOpcode(b.op));
},
.call => |c| {
const id = fnId(c.name) orelse return error.UnknownFunction;
const spec = functions[id];
if (spec.arity) |want| {
if (c.args.len != want) return error.BadArgCount;
} else if (c.args.len == 0) {
return error.BadArgCount;
}
for (c.args) |arg| try self.compile(arg);
try self.emit(.call);
try self.emitByte(id);
try self.emitByte(@intCast(c.args.len));
},
}
}
Look at the .binary arm, because it is the whole idea in three lines: compile the left subtree, compile the right subtree, then emit the operator. Children before parent -- that is what produces postfix order, and it falls out of the recursion for free. The .unary arm is the same rhythm: emit the operand's code, then the negate. Because the recursion handles nesting, a monster like -(1 + 2) * sqrt(3) compiles correctly without a single special case -- each subtree lays down its own bytes, and the operators stack up in exactly the order the machine will need them.
The switch is exhaustive over the five variants, and that is not a nicety -- it is the compiler standing guard. If we ever add a sixth node type to Expr, this function stops compiling until we teach it how to emit code for the new node. In a growing project that refusal-to-compile is worth more than any amount of documentation.
This is my favourite part, because it shows why separating "understand the program" from "run the program" pays off. Two beats in that compile function do work the tree-walker of episode 147 simply could not.
The first is in the .ident arm: pi, e and tau are resolved to a plain literal at compile time. Last episode pi meant a runtime lookup on every evaluation; here it becomes a constant instruction pointing at 3.14159... and the name is never looked up again. That is compile-time constant folding, and it is invisible at run time -- the program just has one fewer thing to do, forever.
The second is more striking. Look at the .call arm: we check arity -- sqrt wants one argument, pow wants two, min/max want at least one -- and if the count is wrong we return BadArgCount right there, during compilation. In episode 147 that same check happened at evaluation time, once per run. Here sqrt(1, 2) is rejected before the program ever executes a single instruction. This is the entire promise of a compiler in miniature: catch what you can before the program runs, so the thing that actually runs is leaner and already known to be well-formed. Here is the small supporting cast -- the function table and the two lookups the walk leans on:
const Fn = struct { name: []const u8, arity: ?u8 }; // null arity = variadic (>= 1)
const functions = [_]Fn{
.{ .name = "sqrt", .arity = 1 }, .{ .name = "abs", .arity = 1 },
.{ .name = "floor", .arity = 1 }, .{ .name = "ceil", .arity = 1 },
.{ .name = "sin", .arity = 1 }, .{ .name = "cos", .arity = 1 },
.{ .name = "ln", .arity = 1 }, .{ .name = "pow", .arity = 2 },
.{ .name = "hypot", .arity = 2 }, .{ .name = "min", .arity = null },
.{ .name = "max", .arity = null },
};
fn fnId(name: []const u8) ?u8 {
for (functions, 0..) |f, i| if (std.mem.eql(u8, f.name, name)) return @intCast(i);
return null;
}
fn lookupConst(name: []const u8) ?f64 {
if (std.mem.eql(u8, name, "pi")) return std.math.pi;
if (std.mem.eql(u8, name, "e")) return std.math.e;
if (std.mem.eql(u8, name, "tau")) return std.math.tau;
return null;
}
fn binOpcode(op: BinOp) OpCode {
return switch (op) {
.add => .add, .sub => .sub, .mul => .mul,
.div => .div, .mod => .mod, .pow => .pow,
};
}
To finish the front door, a one-line entry point that compiles a whole expression and caps it with ret, so the eventual runner knows where the answer is and when to stop:
fn compileProgram(a: std.mem.Allocator, chunk: *Chunk, root: *const Expr) CompileError!void {
var c = Compiler{ .a = a, .chunk = chunk };
try c.compile(root);
try c.emit(.ret);
}
Raw bytes are correct but unreadable, and a mini project that you cannot inspect is a mini project you cannot trust. So before we run anything, we write a disassembler -- a function that walks the code array and prints each instruction in human form. This is not a throwaway debugging aid, either: it is the seed of the interactive debugger the next stage of the project is built around. Get the disassembler right now and half of that work is already done.
fn disasm(a: std.mem.Allocator, chunk: *const Chunk) ![]u8 {
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(a);
var buf: [160]u8 = undefined;
const code = chunk.code.items;
var ip: usize = 0;
while (ip < code.len) {
const at = ip;
const op: OpCode = @enumFromInt(code[ip]);
ip += 1;
const line = switch (op) {
.constant => blk: {
const idx = code[ip];
ip += 1;
break :blk try std.fmt.bufPrint(&buf, "{d:0>4} CONST c{d} (= {d})\n", .{ at, idx, chunk.constants.items[idx] });
},
.get_var => blk: {
const idx = code[ip];
ip += 1;
break :blk try std.fmt.bufPrint(&buf, "{d:0>4} GETVAR {s}\n", .{ at, chunk.names.items[idx] });
},
.call => blk: {
const id = code[ip];
const argc = code[ip + 1];
ip += 2;
break :blk try std.fmt.bufPrint(&buf, "{d:0>4} CALL {s}/{d}\n", .{ at, functions[id].name, argc });
},
else => try std.fmt.bufPrint(&buf, "{d:0>4} {s}\n", .{ at, @tagName(op) }),
};
try out.appendSlice(a, line);
}
return out.toOwnedSlice(a);
}
The instruction pointer ip advances by one for a bare opcode, by two when there is an operand byte to skip, by three for call -- so the disassembler has to understand each opcode's length. That is the same decoding logic the runner will need, which is a nice hint that we are on the right track. The @tagName(op) in the else arm is a small Zig gift: it turns an enum value into its name at no runtime cost, so add prints as add without a hand-written table. Compile 1 + 2 * 3 and disassemble it and you get exactly the postfix stream I promised earlier:
0000 CONST c0 (= 1)
0002 CONST c1 (= 2)
0004 CONST c2 (= 3)
0006 mul
0007 add
0008 ret
We have a compiler and a way to read its output, but the honest test is: does the bytecode actually compute the right number? To answer that I will write the smallest possible executor -- a stack, an instruction pointer, and a while loop over the opcodes. I want to be upfront: this is a sneak preview, not the finished machine. The real virtual machine, with proper error reporting, stack-depth safety, a debugger and step-by-step disassembly, is the whole subject of the next stage. This little loop exists only to confirm the bytes we emitted are correct.
Run-time failures get their own error set -- distinct from CompileError, because these are things that can only go wrong once the machine is actually executing:
const RunError = error{
StackUnderflow, // an opcode wanted more operands than were pushed
DivisionByZero,
DomainError, // sqrt of a negative, ln of zero
UnknownVariable, // a get_var with no binding in the env
};
fn applyFn(id: u8, args: []const f64) RunError!f64 {
const name = functions[id].name;
if (std.mem.eql(u8, name, "sqrt")) return if (args[0] < 0) error.DomainError else std.math.sqrt(args[0]);
if (std.mem.eql(u8, name, "abs")) return @abs(args[0]);
if (std.mem.eql(u8, name, "floor")) return std.math.floor(args[0]);
if (std.mem.eql(u8, name, "ceil")) return std.math.ceil(args[0]);
if (std.mem.eql(u8, name, "sin")) return std.math.sin(args[0]);
if (std.mem.eql(u8, name, "cos")) return std.math.cos(args[0]);
if (std.mem.eql(u8, name, "ln")) return if (args[0] <= 0) error.DomainError else @log(args[0]);
if (std.mem.eql(u8, name, "pow")) return std.math.pow(f64, args[0], args[1]);
if (std.mem.eql(u8, name, "hypot")) return std.math.hypot(args[0], args[1]);
if (std.mem.eql(u8, name, "min")) {
var acc = args[0];
for (args[1..]) |x| if (x < acc) { acc = x; };
return acc;
}
var acc = args[0]; // "max"
for (args[1..]) |x| if (x > acc) { acc = x; };
return acc;
}
fn run(chunk: *const Chunk, env: *const std.StringHashMap(f64)) RunError!f64 {
var stack: [256]f64 = undefined;
var sp: usize = 0;
const code = chunk.code.items;
var ip: usize = 0;
while (ip < code.len) {
const op: OpCode = @enumFromInt(code[ip]);
ip += 1;
switch (op) {
.constant => {
stack[sp] = chunk.constants.items[code[ip]];
ip += 1;
sp += 1;
},
.get_var => {
const name = chunk.names.items[code[ip]];
ip += 1;
stack[sp] = env.get(name) orelse return error.UnknownVariable;
sp += 1;
},
.add, .sub, .mul, .div, .mod, .pow => {
if (sp < 2) return error.StackUnderflow;
const b = stack[sp - 1];
const a = stack[sp - 2];
sp -= 1;
stack[sp - 1] = switch (op) {
.add => a + b,
.sub => a - b,
.mul => a * b,
.div => if (b == 0) return error.DivisionByZero else a / b,
.mod => if (b == 0) return error.DivisionByZero else @rem(a, b),
.pow => std.math.pow(f64, a, b),
else => unreachable,
};
},
.negate => {
if (sp < 1) return error.StackUnderflow;
stack[sp - 1] = -stack[sp - 1];
},
.call => {
const id = code[ip];
const argc = code[ip + 1];
ip += 2;
if (sp < argc) return error.StackUnderflow;
sp -= argc;
stack[sp] = try applyFn(id, stack[sp .. sp + argc]);
sp += 1;
},
.ret => break,
}
}
return stack[sp - 1];
}
Trace CONST 1, CONST 2, CONST 3, MUL, ADD, RET through that loop by hand and watch the stack: [1], [1,2], [1,2,3], then MUL collapses the top two to [1,6], then ADD collapses those to [7], and RET hands back 7. No pointers chased, no recursion, no tree -- just an index marching forward through a byte array. That flat, predictable, forward-only access pattern is exactly what modern CPUs are built to devour, and it is the whole reason we went to this trouble.
As always, the tests read like a specification. First, the compiler produces the precise postfix stream we expect -- we assert on the disassembly, so a wrong opcode or a wrong order fails loudly:
test "compiles 1 + 2 * 3 into postfix bytecode" {
const a = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(a);
defer arena.deinit();
const aa = arena.allocator();
const tree = try bin(aa, .add, try num(aa, 1), try bin(aa, .mul, try num(aa, 2), try num(aa, 3)));
var chunk = Chunk{};
defer chunk.deinit(a);
try compileProgram(a, &chunk, tree);
const text = try disasm(a, &chunk);
defer a.free(text);
try std.testing.expectEqualStrings(
"0000 CONST c0 (= 1)\n0002 CONST c1 (= 2)\n0004 CONST c2 (= 3)\n0006 mul\n0007 add\n0008 ret\n",
text,
);
}
Then the two payoffs. The compiled bytecode runs to the same numbers the tree-walker gave -- (1 + 2) * 3 is 9 whether you walk the tree or march the bytes -- and, crucially, the arity error is caught at compile time, so expectError fires from compileProgram, never reaching run at all:
test "bytecode runs, and bad arity is a compile-time error" {
const a = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(a);
defer arena.deinit();
const aa = arena.allocator();
var env = std.StringHashMap(f64).init(a);
defer env.deinit();
const tree = try bin(aa, .mul, try bin(aa, .add, try num(aa, 1), try num(aa, 2)), try num(aa, 3));
var chunk = Chunk{};
defer chunk.deinit(a);
try compileProgram(a, &chunk, tree);
try std.testing.expect(@abs(9 - try run(&chunk, &env)) < 1e-9);
const args = try aa.alloc(*Expr, 2);
args[0] = try num(aa, 1);
args[1] = try num(aa, 2);
const call = try aa.create(Expr);
call.* = .{ .call = .{ .name = "sqrt", .args = args } };
var c2 = Chunk{};
defer c2.deinit(a);
try std.testing.expectError(error.BadArgCount, compileProgram(a, &c2, call));
}
On my machine zig test runs both green. (The num and bin helpers just allocate Expr nodes by hand so the tests do not depend on the parser -- in the real pipeline the parser from episode 146 hands us the tree.) That second test is the episode in one assertion: sqrt(1, 2) never runs, because it never compiles.
If you have built a bytecode compiler in C -- and the canonical teaching example, the one in Crafting Interpreters, is exactly this -- the structure will feel like home: an opcode enum, a growable byte array, a constant pool, a recursive emitter. What C does not give you is the exhaustive switch. Forget a node type in C and the compiler shrugs; forget one here and Zig refuses to build. C also leaves the enum-to-name mapping to you (a hand-written table that drifts out of sync), where @tagName gives it to us for free and always correct. Rust is the closest cousin: match is exhaustive too, enums carry the same weight, and a Vec<u8> plays the part of our code array -- the difference is mostly Zig's explicit allocators versus Rust's ownership doing the memory bookkeeping. Go would reach for its garbage collector and a slice of bytes, ergonomic and quick to write, but its switch does not enforce exhaustiveness, so "did I emit code for every node?" is back to being your problem in stead of the compiler's. The algorithm -- walk the tree, emit children before parents, keep bulky data in side tables -- is universal. Zig's contribution is that the two guarantees you most want in a compiler (every node handled, every operand byte accounted for) are things the language checks for you rather than things you hope you got right.
Step back and look at what we built. We took the clean Expr tree from the front end and compiled it: a stack-machine instruction set, a chunk that bundles code with its constant and name pools, a recursive emitter that lays down postfix bytecode almost for free, compile-time constant folding, compile-time arity checking, a disassembler that makes the bytes readable, and a bare-bones runner that proves the whole thing computes the same answers our interpreter did -- every line compiled and tested against Zig 0.16. The calculator now has two back ends behind one shared AST: the tree-walker for simplicity, and this compiler for speed.
But that runner was only a preview -- deliberately thin, with a fixed stack and error handling that is more hopeful than robust. The tree-walker could tell you exactly what went wrong and where; our little loop can barely tell you it fell over. Turning this preview into a proper virtual machine -- one you can single-step, whose stack you can watch grow and shrink, that disassembles each instruction as it executes it and reports errors with precision -- is where this mini project heads next. We have the bytes; now we teach a machine to run them, out loud and under a microscope. Bedankt en tot de volgende keer! ;-)
@scipio