Chapter 13: The VM core

This chapter:

Give the bytecode VM its own real runtime value type, Value, and rename Chapter 8's tree-walker types out of the way to make room for the plain name.
Build the VM itself: a shared value stack, a call-frame stack, and a flat dispatch loop.
Make musc run execute through the real VM by default, --walk falling back to the tree-walker for comparison.
Revisit Chapter 9's benchmark with real bytecode-VM numbers, closing that chapter's loop.

Where we left off: musc compile produces correct bytecode for everything through Chapter 12, proven by disassembly and by hand-tracing jump offsets. Nothing has ever actually run one of these chunks.

13.1 Renaming Chapter 8 out of the way

Chapter 8's tree-walker has had a Value, a Function, and a Native_Fn since the chapter that introduced them, and Chapter 10 already flagged that this couldn't last: those names were always provisional, held by the tree-walker only because it got there first. This chapter is where that bill comes due.

// treewalk.odin, after this chapter's rename:
Walk_Value :: union {
	f64,
	string,
	bool,
	^Walk_Function,
	Walk_Native_Fn,
}

Value, Function, and Native_Fn become Walk_Value, Walk_Function, and Walk_Native_Fn, a mechanical, package-wide rename with no behavioural change whatsoever, every example this book has run through --walk still produces exactly the same output afterward. What it buys is a plain, unprefixed Value for the VM's own, real runtime representation, the one every future chapter through Chapter 21 actually means when it says "a Muspel value":

Value :: union {
	f64,
	string,
	bool,
	^Func_Proto,
	Builtin,
	^Struct_Instance,
	^Array_Instance,
}

Three differences from Walk_Value are worth naming. First, ^Func_Proto (Chapter 12's compiled function) stands in for ^Walk_Function directly, no separate "runtime function object" wrapping it: because Muspel's functions capture nothing (section 12.3's honestly-scoped closures), a compiled prototype already is a complete, callable value, with nothing left to attach to it at the moment it's created. Second, Builtin replaces Walk_Native_Fn, same idea, new name, still exactly one registered function (print) until Chapter 16 makes registration a real, curated API. Third, ^Struct_Instance and ^Array_Instance don't have a Walk_-prefixed predecessor to rename at all: they're new here, section 13.2's own reason why this VM's Value needs an arena and Chapter 8's tree-walker never did.

Struct_Instance :: struct {
	type_name:   string,
	field_names: []string,
	values:      []Value,
}

Array_Instance :: struct {
	values: []Value,
}

Both are arena-allocated (section 13.2), never on Odin's general heap the way Chapter 8's Walk_Struct_Instance/Walk_Array_Instance are: this is the point Chapter 5 flagged as not carrying over once a real VM instance exists to own an arena, and this is that promise kept.

value_is_truthy and values_equal are, deliberately, line-for-line the same logic as Chapter 8's walk_is_truthy/walk_values_equal: a value is truthy unless it's false or nil, and two values are only ever equal if they share both an underlying type and that type's own notion of equality. Muspel's semantics don't change between the tree-walker and the VM; only how fast they run does.

13.2 The VM struct

Frame :: struct {
	chunk: ^Chunk,
	ip:    int,
	base:  int,
}

VM :: struct {
	stack:       [dynamic]Value,
	frames:      [dynamic]Frame,
	globals:     map[string]Value,
	value_arena: Value_Arena,
}

stack is genuinely shared across every active call: Chapter 12's Call doesn't give a called function a stack of its own, it just marks out a region of this one stack, starting at base, for that call's locals to live in. Get_Local/Set_Local (Chapter 11) never touch an absolute stack index, only frame.base + slot, which is exactly what lets the same compiled function be called from anywhere, at any stack depth, and always find its own locals starting at slot 0 regardless of how deep the call happens to be.

frames is the call stack: pushing a Frame is the entirety of what a function call does to the VM's own state, and popping one is the entirety of what returning does. There's no separate, Odin-level call for "invoke a Muspel function" the way Chapter 8's call_function was a real, recursive Odin proc call; section 13.3 explains why that difference is the chapter's real point.

value_arena is section 10.5's Design decision, finally with somewhere to live: vm_init calls value_arena_init, sizing its backing buffer once, and every Make_Struct/Make_Array this VM instance ever executes allocates from it and nothing else.

13.3 The dispatch loop

vm_run :: proc(vm: ^VM) {
	for {
		frame := &vm.frames[len(vm.frames) - 1]
		op := Op_Code(read_u8(frame))
		switch op {
		// ... one case per Chapter 10 opcode ...
		}
	}
}

Design decision: a flat loop over the current frame's next instruction, Call pushing a new frame onto the same loop, rather than a recursive Odin proc call per Muspel call. Alternatives considered: the obvious, direct translation of Chapter 8's tree-walker, vm_call(fn, args) as a real Odin procedure that itself calls vm_run recursively on the callee, returning a value back up through Odin's own call stack exactly the way call_function does today. Trade-off: the recursive version is arguably simpler to read for exactly the depth Chapter 6 needed, at the cost of tying every Muspel call to a real Odin stack frame underneath it. That's invisible right up until a script needs to pause mid-call and be resumed later (Chapter 15's whole premise): a paused Odin call stack has no way to be detached, stored, and reattached, Odin gives no primitive for that. A flat loop over an explicit, VM-owned frames array has no such problem, because there's nothing hiding in Odin's own stack to lose: the entire state of every call in progress, arguments, locals, the instruction pointer, is sitting in plain data on the VM struct itself. Choice: the flat loop, Call appending to vm.frames and Return popping from it, both handled as ordinary cases inside the one loop that's already running, never a nested call into vm_run itself. This costs nothing extra today, and it's the entire reason Chapter 15 gets to add Yield as one opcode and a status enum instead of solving stack-switching from scratch.

Call and Return show the pattern directly:

case .Call:
	argc := int(read_u8(frame))
	callee := vm.stack[len(vm.stack) - 1 - argc]
	if native, ok := callee.(Builtin); ok {
		args := vm.stack[len(vm.stack) - argc:]
		result := native(vm, args)
		resize(&vm.stack, len(vm.stack) - argc - 1)
		append(&vm.stack, result)
	} else {
		fn := callee.(^Func_Proto)
		new_base := len(vm.stack) - argc
		append(&vm.frames, Frame{chunk = &fn.chunk, ip = 0, base = new_base})
	}

case .Return:
	result := pop(&vm.stack)
	old := pop(&vm.frames)
	if len(vm.frames) == 0 do return
	resize(&vm.stack, old.base - 1)
	append(&vm.stack, result)

Call's callee and arguments are already sitting on the stack exactly where Chapter 12 compiled them to be, new_base just names that position as the new frame's own base, nothing is copied or moved. Return discards the whole region a call occupied, old.base - 1 (the - 1 drops the callee itself, which was sitting one slot below its own arguments), in one resize, the flat design's real payoff: no per-local cleanup, no walking anything, one call frame's entire lifetime ends in a single array truncation.

Design decision: switch-based dispatch, not computed goto. Alternatives considered: threaded dispatch (direct or indirect), where each opcode handler ends by jumping straight to the next one's address, computed from the next opcode byte, rather than returning to a switch and re-testing which case to run. Trade-off: computed goto can measurably reduce branch-misprediction cost in a real, hot dispatch loop, real production VMs (CPython's, some Lua forks) use it. It costs portability and readability: it depends on a compiler extension (GCC/Clang's labels-as-values, which Odin doesn't expose as a language feature the way C does) and turns the opcode table into scattered jump targets instead of one readable switch. Choice: plain switch dispatch. It's simplest, it's what every opcode's stack-effect table (Chapter 10) maps onto directly, one case per row, and it's fast enough: section 13.6's real numbers, not a hand-wave, back that claim up.

13.4 Struct, array, and enum opcodes

Make_Struct, Get_Field/Set_Field, Make_Array, and Get_Index/Set_Index (Chapter 10) join the dispatch loop as five more ordinary cases, each a direct translation of the pseudocode Chapter 10 already walked through, now against a real stack and a real arena:

case .Make_Struct:
	idx := read_u8(frame)
	layout := frame.chunk.constants[idx].(^Struct_Layout)
	values := make([]Value, len(layout.field_names), value_arena_allocator(&vm.value_arena))
	for i := len(layout.field_indices) - 1; i >= 0; i -= 1 {
		v := pop(&vm.stack)
		fi := layout.field_indices[i]
		if fi >= 0 do values[fi] = v
	}
	inst := new(Struct_Instance, value_arena_allocator(&vm.value_arena))
	inst^ = Struct_Instance{type_name = layout.type_name, field_names = layout.field_names, values = values}
	append(&vm.stack, Value(inst))

case .Get_Field:
	idx := read_u8(frame)
	name := frame.chunk.constants[idx].(string)
	obj := pop(&vm.stack)
	if inst, ok := obj.(^Struct_Instance); ok {
		for n, i in inst.field_names {
			if n == name {
				append(&vm.stack, inst.values[i])
				break
			}
		}
	} else {
		runtime_error(vm, "'.%s' used on a non-struct value", name)
	}

Get_Field's operand is the field name itself, a constant-pool string, and the case scans inst.field_names for it at run time, exactly the by-name lookup section 10.6 named and defended as this book's honest trade-off against a full static type system. Make_Struct pops its pushed values in reverse, len(layout.field_indices) - 1 down to 0, because the compiler (section 11.4) pushed them in forward, literal-written order, last pushed is first popped, off the top of the stack.

Make_Array/Get_Index/Set_Index follow the identical shape, make/new against value_arena_allocator(&vm.value_arena) instead of context.allocator, and a bounds check on every index before touching arr.values, a graceful runtime_error (Chapter 18 gives this proc its full treatment) rather than an Odin-level out-of-bounds panic on a script's own mistake.

An enum member needs no dispatch case at all: it was already compiled straight to Constant (section 11.4), so by the time any of this runs, Phase.Attacking is indistinguishable from a numeric literal that happened to be written differently.

13.5 Wiring it up

musc run compiles and executes through the real VM by default now; --walk still runs the tree-walker, for exactly the comparisons this book keeps making:

if walk {
	interp := muspel.interp_init()
	muspel.exec_program(&interp, stmts)
} else {
	chunk := muspel.chunk_init()
	muspel.compile_program(&chunk, stmts)
	vm := muspel.vm_init()
	muspel.vm_run_chunk(&vm, &chunk)
}

Every example this book has built runs identically either way:

./run.sh run examples/fib.mus
./run.sh run --walk examples/fib.mus

55
55

13.6 Revisiting Chapter 9's benchmark

Chapter 9 measured the tree-walker against bench_fib.mus and bench_loop.mus and promised this chapter would fill in the bytecode-VM column. musc bench now runs both back to back:

./build.sh
./musc bench examples/bench_fib.mus

317811
tree-walk: 139ms
317811
bytecode vm: 52ms

./musc bench examples/bench_loop.mus

1.24999975e+13
tree-walk: 457ms
1.24999975e+13
bytecode vm: 386ms

fib's speed-up (roughly 2.7x) is far larger than bench_loop's (roughly 1.2x), and section 7.3's revised explanation of why bench_loop is slow says exactly why the gap shouldn't be expected to close: total and i are declared at the top level, so both the tree-walker and the VM treat them as globals, a map[string]Value lookup by name, interp.globals[node.name] on one side, Get_Global/Set_Global against vm.globals on the other. That cost is paid by both interpreters equally; a bytecode VM doesn't make a hash lookup faster, it only removes the tree-walker-specific costs (AST pointer-chasing, per-call heap allocation) sitting alongside it.

It's tempting to predict that rewriting bench_loop so its variables become real locals (wrap the loop in a function, call it once) would close most of that gap, on the theory that removing the shared global-lookup cost should let the VM's other advantages show through the way they do for bench_fib. Measured, it doesn't: the function-wrapped version runs in 325ms on the tree-walker and 261ms on the VM, a 1.25x speed-up, barely different from the original's 1.2x, even though both absolute numbers dropped substantially (457ms → 325ms tree-walking, 386ms → 261ms VM). Both interpreters got faster by removing the global lookups; the ratio between them barely moved. The honest reading is that this benchmark's remaining cost, on both sides, is dominated by something the local/global distinction doesn't touch at all, plausibly the sheer per-iteration dispatch overhead of five million passes through either eval_expr's switch or vm_run's, a cost this book doesn't have the tooling in hand to separate out further without an actual profiler. Report what you measure, not what a clean story predicts; the exercise below asks you to reproduce this apparent non-result yourself, precisely because it's a more honest lesson than a tidy one would have been.

Checkpoint

musc run executes every example this book has built, correctly, through a real bytecode VM, including struct, enum, and array construction/access/iteration, agreeing with --walk's tree-walker output exactly in every case, and musc bench reports real, reproducible bytecode-VM timings alongside the tree-walker's own, closing Chapter 9's loop with numbers instead of a promise.

Exercises

Add a Dup-using construct of your own (Chapter 10 named Dup but nothing has used it yet) and confirm it disassembles and executes correctly. A pre-increment-like x = x + 1 reads x once for the addition and doesn't need Dup at all; find a construct that genuinely does, a postfix operation that needs to use a value and keep it on the stack simultaneously is the right shape to look for.
Trace Call/Return's stack arithmetic by hand for a two-argument call: draw the stack before the call, immediately after Call pushes the new frame, and immediately after Return pops it, and confirm new_base and old.base - 1 land exactly where you'd expect.
Rewrite bench_loop.mus so its loop runs inside a function instead of at the top level (call it once, from a print at the top level), forcing total and i to become real locals. Rerun musc bench and confirm section 13.6's own measurement: both absolute times drop, but the tree-walk-to-VM ratio barely changes, the opposite of what "locals should behave like bench_fib's" would predict. Then try to improve on section 13.6's own honest "we'd need a profiler" shrug: with nothing but time.now()/time.since() calls of your own placed inside vm_run's dispatch loop, see how much of the VM's remaining ~260ms you can attribute to a specific opcode case rather than dispatch overhead in general.
Section 13.3's Design decision promises the flat dispatch loop is "the entire reason Chapter 15 gets to add Yield as one opcode." Without reading ahead, write down, in your own words, what you think would go wrong if Call instead called vm_run recursively (a real Odin call), and a script tried to pause partway through a deeply nested call. Check your answer against Chapter 15's own opening once you get there.
Run examples/structs_enums.mus and examples/arrays.mus through both musc run and musc run --walk and confirm every line of output matches exactly. Then deliberately corrupt one: change a Get_Field's constant-pool index by hand (in a copy of the compiled bytecode, via musc compile's own listing as your guide) to name a field that doesn't exist, and confirm Get_Field's runtime_error fires instead of an Odin-level panic.