A Virtual Machine
The compiler produced an array of instructions. This chapter runs it, and the program that does so is the smallest one in the section.
There is an instruction pointer, an index into the array. Read the instruction it points at, move it forward, do what the instruction says, repeat. That loop is called fetch, decode, execute, and it is what a physical processor does too, which is why this one is called a virtual machine rather than an interpreter.
Everything the machine needs is a stack and a table of slots. Instructions never name their operands: they take them from the top of the stack and put the result back.
The program
const std = @import("std");
const lex = @import("lexer.zig");
const ast = @import("parser.zig");
const comp = @import("compiler.zig");
pub const Error = error{
StackOverflow,
StackUnderflow,
DivideByZero,
WriteFailed,
};
pub const Vm = struct {
chunk: *const comp.Chunk,
out: *std.Io.Writer,
stack: [64]i64 = undefined,
top: usize = 0,
/// One value per slot the compiler allocated. Reading a variable is an
/// array index now; the name it had is not present anywhere.
globals: [32]i64 = @splat(0),
/// Instructions executed, so the cost of the loop is visible.
steps: usize = 0,
fn push(vm: *Vm, value: i64) Error!void {
if (vm.top == vm.stack.len) return error.StackOverflow;
vm.stack[vm.top] = value;
vm.top += 1;
}
fn pop(vm: *Vm) Error!i64 {
if (vm.top == 0) return error.StackUnderflow;
vm.top -= 1;
return vm.stack[vm.top];
}
pub fn run(vm: *Vm) Error!void {
// The instruction pointer is an index, not a pointer, and moving it is
// the only control flow this machine has. A jump is an assignment.
var ip: usize = 0;
while (true) {
const instr = vm.chunk.code[ip];
ip += 1;
vm.steps += 1;
switch (instr.op) {
.push => try vm.push(instr.arg),
.load => try vm.push(vm.globals[@intCast(instr.arg)]),
.store => vm.globals[@intCast(instr.arg)] = try vm.pop(),
.neg => try vm.push(-(try vm.pop())),
// Order matters: the right operand was pushed last, so it
// comes off first. Getting this backwards makes `+` look
// correct and `-` silently wrong.
.add, .sub, .mul, .div, .lt, .eq => {
const right = try vm.pop();
const left = try vm.pop();
try vm.push(switch (instr.op) {
.add => left + right,
.sub => left - right,
.mul => left * right,
.div => if (right == 0) return error.DivideByZero else @divTrunc(left, right),
.lt => @intFromBool(left < right),
else => @intFromBool(left == right),
});
},
.print => try vm.out.print("{d}\n", .{try vm.pop()}),
.jmp => ip = @intCast(instr.arg),
.jmp_if_false => if (try vm.pop() == 0) {
ip = @intCast(instr.arg);
},
.halt => return,
}
}
}
};
fn execute(source: []const u8, out: *std.Io.Writer) !usize {
var tokens: [256]lex.Token = undefined;
var nodes: [256]ast.Node = undefined;
var code: [128]comp.Instr = undefined;
var chunk: comp.Chunk = .{ .code = &code };
try comp.compileSource(source, &tokens, &nodes, &chunk);
var vm: Vm = .{ .chunk = &chunk, .out = out };
try vm.run();
return vm.steps;
}
pub fn main(init: std.process.Init) !void {
var buf: [4096]u8 = undefined;
var stdout_writer = std.Io.File.stdout().writerStreaming(init.io, &buf);
const out = &stdout_writer.interface;
try out.writeAll("source -> bytecode -> answer\n");
const loop =
\\let total = 0;
\\while (total < 10) {
\\ total = total + 3;
\\}
\\print total;
;
const steps = try execute(loop, out);
try out.print("{d} instructions executed\n", .{steps});
// The same programs the tree-walking interpreter ran, for comparison.
try out.writeAll("\nsum of squares 1..5\n");
_ = try execute(
\\let total = 0;
\\let i = 1;
\\while (i < 6) {
\\ total = total + i * i;
\\ i = i + 1;
\\}
\\print total;
\\if (total == 55) { print 1; } else { print 0; }
, out);
try out.writeAll("\narithmetic\n");
_ = try execute("print 1 + 2 * 3; print (1 + 2) * 3; print 1 - 2 - 3; print (0 - 7) / 2;", out);
try out.flush();
}What just happened
The answers match the tree-walking interpreter exactly. 55 and 1 for the sum of squares, the same arithmetic results. That is the point worth stopping on: compiling and interpreting are not two computations. They are the same computation with the decisions made at different times. Anything else would mean one of them has a bug.
A jump is an assignment. ip = instr.arg, and that is the entire
implementation of while, if and else. All the structure the parser
carefully found is gone: the tree became a flat array where control flow is
arithmetic on an index. This is what “lowering” means, and it is why a
disassembly is hard to read and fast to run.
Operand order is the bug waiting in this loop. The right operand was pushed
last, so it must be popped first. Get it backwards and + and * still look
correct, because they commute, while - and / are silently wrong. A test
suite of 2 + 3 would pass.
45 instructions for a four-line program. The count is printed so the cost is visible rather than assumed. Each one is a switch dispatch, which is the price of a bytecode VM: real ones use computed goto or a JIT precisely because this switch runs billions of times.
There is no tree, and no names. The globals array is indexed by number.
Nothing in the running program knows a variable was ever called total, which
is why a stripped binary gives you a stack trace full of addresses and why
debug information is a separate thing you choose to keep.
The state of this language
This VM has no call and no ret, so a program using functions compiles to
bytecode that silently leaves them out. That is deliberate for one more
chapter: a calling convention is four separate decisions (where arguments live,
how a frame is addressed, who restores the instruction pointer, who cleans up
the arguments) and each has alternatives worth seeing.
A Calling Convention makes those decisions and runs
fact(5) through compiled bytecode. Read this VM first: it is the same
dispatch loop with two fewer opcodes.
Check yourself
The VM checks for stack overflow and underflow on every push and pop. A real one usually does not. Why is that safe?
Because the compiler is the one producing the bytecode, and it only emits
sequences that balance. add is only ever emitted after two operands, so a
correct compiler cannot produce an add that underflows. Real VMs move the
check to the moment bytecode is loaded, verifying it once rather than on
every instruction, which is exactly what the JVM’s bytecode verifier does and
why it exists. The checks are here because they are cheap at this size and
because a hand-written bad chunk should say so rather than read memory it does
not own.
If you have written C
The dispatch loop is while (1) switch (*ip++), and the standard trick to make
it faster is computed goto, a GCC extension where each instruction ends by
jumping directly to the next handler instead of returning to the top of the
switch. It helps because the branch predictor gets one indirect jump per
opcode rather than one shared one, and it is the single most common
optimisation in real interpreters.
The stack in C would be long stack[64]; int top;, which is what it is here.
The difference is that pushing past the end in C reads and writes past the
array with no complaint, and this chapter’s whole subject is a loop that runs
millions of times, so a bug there corrupts something far away and much later.
Where to go next
That is the pipeline: characters to tokens, tokens to a tree, the tree walked or lowered to instructions, and the instructions run. Every compiler and every interpreter you use is this, with more cases.
If you want the machine underneath rather than the language on top, Groundwork covers what a byte, an address and a stack frame actually are. If you would rather keep building tools, the Unix toolbox is seven more programs in the same spirit.