Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Stack-Based Calculator VM

Build a small stack-based calculator in Zig using tagged unions, switch, error sets, a tokenizer for postfix expressions and a fixed-size stack, with tests and a runnable Go version.

In this project you build a tiny virtual machine that evaluates expressions written in postfix notation (also called reverse Polish notation): 3 4 + 2 * means (3 + 4) * 2. Postfix needs no parentheses and no precedence rules, because a value stack does the work. It is the same model used by the Forth language, the JVM and WebAssembly, and it is a perfect exercise for Zig's tagged unions, exhaustive switch, error sets and fixed-capacity containers.

How a stack machine works

Read the program left to right. A number is pushed. An operator pops its operands, computes, and pushes the result. At the end, exactly one value must remain.

sequenceDiagram
  participant P as program
  participant S as stack
  P->>S: push 3
  P->>S: push 4
  P->>S: "+" pops 4 and 3, pushes 7
  P->>S: push 2
  P->>S: "*" pops 2 and 7, pushes 14
  Note over S: result 14

Caption: evaluating 3 4 + 2 * step by step.

Step 1: instructions as a tagged union

A value is either a number to push or an operator. A tagged union models "one of several shapes" with a compiler-checked tag:

ZIG
const std = @import("std");

const Op = enum { add, sub, mul, div };

const Instr = union(enum) {
    push: f64,
    binary: Op,
    dup,
    swap,
};

union(enum) creates a union with an automatic enum tag. push carries an f64; binary carries an Op; dup and swap carry nothing. You create values with .{ .push = 3.0 } or .dup.

Step 2: errors

Every way the machine can fail gets a name:

ZIG
const VmError = error{
    StackUnderflow,
    StackOverflow,
    DivisionByZero,
    LeftoverValues,
    BadToken,
    EmptyProgram,
};

Step 3: the machine

A fixed-size stack lives inside the struct, so the VM needs no allocator at all:

ZIG
const Vm = struct {
    stack: [64]f64 = undefined,
    len: usize = 0,

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

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

    fn step(self: *Vm, instr: Instr) VmError!void {
        switch (instr) {
            .push => |v| try self.push(v),
            .dup => {
                const top = try self.pop();
                try self.push(top);
                try self.push(top);
            },
            .swap => {
                const b = try self.pop();
                const a = try self.pop();
                try self.push(b);
                try self.push(a);
            },
            .binary => |op| {
                const b = try self.pop(); // right operand is on top
                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,
                });
            },
        }
    }

    fn result(self: *Vm) VmError!f64 {
        if (self.len == 0) return error.EmptyProgram;
        if (self.len > 1) return error.LeftoverValues;
        return self.stack[0];
    }
};

Three Zig features carry this code:

  • Exhaustive switch over the tagged union: if you add a new instruction later, the compiler points at every switch that must handle it. The capture |v| gives the payload of the active variant.
  • Error unions with try thread every failure out to the caller with no exceptions. Note the order of operands for sub and div: the second popped value is the left operand.
  • return error.DivisionByZero inside a switch expression is allowed because return has type noreturn and fits any branch.

Step 4: parsing text

ZIG
fn parseToken(tok: []const u8) VmError!Instr {
    if (tok.len == 1) switch (tok[0]) {
        '+' => return .{ .binary = .add },
        '-' => return .{ .binary = .sub },
        '*' => return .{ .binary = .mul },
        '/' => return .{ .binary = .div },
        else => {},
    };
    if (std.mem.eql(u8, tok, "dup")) return .dup;
    if (std.mem.eql(u8, tok, "swap")) return .swap;
    const n = std.fmt.parseFloat(f64, tok) catch return error.BadToken;
    return .{ .push = n };
}

pub fn evaluate(source: []const u8) VmError!f64 {
    var vm: Vm = .{};
    var it = std.mem.tokenizeAny(u8, source, " \t\r\n");
    while (it.next()) |tok| {
        try vm.step(try parseToken(tok));
    }
    return vm.result();
}

Note that a single-character token - is the operator, while -5 (two characters) is parsed as a number. std.mem.tokenizeAny splits on any of the given separator characters and skips empty pieces. Because parseFloat can fail with its own error, we map it to our BadToken using catch return error.BadToken.

Step 5: main and tests

ZIG
pub fn main() void {
    const programs = [_][]const u8{
        "3 4 + 2 *",
        "10 2 8 * + 3 -",
        "1 0 /",
        "5 +",
        "2 3",
    };
    for (programs) |p| {
        if (evaluate(p)) |value| {
            std.debug.print("{s} = {d}\n", .{ p, value });
        } else |err| {
            std.debug.print("{s} -> error.{s}\n", .{ p, @errorName(err) });
        }
    }
}

test "arithmetic" {
    try std.testing.expectEqual(@as(f64, 14), try evaluate("3 4 + 2 *"));
    try std.testing.expectEqual(@as(f64, 23), try evaluate("10 2 8 * + 3 -"));
}

test "errors" {
    try std.testing.expectError(error.DivisionByZero, evaluate("1 0 /"));
    try std.testing.expectError(error.StackUnderflow, evaluate("5 +"));
    try std.testing.expectError(error.LeftoverValues, evaluate("2 3"));
    try std.testing.expectError(error.BadToken, evaluate("2 x +"));
}

Expected printout: 3 4 + 2 * = 14, 10 2 8 * + 3 - = 23, 1 0 / -> error.DivisionByZero, and so on. (Check 10 2 8 * + 3 - by hand: 2*8 = 16, 10+16 = 26, 26-3 = 23.)

Extensions

  1. Add pow, neg and drop instructions: the compiler will list every switch you must update.
  2. Add a program type: parse once into a slice of Instr (allocated with an arena), then run it many times.
  3. Add variables: Instr gets store: u8 and load: u8, and the VM gets an array of slots.
  4. Turn the Vm into a generic Vm(comptime T: type, comptime capacity: usize) so it works on integers too (see Generic data structures).
  5. Write a fuzz-style test: random postfix strings must never crash, only return errors.

The same machine, runnable

Zig is read-only here, so this is the same design in Go: a tagged union becomes a struct with a kind field, the error set becomes sentinel errors, and the evaluation order is identical.

Go Stack VM in Go (same design as the Zig project)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does union(enum) give you?

    A tagged union stores a tag next to the payload, so switch can safely select the active variant.
  2. 2. Why is a switch on a tagged union handy when you add an instruction?

    Switches must be exhaustive, so a new variant is a compile error until each switch handles it.
  3. 3. In a b -, which popped value is the left operand?

    The right operand is on top of the stack, so it is popped first; the second pop is the left operand.
  4. 4. Why does this VM need no allocator?

    A capacity known at compile time lets the stack live inside the struct on the stack frame.

Summary

  • Postfix evaluation needs just a value stack.
  • Tagged unions plus exhaustive switch model instructions safely.
  • A named error set describes every way the machine fails; try threads errors out.
  • Fixed-capacity structs avoid allocators, and tests with expectError pin the failure modes.

Next: Zig practice exercises