Learn Zig Series (#149) - Mini Project: Calculator - VM with Debugger

scipio(71)
Published in
StemSocial
Words
3951
Reading
18 min
Listen
Play
21d

Learn Zig Series (#149) - Mini Project: Calculator - VM with Debugger

zig.png

Part of a multi-episode project

What will I learn?

  • Why the "bare-bones runner" from last episode was only a preview, and what a proper virtual machine adds on top of it;
  • How to give the VM a bounds-checked value stack with push/pop helpers that turn overflow and underflow into typed errors in stead of silent memory corruption;
  • How to split execution into a single step function -- one instruction per call -- and why that one design choice is what makes a debugger possible at all;
  • How to report a runtime failure with precision: not just what went wrong but where, by remembering the instruction pointer of the faulting opcode;
  • How to write a single-instruction disassembler that both the debugger and the tracer share, so decoding logic lives in exactly one place;
  • How to build a tracer that prints each instruction and the stack it produces, so you can literally watch the stack grow and shrink as the program runs;
  • How to add breakpoints -- freezing the machine mid-flight and inspecting its stack -- with about five lines of code;
  • How all four calculator episodes fit together, and where this whole line of the series is heading next.

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;
  • The Chunk, OpCode and the bare-bones runner from episode 148 -- this episode turns that preview into a real machine;
  • Tagged unions from episode 6, allocators from episode 7, and error unions from episode 4;
  • It also helps to have the stack-machine detour from episodes 135 and 136 fresh in mind;
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#149) - Mini Project: Calculator - VM with Debugger

Last episode I built you a compiler, a disassembler, and then -- with a slightly guilty conscience -- a runner I openly called a sneak preview. It was a fixed array, an instruction pointer, and a while loop, and it computed the right numbers. But I was honest about what it could not do: it could barely tell you it had fallen over, let alone where. The tree-walker of episode 147 could point at the exact node that blew up; our little bytecode loop just crashed into an index and hoped. Today we fix that, and we go further. We turn that preview into a real virtual machine -- one with a bounds-checked stack, precise error reporting, and, best of all, a debugger you can use to watch the machine think, one instruction at a time, the stack breathing in and out beneath it. This is the last stop for the calculator project, so let us finish it properly. Here we go!

The stack, made safe

The preview machine had a stack -- var stack: [256]f64 = undefined; -- and it poked at it with raw index arithmetic. That is fine right up until it is not: a malformed chunk, a hand-written bug in the compiler, an opcode that expects two operands when only one was pushed, and suddenly you are reading or writing stack[sp - 1] with sp at zero. In a language without bounds checks that is a silent corruption; even in Zig it is a panic with a stack trace that points at the VM, not at the reason. So the first thing a grown-up machine does is wrap the stack in two tiny helpers that make every misuse a named error in stead of an accident.

const StepResult = enum { running, done };

const Vm = struct {
    chunk: *const Chunk,
    env: *const std.StringHashMap(f64),
    stack: [256]f64 = undefined,
    sp: usize = 0,
    ip: usize = 0,
    fault_ip: usize = 0,

    fn push(self: *Vm, v: f64) RunError!void {
        if (self.sp >= self.stack.len) return error.StackOverflow;
        self.stack[self.sp] = v;
        self.sp += 1;
    }

    fn pop(self: *Vm) RunError!f64 {
        if (self.sp == 0) return error.StackUnderflow;
        self.sp -= 1;
        return self.stack[self.sp];
    }

The machine is now a proper struct that owns its execution state: the chunk it runs, the env of variable bindings, the value stack, a stack pointer sp, the instruction pointer ip, and one extra field -- fault_ip -- whose entire job is to remember where the machine was standing when something went wrong. We will come back to that one. The push and pop helpers are almost too small to mention, but they are the whole difference between a toy and a tool: push refuses to overflow the 256-slot stack, and pop refuses to underflow it. Two ifs, and every arithmetic operation downstream gets to assume its operands are really there. Note the error set has grown a StackOverflow since last episode -- deep or malformed programs are now a typed failure, not a memory stomp.

const RunError = error{
    StackUnderflow,
    StackOverflow,
    DivisionByZero,
    DomainError, // sqrt of a negative, ln of zero
    UnknownVariable,
};

One step at a time

Here is the design decision that everything else in this episode hangs from. The preview machine ran the whole program inside one while loop; you could not get between two instructions with a crowbar. A debugger, though, is nothing but getting between two instructions -- pausing, peeking, continuing. So we invert the structure: the VM exposes a single step function that executes exactly one instruction and hands control back, reporting whether the machine is still running or has hit ret and is done.

    fn step(self: *Vm) RunError!StepResult {
        const code = self.chunk.code.items;
        self.fault_ip = self.ip; // remember where this instruction started, for errors
        const op: OpCode = @enumFromInt(code[self.ip]);
        self.ip += 1;
        switch (op) {
            .constant => {
                try self.push(self.chunk.constants.items[code[self.ip]]);
                self.ip += 1;
            },
            .get_var => {
                const name = self.chunk.names.items[code[self.ip]];
                self.ip += 1;
                try self.push(self.env.get(name) orelse return error.UnknownVariable);
            },
            .add, .sub, .mul, .div, .mod, .pow => {
                const b = try self.pop();
                const a = try self.pop();
                try self.push(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 => try self.push(-(try self.pop())),
            .call => {
                const id = code[self.ip];
                const argc = code[self.ip + 1];
                self.ip += 2;
                if (self.sp < argc) return error.StackUnderflow;
                self.sp -= argc;
                const result = try applyFn(id, self.stack[self.sp .. self.sp + argc]);
                try self.push(result);
            },
            .ret => return .done,
        }
        return .running;
    }

The very first line of the body -- self.fault_ip = self.ip -- is the quiet hero of the whole episode. Before advancing the instruction pointer, we snapshot where this instruction began. If the opcode faults halfway through (a division by zero, a missing variable), ip has already moved on, but fault_ip still points at the guilty instruction. That single assignment is what lets us say "the error was here" in stead of "the error was somewhere back there, good luck."

Everything else is the same stack machine you already traced by hand last episode, only cleaner: the binary arm pops b then a (order matters -- a was pushed first, so it sits below b), computes, and pushes the result through the same bounds-checked push. The .call arm slices argc values straight off the stack and hands them to applyFn -- the exact same function-table dispatch we wrote in episode 148, unchanged. And ret does not compute anything; it simply reports done, leaving the answer sitting on top of the stack for the caller to collect.

A driver, and the whole thing runs

With step doing the real work, the ordinary "just run it to the end" entry point becomes a three-line loop. This is what you call when you do not want to debug -- production mode, so to speak.

    fn run(self: *Vm) RunError!f64 {
        while (true) {
            switch (try self.step()) {
                .running => {},
                .done => return self.pop(),
            }
        }
    }

Look how thin it is. It steps until step says done, then pops the final value off the stack and returns it. If any instruction along the way returns an error, the try propagates it straight out -- and because pop at the end is itself fallible, even an empty stack at ret (a program that computed nothing) comes back as a clean StackUnderflow rather than a garbage read. The interpreter, the compiler, and now this VM all agree on the same contract: a result is a RunError!f64, and every failure has a name.

Precise errors: where, not just what

Now let us cash in that fault_ip. When run returns an error, the caller knows what failed but not where -- and "your expression divided by zero" is a lot less useful than "your expression divided by zero at the div instruction, offset 4." Because we saved the faulting offset, we can decode that instruction and name it:

    fn faultReport(self: *Vm, a: std.mem.Allocator, err: RunError) ![]u8 {
        const op: OpCode = @enumFromInt(self.chunk.code.items[self.fault_ip]);
        return std.fmt.allocPrint(a, "runtime error: {s} at ip={d} ({s})", .{ @errorName(err), self.fault_ip, @tagName(op) });
    }

Two Zig builtins do the heavy lifting here and neither costs a runtime table. @errorName turns the error value error.DivisionByZero into the string "DivisionByZero"; @tagName turns the opcode enum back into "div". Both are generated by the compiler from types it already knows, so we get human-readable diagnostics for free -- no hand-maintained switch mapping errors or opcodes to strings, no risk of that table drifting out of sync with the enum. A real interpreter would map fault_ip back to a source column too (we kept line info out of the calculator to stay small), but the principle is identical: hold on to where, and your error messages stop being riddles.

Reading the machine as it runs

Last episode's disasm walked the entire chunk and returned one big string. A debugger needs something more surgical: decode one instruction at a given offset, and tell me where the next one starts. So we factor the decoding into a single-instruction version that returns both the printable text and the offset of the following opcode.

const Decoded = struct { text: []const u8, next: usize };

fn disasmAt(chunk: *const Chunk, ip: usize, buf: []u8) error{NoSpaceLeft}!Decoded {
    const code = chunk.code.items;
    const op: OpCode = @enumFromInt(code[ip]);
    return switch (op) {
        .constant => .{
            .text = try std.fmt.bufPrint(buf, "{d:0>4}  CONST   c{d} (= {d})", .{ ip, code[ip + 1], chunk.constants.items[code[ip + 1]] }),
            .next = ip + 2,
        },
        .get_var => .{
            .text = try std.fmt.bufPrint(buf, "{d:0>4}  GETVAR  {s}", .{ ip, chunk.names.items[code[ip + 1]] }),
            .next = ip + 2,
        },
        .call => .{
            .text = try std.fmt.bufPrint(buf, "{d:0>4}  CALL    {s}/{d}", .{ ip, functions[code[ip + 1]].name, code[ip + 2] }),
            .next = ip + 3,
        },
        else => .{
            .text = try std.fmt.bufPrint(buf, "{d:0>4}  {s}", .{ ip, @tagName(op) }),
            .next = ip + 1,
        },
    };
}

The next field encodes each instruction's length: two bytes for constant and get_var, three for call, one for the bare arithmetic opcodes. That is the same length knowledge step needs to advance its own ip, which is a good sign the two are consistent -- decode and execute agree on how big every instruction is. Writing to a caller-provided buf with bufPrint means this does zero allocation; the caller owns the buffer and we just borrow a slice of it. One decoder, reused by the whole-chunk view and the live tracer alike.

The debugger view: watching the stack breathe

This is the part I have been looking forward to. A tracer runs the program like run does, but before letting each instruction fly it prints what that instruction is, and after running it prints the resulting stack. Read a trace top to bottom and you see the exact motion of a stack machine: values pushed on, operators folding pairs back down into one. First a small helper to render the stack as [1, 6] rather than raw floats:

fn appendStack(a: std.mem.Allocator, out: *std.ArrayList(u8), stack: []const f64) !void {
    var buf: [32]u8 = undefined;
    try out.append(a, '[');
    for (stack, 0..) |v, i| {
        if (i != 0) try out.appendSlice(a, ", ");
        try out.appendSlice(a, try std.fmt.bufPrint(&buf, "{d}", .{v}));
    }
    try out.append(a, ']');
}

fn traceRun(vm: *Vm, a: std.mem.Allocator, out: *std.ArrayList(u8)) !f64 {
    var buf: [160]u8 = undefined;
    while (true) {
        const d = try disasmAt(vm.chunk, vm.ip, &buf); // decode the instruction we are about to run
        const line = d.text;
        try out.appendSlice(a, line);
        var pad = line.len;
        while (pad < 26) : (pad += 1) try out.append(a, ' ');
        const res = try vm.step(); // run it
        try out.appendSlice(a, "stack: ");
        try appendStack(a, out, vm.stack[0..vm.sp]);
        try out.append(a, '\n');
        if (res == .done) return vm.pop();
    }
}

The order inside the loop is the whole trick: decode vm.ip first (while it still points at the instruction about to run), then call vm.step(), then read vm.stack[0..vm.sp] to show the effect. Because step mutates ip and sp, doing the decode before and the stack-render after gives you a before/after pairing on one line. The little while (pad < 26) loop just spaces the columns so the output lines up. Feed it our old friend 1 + 2 * 3 and here is what the machine looks like from the inside:

0000  CONST   c0 (= 1)    stack: [1]
0002  CONST   c1 (= 2)    stack: [1, 2]
0004  CONST   c2 (= 3)    stack: [1, 2, 3]
0006  mul                 stack: [1, 6]
0007  add                 stack: [7]
0008  ret                 stack: [7]

That is a stack machine laid bare. Three constants march on -- [1], [1, 2], [1, 2, 3] -- then mul reaches down, folds the top two into 6, and the stack shrinks to [1, 6]; add folds again to [7]; ret leaves the answer standing alone. The first time you see a bug in a bigger program, this trace is where you will spot it: an operator that popped in the wrong order, a constant that never got pushed, a stack that ends with two values when it should end with one. You are no longer guessing what the bytecode did -- you are watching it.

Breakpoints: freezing the machine mid-flight

A tracer shows you everything, which is exactly the wrong amount when a program is long. Often you want to run full speed up to one interesting spot and then start looking. That is a breakpoint, and with step already in hand it is almost embarrassingly short:

    fn runToBreakpoint(self: *Vm, bp: usize) RunError!StepResult {
        while (self.ip != bp) {
            switch (try self.step()) {
                .running => {},
                .done => return .done,
            }
        }
        return .running; // paused at the breakpoint, ip sitting on it
    }

It steps at full speed until ip lands exactly on the offset you asked for, then stops and hands control back with the machine frozen -- stack intact, ip poised on the breakpoint instruction, nothing yet executed at that spot. From there the caller can print vm.stack[0..vm.sp], single-step with vm.step(), drop into traceRun for the interesting stretch, or just call vm.run() to finish. This is the raw material a REPL command like break 6 and continue would sit on top of; the calculator does not ship an interactive front end, but every mechanism one would need is right here in these few functions. Notice we did not add a debugger mode or a pile of flags -- we added one small method, because the machine was built to be steppable from the start. That is the payoff of the "one step at a time" decision back at the top.

Testing the machine and its debugger

As always, the tests are the specification, and here they double as proof that the debugging tools tell the truth. To keep them honest and independent of the parser, I build the chunks by hand -- 1 + 2 * 3 is just six opcodes and three constants -- so the tests exercise the VM in isolation. First, the machine computes the right answer, and a breakpoint really does freeze it with the stack we expect:

test "breakpoint pauses with the expected stack" {
    const a = std.testing.allocator;
    var chunk = try sampleChunk(a); // 1 + 2 * 3
    defer chunk.deinit(a);
    var env = std.StringHashMap(f64).init(a);
    defer env.deinit();

    var vm = Vm{ .chunk = &chunk, .env = &env };
    _ = try vm.runToBreakpoint(6); // MUL sits at offset 6
    try std.testing.expectEqual(@as(usize, 3), vm.sp);
    try std.testing.expectEqual(@as(f64, 1), vm.stack[0]);
    try std.testing.expectEqual(@as(f64, 2), vm.stack[1]);
    try std.testing.expectEqual(@as(f64, 3), vm.stack[2]);
    try std.testing.expect(@abs(7 - try vm.run()) < 1e-9); // then finish
}

Then the two payoffs that this whole episode was about. A bad program reports its fault at the exact instruction, and the tracer produces the precise breathing-stack output we just walked through -- asserted byte for byte, so a wrong opcode or a wrong stack would fail loudly:

test "division by zero reports the exact fault site" {
    const a = std.testing.allocator;
    var chunk = try divZeroChunk(a); // 1 / 0
    defer chunk.deinit(a);
    var env = std.StringHashMap(f64).init(a);
    defer env.deinit();

    var vm = Vm{ .chunk = &chunk, .env = &env };
    try std.testing.expectError(error.DivisionByZero, vm.run());
    const msg = try vm.faultReport(a, error.DivisionByZero);
    defer a.free(msg);
    try std.testing.expectEqualStrings("runtime error: DivisionByZero at ip=4 (div)", msg);
}

test "trace shows the stack growing and shrinking" {
    const a = std.testing.allocator;
    var chunk = try sampleChunk(a);
    defer chunk.deinit(a);
    var env = std.StringHashMap(f64).init(a);
    defer env.deinit();

    var vm = Vm{ .chunk = &chunk, .env = &env };
    var out: std.ArrayList(u8) = .empty;
    defer out.deinit(a);
    try std.testing.expect(@abs(7 - try traceRun(&vm, a, &out)) < 1e-9);
    try std.testing.expectEqualStrings(
        "0000  CONST   c0 (= 1)    stack: [1]\n" ++
            "0002  CONST   c1 (= 2)    stack: [1, 2]\n" ++
            "0004  CONST   c2 (= 3)    stack: [1, 2, 3]\n" ++
            "0006  mul                 stack: [1, 6]\n" ++
            "0007  add                 stack: [7]\n" ++
            "0008  ret                 stack: [7]\n",
        out.items,
    );
}

On my machine zig test runs all of them green against Zig 0.16. That middle test is the episode in one assertion: 1 / 0 fails, and the machine tells you the failure happened at div, offset 4 -- not "somewhere," but there. The sampleChunk and divZeroChunk helpers just append the opcodes and constants by hand; in the real pipeline the compiler from episode 148 hands us the chunk, and the VM neither knows nor cares where the bytes came from.

How this compares elsewhere

If you have used a real debugger, you have met every idea in this episode wearing a fancier coat. A C bytecode VM (again, Crafting Interpreters is the canonical one) traces exactly like this -- print the instruction, print the stack -- but you write the opcode-name and error-name tables by hand, and one forgotten entry gives you a trace full of <unknown>. @tagName and @errorName mean ours cannot drift. Rust would lean on Result and match much as we lean on error unions and switch, and its enums carry the same weight; the flavour difference is Zig handing you @enumFromInt/@intFromEnum as plain builtins where Rust reaches for a crate like num_enum. Go would give you a slice of bytes and a garbage collector and have you tracing in ten minutes, but its switch will not force you to handle every opcode, so "did I cover the new instruction?" is back to being your worry in stead of the compiler's -- the same trade we have seen all series. And a "real" production VM adds source-line mapping, watchpoints, and stepping over calls -- but strip those away and the skeleton is precisely what we built: one steppable instruction, a saved fault site, a shared decoder, a stack you can print. The debugger is not a separate program bolted on; it is the machine, observed.

Where we go next

Step back and look at the calculator we finished. Four episodes ago it was a string. Episode 146 turned it into tokens and a precedence-correct Expr tree; episode 147 walked that tree into a number with typed errors and constant folding; episode 148 compiled the tree into flat bytecode with a disassembler and compile-time checks; and today we gave that bytecode a real machine to run on -- a bounds-checked stack, one-instruction-at-a-time execution, precise fault reporting, a tracer that shows the stack breathing, and breakpoints to freeze it wherever you like. Two back ends behind one shared AST, both tested green against Zig 0.16, and a debugger that makes the fast one inspectable. That is a complete little language pipeline, and every stage of it earned its keep.

The techniques were never really about arithmetic. A lexer, a parser, a tree-walker, a bytecode compiler, a stack VM, a tracing debugger -- that is the shape of every interpreter, from a config-file evaluator to a scripting language embedded in a game. So the natural next move is to keep the same spine and grow the language underneath it: more than numbers, more than one expression, real structure. We have built the machine; soon we point it at something with a good deal more to say. Thanks for building this whole thing with me -- de groeten, and see you in the next one! ;-)

scipio@scipio

stem
stemsocial
steemstem
zig
programming
via hiveblog
This post was published via hiveblog. Ecency is not the originator or editor of this content and displays it for discovery purposes only.
17