Chapter 8: A tree-walking interpreter

This chapter:

Build the simplest thing that can actually run a Muspel program: an interpreter that evaluates the AST directly, no compiler and no bytecode involved.
Add environments, a chain of scope frames that mirrors exactly what the Chapter 7 resolver already computed, so a variable read is a direct array index, not a name search.
Get every example program written so far actually running, including recursion and functions passed around as ordinary values.
Grow musc its fourth subcommand: run.

Where we left off: musc check can confirm a program's variables and calls all make sense, (depth, slot) pairs and all, but nothing has ever executed a single statement of one.

8.1 Why build a tree-walker at all

The bytecode VM (Part IV) is where this book is going. It's reasonable to ask why Chapter 8 spends a whole chapter building something that Chapter 13 replaces.

Design decision: a tree-walking interpreter as a stepping stone, before any compiler exists. Alternatives considered: skip straight to Part III, and validate the language's semantics (does while actually loop correctly, does a block actually shadow correctly, does a return correctly unwind out of three levels of nested calls) using the bytecode VM itself, the first time any of it runs at all. Trade-off: a tree-walker is dramatically less code than a compiler and a VM combined, which makes it a much smaller place to be wrong in. Skipping it doesn't save real work, it just moves the same debugging effort into a much harder-to-inspect place: if fib(10) returns the wrong answer once bytecode exists, is the bug in the AST, the compiler's codegen, the jump patching, or the VM's dispatch loop? A tree-walker collapses that question to one place: either Muspel's semantics are right, evaluated the simplest way anyone could write them, or they aren't. Choice: build the tree-walker first. Every example program this chapter gets running becomes Chapter 11-13's regression suite: once the compiler and VM exist, they're expected to agree with this chapter's answers exactly, and any disagreement is a compiler or VM bug, not a language design question still up in the air.

8.2 Environments: a scope chain that matches the resolver exactly

The resolver (Chapter 7) already decided, for every variable reference in the program, exactly which scope frame it lives in (depth, counting outward from the point of use) and exactly which slot in that frame (slot, in declaration order). The tree-walker's job is to make that pair a real, followable pointer at run time:

Environment :: struct {
	values: [dynamic]Value,
	parent: ^Environment,
}

env_get_at :: proc(env: ^Environment, depth: int, slot: int) -> Value {
	e := env
	for i in 0 ..< depth {
		e = e.parent
	}
	return e.values[slot]
}

depth steps up the parent chain that many times; slot indexes straight into the array that's sitting there. There's no name comparison anywhere in this proc, because the resolver already did every bit of name resolution the tree-walker needs, back in Chapter 7. This is the direct payoff of that chapter's "extra pass": a variable read here costs a fixed number of pointer hops and one array index, never a search.

env_define relies on one fact that's easy to miss and important to state plainly: it just appends.

env_define :: proc(env: ^Environment, value: Value) {
	append(&env.values, value)
}

That works because the tree-walker declares locals in exactly the same left-to-right order the resolver did, into a scope frame created at exactly the same moments (entering a block, entering a function call) the resolver pushed one. Slot 2 at resolve time and slot 2 at run time are the same declaration, reached by the same walk over the same tree, so the array position an append lands a value at always matches the slot number the AST node already carries.

Not every resolver scope needs a matching runtime one for free, though: Stmt_Func's resolver case opens exactly one scope, shared by the parameter list and the body's own statements, rather than a parameter scope nested inside a separate body scope. call_function mirrors that precisely, building one new Environment for the call and running the body's statements directly inside it, not through Stmt_Block's ordinary handling (which would push a second, extra frame):

call_function :: proc(interp: ^Interpreter, fn: ^Function, args: []Value) -> Value {
	call_env := env_new(fn.closure)
	for arg in args {
		env_define(call_env, arg)
	}
	signal, value := exec_block_stmts(interp, call_env, fn.body.stmts)
	if signal == .Return do return value
	return nil
}

Depth 0 at the top of a function body means "this call's own parameters and locals," exactly as the resolver intended. Get this one detail wrong, an extra environment pushed here that the resolver never counted, and every depth computed for a variable inside a function body is off by one, silently.

Globals live outside the chain entirely. A top-level var, a top-level func, and a builtin like print all resolve to depth == -1, and the tree-walker treats that exactly as the special case it is: a lookup in Interpreter.globals, a flat map[string]Value, never a walk up any Environment at all.

8.3 Evaluating expressions

eval_expr is one recursive switch over Expr's union, each case doing exactly what the construct means:

case ^Expr_Ident:
	if node.depth == -1 do return interp.globals[node.name]
	return env_get_at(env, node.depth, node.slot)

Binary and unary operators evaluate their operands (post-order: children before the operator itself, exactly the order a stack machine will later need) and apply Odin's own arithmetic, comparison and boolean logic to the extracted values:

case .Plus:
	if l, ok := left.(string); ok do return strings.concatenate({l, right.(string)})
	return left.(f64) + right.(f64)

+ is overloaded by the left operand's runtime type, string concatenation or numeric addition, chosen with a type assertion rather than a separate opcode or AST node for each. left.(f64) and right.(string) both panic on a type mismatch right now; a script that writes 1 + "two" crashes the interpreter rather than reporting a clean Muspel-level error. That's an honest gap, not an oversight: graceful runtime type errors are Chapter 18's job, once there's a VM whose errors need to survive one script's mistake without taking down every other running instance. A tree-walker built to be thrown away doesn't need that machinery yet.

&& and || short-circuit by only evaluating their right operand when the left one didn't already decide the answer, exactly why Expr_Logical stayed a separate AST node from Expr_Binary back in Chapter 3:

case ^Expr_Logical:
	left := eval_expr(interp, env, node.left)
	#partial switch node.op {
	case .And_And:
		if !is_truthy(left) do return left
	case .Or_Or:
		if is_truthy(left) do return left
	}
	return eval_expr(interp, env, node.right)

8.4 Evaluating statements, and how `return` gets out

Most statements execute and fall through. return is different: it has to escape however many blocks and loop iterations sit between it and the function call it belongs to, without those blocks or loops getting a chance to run anything after it. exec_stmt reports this with a small signal instead of an Odin exception:

Exec_Signal :: enum {
	Normal,
	Return,
}

Every caller that walks a list of statements checks it and stops immediately on .Return:

case ^Stmt_While:
	for is_truthy(eval_expr(interp, env, node.cond)) {
		signal, value := exec_stmt(interp, env, node.body)
		if signal == .Return do return signal, value
	}

A return inside a while body doesn't just end that one loop iteration, it ends the loop entirely and keeps propagating outward, one caller at a time, until it reaches call_function, which is the one place that actually converts .Return back into an ordinary value instead of propagating it further. There's no break/continue signal alongside it: Muspel's grammar (Chapter 4) doesn't have those statements, so there's nothing else for Exec_Signal to carry yet.

Stmt_Block is the one place execution pushes a genuinely new scope for an ordinary { ... }:

case ^Stmt_Block:
	child := env_new(env)
	return exec_block_stmts(interp, child, node.stmts)

if and while bodies are always parsed as Stmt_Block (Chapter 4), so they get this same fresh scope for free, with no special-casing in exec_stmt's own Stmt_If/Stmt_While cases.

8.5 Struct and enum values

A struct instance, at run time, is an ordered pair of parallel slices: the field names it shares with every other instance of the same type, and the values this particular instance actually holds.

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

Building one from a literal places each provided value at the field index Chapter 7 already resolved, leaving any field the literal omitted at its zero value, nil:

case ^Expr_Struct_Literal:
	info := interp.structs[node.type_name]
	values := make([]Value, len(info.fields))
	for i in 0 ..< len(node.keys) {
		idx := node.field_indices[i]
		v := eval_expr(interp, env, node.values[i])
		if idx >= 0 do values[idx] = v
	}
	inst := new(Struct_Instance)
	inst^ = Struct_Instance{type_name = node.type_name, field_names = info.fields, values = values}
	return inst

interp.structs is the resolver's own struct table, Struct_Info (Chapter 7), handed to the interpreter by whichever musc command builds it: interp.structs = r.structs after resolving, before executing. It's the one piece of state the tree-walker borrows directly from the resolver rather than recomputing, since both need the same "declared field order" fact and there's no reason to store it twice.

Field access reads back by name, scanning field_names, rather than by the compile-time index a faster representation might use:

case ^Expr_Field_Access:
	if node.is_enum_member do return f64(node.enum_tag)

	obj := eval_expr(interp, env, node.object)
	inst, ok := obj.(^Struct_Instance)
	if !ok do panic(fmt.tprintf("runtime error: '.%s' used on a non-struct value", node.field))
	for name, i in inst.field_names {
		if name == node.field do return inst.values[i]
	}
	panic(fmt.tprintf("runtime error: struct '%s' has no field '%s'", inst.type_name, node.field))

The enum-member case above it needs nothing but the tag Chapter 7 already resolved: no struct instance, no lookup, Phase.Attacking evaluates to the plain number 1 (or whatever Phase's member order made it) and nothing more. Field assignment (Expr_Field_Assign) is the same by-name scan, writing inst.values[i] in place instead of reading it; because Struct_Instance is accessed everywhere through a pointer, that mutation is visible through every other reference to the same instance, exactly the aliasing a script author expects from a value they've assigned to two variables.

A gap this chapter accepts, on purpose. A field access on a value that turns out not to be a struct at all (5.x, say) currently panics the whole musc process, the same honest gap section 8.3 already named for 1 + "two". Chapter 18 is still where that becomes a graceful, contained, per-script error; this chapter's tree-walker doesn't pretend to that robustness any more here than it did for arithmetic.

8.6 Arrays and `for item in list`

An array value is simpler still, a fixed-length slice and nothing else:

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

An array literal evaluates every element, in order, into a slice sized exactly once:

case ^Expr_Array_Literal:
	values := make([]Value, len(node.elements))
	for el, i in node.elements {
		values[i] = eval_expr(interp, env, el)
	}
	inst := new(Array_Instance)
	inst^ = Array_Instance{values = values}
	return inst

Indexing is where Chapter 6's "bounds checking is a language guarantee" promise gets kept:

case ^Expr_Index:
	obj := eval_expr(interp, env, node.object)
	arr, ok := obj.(^Array_Instance)
	if !ok do panic("runtime error: '[]' used on a non-array value")
	i := int(eval_expr(interp, env, node.index).(f64))
	if i < 0 || i >= len(arr.values) {
		panic(fmt.tprintf("runtime error: index %d out of bounds for array of length %d", i, len(arr.values)))
	}
	return arr.values[i]

An out-of-range index is a distinct, clearly-worded failure, not whatever Odin's own slice bounds check happens to produce if this if weren't here (it would be a very similar-looking panic, but this chapter's own message, chosen deliberately, is what a later, non-panicking version of this check reuses almost verbatim in Chapter 13).

for item in list is a straight Odin for loop over the array's own values, each iteration getting a fresh child environment holding just that one binding, exactly mirroring the resolver's own "the loop variable gets its own scope, one level outside the body's" decision from section 7.7:

case ^Stmt_For_In:
	list_val := eval_expr(interp, env, node.list)
	arr, ok := list_val.(^Array_Instance)
	if !ok do panic("runtime error: 'for ... in' requires an array")
	for item in arr.values {
		item_env := env_new(env)
		env_define(item_env, item)
		signal, value := exec_stmt(interp, item_env, node.body)
		if signal == .Return do return signal, value
	}

Gotcha: it's easy to run the body against the wrong environment. item_env, not env, is what exec_stmt has to be called with here: it's the frame env_define(item_env, item) just populated. Swap that one argument back to the outer env (easy to do without noticing, since both are in scope and both type-check) and the loop variable silently stops being visible inside its own body, an "undefined variable" panic on the very first iteration despite the loop otherwise looking correct. Worth deliberately breaking once in your own project and watching it fail, so the fix is muscle memory the next time a scope-frame mismatch like this one shows up somewhere less obvious.

len(list) needs no new grammar or AST node at all, section 6.2 already noted: it's a native builtin, registered exactly like print:

native_len :: proc(interp: ^Interpreter, args: []Value) -> Value {
	arr, ok := args[0].(^Array_Instance)
	if !ok do panic("runtime error: 'len' expects an array")
	return f64(len(arr.values))
}

8.7 Functions as values

A Muspel function, once declared, is a value like any other: it can be looked up by name, passed as an argument, and called through whatever expression evaluates to it, not just its own name. examples/callbacks.mus is the whole idea in four lines:

func add(a, b) {
    return a + b
}

func apply(f, x, y) {
    return f(x, y)
}

print(apply(add, 2, 3))

add is read as an ordinary Expr_Ident (resolving to depth == -1, exactly like any other top-level name), evaluates to a ^Function value, and travels into apply as an argument like any number or string would. Inside apply, f(x, y) calls whatever ^Function happens to be sitting in that parameter slot: Expr_Call's callee is evaluated generically, and call_value doesn't care whether the value it's holding came from a literal function name or a variable that was handed one.

Function :: struct {
	name:    string,
	params:  []string,
	body:    ^Stmt_Block,
	closure: ^Environment,
}

That closure field is doing real work in principle, even though Muspel's current grammar (top- level-only function declarations, Chapter 4) only ever gives it nil: every top-level function closes over the global scope, which is already reachable through Interpreter.globals regardless. The reason it's there at all, and the reason this section is titled "functions as values" rather than just "calling functions," is to name the mechanism plainly before it does anything more interesting. If Muspel ever grows nested function declarations, a function created inside another function's body would capture that enclosing Environment instead of nil, and every later call to it would see whatever local variables were live at the moment it was declared, not at the moment it's called. That's what makes a tree-walk closure "nearly free": the environment it needs to remember already exists, as a live Odin value the closure just keeps a pointer to. Chapter 12's bytecode closures have to reconstruct the same guarantee by hand, capturing values instead of keeping a live environment pointer around, precisely because the compiled representation has no such thing sitting on a heap already. That contrast is worth remembering now, three parts early.

8.8 `musc run`

./run.sh run examples/fib.mus

fib recurses ten levels deep, each call getting its own fresh Environment parented at the global scope, each return propagating correctly back out through however many pending calls are waiting for it. cmd_run is the same lex-parse-resolve pipeline cmd_check already had, one step further: a program with syntax or resolution errors is reported and never reaches exec_program at all.

cmd_run :: proc(src: string) {
	// ... lex, parse, resolve, same as cmd_check ...

	interp := muspel.interp_init()
	muspel.exec_program(&interp, stmts)
}

Checkpoint

musc run correctly executes every example program written since Chapter 2: variable declarations and shadowing, if/else, while loops, recursive function calls (examples/fib.mus), structs and enums (examples/structs_enums.mus), arrays and for item in list (examples/arrays.mus), and functions passed around as ordinary values (examples/callbacks.mus).

Exercises

Trace fib(3) by hand: draw the call tree, note which Environment each call's n lives in, and confirm the order return values combine in matches what print(fib(3)) actually prints.
1 + "two" currently panics the whole musc process (section 8.3). Write that example, run it, and read the panic message Odin's own type assertion produces. Keep a mental note of this exact failure mode: Chapter 18 replaces it with a script-level error that doesn't take the host down, and being able to say "here's what used to happen instead" will make that chapter's payoff concrete.
len is already registered as a native builtin (native_len, section 8.6). Add a second native builtin of your own, abs(n) say, following native_len's shape, and confirm a script can call it.
Section 8.7 explains why Function.closure is always nil under Muspel's current grammar. Without changing the grammar, construct an example that still demonstrates a real, observable consequence of functions being values (not just declarations you call by name): a function stored in a variable, or passed through two levels of apply-style indirection, and confirm it still calls correctly.
Build a struct whose field holds an array of other structs (struct Wave { enemies }, an array of Enemy values) and write a for loop that sums a field across every element. This is exactly Chapter 21's common.mus shape, three parts early.