Source code --> Lexer --> tokens --> Parser --> AST --> Evaluator --> value
^^^^^^^^^
you are here
In chapter 1 we turned our source into tokens. In chapter 2 we turned our tokens into a tree (AST). Now we’re going to walk the AST and produce values with an evaluator. Let’s return to our running example of 5 + 3 * 4. When the evaluator sees an InfixExpression node with the operator +, a left child Int(5) and a right child that is itself an Infix(*) node, it evaluates both children first. The left child is trivially 5. The right child is another infix expression, so the evaluator recurses into it, evaluates 3 and 4, multiplies them to get 12, and comes back up. Only then does it add 5 and 12. The shape of the tree tells the evaluator what to do and in what order, which is why we spent so long getting that shape right in chapter 2.
"5 + 3 * 4" --> AST --> Object(17)
Infix(+)
/ \
Int(5) Infix(*) evaluate the children first:
/ \ 3 * 4 = 12
Int(3) Int(4) then 5 + 12 = 17
This style of interpreter is called a tree-walking interpreter, because that’s literally all it does. It’s the simplest kind you can build and it’s slow compared to a bytecode VM, but every concept in it carries over to the fancier designs. To build one we need three things:
- An object system to represent runtime values (integers, bools, strings, funcs, etc)
- An environment for variable bindings with scope chains
- The evaluator itself, for walking the tree recursively
In this chapter we’re going to build this across three files: object.zig for the runtime object system, environment.zig for variable binding environments, evaluator.zig for the tree-walking evaluator.
Object System (object.zig)
#
Just like our parser used an Expression union to represent “any expression”, our evaluator will use an Object to represent “any value”.
Why do we need a second set of types at all? The AST already has IntegerLiteral, why not evaluate to that? Because syntax and values are different things. IntegerLiteral is the text 5 in your source. Integer is the number five, which might have come from the literal 5, or from 2 + 3, or from len("hello"). The split is clearest with functions. A FunctionLiteral is just the code, fn(x) { x + 1 }. A Function object is that code plus the environment it was created in, and that second part is what makes closures work. Keeping syntax and values separate is one of those decisions that seems like extra typing now and saves you from a mess later.
One Zig-specific note. Object is a tagged union passed around by value, not a pointer to a heap object like the Go version. Copying an Object copies the tag and the payload, and for the payloads that hold slices or hash maps that’s a shallow copy, both copies point at the same elements. That’s safe because Monkey values are immutable. push returns a new array instead of modifying the old one, string concatenation makes a new string, and so on. If you ever add mutation to Monkey, this is the first thing you’ll need to revisit.
The value types #
const std = @import("std");
const ast = @import("ast.zig");
const Environment = @import("environment.zig").Environment;
pub const ObjectType = enum {
integer,
boolean,
null,
return_value,
err,
function,
string,
builtin,
array,
hash,
};
Simple value structs #
pub const Integer = struct { value: i64 };
pub const Boolean = struct { value: bool };
pub const Null = struct {};
pub const ReturnValue = struct { value: *const Object };
pub const Error = struct { message: []const u8 };
pub const String = struct { value: []const u8 };
pub const BuiltinFn = *const fn (allocator: std.mem.Allocator, args: []const Object) Object;
pub const Builtin = struct { func: BuiltinFn };
pub const Array = struct { elements: []const Object };
pub const Hash = struct { pairs: std.AutoHashMap(HashKey, HashPair) };
Hash keys #
Monkey hashes can be keyed by integers, booleans and strings, and {1: "a"}["1"] must not find anything, the integer 1 and the string "1" are different keys. We convert all three to a uniform HashKey that pairs the type with a u64. Integers are bit-cast directly, booleans become 0 or 1, and strings are run through a hash function.
pub const HashKey = struct {
type: ObjectType,
value: u64,
};
There’s a caveat with strings that the Go book also points out. We’re using the 64-bit hash as the key, so two different strings that happen to hash to the same value would collide and share a slot. With a good 64-bit hash that’s astronomically unlikely for a toy language, but a real implementation would store the original string alongside and compare on collision. Good exercise once you’re done.
Functions capture their environment #
A function object holds the parameter list and body straight from the AST, plus a pointer to an Environment. That pointer is the environment the function was defined in, not the one it’s called from, and it’s captured at the moment the fn literal is evaluated. This is what makes Monkey lexically scoped: an inner function can see the variables of the function that created it, forever, even after that outer function has returned. We’ll see exactly how in the environment section below.
ReturnValue also holds a pointer, for a more boring reason. A union can’t contain itself by value, so the wrapped object has to live on the heap. Why we need a ReturnValue type at all is explained in the evaluator section.
pub const Function = struct {
parameters: []const ast.Identifier,
body: ast.BlockStatement,
env: *Environment,
};
pub const HashPair = struct {
key: Object,
value: Object,
};
The Object union
#
pub const Object = union(enum) {
integer: Integer,
boolean: Boolean,
null: Null,
return_value: ReturnValue,
err: Error,
function: Function,
string: String,
builtin: Builtin,
array: Array,
hash: Hash,
pub fn objectType(self: Object) ObjectType {
return switch (self) {
.integer => .integer,
.boolean => .boolean,
.null => .null,
.return_value => .return_value,
.err => .err,
.function => .function,
.string => .string,
.builtin => .builtin,
.array => .array,
.hash => .hash,
};
}
Inspection and hashing #
inspect is how the REPL prints a value. typeName gives the uppercase names you’ll see in error messages like type mismatch: INTEGER + BOOLEAN. hashKey returns null for anything that can’t be a hash key, which the evaluator turns into an “unusable as hash key” error.
pub fn inspect(self: Object, allocator: std.mem.Allocator) ![]const u8 {
return switch (self) {
.integer => |i| try std.fmt.allocPrint(allocator, "{d}", .{i.value}),
.boolean => |b| try std.fmt.allocPrint(allocator, "{s}", .{if (b.value) "true" else "false"}),
.null => try allocator.dupe(u8, "null"),
.return_value => |rv| rv.value.inspect(allocator),
.err => |e| try std.fmt.allocPrint(allocator, "ERROR: {s}", .{e.message}),
.function => try allocator.dupe(u8, "fn(...) { ... }"),
.string => |s| try allocator.dupe(u8, s.value),
.builtin => try allocator.dupe(u8, "builtin function"),
.array => |a| {
var buf: std.ArrayList(u8) = .empty;
try buf.appendSlice(allocator, "[");
for (a.elements, 0..) |elem, idx| {
if (idx > 0) try buf.appendSlice(allocator, ", ");
const s = try elem.inspect(allocator);
try buf.appendSlice(allocator, s);
}
try buf.appendSlice(allocator, "]");
return buf.toOwnedSlice(allocator);
},
.hash => try allocator.dupe(u8, "{...}"),
};
}
pub fn typeName(self: Object) []const u8 {
return switch (self) {
.integer => "INTEGER",
.boolean => "BOOLEAN",
.null => "NULL",
.return_value => "RETURN_VALUE",
.err => "ERROR",
.function => "FUNCTION",
.string => "STRING",
.builtin => "BUILTIN",
.array => "ARRAY",
.hash => "HASH",
};
}
pub fn hashKey(self: Object) ?HashKey {
return switch (self) {
.integer => |i| .{ .type = .integer, .value = @bitCast(i.value) },
.boolean => |b| .{ .type = .boolean, .value = if (b.value) 1 else 0 },
.string => |s| .{ .type = .string, .value = std.hash.Wyhash.hash(0, s.value) },
else => null,
};
}
};
Complete object.zig
#
const std = @import("std");
const ast = @import("ast.zig");
const Environment = @import("environment.zig").Environment;
pub const ObjectType = enum {
integer,
boolean,
null,
return_value,
err,
function,
string,
builtin,
array,
hash,
};
pub const Integer = struct { value: i64 };
pub const Boolean = struct { value: bool };
pub const Null = struct {};
pub const ReturnValue = struct { value: *const Object };
pub const Error = struct { message: []const u8 };
pub const String = struct { value: []const u8 };
pub const BuiltinFn = *const fn (allocator: std.mem.Allocator, args: []const Object) Object;
pub const Builtin = struct { func: BuiltinFn };
pub const Array = struct { elements: []const Object };
pub const Hash = struct { pairs: std.AutoHashMap(HashKey, HashPair) };
pub const HashKey = struct {
type: ObjectType,
value: u64,
};
pub const Function = struct {
parameters: []const ast.Identifier,
body: ast.BlockStatement,
env: *Environment,
};
pub const HashPair = struct {
key: Object,
value: Object,
};
pub const Object = union(enum) {
integer: Integer,
boolean: Boolean,
null: Null,
return_value: ReturnValue,
err: Error,
function: Function,
string: String,
builtin: Builtin,
array: Array,
hash: Hash,
pub fn objectType(self: Object) ObjectType {
return switch (self) {
.integer => .integer,
.boolean => .boolean,
.null => .null,
.return_value => .return_value,
.err => .err,
.function => .function,
.string => .string,
.builtin => .builtin,
.array => .array,
.hash => .hash,
};
}
pub fn inspect(self: Object, allocator: std.mem.Allocator) ![]const u8 {
return switch (self) {
.integer => |i| try std.fmt.allocPrint(allocator, "{d}", .{i.value}),
.boolean => |b| try std.fmt.allocPrint(allocator, "{s}", .{if (b.value) "true" else "false"}),
.null => try allocator.dupe(u8, "null"),
.return_value => |rv| rv.value.inspect(allocator),
.err => |e| try std.fmt.allocPrint(allocator, "ERROR: {s}", .{e.message}),
.function => try allocator.dupe(u8, "fn(...) { ... }"),
.string => |s| try allocator.dupe(u8, s.value),
.builtin => try allocator.dupe(u8, "builtin function"),
.array => |a| {
var buf: std.ArrayList(u8) = .empty;
try buf.appendSlice(allocator, "[");
for (a.elements, 0..) |elem, idx| {
if (idx > 0) try buf.appendSlice(allocator, ", ");
const s = try elem.inspect(allocator);
try buf.appendSlice(allocator, s);
}
try buf.appendSlice(allocator, "]");
return buf.toOwnedSlice(allocator);
},
.hash => try allocator.dupe(u8, "{...}"),
};
}
pub fn typeName(self: Object) []const u8 {
return switch (self) {
.integer => "INTEGER",
.boolean => "BOOLEAN",
.null => "NULL",
.return_value => "RETURN_VALUE",
.err => "ERROR",
.function => "FUNCTION",
.string => "STRING",
.builtin => "BUILTIN",
.array => "ARRAY",
.hash => "HASH",
};
}
pub fn hashKey(self: Object) ?HashKey {
return switch (self) {
.integer => |i| .{ .type = .integer, .value = @bitCast(i.value) },
.boolean => |b| .{ .type = .boolean, .value = if (b.value) 1 else 0 },
.string => |s| .{ .type = .string, .value = std.hash.Wyhash.hash(0, s.value) },
else => null,
};
}
};
Environment (environment.zig)
#
How scope chains work #
An environment is a hash map from names to objects, plus an optional pointer to an outer environment. That’s enough to give Monkey proper lexical scoping. get checks the local map first and if the name isn’t there it asks the outer environment, which asks its outer, and so on up to the global environment. set only ever writes to the local map. Together those two rules mean inner names shadow outer ones and a function can’t accidentally clobber a global.
Every function call creates a fresh environment for its parameters, with outer pointing at the environment the function captured when it was defined. Let’s look at what that means for the closure example from the introduction, at the moment x + y is being evaluated inside addTwo(3).
let newAdder = fn(x) { fn(y) { x + y; }; };
let addTwo = newAdder(2);
addTwo(3);
env for the call addTwo(3) { y: 3 }
|
| outer
v
env for the call newAdder(2) { x: 2 } <- the inner fn captured this
| when it was created
| outer
v
global env { newAdder: fn, addTwo: fn }
Looking up y hits immediately. Looking up x misses in the top map, follows outer, and finds 2. The interesting part is the middle environment. newAdder(2) returned a long time ago, but its environment is still alive because the function object stored in addTwo holds a pointer to it. That’s what a closure is, a function plus the environment it closed over. It’s also why, in a language without a garbage collector, that environment has to be heap-allocated and has to live at least as long as the function object. The arena handles the lifetime for us. Get this wrong and you’ll see it in the evaluator, there’s a comment marking the spot.
Okay now let’s write the code.
Complete environment.zig
#
const std = @import("std");
const object = @import("object.zig");
pub const Environment = struct {
store: std.StringHashMap(object.Object),
outer: ?*Environment,
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator) Environment {
return .{
.store = std.StringHashMap(object.Object).init(allocator),
.outer = null,
.allocator = allocator,
};
}
pub fn initEnclosed(allocator: std.mem.Allocator, outer: *Environment) Environment {
var env = init(allocator);
env.outer = outer;
return env;
}
pub fn get(self: *const Environment, name: []const u8) ?object.Object {
if (self.store.get(name)) |val| return val;
if (self.outer) |outer| return outer.get(name);
return null;
}
pub fn set(self: *Environment, name: []const u8, val: object.Object) !void {
const owned_name = try self.allocator.dupe(u8, name);
try self.store.put(owned_name, val);
}
};
set copies the name before storing it so the map owns its keys and doesn’t depend on whatever string the caller handed us. With the arena strategy it would technically be fine to store the slice directly, but this keeps the environment self-contained and it costs almost nothing.
Evaluator (evaluator.zig)
#
The evaluator is a set of recursive functions that switch on AST node types and produce results, the engine that drives Monkey. Without the evaluator you just have a tree representation of your source without action.
Two kinds of errors #
Before the code, one design decision that’s easy to miss because it’s spread across every function. Look at the return type, EvalError!object.Object, and notice that EvalError is just std.mem.Allocator.Error. The only Zig error the evaluator can return is out of memory. So where do Monkey’s errors go, like type mismatch: INTEGER + BOOLEAN or identifier not found: foobar?
They’re values, an Object with the .err tag, produced by newError and returned like any other result. This is a deliberate split between two kinds of failure. Host errors are problems with the interpreter itself, we ran out of memory, and those use Zig’s error system because there’s nothing sensible Monkey can do about them. Guest errors are problems with the Monkey program, and those are ordinary runtime values the Monkey program produced. The REPL prints them, a future version of Monkey could catch them.
The cost of this design is that every place we evaluate a sub-expression has to check isError and bail out, which is why you’ll see that pattern so many times below. That’s what makes errors short-circuit: 5 + true; 5; evaluates to the error and never gets to the second statement.
Constants and helpers #
const std = @import("std");
const ast = @import("ast.zig");
const object = @import("object.zig");
const Environment = @import("environment.zig").Environment;
const EvalError = std.mem.Allocator.Error;
const TRUE = object.Object{ .boolean = .{ .value = true } };
const FALSE = object.Object{ .boolean = .{ .value = false } };
const NULL = object.Object{ .null = .{} };
fn nativeBoolToObject(value: bool) object.Object {
return if (value) TRUE else FALSE;
}
fn isError(obj: object.Object) bool {
return switch (obj) {
.err => true,
else => false,
};
}
fn newError(allocator: std.mem.Allocator, comptime fmt: []const u8, args: anytype) EvalError!object.Object {
const message = try std.fmt.allocPrint(allocator, fmt, args);
return .{ .err = .{ .message = message } };
}
Program and block evaluation #
These two functions look almost identical and the difference between them is the most important idea in this chapter, so let’s go slow.
Both loop over statements, evaluate each one, and return the value of the last. The question is what happens when one of those statements is a return. In a tree-walking interpreter there’s no jump instruction, the only way out of a nested block is to return up through every recursive call in between. So when the evaluator hits a return statement it wraps the value in a ReturnValue object, and every block on the way up checks for that wrapper and stops early, passing it along untouched.
let f = fn(x) {
if (x > 5) { <- outer block
if (x > 10) { <- inner block
return 10; <- wrapped: ReturnValue(10)
} inner block sees the wrapper, stops, passes it up
return 1; never runs
} outer block sees the wrapper, stops, passes it up
}; applyFunction unwraps it: 10
Now for the difference. evalBlockStatement passes the wrapper up without unwrapping it. If it unwrapped, the outer block would receive a plain 10, treat it as the value of an ordinary expression statement, carry on, and run return 1. Only the boundaries unwrap: evalProgram at the top level, and applyFunction when a function call finishes. Errors work the same way, any block that sees an .err stops and passes it up, which is how if (10 > 1) { true + false; } produces an error instead of null.
pub fn evalProgram(allocator: std.mem.Allocator, program: ast.Program, env: *Environment) EvalError!object.Object {
var result: object.Object = NULL;
for (program.statements) |stmt| {
result = try evalStatement(allocator, stmt, env);
switch (result) {
.return_value => |rv| return rv.value.*,
.err => return result,
else => {},
}
}
return result;
}
fn evalBlockStatement(allocator: std.mem.Allocator, block: ast.BlockStatement, env: *Environment) EvalError!object.Object {
var result: object.Object = NULL;
for (block.statements) |stmt| {
result = try evalStatement(allocator, stmt, env);
switch (result) {
.return_value, .err => return result,
else => {},
}
}
return result;
}
Statement evaluation #
A let evaluates its right-hand side and binds the result in the current environment. It evaluates to NULL, which is why typing let x = 5 into the REPL will print null. A return evaluates its expression and wraps the result, per the story above. Both check for errors first so a failed expression doesn’t get bound or returned.
fn evalStatement(allocator: std.mem.Allocator, stmt: ast.Statement, env: *Environment) EvalError!object.Object {
return switch (stmt) {
.expression_statement => |es| try evalExpression(allocator, es.expression, env),
.let_statement => |ls| {
const val = try evalExpression(allocator, ls.value, env);
if (isError(val)) return val;
try env.set(ls.name, val);
return NULL;
},
.return_statement => |rs| {
const val = try evalExpression(allocator, rs.value, env);
if (isError(val)) return val;
const val_ptr = try allocator.create(object.Object);
val_ptr.* = val;
return .{ .return_value = .{ .value = val_ptr } };
},
};
}
Expression evaluation, the main dispatch #
This is the big switch. Literals become objects directly. Everything else evaluates its children and then hands the resulting objects to a helper. A couple of things to notice as you read it:
- Infix expressions evaluate
leftbeforeright. That’s Monkey’s evaluation order, and it’s a decision we’re making for the language. Some languages leave it unspecified. - A
function_literaldoesn’t call anything. It builds aFunctionobject that grabs the currentenv. That single assignment,.env = env, is where closures come from. - A
callevaluates the function expression first, then the arguments left to right, then hands everything toapplyFunction. The function expression can be anything that produces a function, an identifier, a call that returns a function, or a literal called on the spot.
fn evalExpression(allocator: std.mem.Allocator, expr: ast.Expression, env: *Environment) EvalError!object.Object {
return switch (expr) {
.integer_literal => |il| .{ .integer = .{ .value = il.value } },
.boolean => |b| nativeBoolToObject(b.value),
.string_literal => |s| .{ .string = .{ .value = s.value } },
.prefix => |p| {
const right = try evalExpression(allocator, p.right.*, env);
if (isError(right)) return right;
return evalPrefixExpression(allocator, p.operator, right);
},
.infix => |i| {
const left = try evalExpression(allocator, i.left.*, env);
if (isError(left)) return left;
const right = try evalExpression(allocator, i.right.*, env);
if (isError(right)) return right;
return evalInfixExpression(allocator, i.operator, left, right);
},
.if_expression => |ie| try evalIfExpression(allocator, ie, env),
.identifier => |id| evalIdentifier(allocator, id, env),
.function_literal => |fl| .{ .function = .{
.parameters = fl.parameters,
.body = fl.body,
.env = env,
} },
.call => |c| {
const func = try evalExpression(allocator, c.function.*, env);
if (isError(func)) return func;
var args: std.ArrayList(object.Object) = .empty;
for (c.arguments) |arg_expr| {
const arg = try evalExpression(allocator, arg_expr, env);
if (isError(arg)) return arg;
try args.append(allocator, arg);
}
return applyFunction(allocator, func, args.items);
},
.array_literal => |a| {
var elements: std.ArrayList(object.Object) = .empty;
for (a.elements) |elem_expr| {
const elem = try evalExpression(allocator, elem_expr, env);
if (isError(elem)) return elem;
try elements.append(allocator, elem);
}
return .{ .array = .{ .elements = try elements.toOwnedSlice(allocator) } };
},
.index_expression => |ie| {
const left = try evalExpression(allocator, ie.left.*, env);
if (isError(left)) return left;
const index = try evalExpression(allocator, ie.index.*, env);
if (isError(index)) return index;
return evalIndexExpression(allocator, left, index);
},
.hash_literal => |h| try evalHashLiteral(allocator, h, env),
};
}
Prefix and infix operators #
! works on any value using Monkey’s truthiness rules (more on those in a moment), - only works on integers. The operator arrives as a string because that’s how we stored it in the AST, so the dispatch is a couple of std.mem.eql calls.
fn evalPrefixExpression(allocator: std.mem.Allocator, operator: []const u8, right: object.Object) EvalError!object.Object {
if (std.mem.eql(u8, operator, "!")) {
return evalBangOperator(right);
} else if (std.mem.eql(u8, operator, "-")) {
return evalMinusPrefixOperator(allocator, right);
}
return newError(allocator, "unknown operator: {s}{s}", .{ operator, right.typeName() });
}
fn evalBangOperator(right: object.Object) object.Object {
return switch (right) {
.boolean => |b| nativeBoolToObject(!b.value),
.null => TRUE,
else => FALSE,
};
}
fn evalMinusPrefixOperator(allocator: std.mem.Allocator, right: object.Object) EvalError!object.Object {
return switch (right) {
.integer => |i| .{ .integer = .{ .value = -i.value } },
else => newError(allocator, "unknown operator: -{s}", .{right.typeName()}),
};
}
Infix evaluation #
The order of the checks here determines the error messages. Two integers go to integer arithmetic. Two strings support + and nothing else. Two booleans support == and !=. After that, if the types differ it’s a type mismatch, and if they’re the same type but we got here anyway it’s an unknown operator. Comparing an integer to a boolean with == is a type mismatch in Monkey, not false. That’s a stricter choice than most dynamic languages make and it’s a one-line change if you disagree.
Division checks for zero and returns a Monkey error instead of letting Zig panic. We don’t do anything about integer overflow, which will trip a safety check in Debug builds and wrap silently in ReleaseFast. Deciding what 9223372036854775807 + 1 should mean in Monkey is left to you.
fn evalInfixExpression(
allocator: std.mem.Allocator,
operator: []const u8,
left: object.Object,
right: object.Object,
) EvalError!object.Object {
if (left == .integer and right == .integer) {
return evalIntegerInfixExpression(allocator, operator, left.integer.value, right.integer.value);
}
if (left == .string and right == .string) {
if (std.mem.eql(u8, operator, "+")) {
const new_val = try std.fmt.allocPrint(allocator, "{s}{s}", .{ left.string.value, right.string.value });
return .{ .string = .{ .value = new_val } };
}
return newError(allocator, "unknown operator: STRING {s} STRING", .{operator});
}
if (left == .boolean and right == .boolean) {
if (std.mem.eql(u8, operator, "==")) return nativeBoolToObject(left.boolean.value == right.boolean.value);
if (std.mem.eql(u8, operator, "!=")) return nativeBoolToObject(left.boolean.value != right.boolean.value);
}
if (left.objectType() != right.objectType()) {
return newError(allocator, "type mismatch: {s} {s} {s}", .{ left.typeName(), operator, right.typeName() });
}
return newError(allocator, "unknown operator: {s} {s} {s}", .{ left.typeName(), operator, right.typeName() });
}
fn evalIntegerInfixExpression(allocator: std.mem.Allocator, operator: []const u8, left: i64, right: i64) EvalError!object.Object {
if (std.mem.eql(u8, operator, "+")) return .{ .integer = .{ .value = left + right } };
if (std.mem.eql(u8, operator, "-")) return .{ .integer = .{ .value = left - right } };
if (std.mem.eql(u8, operator, "*")) return .{ .integer = .{ .value = left * right } };
if (std.mem.eql(u8, operator, "/")) {
if (right == 0) return newError(allocator, "division by zero", .{});
return .{ .integer = .{ .value = @divTrunc(left, right) } };
}
if (std.mem.eql(u8, operator, "<")) return nativeBoolToObject(left < right);
if (std.mem.eql(u8, operator, ">")) return nativeBoolToObject(left > right);
if (std.mem.eql(u8, operator, "==")) return nativeBoolToObject(left == right);
if (std.mem.eql(u8, operator, "!=")) return nativeBoolToObject(left != right);
return newError(allocator, "unknown operator: INTEGER {s} INTEGER", .{operator});
}
Conditionals and truthiness #
Because if is an expression it has to produce a value, and when the condition is false and there’s no else that value is NULL. Truthiness is deliberately simple: null and false are falsy, everything else is truthy, including 0 and "". That’s different from C and JavaScript and it’s the kind of decision you get to make when it’s your language.
fn evalIfExpression(allocator: std.mem.Allocator, ie: ast.IfExpression, env: *Environment) EvalError!object.Object {
const condition = try evalExpression(allocator, ie.condition.*, env);
if (isError(condition)) return condition;
if (isTruthy(condition)) {
return evalBlockStatement(allocator, ie.consequence, env);
} else if (ie.alternative) |alt| {
return evalBlockStatement(allocator, alt, env);
} else {
return NULL;
}
}
fn isTruthy(obj: object.Object) bool {
return switch (obj) {
.null => false,
.boolean => |b| b.value,
else => true, // integers (including 0), strings, etc. are truthy
};
}
Identifiers and function application #
evalIdentifier is just an environment lookup with an error for the miss. applyFunction is where the environment chain from earlier gets built. For a user-defined function it creates a new enclosed environment whose outer is the environment the function captured, binds each argument to the matching parameter name, and evaluates the body in that environment. Then it unwraps any ReturnValue, because a function call is a boundary. Builtins skip all of that and just get called with the argument slice, we’ll fill those in next chapter.
We check the argument count before binding. The Go book doesn’t, and calling a two-parameter function with one argument will index past the end of args. In Zig that’s a safety panic in Debug and undefined behavior in ReleaseFast. Neither is a reasonable response to a typo in a Monkey program, so it’s a Monkey error instead.
fn evalIdentifier(allocator: std.mem.Allocator, id: ast.Identifier, env: *Environment) EvalError!object.Object {
if (env.get(id.value)) |val| return val;
return newError(allocator, "identifier not found: {s}", .{id.value});
}
fn applyFunction(allocator: std.mem.Allocator, func: object.Object, args: []const object.Object) EvalError!object.Object {
return switch (func) {
.function => |f| {
if (args.len != f.parameters.len) {
return newError(allocator, "wrong number of arguments: expected {d}, got {d}", .{ f.parameters.len, args.len });
}
// IMPORTANT: The enclosed environment must be heap-allocated.
// If it were stack-allocated, closures returned from this function
// would hold a dangling pointer to the destroyed stack frame.
// I filled 32GB of ram and could sear a steak on my laptop making this mistake.
const extended_env = try allocator.create(Environment);
extended_env.* = Environment.initEnclosed(allocator, f.env);
for (f.parameters, 0..) |param, i| {
try extended_env.set(param.value, args[i]);
}
const result = try evalBlockStatement(allocator, f.body, extended_env);
// Unwrap return value so it does not bubble past the function boundary.
return switch (result) {
.return_value => |rv| rv.value.*,
else => result,
};
},
.builtin => |b| b.func(allocator, args),
else => newError(allocator, "not a function: {s}", .{func.typeName()}),
};
}
Indexing and hash literals #
Array indexing with an out-of-range index returns NULL rather than an error, which matches the Go book. Hash indexing converts the index to a HashKey and looks it up, again with NULL for a miss. evalHashLiteral evaluates every key and value expression, so keys can be computed, {"thr" + "ee": 3} works. Because Hash.pairs stores the original key object next to the value, we can still print or return the real key later even though the map is indexed by the hashed form.
fn evalIndexExpression(allocator: std.mem.Allocator, left: object.Object, index: object.Object) EvalError!object.Object {
if (left == .array and index == .integer) return evalArrayIndexExpression(left, index);
if (left == .hash) return evalHashIndexExpression(allocator, left, index);
return newError(allocator, "index operator not supported: {s}", .{left.typeName()});
}
fn evalArrayIndexExpression(array: object.Object, index: object.Object) object.Object {
const elements = array.array.elements;
const idx = index.integer.value;
const max: i64 = @as(i64, @intCast(elements.len)) - 1;
if (idx < 0 or idx > max) return NULL;
return elements[@intCast(idx)];
}
fn evalHashIndexExpression(allocator: std.mem.Allocator, hash_obj: object.Object, index: object.Object) EvalError!object.Object {
const hash = hash_obj.hash;
const key = index.hashKey() orelse
return newError(allocator, "unusable as hash key: {s}", .{index.typeName()});
const pair = hash.pairs.get(key) orelse return NULL;
return pair.value;
}
fn evalHashLiteral(allocator: std.mem.Allocator, node: ast.HashLiteral, env: *Environment) EvalError!object.Object {
var pairs = std.AutoHashMap(object.HashKey, object.HashPair).init(allocator);
for (node.pairs) |pair| {
const key = try evalExpression(allocator, pair.key, env);
if (isError(key)) return key;
const hash_key = key.hashKey() orelse
return newError(allocator, "unusable as hash key: {s}", .{key.typeName()});
const value = try evalExpression(allocator, pair.value, env);
if (isError(value)) return value;
try pairs.put(hash_key, .{ .key = key, .value = value });
}
return .{ .hash = .{ .pairs = pairs } };
}
Complete evaluator.zig
#
const std = @import("std");
const ast = @import("ast.zig");
const object = @import("object.zig");
const Environment = @import("environment.zig").Environment;
const EvalError = std.mem.Allocator.Error;
const TRUE = object.Object{ .boolean = .{ .value = true } };
const FALSE = object.Object{ .boolean = .{ .value = false } };
const NULL = object.Object{ .null = .{} };
fn nativeBoolToObject(value: bool) object.Object {
return if (value) TRUE else FALSE;
}
fn isError(obj: object.Object) bool {
return switch (obj) {
.err => true,
else => false,
};
}
fn newError(allocator: std.mem.Allocator, comptime fmt: []const u8, args: anytype) EvalError!object.Object {
const message = try std.fmt.allocPrint(allocator, fmt, args);
return .{ .err = .{ .message = message } };
}
pub fn evalProgram(allocator: std.mem.Allocator, program: ast.Program, env: *Environment) EvalError!object.Object {
var result: object.Object = NULL;
for (program.statements) |stmt| {
result = try evalStatement(allocator, stmt, env);
switch (result) {
.return_value => |rv| return rv.value.*,
.err => return result,
else => {},
}
}
return result;
}
fn evalBlockStatement(allocator: std.mem.Allocator, block: ast.BlockStatement, env: *Environment) EvalError!object.Object {
var result: object.Object = NULL;
for (block.statements) |stmt| {
result = try evalStatement(allocator, stmt, env);
switch (result) {
.return_value, .err => return result,
else => {},
}
}
return result;
}
fn evalStatement(allocator: std.mem.Allocator, stmt: ast.Statement, env: *Environment) EvalError!object.Object {
return switch (stmt) {
.expression_statement => |es| try evalExpression(allocator, es.expression, env),
.let_statement => |ls| {
const val = try evalExpression(allocator, ls.value, env);
if (isError(val)) return val;
try env.set(ls.name, val);
return NULL;
},
.return_statement => |rs| {
const val = try evalExpression(allocator, rs.value, env);
if (isError(val)) return val;
const val_ptr = try allocator.create(object.Object);
val_ptr.* = val;
return .{ .return_value = .{ .value = val_ptr } };
},
};
}
fn evalExpression(allocator: std.mem.Allocator, expr: ast.Expression, env: *Environment) EvalError!object.Object {
return switch (expr) {
.integer_literal => |il| .{ .integer = .{ .value = il.value } },
.boolean => |b| nativeBoolToObject(b.value),
.string_literal => |s| .{ .string = .{ .value = s.value } },
.prefix => |p| {
const right = try evalExpression(allocator, p.right.*, env);
if (isError(right)) return right;
return evalPrefixExpression(allocator, p.operator, right);
},
.infix => |i| {
const left = try evalExpression(allocator, i.left.*, env);
if (isError(left)) return left;
const right = try evalExpression(allocator, i.right.*, env);
if (isError(right)) return right;
return evalInfixExpression(allocator, i.operator, left, right);
},
.if_expression => |ie| try evalIfExpression(allocator, ie, env),
.identifier => |id| evalIdentifier(allocator, id, env),
.function_literal => |fl| .{ .function = .{
.parameters = fl.parameters,
.body = fl.body,
.env = env,
} },
.call => |c| {
const func = try evalExpression(allocator, c.function.*, env);
if (isError(func)) return func;
var args: std.ArrayList(object.Object) = .empty;
for (c.arguments) |arg_expr| {
const arg = try evalExpression(allocator, arg_expr, env);
if (isError(arg)) return arg;
try args.append(allocator, arg);
}
return applyFunction(allocator, func, args.items);
},
.array_literal => |a| {
var elements: std.ArrayList(object.Object) = .empty;
for (a.elements) |elem_expr| {
const elem = try evalExpression(allocator, elem_expr, env);
if (isError(elem)) return elem;
try elements.append(allocator, elem);
}
return .{ .array = .{ .elements = try elements.toOwnedSlice(allocator) } };
},
.index_expression => |ie| {
const left = try evalExpression(allocator, ie.left.*, env);
if (isError(left)) return left;
const index = try evalExpression(allocator, ie.index.*, env);
if (isError(index)) return index;
return evalIndexExpression(allocator, left, index);
},
.hash_literal => |h| try evalHashLiteral(allocator, h, env),
};
}
fn evalPrefixExpression(allocator: std.mem.Allocator, operator: []const u8, right: object.Object) EvalError!object.Object {
if (std.mem.eql(u8, operator, "!")) {
return evalBangOperator(right);
} else if (std.mem.eql(u8, operator, "-")) {
return evalMinusPrefixOperator(allocator, right);
}
return newError(allocator, "unknown operator: {s}{s}", .{ operator, right.typeName() });
}
fn evalBangOperator(right: object.Object) object.Object {
return switch (right) {
.boolean => |b| nativeBoolToObject(!b.value),
.null => TRUE,
else => FALSE,
};
}
fn evalMinusPrefixOperator(allocator: std.mem.Allocator, right: object.Object) EvalError!object.Object {
return switch (right) {
.integer => |i| .{ .integer = .{ .value = -i.value } },
else => newError(allocator, "unknown operator: -{s}", .{right.typeName()}),
};
}
fn evalInfixExpression(
allocator: std.mem.Allocator,
operator: []const u8,
left: object.Object,
right: object.Object,
) EvalError!object.Object {
if (left == .integer and right == .integer) {
return evalIntegerInfixExpression(allocator, operator, left.integer.value, right.integer.value);
}
if (left == .string and right == .string) {
if (std.mem.eql(u8, operator, "+")) {
const new_val = try std.fmt.allocPrint(allocator, "{s}{s}", .{ left.string.value, right.string.value });
return .{ .string = .{ .value = new_val } };
}
return newError(allocator, "unknown operator: STRING {s} STRING", .{operator});
}
if (left == .boolean and right == .boolean) {
if (std.mem.eql(u8, operator, "==")) return nativeBoolToObject(left.boolean.value == right.boolean.value);
if (std.mem.eql(u8, operator, "!=")) return nativeBoolToObject(left.boolean.value != right.boolean.value);
}
if (left.objectType() != right.objectType()) {
return newError(allocator, "type mismatch: {s} {s} {s}", .{ left.typeName(), operator, right.typeName() });
}
return newError(allocator, "unknown operator: {s} {s} {s}", .{ left.typeName(), operator, right.typeName() });
}
fn evalIntegerInfixExpression(allocator: std.mem.Allocator, operator: []const u8, left: i64, right: i64) EvalError!object.Object {
if (std.mem.eql(u8, operator, "+")) return .{ .integer = .{ .value = left + right } };
if (std.mem.eql(u8, operator, "-")) return .{ .integer = .{ .value = left - right } };
if (std.mem.eql(u8, operator, "*")) return .{ .integer = .{ .value = left * right } };
if (std.mem.eql(u8, operator, "/")) {
if (right == 0) return newError(allocator, "division by zero", .{});
return .{ .integer = .{ .value = @divTrunc(left, right) } };
}
if (std.mem.eql(u8, operator, "<")) return nativeBoolToObject(left < right);
if (std.mem.eql(u8, operator, ">")) return nativeBoolToObject(left > right);
if (std.mem.eql(u8, operator, "==")) return nativeBoolToObject(left == right);
if (std.mem.eql(u8, operator, "!=")) return nativeBoolToObject(left != right);
return newError(allocator, "unknown operator: INTEGER {s} INTEGER", .{operator});
}
fn evalIfExpression(allocator: std.mem.Allocator, ie: ast.IfExpression, env: *Environment) EvalError!object.Object {
const condition = try evalExpression(allocator, ie.condition.*, env);
if (isError(condition)) return condition;
if (isTruthy(condition)) {
return evalBlockStatement(allocator, ie.consequence, env);
} else if (ie.alternative) |alt| {
return evalBlockStatement(allocator, alt, env);
} else {
return NULL;
}
}
fn isTruthy(obj: object.Object) bool {
return switch (obj) {
.null => false,
.boolean => |b| b.value,
else => true, // integers (including 0), strings, etc. are truthy
};
}
fn evalIdentifier(allocator: std.mem.Allocator, id: ast.Identifier, env: *Environment) EvalError!object.Object {
if (env.get(id.value)) |val| return val;
return newError(allocator, "identifier not found: {s}", .{id.value});
}
fn applyFunction(allocator: std.mem.Allocator, func: object.Object, args: []const object.Object) EvalError!object.Object {
return switch (func) {
.function => |f| {
if (args.len != f.parameters.len) {
return newError(allocator, "wrong number of arguments: expected {d}, got {d}", .{ f.parameters.len, args.len });
}
// IMPORTANT: The enclosed environment must be heap-allocated.
// If it were stack-allocated, closures returned from this function
// would hold a dangling pointer to the destroyed stack frame.
// I filled 32GB of ram and could sear a steak on my laptop making this mistake.
const extended_env = try allocator.create(Environment);
extended_env.* = Environment.initEnclosed(allocator, f.env);
for (f.parameters, 0..) |param, i| {
try extended_env.set(param.value, args[i]);
}
const result = try evalBlockStatement(allocator, f.body, extended_env);
// Unwrap return value so it does not bubble past the function boundary.
return switch (result) {
.return_value => |rv| rv.value.*,
else => result,
};
},
.builtin => |b| b.func(allocator, args),
else => newError(allocator, "not a function: {s}", .{func.typeName()}),
};
}
fn evalIndexExpression(allocator: std.mem.Allocator, left: object.Object, index: object.Object) EvalError!object.Object {
if (left == .array and index == .integer) return evalArrayIndexExpression(left, index);
if (left == .hash) return evalHashIndexExpression(allocator, left, index);
return newError(allocator, "index operator not supported: {s}", .{left.typeName()});
}
fn evalArrayIndexExpression(array: object.Object, index: object.Object) object.Object {
const elements = array.array.elements;
const idx = index.integer.value;
const max: i64 = @as(i64, @intCast(elements.len)) - 1;
if (idx < 0 or idx > max) return NULL;
return elements[@intCast(idx)];
}
fn evalHashIndexExpression(allocator: std.mem.Allocator, hash_obj: object.Object, index: object.Object) EvalError!object.Object {
const hash = hash_obj.hash;
const key = index.hashKey() orelse
return newError(allocator, "unusable as hash key: {s}", .{index.typeName()});
const pair = hash.pairs.get(key) orelse return NULL;
return pair.value;
}
fn evalHashLiteral(allocator: std.mem.Allocator, node: ast.HashLiteral, env: *Environment) EvalError!object.Object {
var pairs = std.AutoHashMap(object.HashKey, object.HashPair).init(allocator);
for (node.pairs) |pair| {
const key = try evalExpression(allocator, pair.key, env);
if (isError(key)) return key;
const hash_key = key.hashKey() orelse
return newError(allocator, "unusable as hash key: {s}", .{key.typeName()});
const value = try evalExpression(allocator, pair.value, env);
if (isError(value)) return value;
try pairs.put(hash_key, .{ .key = key, .value = value });
}
return .{ .hash = .{ .pairs = pairs } };
}
Tests #
The evaluator tests need the lexer and parser, so they go in a separate file src/evaluator_test.zig. The testEval helper runs the whole pipeline on a string and returns the resulting object. Most tests then just reach into the union with .integer.value or .err.message, which will fail the test with a panic if the tag is wrong. That’s crude but it tells you exactly which input misbehaved.
const std = @import("std");
const object = @import("object.zig");
const Environment = @import("environment.zig").Environment;
const evalProgram = @import("evaluator.zig").evalProgram;
const Lexer = @import("lexer.zig").Lexer;
const Parser = @import("parser.zig").Parser;
fn testEval(allocator: std.mem.Allocator, input: []const u8) !object.Object {
var l = Lexer.init(input);
var p = Parser.init(allocator, &l);
const program = try p.parseProgram();
var env = Environment.init(allocator);
return try evalProgram(allocator, program, &env);
}
test "eval integer expression" {
const tests = [_]struct { input: []const u8, expected: i64 }{
.{ .input = "5", .expected = 5 },
.{ .input = "10", .expected = 10 },
.{ .input = "-5", .expected = -5 },
.{ .input = "-10", .expected = -10 },
.{ .input = "5 + 5 + 5 + 5 - 10", .expected = 10 },
.{ .input = "2 * 2 * 2 * 2 * 2", .expected = 32 },
.{ .input = "-50 + 100 + -50", .expected = 0 },
.{ .input = "5 * 2 + 10", .expected = 20 },
.{ .input = "5 + 2 * 10", .expected = 25 },
.{ .input = "50 / 2 * 2 + 10", .expected = 60 },
.{ .input = "(5 + 10 * 2 + 15 / 3) * 2 + -10", .expected = 50 },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.integer.value);
}
}
test "eval boolean expression" {
const tests = [_]struct { input: []const u8, expected: bool }{
.{ .input = "true", .expected = true },
.{ .input = "false", .expected = false },
.{ .input = "1 < 2", .expected = true },
.{ .input = "1 > 2", .expected = false },
.{ .input = "1 == 1", .expected = true },
.{ .input = "1 != 1", .expected = false },
.{ .input = "true == true", .expected = true },
.{ .input = "true != false", .expected = true },
.{ .input = "(1 < 2) == true", .expected = true },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.boolean.value);
}
}
test "bang operator" {
const tests = [_]struct { input: []const u8, expected: bool }{
.{ .input = "!true", .expected = false },
.{ .input = "!false", .expected = true },
.{ .input = "!5", .expected = false },
.{ .input = "!!true", .expected = true },
.{ .input = "!!false", .expected = false },
.{ .input = "!!5", .expected = true },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.boolean.value);
}
}
test "if else" {
// expected null means we want the NULL object back.
const tests = [_]struct { input: []const u8, expected: ?i64 }{
.{ .input = "if (true) { 10 }", .expected = 10 },
.{ .input = "if (false) { 10 }", .expected = null },
.{ .input = "if (1) { 10 }", .expected = 10 },
.{ .input = "if (1 < 2) { 10 }", .expected = 10 },
.{ .input = "if (1 > 2) { 10 }", .expected = null },
.{ .input = "if (1 > 2) { 10 } else { 20 }", .expected = 20 },
.{ .input = "if (1 < 2) { 10 } else { 20 }", .expected = 10 },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
if (tt.expected) |expected| {
try std.testing.expectEqual(expected, result.integer.value);
} else {
try std.testing.expect(result == .null);
}
}
}
test "return statements" {
const tests = [_]struct { input: []const u8, expected: i64 }{
.{ .input = "return 10;", .expected = 10 },
.{ .input = "return 10; 9;", .expected = 10 },
.{ .input = "return 2 * 5; 9;", .expected = 10 },
.{ .input = "9; return 2 * 5; 9;", .expected = 10 },
// nested return, if evalBlockStatement unwrapped this would be 1.
.{ .input = "if (10 > 1) { if (10 > 1) { return 10; } return 1; }", .expected = 10 },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.integer.value);
}
}
test "let statements" {
const tests = [_]struct { input: []const u8, expected: i64 }{
.{ .input = "let a = 5; a;", .expected = 5 },
.{ .input = "let a = 5 * 5; a;", .expected = 25 },
.{ .input = "let a = 5; let b = a; b;", .expected = 5 },
.{ .input = "let a = 5; let b = a; let c = a + b + 5; c;", .expected = 15 },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.integer.value);
}
}
test "function object" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), "fn(x) { x + 2; };");
const func = result.function;
try std.testing.expectEqual(@as(usize, 1), func.parameters.len);
try std.testing.expectEqualStrings("x", func.parameters[0].value);
const body = func.body.statements[0].expression_statement.expression;
try std.testing.expectEqualStrings("(x + 2)", try body.string(arena.allocator()));
}
test "function application" {
const tests = [_]struct { input: []const u8, expected: i64 }{
.{ .input = "let identity = fn(x) { x; }; identity(5);", .expected = 5 },
.{ .input = "let identity = fn(x) { return x; }; identity(5);", .expected = 5 },
.{ .input = "let double = fn(x) { x * 2; }; double(5);", .expected = 10 },
.{ .input = "let add = fn(x, y) { x + y; }; add(5, 5);", .expected = 10 },
.{ .input = "let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", .expected = 20 },
.{ .input = "fn(x) { x; }(5)", .expected = 5 },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqual(tt.expected, result.integer.value);
}
}
test "closures" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const input =
\\let newAdder = fn(x) {
\\ fn(y) { x + y; };
\\};
\\let addTwo = newAdder(2);
\\addTwo(3);
;
const result = try testEval(arena.allocator(), input);
try std.testing.expectEqual(@as(i64, 5), result.integer.value);
}
test "strings" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var result = try testEval(arena.allocator(), "\"Hello World!\"");
try std.testing.expectEqualStrings("Hello World!", result.string.value);
result = try testEval(arena.allocator(), "\"Hello\" + \" \" + \"World!\"");
try std.testing.expectEqualStrings("Hello World!", result.string.value);
}
test "arrays" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), "[1, 2 * 2, 3 + 3]");
try std.testing.expectEqual(@as(usize, 3), result.array.elements.len);
try std.testing.expectEqual(@as(i64, 1), result.array.elements[0].integer.value);
try std.testing.expectEqual(@as(i64, 4), result.array.elements[1].integer.value);
try std.testing.expectEqual(@as(i64, 6), result.array.elements[2].integer.value);
const tests = [_]struct { input: []const u8, expected: ?i64 }{
.{ .input = "[1, 2, 3][0]", .expected = 1 },
.{ .input = "[1, 2, 3][2]", .expected = 3 },
.{ .input = "let i = 0; [1][i];", .expected = 1 },
.{ .input = "let myArray = [1, 2, 3]; myArray[2];", .expected = 3 },
.{ .input = "let myArray = [1, 2, 3]; myArray[0] + myArray[1] + myArray[2];", .expected = 6 },
.{ .input = "[1, 2, 3][3]", .expected = null },
.{ .input = "[1, 2, 3][-1]", .expected = null },
};
for (tests) |tt| {
const r = try testEval(arena.allocator(), tt.input);
if (tt.expected) |expected| {
try std.testing.expectEqual(expected, r.integer.value);
} else {
try std.testing.expect(r == .null);
}
}
}
test "hashes" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const input =
\\let two = "two";
\\{
\\ "one": 10 - 9,
\\ two: 1 + 1,
\\ "thr" + "ee": 6 / 2,
\\ 4: 4,
\\ true: 5,
\\ false: 6
\\}
;
const result = try testEval(arena.allocator(), input);
try std.testing.expectEqual(@as(u32, 6), result.hash.pairs.count());
const str_key = object.Object{ .string = .{ .value = "one" } };
const int_key = object.Object{ .integer = .{ .value = 4 } };
const bool_key = object.Object{ .boolean = .{ .value = true } };
const one = result.hash.pairs.get(str_key.hashKey().?).?;
try std.testing.expectEqual(@as(i64, 1), one.value.integer.value);
const four = result.hash.pairs.get(int_key.hashKey().?).?;
try std.testing.expectEqual(@as(i64, 4), four.value.integer.value);
const five = result.hash.pairs.get(bool_key.hashKey().?).?;
try std.testing.expectEqual(@as(i64, 5), five.value.integer.value);
const tests = [_]struct { input: []const u8, expected: ?i64 }{
.{ .input = "{\"foo\": 5}[\"foo\"]", .expected = 5 },
.{ .input = "{\"foo\": 5}[\"bar\"]", .expected = null },
.{ .input = "let key = \"foo\"; {\"foo\": 5}[key]", .expected = 5 },
.{ .input = "{}[\"foo\"]", .expected = null },
.{ .input = "{5: 5}[5]", .expected = 5 },
.{ .input = "{true: 5}[true]", .expected = 5 },
};
for (tests) |tt| {
const r = try testEval(arena.allocator(), tt.input);
if (tt.expected) |expected| {
try std.testing.expectEqual(expected, r.integer.value);
} else {
try std.testing.expect(r == .null);
}
}
}
test "error handling" {
const tests = [_]struct { input: []const u8, expected: []const u8 }{
.{ .input = "5 + true;", .expected = "type mismatch: INTEGER + BOOLEAN" },
.{ .input = "5 + true; 5;", .expected = "type mismatch: INTEGER + BOOLEAN" },
.{ .input = "-true", .expected = "unknown operator: -BOOLEAN" },
.{ .input = "true + false;", .expected = "unknown operator: BOOLEAN + BOOLEAN" },
.{ .input = "5; true + false; 5", .expected = "unknown operator: BOOLEAN + BOOLEAN" },
.{ .input = "if (10 > 1) { true + false; }", .expected = "unknown operator: BOOLEAN + BOOLEAN" },
.{ .input = "if (10 > 1) { if (10 > 1) { return true + false; } return 1; }", .expected = "unknown operator: BOOLEAN + BOOLEAN" },
.{ .input = "foobar", .expected = "identifier not found: foobar" },
.{ .input = "\"Hello\" - \"World\"", .expected = "unknown operator: STRING - STRING" },
.{ .input = "{\"name\": \"Monkey\"}[fn(x) { x }];", .expected = "unusable as hash key: FUNCTION" },
.{ .input = "5 / 0", .expected = "division by zero" },
.{ .input = "fn(a, b) { a }(1)", .expected = "wrong number of arguments: expected 2, got 1" },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try testEval(arena.allocator(), tt.input);
try std.testing.expectEqualStrings(tt.expected, result.err.message);
}
}
Verify it works #
Make sure you uncommented the evaluator_test.zig line in build.zig, then run zig build test. No output means all tests passed.
What we built #
This is the chapter where Monkey started running. You now have a working tree-walking interpreter with integers, booleans, strings, arrays, hashes, conditionals, first-class functions and closures. The ideas worth keeping:
- Syntax and values are different things. The AST describes a computation, objects are the results of performing it.
- A tree-walking evaluator is one recursive function per kind of node. Evaluate the children, combine the results.
returnis implemented by wrapping the value and having every block pass the wrapper up unchanged. Only function and program boundaries unwrap it.- Environments are hash maps with a pointer to an outer environment. Lookup walks the chain. Functions capture the environment they were defined in, and that’s all a closure is.
- Monkey’s runtime errors are values, not Zig errors. Zig errors are reserved for the interpreter itself failing.
What’s missing is a way to interact with the outside world. There’s no len, no puts, and no way to run Monkey except from a test. Chapter 4 adds built-in functions and the REPL.