Learn Zig Series (#136) - Stack-Based Virtual Machine

What will I learn?

What a virtual machine actually is once the mystique is stripped away -- a loop, an instruction pointer, and a stack -- and why "virtual" just means "in software instead of silicon";
How to model an operand stack on Zig's unmanaged ArrayList and how push/pop become the two verbs the whole machine is built from;
How the fetch-decode-dispatch loop works -- read one opcode, switch on it, do the thing, advance the instruction pointer -- and why this three-line shape is the beating heart of CPython, the JVM, and Lua alike;
How arithmetic opcodes pop two and push one, so the byte order we compiled in the last episode makes 2 + 3 * 4 evaluate to 14 with no cleverness at all;
How Zig's error unions turn stack underflow, type mismatches and division-by-zero into honest, recoverable failures instead of undefined behaviour or a crash;
How to test a VM the same way you test a pure function -- feed it a chunk, assert on the value that comes back;
Where the real performance of an interpreter lives (dispatch, not arithmetic) and what direct threading and computed gotos buy the runtimes that need them;
Three exercises that grow the machine toward variables, printing, and the control flow a real language needs.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
The Chunk, OpCode, Value and Compiler from episode 135 fresh in mind -- today we finally write the machine that runs what that compiler emits;
Tagged unions from episode 6, allocators from episode 7, error handling from episode 4, and the disassembler instinct we sharpened in episode 61 and again in 135;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#136) - Stack-Based Virtual Machine

Last episode I left you holding a program that could not run. We compiled the AST down to a flat array of bytes, built a disassembler so we could read those bytes back, and asserted on the exact sequence constant, constant, add -- but nothing ever executed. "We have written the machine's language and not the machine," I said. Today we build the machine. By the end of this post, 2 + 3 * 4 will not just compile to the right bytes -- it will actually evaluate, on our own little processor written in Zig, to the integer 14.

And here is the part that always delights students the first time they see it: the machine is small. A virtual machine sounds like a big, mysterious thing (the word conjures VMware and QEMU and whole operating systems), but the VM at the heart of CPython or the JVM is, stripped to its bones, three things -- an instruction pointer that says which byte we are looking at, an operand stack that holds intermediate values, and a loop that fetches one opcode, decides what it means, and does it. That is the entire idea. "Virtual" just means the processor is made of software instead of silicon. Once you have built one, the CPU in your laptop stops being magic and starts looking like exactly this loop, only carved into transistors. Here we go!

Solutions to Episode 135 Exercises

Three exercises last time, all pushing the bytecode design toward something executable. Full code for each, as always.

Exercise 1 -- Add a modulo opcode end to end. The task was to wire one new operation through all three layers we built: a mod variant on OpCode, a mapping from the % token in binaryOp, and confirmation that 7 % 3 compiles to constant, constant, mod. The opcode enum grows by one arm (I slot it in with its arithmetic siblings so the table stays legible), and binaryOp grows by one line. This is the whole point of putting all the operator policy in one function -- a new operator is a one-line edit:

const OpCode = enum(u8) {
    constant,
    add,
    sub,
    mul,
    div,
    mod,
    negate,
    not,
    ret,
};

fn binaryOp(op: u8) ?OpCode {
    return switch (op) {
        '+' => .add,
        '-' => .sub,
        '*' => .mul,
        '/' => .div,
        '%' => .mod,
        else => null,
    };
}

test "7 % 3 compiles to constant, constant, mod" {
    // The compiler emits: const(7), const(3), mod -- post-order, operator last.
    const code = [_]u8{
        @intFromEnum(OpCode.constant), 0,
        @intFromEnum(OpCode.constant), 1,
        @intFromEnum(OpCode.mod),
    };
    try std.testing.expectEqual(OpCode.mod, @as(OpCode, @enumFromInt(code[4])));
    try std.testing.expectEqual(binaryOp('%').?, OpCode.mod);
}

Note I model the token as a plain u8 character here so the solution is self-contained and compiles on its own -- in the real language binaryOp takes a TokenKind, and you would add a .percent variant to the lexer first. The lesson is unchanged: an instruction is only "real" once it exists in the opcode table, the compiler knows how to emit it, and the disassembler knows how to name it. Miss any one layer and you get bytes the machine cannot read.

Exercise 2 -- Deduplicate the constant pool. Compiling 2 + 2 stored the value 2 twice, wasting a pool slot on every repeated literal. The fix lives entirely inside addConstant: before appending, scan the existing pool for an equal value and return that index instead. Because our Value is a tagged union, "equal" needs a small helper that compares tag-then-payload -- you cannot just == two unions whose active fields might differ:

const Value = union(enum) {
    int: i64,
    float: f64,
    boolean: bool,
};

fn valueEql(a: Value, b: Value) bool {
    return switch (a) {
        .int => |x| b == .int and b.int == x,
        .float => |x| b == .float and b.float == x,
        .boolean => |x| b == .boolean and b.boolean == x,
    };
}

fn addConstant(constants: *std.ArrayList(Value), alloc: std.mem.Allocator, v: Value) !u8 {
    for (constants.items, 0..) |existing, i| {
        if (valueEql(existing, v)) return @intCast(i);
    }
    const idx = constants.items.len;
    try constants.append(alloc, v);
    return @intCast(idx);
}

test "2 + 2 stores the constant only once" {
    var constants: std.ArrayList(Value) = .empty;
    defer constants.deinit(std.testing.allocator);
    const a = std.testing.allocator;

    const idx_a = try addConstant(&constants, a, .{ .int = 2 });
    const idx_b = try addConstant(&constants, a, .{ .int = 2 });
    try std.testing.expectEqual(idx_a, idx_b); // same slot both times
    try std.testing.expectEqual(@as(usize, 1), constants.items.len);
}

The satisfying result: both constant instructions in 2 + 2 now carry index 0, and the pool holds a single 2. One wary note I flagged last episode -- floats. Comparing f64 with == is exact, so 0.1 + 0.2 will not dedupe against a literal 0.3, and a stored NaN never equals itself. For a constant pool that is fine (we only ever dedupe identical literals from the source), but it is a reflex worth keeping: float equality is a trap in any other context.

Exercise 3 -- Compute the maximum stack depth of a chunk. Every opcode has a net stack effect: constant pushes one value (+1), a binary op pops two and pushes one (-1 net), negate leaves the depth unchanged (0). Walking the chunk and tracking the running depth tells you the peak -- which is exactly how many slots the machine must pre-allocate so it never has to grow the stack mid-run. The one subtlety is that the walk must respect instruction widths: constant is two bytes, everything else is one:

fn stackEffect(op: OpCode) i32 {
    return switch (op) {
        .constant => 1,
        .add, .sub, .mul, .div, .mod => -1,
        .negate, .not => 0,
        .ret => -1,
    };
}

fn maxStackDepth(code: []const u8) i32 {
    var depth: i32 = 0;
    var max: i32 = 0;
    var offset: usize = 0;
    while (offset < code.len) {
        const op: OpCode = @enumFromInt(code[offset]);
        depth += stackEffect(op);
        if (depth > max) max = depth;
        offset += if (op == .constant) 2 else 1;
    }
    return max;
}

test "2 + 3 * 4 peaks at depth 3" {
    // const 2, const 3, const 4, mul, add
    const code = [_]u8{
        @intFromEnum(OpCode.constant), 0,
        @intFromEnum(OpCode.constant), 1,
        @intFromEnum(OpCode.constant), 2,
        @intFromEnum(OpCode.mul),
        @intFromEnum(OpCode.add),
    };
    try std.testing.expectEqual(@as(i32, 3), maxStackDepth(&code));
}

Trace it by hand: three constants drive the depth up to 3, then mul drops it to 2, then add to 1. Peak = 3. That number is not busywork -- it is precisely the stack size the VM we are about to write would use if it wanted a fixed, never-reallocating operand stack (a real optimisation many production VMs make). For today I will keep our stack dynamic on an ArrayList, but keep this exercise in the back of your mind: you already know how to size the stack exactly.

The machine, in one paragraph

Let me describe the whole VM before a single line of code, because the shape is that simple. It owns a pointer to the Chunk it is running, an instruction pointer (ip) -- an index into chunk.code marking the next byte to fetch -- and an operand stack of Values. It runs one loop. Each turn: read the byte at ip, advance ip past it, switch on which opcode that byte names, and carry out the action -- which almost always means popping some values off the stack and pushing a result back. When it hits ret, it pops the final value and hands it back as the answer. Fetch, decode, dispatch, repeat. Everything else is filling in the arms of that switch.

Push and pop: the two verbs

The operand stack is the machine's scratchpad, and I model it on the unmanaged ArrayList we have leaned on all arc long. Two helpers -- push and pop -- are the only ways anything touches it, and both are honest about failure. Pushing can fail if allocation fails; popping can fail if the stack is empty, which would mean the bytecode is malformed. Zig's error unions make both of these visible at every call site instead of silent:

const std = @import("std");

const InterpretError = error{
    StackUnderflow,
    TypeMismatch,
    DivisionByZero,
    OutOfMemory,
};

const VM = struct {
    chunk: *const Chunk,
    ip: usize = 0,
    stack: std.ArrayList(Value) = .empty,
    alloc: std.mem.Allocator,

    fn deinit(self: *VM) void {
        self.stack.deinit(self.alloc);
    }

    fn push(self: *VM, v: Value) !void {
        try self.stack.append(self.alloc, v);
    }

    fn pop(self: *VM) InterpretError!Value {
        return self.stack.pop() orelse error.StackUnderflow;
    }

    fn readByte(self: *VM) u8 {
        const b = self.chunk.code.items[self.ip];
        self.ip += 1;
        return b;
    }
};

Look at pop. In modern Zig the unmanaged ArrayList.pop() returns an optional -- ?Value -- because popping an empty list has no sensible answer. Rather than .? it (which would panic on a bad program, exactly the kind of crash a VM must never inflict on its host), I turn null into error.StackUnderflow. Now a corrupt or hand-crafted-malicious chunk produces a clean, catchable error, not a segfault. That distinction -- the guest program misbehaving must never take down the host -- is the whole reason interpreters exist instead of just running raw machine code, and Zig lets us honour it without a garbage collector or a single hidden allocation. readByte is the other primitive: grab the byte under ip, step ip forward, done. Every fetch in the machine goes through it.

The fetch-decode-dispatch loop

Here is the core, the loop that is the machine. It reads an opcode, switches on it, and each arm does its small job. I have kept the arithmetic in a helper (next section) so the loop itself reads like a table of contents for the instruction set:

fn run(self: *VM) InterpretError!Value {
    while (true) {
        const op: OpCode = @enumFromInt(self.readByte());
        switch (op) {
            .constant => {
                const idx = self.readByte();
                try self.push(self.chunk.constants.items[idx]);
            },
            .add, .sub, .mul, .div, .mod => try self.binaryNumeric(op),
            .negate => {
                const v = try self.pop();
                switch (v) {
                    .int => |n| try self.push(.{ .int = -n }),
                    .float => |f| try self.push(.{ .float = -f }),
                    .boolean => return error.TypeMismatch,
                }
            },
            .not => {
                const v = try self.pop();
                if (v != .boolean) return error.TypeMismatch;
                try self.push(.{ .boolean = !v.boolean });
            },
            .ret => return self.pop(),
        }
    }
}

Read the .constant arm closely, because it shows the variable-width decoding we designed the disassembler around last episode. A constant opcode is two bytes: the opcode itself, then a one-byte index. So after reading the opcode we call readByte again to grab the index, look that slot up in the constant pool, and push the value. Every other opcode here is a single byte -- readByte returned the opcode and the loop is already positioned at the next instruction. The ip bookkeeping that the disassembler did by returning the next offset, the machine does by mutating ip as it fetches. Same knowledge, two shapes.

The .negate arm is a nice miniature of the whole philosophy: pop a value, and if it is an integer negate the integer, if a float negate the float, and if a boolean -- refuse, loudly, with error.TypeMismatch. There is no -true in a sane language, and rather than silently produce nonsense (C would happily give you -1 here), we make it a catchable runtime error. Having said that, in a real language most of these type errors would already be caught at compile time by the checker from episode 134 -- the runtime check is a belt-and-braces backstop for bytecode that arrived from who-knows-where.

Arithmetic: pop two, push one

Now the helper the loop delegated to. Every binary arithmetic op has the identical shape -- pop the right operand, pop the left (note the order! the left was pushed first, so it is deeper in the stack and comes off second), compute, push the result. The only branching is on the value types and the operator:

fn binaryNumeric(self: *VM, op: OpCode) InterpretError!void {
    const b = try self.pop();
    const a = try self.pop();

    if (a == .int and b == .int) {
        const x = a.int;
        const y = b.int;
        const r: i64 = switch (op) {
            .add => x + y,
            .sub => x - y,
            .mul => x * y,
            .div => if (y == 0) return error.DivisionByZero else @divTrunc(x, y),
            .mod => if (y == 0) return error.DivisionByZero else @rem(x, y),
            else => unreachable,
        };
        try self.push(.{ .int = r });
    } else if (a == .float and b == .float) {
        const x = a.float;
        const y = b.float;
        const r: f64 = switch (op) {
            .add => x + y,
            .sub => x - y,
            .mul => x * y,
            .div => x / y,
            .mod => @rem(x, y),
            else => unreachable,
        };
        try self.push(.{ .float = r });
    } else {
        return error.TypeMismatch;
    }
}

The pop order is the single most common bug in a hand-written VM, so let me hammer it. To compile 10 - 3 the compiler emitted const 10, const 3, sub. At the moment sub runs, the stack (bottom to top) is [10, 3]. Pop once and you get 3 -- that is b, the right operand. Pop again and you get 10 -- that is a, the left. So x - y is 10 - 3 = 7, correct. Swap the two pops and you would compute 3 - 10 = -7 and every non-commutative operation in your language would be silently backwards. This is why the byte-order tests from last episode matter so much: they pin down the exact sequence the machine relies on here.

Two Zig-specific niceties. @divTrunc and @rem are the explicit builtins for integer division and remainder -- Zig refuses to guess whether you want truncating or flooring division (a genuine ambiguity for negative numbers that C leaves implementation-defined), so it makes you name which one, and I pick truncation to match C and most languages. And the division-by-zero guard returns error.DivisionByZero rather than letting the CPU trap -- again, a guest program dividing by zero should be a catchable error in the host, never a hardware fault that kills the process.

Running it, end to end

Everything is in place. Let me tie the whole pipeline together the way you actually use it: hand-build the chunk for 2 + 3 * 4 (in a real program the compiler from episode 135 does this for you), run the machine, and check the answer:

fn interpret(chunk: *const Chunk, alloc: std.mem.Allocator) InterpretError!Value {
    var vm = VM{ .chunk = chunk, .alloc = alloc };
    defer vm.deinit();
    return vm.run();
}

test "2 + 3 * 4 evaluates to 14 on the VM" {
    const a = std.testing.allocator;

    var chunk = Chunk{ .alloc = a };
    defer chunk.deinit();

    // Constant pool: [2, 3, 4]
    const c2 = try chunk.addConstant(.{ .int = 2 });
    const c3 = try chunk.addConstant(.{ .int = 3 });
    const c4 = try chunk.addConstant(.{ .int = 4 });

    // Emit: const 2, const 3, const 4, mul, add, ret
    try chunk.writeOp(.constant, 1);
    try chunk.writeByte(c2, 1);
    try chunk.writeOp(.constant, 1);
    try chunk.writeByte(c3, 1);
    try chunk.writeOp(.constant, 1);
    try chunk.writeByte(c4, 1);
    try chunk.writeOp(.mul, 1);
    try chunk.writeOp(.add, 1);
    try chunk.writeOp(.ret, 1);

    const result = try interpret(&chunk, a);
    try std.testing.expectEqual(@as(i64, 14), result.int);
}

Run zig test on the file and it goes green. Trace the machine one turn at a time and marvel at how the arithmetic just falls out of the byte order: push 2, push 3, push 4 (stack [2, 3, 4]), mul pops 3 and 4 and pushes 12 (stack [2, 12]), add pops 2 and 12 and pushes 14 (stack [14]), ret pops and returns 14. The operator precedence we fought for in the parser back in episode 132, then baked into byte order in episode 135, now expresses itself as the order values arrive on the stack. Nobody in the VM knows or cares that * binds tighter than + -- the compiler already encoded that truth into the bytes, and the machine just obeys. That separation of concerns is the deep beauty of the bytecode approach.

Testing a VM is testing a pure function

Notice what that test did NOT need: no files, no network, no clock, no global state. A chunk goes in, a Value comes out, and you assert on it. A stack VM is, from the outside, a pure function from bytecode to result -- which makes it a joy to test exhaustively. You write one tiny test per opcode (negate of 5 gives -5, div by zero gives error.DivisionByZero, sub respects operand order) and one integration test per interesting expression, and you sleep soundly. Error cases are just as easy because they are values too:

test "division by zero is a catchable error, not a crash" {
    const a = std.testing.allocator;
    var chunk = Chunk{ .alloc = a };
    defer chunk.deinit();

    const c10 = try chunk.addConstant(.{ .int = 10 });
    const c0 = try chunk.addConstant(.{ .int = 0 });
    try chunk.writeOp(.constant, 1);
    try chunk.writeByte(c10, 1);
    try chunk.writeOp(.constant, 1);
    try chunk.writeByte(c0, 1);
    try chunk.writeOp(.div, 1);
    try chunk.writeOp(.ret, 1);

    try std.testing.expectError(error.DivisionByZero, interpret(&chunk, a));
}

That test asserts the machine fails gracefully. The guest program did something illegal, and instead of a hardware trap taking down the whole process, we got a clean error.DivisionByZero the host can catch, log, and report with a line number (remember the lines array we carried in the chunk? that is what turns this into "runtime error on line 1"). This is the difference between an interpreter and just eval-ing raw machine code: containment.

Where the speed actually lives

A fair question: is this fast? Faster than the tree-walker from episode 133, meaningfully -- the instructions are contiguous, the dispatch is one predictable switch, and we walked the tree only once at compile time. But if you profile a simple bytecode VM, you will find the arithmetic is not the bottleneck. The bottleneck is dispatch: the cost of that switch at the top of the loop, executed once per instruction, whose target the CPU's branch predictor struggles to guess because the next opcode could be anything.

The classic cure is direct threading (sometimes "computed goto"): instead of one central switch, each opcode's handler ends by jumping directly to the next handler, so the branch predictor sees many separate, more-predictable jumps rather than one chaotic one. GCC and Clang expose this via a labels-as-values extension; Zig does not have computed goto today, but its switch compiles to a jump table that is already quite good, and for a teaching VM (and honestly for a great many production ones) the plain switch is entirely fine. Nota bene: reach for direct threading only after you have measured dispatch as your bottleneck -- as we discussed all the way back in episode 34, guessing at performance is how you spend a week optimising the 2% that never mattered. The bigger wins usually come first from a smarter instruction set (fewer, fatter opcodes) than from a cleverer loop.

How the grown-ups do it

What we built is not a toy imitation of a real VM -- it is the real thing at small scale, and the vocabulary proves it. CPython's evaluation loop is a giant switch (historically a computed-goto in ceval.c) over exactly this kind of opcode, running over a co_code bytes blob with a value stack -- pop the arguments, push the result, precisely our shape. The JVM is defined as a stack machine in its specification: iadd pops two ints and pushes their sum, character for character what our add does. Lua famously runs a register VM instead (the road we chose not to take last episode), trading a more complex compiler for fewer dispatch cycles. And WebAssembly is, at its core, a standardised stack-machine bytecode with a validation pass -- your browser runs a VM shaped like ours millions of times a day.

Compared to writing the same machine in C, the Zig version buys you two things for free: the Value tagged union carries its own tag so you cannot mis-read an int as a float (C's tagless unions are a notorious footgun here), and the error-union return means underflow and divide-by-zero are in the type signature, impossible to forget to handle. Compared to Rust, the shapes are near-identical -- a Vec stack, an enum of opcodes, a match loop, a Result return -- with Zig trading Rust's borrow-checker guarantees for explicit allocators and a smaller language. Compared to Go, you get no garbage collector and no hidden allocations in the hot loop, which for an interpreter's innermost while is exactly where you want the control. Different trade-offs, one architecture -- because there is really only one good architecture for this, and you now know it from the inside.

Where this is heading

Take stock. We have a VM with an instruction pointer and an operand stack, a fetch-decode-dispatch loop, arithmetic that pops two and pushes one, unary negate and not, honest runtime errors for underflow and type-mismatch and divide-by-zero, and a test suite that treats the whole thing as a pure function. Feed it the bytecode our episode-135 compiler emits and it computes real answers. We have, genuinely, a working little processor.

But it can only do arithmetic on values that were literally in the source. It cannot remember anything -- there are no variables, no way to say let x = 5 and use x later -- because that needs storage the flat stack does not yet model, and a way for one piece of code to reach back and grab a value another piece stashed away. Give a stack machine local slots and a way for an inner function to capture an outer variable, and you are suddenly staring at one of the most elegant ideas in all of language implementation -- the thing that makes a function-plus-its-environment into a first-class value you can pass around. That capture problem is the next brick, and it is where our little machine grows the ability to remember. The stack is running; next we teach it to hold on. ;-)

Exercises

Add comparison and boolean opcodes. Give OpCode a less, greater and equal (last episode's design already reserved these), and handle them in run: each pops two values and pushes a boolean. Make equal work across types (an int is never equal to a float of the same magnitude, decide and document your rule), but less/greater only on two numbers of the same type, error.TypeMismatch otherwise. Write a test that compiles and runs 3 < 5 and asserts the result is .boolean = true.
A print opcode with an out-of-band effect. Add a print opcode that pops the top value and appends its textual form to a std.ArrayList(u8) buffer the VM owns (do NOT write to stdout directly -- keeping output in a buffer is what makes it testable). Format each Value variant sensibly (int as a number, boolean as true/false). Write a test that runs const 42, print, ret and asserts the buffer contains "42". This is your first side-effecting instruction, and doing it through a buffer is the pattern every serious VM test suite uses.
Pre-size the stack from maxStackDepth. Combine this episode's VM with exercise 3's maxStackDepth from the solutions above: before running, compute the chunk's peak depth, call try self.stack.ensureTotalCapacity(alloc, @intCast(depth)) once, and then have push use the non-failing appendAssumeCapacity. Prove with a test that a normal expression still evaluates correctly, and reason (in a comment) about why this is safe only because the depth was computed from the exact same bytecode the machine will run. This is a real production technique -- the stack never reallocates mid-run.

Bedankt voor het lezen, en tot de volgende keer -- the language has a machine now, and next time we give it a memory! ;-)

@scipio

Learn Zig Series (#136) - Stack-Based Virtual Machine

Learn Zig Series (#136) - Stack-Based Virtual Machine

What will I learn?

Requirements

Difficulty

Curriculum (of the Learn Zig Series):

Learn Zig Series (#136) - Stack-Based Virtual Machine

Solutions to Episode 135 Exercises

The machine, in one paragraph

Push and pop: the two verbs

The fetch-decode-dispatch loop

Arithmetic: pop two, push one

Running it, end to end

Testing a VM is testing a pure function

Where the speed actually lives

How the grown-ups do it

Where this is heading

Exercises

Curriculum (of the `Learn Zig Series`):