Learn Zig Series (#147) - Mini Project: Calculator - Interpreter

scipio(71)

Published in

StemSocial

Words

3883

Reading

18 min

Listen

Play

21d

Learn Zig Series (#147) - Mini Project: Calculator - Interpreter

Part of a multi-episode project

What will I learn?

How to turn the AST we built last time into an actual answer -- a tree-walking evaluator that reads an Expr and computes an f64;
Why keeping the evaluator strictly seperate from the parser is what lets each side grow on its own, and how the recursion mirrors the tree exactly;
How to evaluate every node type -- numbers, constants, unary minus, the six binary operators, and function calls -- with one small switch the compiler forces you to complete;
How Zig's error unions turn runtime mistakes (DivisionByZero, UnknownFunction, DomainError) into precise, typed values the caller physically cannot forget to handle;
How to build a small library of constants (pi, e) and functions (sqrt, min, max, hypot), including proper arity checking so sqrt(1, 2) is a clean error;
How to add variables with an environment, turning the calculator from a one-shot evaluator into something you can drive from a REPL;
A first taste of optimization -- a constant-folding pass that collapses 2 + 3 into 5 before evaluation ever runs;
Where a tree-walking interpreter starts to hurt on performance, and why that pain is exactly what the next stage of this project sets out to fix.

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 lexer, AST and precedence-climbing parser from episode 146 -- this episode picks up the tree exactly where that one left off;
Tagged unions from episode 6, allocators and arenas from episode 7, and error unions from episode 4 -- all three come together here;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#147) - Mini Project: Calculator - Interpreter

Last episode we built the front end of our calculator -- a lexer that turns a raw string into tokens, an AST that captures the shape of an expression, and a precedence-climbing parser that gets * binding tighter than +, right-associative powers, unary minus, parentheses and function calls all correct. At the end of it we could read -2 * (3 + x) and print its tree as (* (neg 2) (+ 3 x)). That was satisfying, but let us be honest: a calculator that can describe a sum without computing it is a strange sort of calculator. Today we fix that. We write the evaluator -- the piece that walks the tree and finally hands you a number. Here we go!

From tree to number

The whole reason we split the calculator into a front end and a back end is that the two halves speak through one clean interface: the AST. The parser's only job is to produce a correct Expr; the evaluator's only job is to consume one. Neither knows -- or cares -- how the other works. That seperation is not academic tidiness. It means today's evaluator can be written, tested and later replaced (we will replace it, in fact) without touching a single line of the parser. Keep that in mind as we go: everything below reads an Expr and returns an f64, and that is the entire contract.

Here is the Expr union we are working against, unchanged from episode 146. I reproduce it so the rest of the code has something concrete to point at:

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 },
};

Five variants. An evaluator, therefore, is a function that answers the question "what number does this node mean?" for each of the five -- and because Expr is a union(enum), the compiler will physically refuse to let us forget one. That exhaustiveness is the quiet backbone of this whole design.

Errors are values, not surprises

Before we compute anything, we have to decide what happens when computing goes wrong. And plenty can go wrong at evaluation time that the parser had no way to catch: dividing by zero, asking for a constant that does not exist (x when we never defined x), calling a function nobody wrote, or handing sqrt a negative number. In many languages these become runtime exceptions or -- worse -- silent NaNs that quietly poison the rest of the calculation. In Zig, they become a typed error set:

const EvalError = error{
    DivisionByZero,
    UnknownConstant,
    UnknownFunction,
    BadArgCount,
    DomainError,
};

Every evaluation function will return EvalError!f64 -- either a real number or one of these five named failures. Nota bene: this is not decoration. Because the return type is an error union, every caller must try it (or handle it explicitly), and there is no path where a division-by-zero silently sails past unnoticed. The type system is doing the bookkeeping that a human reviewer would otherwise have to do by hand, and humans are much worse at it.

The binary operators

Let us start with the arithmetic, since it is the most familiar. Given an operator and two already-computed operands, evalBinary returns the result -- and it is exactly here that DivisionByZero gets caught, at the moment it matters:

fn evalBinary(op: BinOp, a: f64, b: f64) EvalError!f64 {
    return switch (op) {
        .add => a + b,
        .sub => a - b,
        .mul => a * b,
        .div => if (b == 0) error.DivisionByZero else a / b,
        .mod => if (b == 0) error.DivisionByZero else @rem(a, b),
        .pow => std.math.pow(f64, a, b),
    };
}

A few things worth pointing out. The switch over BinOp is exhaustive -- add a seventh operator to the enum later and this function stops compiling until you handle it, which is precisely the safety net you want in a growing language. For % I use @rem, Zig's built-in remainder, which is well-defined for floats and lets 10.5 % 3 behave sensibly. And ^ leans on std.math.pow rather than a hand-rolled loop -- no point reinventing exponentiation when the standard library already does it correctly for the whole f64 range, negative and fractional exponents included. Having said that, notice what evalBinary does not do: it does not evaluate anything itself. It receives two finished numbers. The recursion lives elsewhere, which keeps this function trivially testable in isolation.

Constants and the function library

A bare identifier like pi is a constant, and a name followed by parentheses like sqrt(2) is a function call. Constants are the simpler of the two -- a small lookup that either recognises the name or returns a typed error:

fn lookupConst(name: []const u8) EvalError!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 error.UnknownConstant;
}

Functions are more interesting, because a real function library has to worry about arity -- how many arguments each function takes. sqrt wants exactly one; pow wants two; min and max want at least one but happily take a dozen. A robust evaluator does not just compute the answer, it also rejects sqrt(1, 2) with a clear BadArgCount rather than silently ignoring the extra argument. Here is the dispatcher, and note that it evaluates each argument by recursing back into the main eval (which we meet in a moment):

fn isKnownFn(name: []const u8) bool {
    const names = [_][]const u8{
        "min", "max", "sqrt", "abs", "floor",
        "ceil", "sin", "cos", "ln", "pow", "hypot",
    };
    for (names) |n| if (std.mem.eql(u8, name, n)) return true;
    return false;
}

fn evalCall(name: []const u8, args: []const *Expr) EvalError!f64 {
    // Variadic: min and max take one or more arguments.
    if (std.mem.eql(u8, name, "min") or std.mem.eql(u8, name, "max")) {
        if (args.len == 0) return error.BadArgCount;
        const want_max = std.mem.eql(u8, name, "max");
        var acc = try eval(args[0]);
        for (args[1..]) |a| {
            const v = try eval(a);
            if (want_max) {
                if (v > acc) acc = v;
            } else if (v < acc) acc = v;
        }
        return acc;
    }

    // Fixed arity: one argument.
    if (args.len == 1) {
        const x = try eval(args[0]);
        if (std.mem.eql(u8, name, "sqrt")) return if (x < 0) error.DomainError else std.math.sqrt(x);
        if (std.mem.eql(u8, name, "abs")) return @abs(x);
        if (std.mem.eql(u8, name, "floor")) return std.math.floor(x);
        if (std.mem.eql(u8, name, "ceil")) return std.math.ceil(x);
        if (std.mem.eql(u8, name, "sin")) return std.math.sin(x);
        if (std.mem.eql(u8, name, "cos")) return std.math.cos(x);
        if (std.mem.eql(u8, name, "ln")) return if (x <= 0) error.DomainError else @log(x);
    }

    // Fixed arity: two arguments.
    if (args.len == 2) {
        const a = try eval(args[0]);
        const b = try eval(args[1]);
        if (std.mem.eql(u8, name, "pow")) return std.math.pow(f64, a, b);
        if (std.mem.eql(u8, name, "hypot")) return std.math.hypot(a, b);
    }

    // The name is real but the argument count is wrong -> a precise error.
    if (isKnownFn(name)) return error.BadArgCount;
    return error.UnknownFunction;
}

The structure here is deliberate. We match on name-and-arity together, so a call falls through to the bottom only if either the name is unknown (UnknownFunction) or the name is known but the count is wrong (BadArgCount). That final isKnownFn check is what lets us give the better of the two error messages -- telling a user "you gave sqrt the wrong number of arguments" is far more useful than a generic "unknown function". Domain errors get the same care: sqrt(-1) and ln(0) return DomainError in stead of an NaN that would silently spread through the rest of the sum. This is a lot of guardrails for a toy calculator, I know -- but the whole point of a mini project is to practise building the real thing at a size you can hold in your head.

The heart: the recursive walk

Now everything comes together in one small function. eval takes a pointer to any Expr and returns its value, dispatching on the tag and recursing into children. This is the classic tree-walking interpreter, and its beauty is how directly it mirrors the data:

fn eval(e: *const Expr) EvalError!f64 {
    return switch (e.*) {
        .number => |v| v,
        .ident => |name| lookupConst(name),
        .unary => |u| switch (u.op) {
            .neg => -(try eval(u.operand)),
        },
        .binary => |b| try evalBinary(b.op, try eval(b.lhs), try eval(b.rhs)),
        .call => |c| try evalCall(c.name, c.args),
    };
}

Read it slowly, because there is a lot of correctness packed into five arms. A .number is its own value -- the base case that stops the recursion. An .ident defers to lookupConst. A .unary negation evaluates its operand first and then flips the sign -- and because that inner eval can fail, the try propagates any error straight up. The .binary arm is the one to admire: try eval(b.lhs) and try eval(b.rhs) each recurse down a whole subtree, and only once both return real numbers does evalBinary combine them. The tree's structure -- built by the parser to encode precedence -- is the evaluation order. We never wrote a single line about "do multiplication before addition"; the parser already baked that into the shape of the tree, and the evaluator just walks it. That is the front-end/back-end split earning its keep.

Wiring it up and testing it

To drive the whole pipeline from a string, we parse into an arena and evaluate the resulting tree. The arena (episode 7) owns every node, so one defer arena.deinit() cleans up the entire tree the instant we have our answer:

fn evalStr(gpa: std.mem.Allocator, src: []const u8) !f64 {
    var arena = std.heap.ArenaAllocator.init(gpa);
    defer arena.deinit();
    const tree = try parse(arena.allocator(), src);
    return eval(tree);
}

And here is where a mini project pays you back for all that discipline: the tests read like a specification. Floating point means we compare with a small tolerance rather than ==, so a tiny approx helper does the honours. First, the arithmetic -- precedence, associativity, unary minus, parentheses and modulo, all evaluated to their true numeric answers:

fn approx(a: f64, b: f64) bool {
    return @abs(a - b) < 1e-9;
}

test "arithmetic, precedence and associativity evaluate correctly" {
    const gpa = std.testing.allocator;
    try std.testing.expect(approx(7, try evalStr(gpa, "1 + 2 * 3")));
    try std.testing.expect(approx(5, try evalStr(gpa, "10 - 3 - 2")));
    try std.testing.expect(approx(512, try evalStr(gpa, "2 ^ 3 ^ 2")));
    try std.testing.expect(approx(-4, try evalStr(gpa, "-2 ^ 2")));
    try std.testing.expect(approx(9, try evalStr(gpa, "(1 + 2) * 3")));
    try std.testing.expect(approx(1, try evalStr(gpa, "10 % 3")));
}

Look at 2 ^ 3 ^ 2 giving 512 and -2 ^ 2 giving -4. Those two lines silently prove that last episode's binding-power table was right: powers are right-associative (2 ^ (3 ^ 2) = 2 ^ 9 = 512) and unary minus binds looser than ^ (-(2 ^ 2) = -4). We are testing the parser and the evaluator together now, end to end. Next, the constants and the function library, including the variadic max/min:

test "constants and functions" {
    const gpa = std.testing.allocator;
    try std.testing.expect(approx(std.math.pi, try evalStr(gpa, "pi")));
    try std.testing.expect(approx(3, try evalStr(gpa, "sqrt(2 + 7)")));
    try std.testing.expect(approx(3, try evalStr(gpa, "max(1, 2, 3)")));
    try std.testing.expect(approx(1, try evalStr(gpa, "min(3, 1, 2)")));
    try std.testing.expect(approx(5, try evalStr(gpa, "hypot(3, 4)")));
    try std.testing.expect(approx(2, try evalStr(gpa, "abs(-2)")));
}

hypot(3, 4) returning 5 is my favourite -- a whole Pythagorean triple falling out of one line of test. And finally, the part that separates a real evaluator from a fragile one: every failure mode returns its specific typed error, and expectError proves it:

test "evaluator reports precise, typed errors" {
    const gpa = std.testing.allocator;
    try std.testing.expectError(error.DivisionByZero, evalStr(gpa, "1 / 0"));
    try std.testing.expectError(error.DivisionByZero, evalStr(gpa, "5 % 0"));
    try std.testing.expectError(error.UnknownConstant, evalStr(gpa, "x + 1"));
    try std.testing.expectError(error.UnknownFunction, evalStr(gpa, "frobnicate(2)"));
    try std.testing.expectError(error.BadArgCount, evalStr(gpa, "sqrt(1, 2)"));
    try std.testing.expectError(error.DomainError, evalStr(gpa, "sqrt(-1)"));
}

Six failure modes, six precise errors, zero crashes and zero NaNs leaking out. A user of this calculator gets told exactly what went wrong, and we -- the implementers -- got told by the compiler that we handled every case. On my machine zig test runs all three of these green.

Giving it variables: an environment

Right now x is an error, because we only know pi, e and tau. But the natural next feature for any calculator is variables -- let the user say x = 10 and then compute x * x + 1. The clean way to do that is an environment: a map from names to values that the evaluator consults. We can generalise lookupConst into an Env that checks user variables first, then falls back to the built-in constants:

const Env = struct {
    vars: std.StringHashMap(f64),

    fn init(gpa: std.mem.Allocator) Env {
        return .{ .vars = std.StringHashMap(f64).init(gpa) };
    }
    fn deinit(self: *Env) void {
        self.vars.deinit();
    }
    fn set(self: *Env, name: []const u8, value: f64) !void {
        try self.vars.put(name, value);
    }
    fn lookup(self: *const Env, name: []const u8) EvalError!f64 {
        if (self.vars.get(name)) |v| return v;
        if (std.mem.eql(u8, name, "pi")) return std.math.pi;
        if (std.mem.eql(u8, name, "e")) return std.math.e;
        return error.UnknownConstant;
    }
};

fn evalEnv(env: *const Env, e: *const Expr) EvalError!f64 {
    return switch (e.*) {
        .number => |v| v,
        .ident => |name| env.lookup(name),
        .unary => |u| switch (u.op) { .neg => -(try evalEnv(env, u.operand)) },
        .binary => |b| try evalBinary(b.op, try evalEnv(env, b.lhs), try evalEnv(env, b.rhs)),
        .call => |c| try evalCall(c.name, c.args),
    };
}

Notice how tiny the change is: evalEnv is eval with an extra *const Env threaded through, and only the .ident arm actually uses it. That is the sign of a healthy design -- a genuinely new capability (variables) drops in without disturbing the arithmetic, the functions, or the error handling. This Env is also the seed of a REPL: read a line, if it looks like name = expr then evaluate the right-hand side and env.set the result, otherwise evaluate and print. A calculator you can hold a conversation with is suddenly one small loop away.

A first optimization: constant folding

We now have a correct interpreter, and the series' recurring lesson applies here as much as anywhere -- measure before you optimize (episode 34). But there is one optimization so classic and so cheap that it is worth meeting now: constant folding. If a subtree contains no variables -- 2 + 3 * 4 -- its value never changes, so we can compute it once and replace the whole subtree with a single number node. Evaluate the folded tree a million times (say, plotting a graph) and you skip all that repeated arithmetic:

fn fold(arena: std.mem.Allocator, e: *Expr) !*Expr {
    switch (e.*) {
        .binary => |b| {
            const l = try fold(arena, b.lhs);
            const r = try fold(arena, b.rhs);
            if (l.* == .number and r.* == .number) {
                if (evalBinary(b.op, l.number, r.number)) |v| {
                    const n = try arena.create(Expr);
                    n.* = .{ .number = v };
                    return n;
                } else |_| {
                    // e.g. a literal 1/0 -- leave it for the evaluator to report.
                }
            }
            e.* = .{ .binary = .{ .op = b.op, .lhs = l, .rhs = r } };
            return e;
        },
        .unary => |u| {
            const inner = try fold(arena, u.operand);
            if (inner.* == .number) {
                const n = try arena.create(Expr);
                n.* = .{ .number = -inner.number };
                return n;
            }
            e.* = .{ .unary = .{ .op = u.op, .operand = inner } };
            return e;
        },
        else => return e,
    }
}

Fold turns (+ 2 (* 3 4)) into just 14 -- a leaf. The subtlety I want to flag is that error-catching if (evalBinary(...)) |v| ... else |_| ...: if a constant subtree would divide by zero, we do not fold it into a bogus value, we leave the original binary node in place so the real evaluator reports DivisionByZero at run time, exactly as before. Folding must never change what a program means, only how fast it gets there. That is the golden rule of every optimizer, from this ten-line pass all the way up to the register allocator we wrote back in episode 145.

Where the tree-walker starts to hurt

So we have a real, tested, extensible interpreter. Is it fast? For a calculator a human types into, absolutely -- it evaluates in microseconds, and you would never notice. But step back and look at what eval actually costs per node: a switch on the union tag, a pointer chase to a child that lives who-knows-where in memory, another function call, and back up again. For a tree evaluated once, that is nothing. For a tree evaluated in a hot loop -- a spreadsheet recomputing ten thousand cells, or a plotter sampling a function a million times -- those scattered pointer chases and per-node dispatches add up. The tree is a lovely thing to reason about and a mediocre thing to execute, because the CPU hates chasing pointers all over the heap.

This is the exact tension the back half of this mini project exists to resolve, and if the words "bytecode", "stack machine" and "VM" are ringing a bell from episodes 135 and 136, you are reading the map correctly. A flat array of instructions the CPU can march through linearly beats a pointer-chasing tree for repeated execution -- and turning our Expr tree into exactly that is where we head next. We have the tree; soon we compile it.

How this compares elsewhere

If you have written a tree-walking evaluator in C, the shape is familiar -- a switch on an enum tag, recursion over child pointers -- but the safety is not. C's switch will happily let you forget a case and fall through to whatever comes next; ours cannot compile with a missing arm. C's division-by-zero on floats gives you infinity and marches on; ours returns a typed error you cannot ignore. And C's "unknown function" would likely be a null function pointer waiting to segfault, where ours is a clean UnknownFunction value. Rust matches Zig here almost beat for beat -- exhaustive match, Result for errors, the same recursive walk -- with the borrow checker where Zig gives you explicit allocators and arenas. Go would lean on its garbage collector for the tree and (value, err) pairs for errors, ergonomic but paying a GC cost we simply do not; and Go's switch does not enforce exhaustiveness, so the "did I handle every node?" guarantee is back on you. The tree-walking algorithm itself is identical in every language -- it is one of those beautiful, universal ideas -- but Zig lets us write it with exhaustive dispatch, typed errors and zero hidden allocation, which for an interpreter is precisely the combination you want.

That is the calculator computing at last: a tree-walking evaluator that handles every node type, a function library with real arity and domain checking, precise typed errors for every failure, an environment that opens the door to variables and a REPL, and a constant-folding pass as a first taste of optimization -- every line of it compiled and tested against Zig 0.16. We can now read an expression and tell you what it equals. The obvious frontier from here is speed: taking this clean tree and turning it into something a machine can rip through, using the compiler toolbox we spent this whole arc building. Thanks for reading, and happy hacking! ;-)

@scipio