enum(u8), and why the stack model makes the compiler almost embarrassingly simple;ArrayList;2 + 3 becomes const, const, add without any cleverness;Expr struct with a span and a kind union) and the type checker from episode 134 fresh in mind -- today we stop walking that tree and start compiling it;Learn Zig Series):Last episode I closed with a small promise. Once the type checker knows the type of every expression, I said, you know things the tree could only guess at -- how many bytes a value needs, whether a + is an integer add or a float add -- and that knowledge is precisely the input the next stage needs, because we were about to stop interpreting the tree by walking it and start compiling it down to something lower and faster. "The tree got us to meaning; the next brick turns meaning into something that runs." This is that brick. Today the tree goes flat.
Flat is the operative word. For four episodes we have lived inside a tree -- lexer to tokens, tokens to a tree, a checker over the tree, a folder over the tree. A tree is a wonderful thing to reason about and a genuinely lousy thing to execute fast, and this episode is about swapping the first virtue for the second. We compile the tree ONCE into a compact array of bytes -- bytecode -- that a tiny machine can chew through without ever chasing a pointer again. We will not build that machine today (that is the very next brick), but we will design its language, write the compiler that speaks it, and build the disassembler that lets us read it back. Let's dive right in!
As always, the three exercises first, with complete code. All three build on the type checker from last episode -- the Type enum, the Checker struct with its env, and the checkBinary switch that holds the language's type policy in one place.
Exercise 1 -- A string type and typed concatenation. The task was to add a string variant to Type, teach the checker that a string literal has type string, and make + legal on two strings (producing a string) while "a" + 1 stays a mismatch. The enum grows by exactly one arm, and so does its name helper -- and because I wired the checker to return Type.name() strings in error messages, that one addition also makes string errors print nicely:
const Type = enum {
int,
float,
boolean,
string,
fn name(self: Type) []const u8 {
return switch (self) {
.int => "int",
.float => "float",
.boolean => "boolean",
.string => "string",
};
}
};
Exercise 2 -- Name the two conflicting types in the message. Last episode checkBinary failed with a generic "arithmetic needs two operands of the same numeric type". The task was to report the actual offenders -- something like "cannot combine int and boolean" -- by formatting the two Type.name() strings into an allocated message. That means the checker now needs an allocator, and a mismatch helper that builds the string. Here it is, together with the + rule that accepts two strings but nothing mixed:
fn mismatch(self: *Checker, span: Span, l: Type, r: Type) TypeError {
self.err_span = span;
self.err_msg = try std.fmt.allocPrint(self.alloc, "cannot combine {s} and {s}", .{ l.name(), r.name() });
return error.TypeMismatch;
}
fn checkBinary(self: *Checker, span: Span, op: TokenKind, l: Type, r: Type) TypeError!Type {
switch (op) {
.plus => {
if (l == .string and r == .string) return .string; // typed concatenation
if (l == r and (l == .int or l == .float)) return .int;
return self.mismatch(span, l, r);
},
.minus, .star, .slash => {
if (l == r and (l == .int or l == .float)) return l;
return self.mismatch(span, l, r);
},
else => return self.mismatch(span, l, r),
}
}
The satisfying part is that mismatch returns a TypeError, so at every call site I just return self.mismatch(...) and the error propagates with the message already stashed. Because allocPrint can fail, TypeError had to gain OutOfMemory -- which it already carried from episode 134. The test asserts both that "foo" + "bar" checks to string, and that "foo" + 1 is rejected with a message mentioning both offending type names:
test "string + string checks to string; string + int is a mismatch" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const a = arena.allocator();
const sp = Span{ .line = 1, .col = 1 };
const s1 = try makeExpr(a, sp, .{ .string = "foo" });
const s2 = try makeExpr(a, sp, .{ .string = "bar" });
const cat = try makeExpr(a, sp, .{ .binary = .{ .op = .plus, .lhs = s1, .rhs = s2 } });
var checker = Checker{ .env = std.StringHashMap(Type).init(a), .alloc = a };
defer checker.env.deinit();
try std.testing.expectEqual(Type.string, try checker.checkExpr(cat));
const one = try makeExpr(a, sp, .{ .int = 1 });
const bad = try makeExpr(a, sp, .{ .binary = .{ .op = .plus, .lhs = s1, .rhs = one } });
try std.testing.expectError(error.TypeMismatch, checker.checkExpr(bad));
try std.testing.expect(std.mem.indexOf(u8, checker.err_msg, "string") != null);
try std.testing.expect(std.mem.indexOf(u8, checker.err_msg, "int") != null);
}
Exercise 3 -- Block scoping with a stack of environments. The single flat env from episode 134 meant a name, once defined, stayed defined forever. The task was to give the checker a stack of scopes: push on entering a block, pop on leaving, and look a name up from the innermost scope outward -- so a name introduced inside a block disappears when the block closes. I added a minimal block: []const Stmt statement variant to drive it, and a ScopedChecker that owns the stack:
const ScopedChecker = struct {
scopes: std.ArrayList(std.StringHashMap(Type)),
alloc: std.mem.Allocator,
err_msg: []const u8 = "",
const Err = error{ UndefinedVariable, TypeMismatch, OutOfMemory };
fn pushScope(self: *ScopedChecker) !void {
try self.scopes.append(self.alloc, std.StringHashMap(Type).init(self.alloc));
}
fn popScope(self: *ScopedChecker) void {
var top = self.scopes.pop().?;
top.deinit();
}
fn define(self: *ScopedChecker, nm: []const u8, t: Type) !void {
try self.scopes.items[self.scopes.items.len - 1].put(nm, t);
}
fn lookup(self: *ScopedChecker, nm: []const u8) ?Type {
var i = self.scopes.items.len;
while (i > 0) {
i -= 1;
if (self.scopes.items[i].get(nm)) |t| return t;
}
return null;
}
};
The whole idea lives in lookup: it counts down from the top of the stack, so an inner x shadows an outer x, and once the block's scope is popped its names are simply gone. The test builds a program that defines inside within a block and then uses it after the block, and asserts the use is caught as undefined:
test "a name bound inside a block is invisible after it closes" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const a = arena.allocator();
const sp = Span{ .line = 1, .col = 1 };
const inner_val = try makeExpr(a, sp, .{ .int = 1 });
const use_after = try makeExpr(a, sp, .{ .ident = "inside" });
const block_body = [_]Stmt{
.{ .let = .{ .name = "inside", .value = inner_val, .span = sp } },
};
const program = [_]Stmt{
.{ .block = &block_body },
.{ .expr = use_after },
};
var sc = ScopedChecker{ .scopes = .empty, .alloc = a };
try sc.pushScope(); // global scope
try std.testing.expectError(error.UndefinedVariable, sc.checkStmts(&program));
}
A stack of hash maps is exactly how real compilers model lexical scope -- every language with { } blocks does some version of this. Nota bene: notice scopes is initialised with .empty and every append takes the allocator explicitly. That is the modern unmanaged ArrayList, and it is the same collection we lean on for the rest of this episode, so keep the shape in mind.
Here is the honest question a good student asks: the tree-walker works. Episode 133 walks it, 134 checks it, and we could bolt an evaluator onto the same visitor and be done. Why complicate life with a whole new representation?
Speed, and the reason is architecture, not micro-optimisation. A tree is a cloud of little heap nodes connected by pointers. To evaluate 2 + 3 * 4, the interpreter visits the + node, follows a pointer to the left child, follows another to the right, which is a * node, follows two more pointers to its children -- and every one of those pointer hops is a potential cache miss, a jump to some unrelated address the CPU could not predict. Worse, you pay that cost every single time the expression runs. A loop that runs a body a million times re-walks the same tree a million times, re-dispatching on each node's tag over and over. We talked about cache behaviour and branch prediction back in episode 34, and a tree is close to the worst-case shape for both.
Bytecode fixes this by separating compile time from run time. You walk the tree once, up front, and flatten it into a contiguous array of bytes laid out in execution order. Then the machine runs that array in a tight loop: fetch a byte, decode which operation it is, do it, advance. The instructions sit next to each other in memory (cache-friendly), the dispatch is one predictable switch, and the expensive tree-walking happened exactly once. This compile-once-run-many split is why CPython, the JVM, Lua, Ruby, C#, WebAssembly and countless others all compile to bytecode rather than interpret an AST directly. Having said that, we are not chasing raw metal today -- we are designing the language that flat machine will speak.
Before a single byte, a design decision: what does an instruction operate on? The simplest, most classic answer is a stack machine. There are no registers to name and no addresses to juggle -- instructions push values onto an operand stack and pop them off. add means "pop two, push their sum". A literal means "push this value". That is the entire mental model, and it makes the compiler almost trivially simple, as you will see in a moment.
Our values are the same three the checker knew about, wrapped in a tagged union so the stack can hold any of them:
const Value = union(enum) {
int: i64,
float: f64,
boolean: bool,
};
And the instruction set itself is an enum(u8) -- one byte per opcode, which is where the byte in bytecode comes from. Each variant is a verb the machine will understand. Most take no operand (they just act on the stack); constant is special -- it carries a one-byte index into a side table of literals:
const OpCode = enum(u8) {
constant,
add,
sub,
mul,
div,
negate,
not,
less,
less_equal,
greater,
greater_equal,
equal,
not_equal,
op_and,
op_or,
push_true,
push_false,
ret,
};
Two design choices worth calling out. First, why not store the literal 2 directly in the instruction stream? Because values can be big (an f64 is eight bytes) and repeated, so we keep the code stream lean -- one byte of opcode, one byte of index -- and park the actual values in a constant pool. constant 0 means "push whatever lives at slot 0 of the pool". Second, push_true and push_false are their own opcodes rather than constants, because booleans are so common that giving them a dedicated one-byte instruction (no pool lookup at all) is a cheap, classic win -- CPython and the JVM both do exactly this with their LOAD_CONST-versus-dedicated-ICONST style split. The _ suffix dance (op_and, op_or) is just because and/or are Zig keywords -- a small naming tax, nothing deeper.
An opcode enum on its own is not runnable. It needs to live in a container that also holds the constant pool it references and -- for good error messages later -- the source line each byte came from. That container is universally called a chunk, and ours is a struct wrapping three unmanaged ArrayLists:
const Chunk = struct {
alloc: std.mem.Allocator,
code: std.ArrayList(u8) = .empty,
constants: std.ArrayList(Value) = .empty,
lines: std.ArrayList(usize) = .empty,
fn deinit(self: *Chunk) void {
self.code.deinit(self.alloc);
self.constants.deinit(self.alloc);
self.lines.deinit(self.alloc);
}
fn writeByte(self: *Chunk, byte: u8, line: usize) !void {
try self.code.append(self.alloc, byte);
try self.lines.append(self.alloc, line);
}
fn writeOp(self: *Chunk, op: OpCode, line: usize) !void {
try self.writeByte(@intFromEnum(op), line);
}
fn addConstant(self: *Chunk, v: Value) !u8 {
const idx = self.constants.items.len;
try self.constants.append(self.alloc, v);
return @intCast(idx);
}
};
Three small deliberate things here. writeOp is a thin wrapper over writeByte that does the @intFromEnum conversion, so the compiler never has to think about the fact that an opcode is "really" a byte -- it writes OpCode values and the chunk handles the encoding. lines grows in lockstep with code: one line number per byte. That is wasteful (a run-length encoding would be tighter, and I leave that as an exercise) but it is dead simple and means that given any code offset, we can name the source line instantly -- the same span-carrying discipline we started in episode 133, carried one layer deeper. And addConstant returns the u8 index it just wrote to, which is exactly the operand the constant opcode needs. Storing the allocator in the chunk keeps every call site clean: chunk.writeOp(.add, line) reads like a verb, not a memory-management chore.
Now the payoff, and it is beautiful how little code it takes. The compiler walks the AST exactly like the checker did -- one recursive function, one switch over the node kind -- but instead of returning a type it emits bytes. And the stack model makes the emission order almost write itself: to compute a binary operation, you emit the code for the left operand, then the right operand, then the operator. Post-order. The operands leave their results on the stack; the operator pops them:
const Compiler = struct {
chunk: *Chunk,
const Err = error{ UnsupportedExpr, BadOperator, OutOfMemory };
fn emitConstant(self: *Compiler, v: Value, line: usize) !void {
const idx = try self.chunk.addConstant(v);
try self.chunk.writeOp(.constant, line);
try self.chunk.writeByte(idx, line);
}
fn compileExpr(self: *Compiler, e: *const Expr) Err!void {
switch (e.kind) {
.int => |v| try self.emitConstant(.{ .int = v }, e.span.line),
.float => |v| try self.emitConstant(.{ .float = v }, e.span.line),
.boolean => |b| try self.chunk.writeOp(if (b) .push_true else .push_false, e.span.line),
.string, .ident => return error.UnsupportedExpr,
.unary => |u| {
try self.compileExpr(u.rhs);
const op: OpCode = switch (u.op) {
.minus => .negate,
.bang => .not,
else => return error.BadOperator,
};
try self.chunk.writeOp(op, e.span.line);
},
.binary => |b| {
try self.compileExpr(b.lhs);
try self.compileExpr(b.rhs);
try self.chunk.writeOp(binaryOp(b.op) orelse return error.BadOperator, e.span.line);
},
}
}
};
Read the .binary arm slowly, because it is the whole trick. compileExpr(b.lhs) recursively emits everything needed to leave the left value on the stack. Then compileExpr(b.rhs) does the same for the right. Then one opcode for the operator, which at run time will pop both and push the result. For 2 + 3 * 4, the recursion naturally emits const 2, then descends into 3 * 4 to emit const 3, const 4, mul, then add -- and the operator precedence we fought for in the parser (episode 132) is now baked into the order of the bytes. The tree's shape became the stream's order. That is not a coincidence you have to engineer; it falls out of post-order traversal for free.
The operator mapping lives in its own little function, the same "all the policy in one place" move I keep making, so adding an opcode is a one-line edit:
fn binaryOp(op: TokenKind) ?OpCode {
return switch (op) {
.plus => .add,
.minus => .sub,
.star => .mul,
.slash => .div,
.lt => .less,
.lte => .less_equal,
.gt => .greater,
.gte => .greater_equal,
.eq => .equal,
.neq => .not_equal,
.kw_and => .op_and,
.kw_or => .op_or,
else => null,
};
}
Notice .string and .ident return error.UnsupportedExpr for now. Strings need heap-managed objects and identifiers need a notion of variable storage the flat machine does not have yet -- both are jobs for later bricks in this arc. Refusing them loudly, in stead of silently emitting garbage, is the honest Zig thing to do: an unfinished feature should be a compile error you can see, not a mystery at run time.
Here is a hard truth about bytecode: the moment you have it, you cannot read it. 04 00 04 01 01 means nothing to human eyes. So the very first tool you build alongside any bytecode compiler is a disassembler -- the exact inverse of the assembler's disassembler from episode 61 -- that turns the bytes back into named mnemonics. You will use it constantly to debug the compiler, and again next episode to debug the machine. Skipping it is the classic beginner mistake; writing it first is the mark of someone who has done this before.
The disassembler walks the code array, and here is the subtle bit that teaches you how the stream is really structured: it advances by a variable amount. A plain opcode is one byte, so we step by one. But constant is followed by its index byte, so we step by two. The decode loop has to know each instruction's width -- which is precisely what the machine will need to know too:
fn appendLine(out: *std.ArrayList(u8), a: std.mem.Allocator, comptime fmt: []const u8, args: anytype) !void {
const s = try std.fmt.allocPrint(a, fmt, args);
defer a.free(s);
try out.appendSlice(a, s);
}
fn disassembleInstruction(chunk: *const Chunk, offset: usize, out: *std.ArrayList(u8), a: std.mem.Allocator) !usize {
const op: OpCode = @enumFromInt(chunk.code.items[offset]);
switch (op) {
.constant => {
const idx = chunk.code.items[offset + 1];
try appendLine(out, a, "{d:0>4} {s:<14} {d}\n", .{ offset, @tagName(op), idx });
return offset + 2;
},
else => {
try appendLine(out, a, "{d:0>4} {s}\n", .{ offset, @tagName(op) });
return offset + 1;
},
}
}
fn disassemble(chunk: *const Chunk, a: std.mem.Allocator) ![]u8 {
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(a);
var offset: usize = 0;
while (offset < chunk.code.items.len) {
offset = try disassembleInstruction(chunk, offset, &out, a);
}
return out.toOwnedSlice(a);
}
The lovely part is @tagName(op), from episode 32's reflection toolkit: it hands us the string "constant" or "negate" straight from the enum, so we never maintain a parallel table of names that can drift out of sync with the opcodes. The disassembleInstruction function returns the next offset, and the outer loop just keeps assigning that back -- so the loop itself contains zero knowledge of instruction widths, all of which lives in the one switch. Compiling -5 and disassembling it prints constant 0, then negate, then ret: the flat, honest truth of what the machine will do, in the order it will do it.
I picked a stack machine, and it is worth a paragraph on the alternative because it is a real fork in the road. The other main design is a register-based bytecode, where instructions name their operands: add r3, r1, r2 means "add registers 1 and 2, store in register 3". Lua famously switched to a register VM in version 5.0 and got a nice speedup, because register code needs fewer instructions -- no separate push/pop churn -- which means fewer trips around the dispatch loop.
So why did I choose the stack? Because the compiler is dramatically simpler. Look again at our compileExpr: it never allocates a register, never tracks which ones are free, never spills anything to memory. Post-order emission and an implicit stack do all the bookkeeping. A register compiler has to solve register allocation, which is a genuinely hard problem (a whole later brick in this arc, in fact). For learning -- and for plenty of production runtimes, CPython and the JVM among them -- the stack machine's simplicity wins. You reach for registers when you have profiled and know the dispatch overhead is your bottleneck, not before. Premature register allocation is a fine way to spend a week and learn nothing.
Bytecode is wonderfully testable precisely because it is data, not behaviour. You do not need to run anything to check the compiler -- you compile an expression and assert the exact byte sequence it produced. This is the tightest possible feedback loop, and it catches emission-order bugs the instant they appear:
test "compiling 2 + 3 emits const, const, add with a filled constant pool" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const a = arena.allocator();
const sp = Span{ .line = 1, .col = 1 };
const two = try makeExpr(a, sp, .{ .int = 2 });
const three = try makeExpr(a, sp, .{ .int = 3 });
const sum = try makeExpr(a, sp, .{ .binary = .{ .op = .plus, .lhs = two, .rhs = three } });
var chunk = Chunk{ .alloc = a };
defer chunk.deinit();
var compiler = Compiler{ .chunk = &chunk };
try compiler.compileExpr(sum);
try chunk.writeOp(.ret, sp.line);
const expected = [_]u8{
@intFromEnum(OpCode.constant), 0,
@intFromEnum(OpCode.constant), 1,
@intFromEnum(OpCode.add),
@intFromEnum(OpCode.ret),
};
try std.testing.expectEqualSlices(u8, &expected, chunk.code.items);
try std.testing.expectEqual(@as(usize, 2), chunk.constants.items.len);
try std.testing.expectEqual(@as(i64, 2), chunk.constants.items[0].int);
try std.testing.expectEqual(@as(i64, 3), chunk.constants.items[1].int);
}
That expectEqualSlices is asserting on the literal bytes -- constant, index 0, constant, index 1, add, ret -- and on the constant pool holding 2 and 3 at exactly those slots. If a future refactor accidentally emits the right operand before the left, this test screams immediately. The second test aims at the disassembler, checking the human-readable output is actually human-readable:
test "disassembly is human readable" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const a = arena.allocator();
const sp = Span{ .line = 1, .col = 1 };
const five = try makeExpr(a, sp, .{ .int = 5 });
const neg = try makeExpr(a, sp, .{ .unary = .{ .op = .minus, .rhs = five } });
var chunk = Chunk{ .alloc = a };
defer chunk.deinit();
var compiler = Compiler{ .chunk = &chunk };
try compiler.compileExpr(neg);
try chunk.writeOp(.ret, sp.line);
const text = try disassemble(&chunk, a);
defer a.free(text);
try std.testing.expect(std.mem.indexOf(u8, text, "constant") != null);
try std.testing.expect(std.mem.indexOf(u8, text, "negate") != null);
try std.testing.expect(std.mem.indexOf(u8, text, "ret") != null);
}
Between these two -- assert the bytes, assert the disassembly -- you have a compiler you can trust before you have written a single line of the machine that runs it. That is the whole reason we build the disassembler first: it makes the invisible visible.
None of this is a toy dialect of how real runtimes work -- it is the same idea with a bigger opcode table. In CPython, your .py file is compiled to exactly this: a code object holding a co_code bytes blob and a co_consts constant tuple, and you can literally see it by running import dis; dis.dis(func) -- the output is a disassembly listing that looks strikingly like ours, LOAD_CONST, BINARY_ADD and friends. The JVM compiles Java to .class files full of stack-machine bytecode (iconst, iadd, invokevirtual), which is why the same .jar runs on any platform with a JVM -- the bytecode is the portable layer. Lua compiles to a register bytecode, the road not taken above. WebAssembly is, at heart, a standardized stack-machine bytecode for the web. And Rust? rustc lowers your code through MIR (a control-flow-graph IR, closer in spirit to the register world) before machine code -- a reminder that "bytecode" is one point on a whole spectrum of intermediate representations, all serving the same goal: a form that is easier to optimise and execute than a syntax tree.
The vocabulary is shared too. "Constant pool", "opcode", "operand stack", "disassembly" -- these are the exact words the CPython and JVM source use. What you built today is the small, honest heart of the thing every one of these runtimes stands on.
Take stock of what we have. A Value union for the things the machine pushes around. An OpCode enum -- a one-byte instruction set for a stack machine. A Chunk that holds the code bytes, a constant pool, and per-byte line info. A Compiler that walks the ep133 tree bottom-up and flattens it into that chunk, turning operator precedence into byte order for free. And a disassembler that reads the whole thing back so you are never staring at raw hex. The tree has become a flat, linear, cache-friendly program.
But it does not run yet. We have written the machine's language and not the machine. Everything today produced bytes and asserted on bytes; nothing pushed a value or popped one or computed 2 + 3 to actually get 5. That is the missing half, and it is the next brick: a small loop that holds an operand stack, fetches one opcode at a time, and does what each one says -- constant pushes, add pops two and pushes their sum, ret hands back the answer on top of the stack. The disassembler you built today will be the flashlight you debug it with. Build the compiler, feed it a handful of expressions, disassemble the output until the bytes read exactly the way you expect -- and you will be holding a program that is finally ready to execute. ;-)
Add a modulo opcode end to end. Introduce a mod variant to OpCode, map the % token (add a .percent TokenKind if you need it) to it in binaryOp, and confirm that compiling 7 % 3 emits constant, constant, mod. Write a test asserting the exact byte sequence, and a second test asserting the disassembly contains "mod". You are wiring one operation through all three layers (opcode, compiler, disassembler) -- the same path every future instruction takes.
Deduplicate the constant pool. Right now compiling 2 + 2 stores the value 2 twice. Change addConstant so that before appending, it scans the existing pool for an equal Value and returns that index instead. Write a test that compiles 2 + 2 and asserts chunk.constants.items.len == 1 while the code still emits two constant 0 instructions. Think about which Value variants can be compared with == and which (floats!) deserve a wary eye.
Compute the stack effect of a chunk. Every opcode has a net effect on the operand stack depth: constant and push_true add one (+1), add/sub/mul/div remove two and add one (-1), negate and not leave depth unchanged (0), ret needs one already there. Write a function that walks a chunk and returns the maximum stack depth it ever reaches -- the exact number of slots the machine will need to pre-allocate. Test it against the compiled form of 2 + 3 * 4 (which should peak at depth 3). This number is not busywork -- it is precisely what the next brick uses to size its stack.
Bedankt en tot de volgende keer -- the tree is flat, the bytes are written, and next time we finally make them run! ;-)
@scipio