Source code --> Lexer --> tokens --> Parser --> AST --> Evaluator --> value
^^^^^^^^^^^ ^^^^^
the REPL feeds this end and prints this end
Two things are missing. Monkey has no way to talk to the outside world, there’s no len, no puts, nothing that can look inside a string or print to the screen. And you have no way to run Monkey except by writing a test. This chapter fixes both. We add the six built-in functions in builtins.zig, wire them into the evaluator, and write the REPL in main.zig.
REPL stands for Read Evaluate Print Loop, it’s the interactive prompt you’ve used in Python or Node. Read a line from the user, run it through lexer, parser and evaluator, print the resulting object, go back to the top. It sounds simple, but it’s also where the memory decisions we’ve been making since chapter 2 finally get tested, because it’s the first time state has to survive from one program to the next.
Built-in functions (builtins.zig)
#
Some things can’t be written in Monkey. len("hello") needs to look inside a string, and Monkey has no way to do that. puts needs to do I/O. So the interpreter has to provide them, written in the host language and exposed to Monkey as if they were ordinary functions.
The design is small. A builtin is a Zig function pointer with a fixed signature: it gets an allocator and a slice of already-evaluated argument objects, and it returns an object. We wrap that pointer in a Builtin object (you saw the type in chapter 3) so a builtin can be stored in a variable, passed to another function, and called through applyFunction like anything else. Errors follow the rule from chapter 3, they’re Monkey error values, not Zig errors. The one place we have to fudge that is when an allocation fails inside a builtin, since the signature doesn’t allow a Zig error we turn that into a Monkey error too.
Notice that rest and push build new arrays instead of modifying the one they were given. Monkey arrays are immutable, and since objects are copied by value and share their element slices, mutating in place would change every copy. The immutability is what makes the by-value object design safe.
const std = @import("std");
const object = @import("object.zig");
pub const BuiltinFn = object.BuiltinFn;
pub fn lookup(name: []const u8) ?BuiltinFn {
const map = std.StaticStringMap(BuiltinFn).initComptime(.{
.{ "len", &builtinLen },
.{ "first", &builtinFirst },
.{ "last", &builtinLast },
.{ "rest", &builtinRest },
.{ "push", &builtinPush },
.{ "puts", &builtinPuts },
});
return map.get(name);
}
fn builtinLen(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
_ = allocator;
if (args.len != 1) return .{ .err = .{ .message = "wrong number of arguments to `len`" } };
return switch (args[0]) {
.string => |s| .{ .integer = .{ .value = @intCast(s.value.len) } },
.array => |a| .{ .integer = .{ .value = @intCast(a.elements.len) } },
else => .{ .err = .{ .message = "argument to `len` not supported" } },
};
}
fn builtinFirst(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
_ = allocator;
if (args.len != 1) return .{ .err = .{ .message = "wrong number of arguments to `first`" } };
return switch (args[0]) {
.array => |a| {
if (a.elements.len > 0) return a.elements[0];
return .{ .null = .{} };
},
else => .{ .err = .{ .message = "argument to `first` must be ARRAY" } },
};
}
fn builtinLast(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
_ = allocator;
if (args.len != 1) return .{ .err = .{ .message = "wrong number of arguments to `last`" } };
return switch (args[0]) {
.array => |a| {
if (a.elements.len > 0) return a.elements[a.elements.len - 1];
return .{ .null = .{} };
},
else => .{ .err = .{ .message = "argument to `last` must be ARRAY" } },
};
}
fn builtinRest(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
if (args.len != 1) return .{ .err = .{ .message = "wrong number of arguments to `rest`" } };
return switch (args[0]) {
.array => |a| {
if (a.elements.len == 0) return .{ .null = .{} };
const new_elements = allocator.dupe(object.Object, a.elements[1..]) catch {
return .{ .err = .{ .message = "allocation failed in `rest`" } };
};
return .{ .array = .{ .elements = new_elements } };
},
else => .{ .err = .{ .message = "argument to `rest` must be ARRAY" } },
};
}
fn builtinPush(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
if (args.len != 2) return .{ .err = .{ .message = "wrong number of arguments to `push`" } };
return switch (args[0]) {
.array => |a| {
const new_elements = allocator.alloc(object.Object, a.elements.len + 1) catch {
return .{ .err = .{ .message = "allocation failed in `push`" } };
};
@memcpy(new_elements[0..a.elements.len], a.elements);
new_elements[a.elements.len] = args[1];
return .{ .array = .{ .elements = new_elements } };
},
else => .{ .err = .{ .message = "first argument to `push` must be ARRAY" } },
};
}
fn builtinPuts(allocator: std.mem.Allocator, args: []const object.Object) object.Object {
for (args) |arg| {
const s = arg.inspect(allocator) catch {
return .{ .err = .{ .message = "allocation failed in `puts`" } };
};
std.debug.print("{s}\n", .{s});
}
return .{ .null = .{} };
}
puts prints with std.debug.print, which goes to stderr, same as everything else the REPL prints. That keeps us out of the standard library’s I/O machinery, which isn’t what this book is about. If you want real stdout, that’s a small change to make once you’re done.
Wiring builtins into evaluator.zig
#
Add the import at the top of evaluator.zig.
const std = @import("std");
const ast = @import("ast.zig");
const object = @import("object.zig");
const Environment = @import("environment.zig").Environment;
const builtins = @import("builtins.zig");
Update evalIdentifier
#
In chapter 3, evalIdentifier only checked the environment. Now add the builtins lookup as a fallback.
fn evalIdentifier(allocator: std.mem.Allocator, id: ast.Identifier, env: *Environment) EvalError!object.Object {
if (env.get(id.value)) |val| return val;
if (builtins.lookup(id.value)) |func| return .{ .builtin = .{ .func = func } };
return newError(allocator, "identifier not found: {s}", .{id.value});
}
The lookup order matters. Environment first, then builtins. This means a user can shadow a builtin with let len = 5;, which is what most languages do. The other common design is to pre-load the builtins into the global environment at startup. That works too, the difference is that with a fallback lookup the builtins can never be accidentally removed, and the environment stays empty until the user puts something in it.
That’s the entire change to the evaluator. Everything else, calling a builtin, passing one around, storing one in an array, already works because applyFunction had a .builtin case waiting since chapter 3.
Builtin and capstone tests #
Add these tests to evaluator_test.zig. They use the same testEval helper from chapter 3. The last two are the map and fibonacci programs from the introduction. Between them they hit closures, recursion, conditionals, arrays and three builtins, so if they pass, the interpreter is done.
test "builtin len" {
const tests = [_]struct { input: []const u8, expected_int: ?i64, expected_err: ?[]const u8 }{
.{ .input = "len(\"\")", .expected_int = 0, .expected_err = null },
.{ .input = "len(\"four\")", .expected_int = 4, .expected_err = null },
.{ .input = "len(\"hello world\")", .expected_int = 11, .expected_err = null },
.{ .input = "len([1, 2, 3])", .expected_int = 3, .expected_err = null },
.{ .input = "len(1)", .expected_int = null, .expected_err = "argument to `len` not supported" },
.{ .input = "len(\"one\", \"two\")", .expected_int = null, .expected_err = "wrong number of arguments to `len`" },
};
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_int) |expected| try std.testing.expectEqual(expected, result.integer.value);
if (tt.expected_err) |expected| try std.testing.expectEqualStrings(expected, result.err.message);
}
}
test "builtin array functions" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var result = try testEval(arena.allocator(), "first([1, 2, 3])");
try std.testing.expectEqual(@as(i64, 1), result.integer.value);
result = try testEval(arena.allocator(), "first([])");
try std.testing.expect(result == .null);
result = try testEval(arena.allocator(), "last([1, 2, 3])");
try std.testing.expectEqual(@as(i64, 3), result.integer.value);
result = try testEval(arena.allocator(), "rest([1, 2, 3])");
try std.testing.expectEqual(@as(usize, 2), result.array.elements.len);
try std.testing.expectEqual(@as(i64, 2), result.array.elements[0].integer.value);
try std.testing.expectEqual(@as(i64, 3), result.array.elements[1].integer.value);
result = try testEval(arena.allocator(), "push([1, 2], 3)");
try std.testing.expectEqual(@as(usize, 3), result.array.elements.len);
try std.testing.expectEqual(@as(i64, 3), result.array.elements[2].integer.value);
// push returns a new array, the original is untouched.
result = try testEval(arena.allocator(), "let a = [1, 2]; let b = push(a, 3); len(a)");
try std.testing.expectEqual(@as(i64, 2), result.integer.value);
// A user binding shadows a builtin.
result = try testEval(arena.allocator(), "let len = 5; len");
try std.testing.expectEqual(@as(i64, 5), result.integer.value);
}
test "map" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const input =
\\let map = fn(arr, f) {
\\ let iter = fn(arr, accumulated) {
\\ if (len(arr) == 0) {
\\ accumulated
\\ } else {
\\ iter(rest(arr), push(accumulated, f(first(arr))));
\\ }
\\ };
\\ iter(arr, []);
\\};
\\map([1, 2, 3, 4, 5], fn(x) { x * 2; });
;
const result = try testEval(arena.allocator(), input);
const expected = [_]i64{ 2, 4, 6, 8, 10 };
try std.testing.expectEqual(expected.len, result.array.elements.len);
for (expected, 0..) |value, i| {
try std.testing.expectEqual(value, result.array.elements[i].integer.value);
}
}
test "fibonacci" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const input =
\\let fibonacci = fn(x) {
\\ if (x == 0) {
\\ 0
\\ } else {
\\ if (x == 1) {
\\ return 1;
\\ } else {
\\ fibonacci(x - 1) + fibonacci(x - 2);
\\ }
\\ }
\\};
\\fibonacci(10);
;
const result = try testEval(arena.allocator(), input);
try std.testing.expectEqual(@as(i64, 55), result.integer.value);
}
The REPL (main.zig)
#
Here’s the loop we’re about to write.
flowchart TD
A[Print prompt, read a line] --> B{EOF?}
B -- Yes --> Z[Goodbye]
B -- No --> C[Lexer + Parser]
C --> D{Parser errors?}
D -- Yes --> E[Print the monkey face
and every error message] --> A
D -- No --> F[evalProgram with the
session environment]
F --> G[Print result.inspect] --> A
The one design decision that matters here is memory, and I want to walk through it because the obvious approach is wrong. In the tests, each program gets its own arena and everything is thrown away at the end. The obvious REPL design is the same thing per line: make an arena, lex, parse, evaluate, print, free the arena, loop. The problem is the environment. It has to survive across lines, otherwise let x = 5 on one line and x on the next can’t work. And the environment holds objects, and the objects point into memory the arena owns. A String object’s value is a slice into the line you typed (remember, the lexer never copies). A Function object’s parameters and body point at AST nodes. Free the per-line arena and every one of those becomes a dangling pointer, and the next line that touches x is reading freed memory. If you’re lucky it crashes.
So the REPL uses one arena for the whole session. Every line you type, every AST node, every object and every environment lives in it until you quit, and then it’s all freed at once. That’s the same strategy as the tests, just with a longer lifetime, and it’s the honest answer to “what’s the lifetime of a value in Monkey?” It lives as long as the session does. A real language would need a garbage collector to reclaim values that nothing refers to anymore, and writing one is the last exercise in the next chapter.
The arena sits on top of page_allocator and gets freed once, on the way out.
A small note on reading input. We read one byte at a time with std.posix.read straight from the stdin file descriptor. It’s slow and it’s not how you’d do it in a real program, but it’s ten lines with no dependency on the standard library’s I/O layer, which changes between Zig releases. Swap in a buffered reader if you like, it makes no difference to the interpreter.
const std = @import("std");
const Lexer = @import("lexer.zig").Lexer;
const Parser = @import("parser.zig").Parser;
const evaluator = @import("evaluator.zig");
const Environment = @import("environment.zig").Environment;
const PROMPT = ">> ";
const MONKEY_FACE =
\\ __,__
\\ .--. .-" "-. .--.
\\ / .. \/ .-. .-. \/ .. \
\\ | | '| / Y \ |' | |
\\ | \ \ \ 0 | 0 / / / |
\\ \ '- ,\.-"""""""-./, -' /
\\ ''-' /_ ^ ^ _\ '-''
\\ | \._ _./ |
\\ \ \ '~' / /
\\ '._ '-=-' _.'
\\ '-----'
;
fn readLine(allocator: std.mem.Allocator) !?[]u8 {
var line: std.ArrayList(u8) = .empty;
errdefer line.deinit(allocator);
while (true) {
var buf: [1]u8 = undefined;
const n = std.posix.read(std.posix.STDIN_FILENO, &buf) catch return null;
if (n == 0) {
// EOF (Ctrl-D).
if (line.items.len == 0) return null;
return try line.toOwnedSlice(allocator);
}
if (buf[0] == '\n') return try line.toOwnedSlice(allocator);
try line.append(allocator, buf[0]);
}
}
fn printParserErrors(errors: []const []const u8) void {
std.debug.print("{s}\n", .{MONKEY_FACE});
std.debug.print("Woops! We ran into some monkey business here!\n", .{});
std.debug.print(" parser errors:\n", .{});
for (errors) |err| std.debug.print("\t{s}\n", .{err});
}
pub fn main() !void {
// One arena for the whole session. Every line you type, every AST node,
// every object and every environment lives in here until you quit.
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();
var env = Environment.init(allocator);
std.debug.print("Welcome to the Monkey programming language!\n", .{});
std.debug.print("Feel free to type in commands\n", .{});
while (true) {
std.debug.print("{s}", .{PROMPT});
const line = try readLine(allocator) orelse break;
var l = Lexer.init(line);
var p = Parser.init(allocator, &l);
const program = p.parseProgram() catch |err| switch (err) {
error.ParseError => {
printParserErrors(p.errors.items);
continue;
},
error.OutOfMemory => return err,
};
if (p.errors.items.len > 0) {
printParserErrors(p.errors.items);
continue;
}
const result = try evaluator.evalProgram(allocator, program, &env);
const output = try result.inspect(allocator);
std.debug.print("{s}\n", .{output});
}
std.debug.print("\nGoodbye!\n", .{});
}
Both parser failure modes from chapter 2 end up in printParserErrors. A statement-level problem leaves messages in p.errors and parseProgram returns normally, so we check the list. An expression-level problem returns error.ParseError, and the message is still in the list, so we print it from the catch too. Either way the user sees what went wrong and not just the name of a Zig error.
The evaluator’s only Zig error is out of memory, so we let try end the program there. Monkey’s own errors come back as objects and get printed by inspect like any other value, with the ERROR: prefix.
Verify it works #
Run zig build test one more time. No output means all tests passed, including the capstone programs.
Then build and run the REPL.
zig build run
Here’s a real session. Note the null after each let, that’s the NULL object a let statement evaluates to. Making let silent in the REPL is a nice first exercise.
Welcome to the Monkey programming language!
Feel free to type in commands
>> let x = 5;
null
>> let add = fn(a, b) { a + b; };
null
>> add(x, 10)
15
>> len("hello")
5
>> push([1, 2], 3)
[1, 2, 3]
>> let newAdder = fn(x) { fn(y) { x + y; }; };
null
>> let addTwo = newAdder(2);
null
>> addTwo(3)
5
>> {"name": "Monkey"}["name"]
Monkey
>> 5 + true
ERROR: type mismatch: INTEGER + BOOLEAN
>> if (x
__,__
.--. .-" "-. .--.
/ .. \/ .-. .-. \/ .. \
| | '| / Y \ |' | |
| \ \ \ 0 | 0 / / / |
\ '- ,\.-"""""""-./, -' /
''-' /_ ^ ^ _\ '-''
| \._ _./ |
\ \ '~' / /
'._ '-=-' _.'
'-----'
Woops! We ran into some monkey business here!
parser errors:
expected next token to be rparen, got eof instead
>>
Press Ctrl-D to exit.
What we built #
A complete Monkey interpreter. Lexer, parser, evaluator, six builtins and a REPL. The ideas from this chapter:
- Builtins are host functions wrapped in an object type so they can be called, passed and stored like any Monkey function. The evaluator finds them by falling back from the environment to a static table.
- A REPL is the pipeline in a loop with an environment that outlives any single line. That’s what forces you to decide how long values live.
- With arenas and no garbage collector, the answer for Monkey is “as long as the session”. A per-line arena looks right and is a use-after-free waiting to happen.
Congrats, you’ve done it. The last chapter is a list of things to try next.