Chapter 11: The compiler, part 1: expressions and control flow

This chapter:

Compile the resolved AST (Parts I and II's output) to Chapter 10's bytecode, one statement and expression at a time.
Handle if/while with jump patching: emitting a jump before its target is known, and backfilling the real offset once it is.
Grow musc its sixth subcommand, compile, pairing the Chapter 10 disassembler with real, generated bytecode for the first time.

Where we left off: musc asm-demo proved Chapter 10's instruction format is sound, by hand. Nothing has generated a Chunk automatically yet.

11.1 The compiler's own locals, and why they aren't Chapter 7's

The compiler needs to know, for every variable reference, whether it's a local or a global, and if local, which flat stack slot to read or write. Chapter 7's resolver already computes something that sounds like exactly this, (depth, slot), and its own manuscript said so plainly. It's worth being honest here about why the compiler doesn't just read those numbers back off the AST.

Design decision: the compiler tracks its own locals, rather than reusing the resolver's (depth, slot) pairs directly. Alternatives considered: have Chapter 7's resolver stamp a second, bytecode-flavoured slot number onto every Expr_Ident/Stmt_Var/Expr_Assign node, alongside the pair the tree-walker already uses, so both backends read from the same pass. Trade-off: the resolver's slot restarts at zero in every nested block, exactly right for Chapter 8's tree-walker, where each block gets its own freshly allocated Environment and depth says how many of those to hop through. A bytecode VM has no such per-block allocation: every local a function declares, across all its nested blocks, ends up in one flat region of the VM's value stack (Chapter 13), which means two variables in sibling blocks can safely share a slot number (never live at the same time) while two nested one inside the other never can, a distinction the resolver's per-block counter was never built to make. Stamping a second number onto the resolver's output would couple Chapter 7's pass to a bytecode design it otherwise has no reason to know exists. Choice: the compiler re-derives locals with its own small scope-stack, the same left-to-right declare-before-use walk the resolver already validated is correct, assigning flat slots instead of per-block ones. It reuses exactly one thing from Chapter 7, genuinely backend-agnostic: the global-versus-local distinction itself (top level versus everywhere else). Everything past that is recomputed for the layout a bytecode VM actually needs.

Compiler_Local :: struct {
	name:  string,
	depth: int,
}

Compiler :: struct {
	chunk:       ^Chunk,
	locals:      [dynamic]Compiler_Local,
	scope_depth: int,
}

locals is used as a stack: declare_local appends, end_scope truncates it back down when a block closes, emitting one POP per local it removes:

end_scope :: proc(c: ^Compiler, line: int) {
	c.scope_depth -= 1
	for len(c.locals) > 0 && c.locals[len(c.locals) - 1].depth > c.scope_depth {
		pop(&c.locals)
		chunk_write_op(c.chunk, .Pop, line)
	}
}

Because slots are just array indices into this stack, two sequential sibling blocks reuse the same slot numbers automatically: the first block's locals get truncated away before the second block ever declares its own, so len(c.locals) returns to the same count both times. Nested blocks never collide, because a still-open outer block's locals are still sitting in the array when an inner block starts declaring its own, at higher indices. resolve_local searches innermost-first, so a shadowing local (declared later, appended later) is always found before whatever it's shadowing:

resolve_local :: proc(c: ^Compiler, name: string) -> (slot: u8, found: bool) {
	for i := len(c.locals) - 1; i >= 0; i -= 1 {
		if c.locals[i].name == name do return u8(i), true
	}
	return 0, false
}

A name resolve_local doesn't find is a global, exactly the same convention Chapter 7 used (depth == -1): a fresh Compiler starts at scope_depth == 0, and a top-level Stmt_Var compiles to Define_Global rather than a local slot, checked the same way:

if c.scope_depth == 0 {
	idx := chunk_add_const(c.chunk, Const_Value(node.name))
	chunk_write_op(c.chunk, .Define_Global, node.line)
	chunk_write(c.chunk, idx, node.line)
} else {
	declare_local(c, node.name)
}

One consequence worth naming up front, because it isn't obvious and matters again in Chapter 13: a bare { ... } block at the top level (not inside any function) still declares real locals, not globals, exactly the way Chapter 7's resolver already treats it (any var inside a pushed scope gets depth == 0, never -1, regardless of whether that scope belongs to a function or is just a top-level block). That only works at run time if the whole script itself is treated as one implicit call frame, Chapter 13's VM does exactly that, the same convention a production bytecode VM (clox included) uses for its own top level.

11.2 Expression codegen

compile_expr walks Expr's union, post-order: compile the operands, then emit the operator that consumes them.

case ^Expr_Binary:
	compile_expr(c, node.left)
	compile_expr(c, node.right)
	#partial switch node.op {
	case .Plus: chunk_write_op(c.chunk, .Add, node.line)
	// ...
	}

Literals push either a constant-pool value (f64/string) or a dedicated zero-operand instruction (bool/nil, section 10.4's Nil/True/False), and a variable read chooses Get_Local or Get_Global based on section 11.1's resolve_local:

case ^Expr_Ident:
	if slot, found := resolve_local(c, node.name); found {
		chunk_write_op(c.chunk, .Get_Local, node.line)
		chunk_write(c.chunk, slot, node.line)
	} else {
		idx := chunk_add_const(c.chunk, Const_Value(node.name))
		chunk_write_op(c.chunk, .Get_Global, node.line)
		chunk_write(c.chunk, idx, node.line)
	}

&&/|| short-circuit using only Jump and Jump_If_False, the same two opcodes if/while use (section 11.3), rather than a third jump opcode of their own. Jump_If_False peeks (section 10.4): it never pops the value it tests, so a falsy left operand of && is still sitting on the stack, ready to be the whole expression's result, exactly when the jump is taken:

case .And_And:
	end_jump := emit_jump(c, .Jump_If_False, node.line)
	chunk_write_op(c.chunk, .Pop, node.line) // only reached when left was truthy: discard it
	compile_expr(c, node.right)
	patch_jump(c, end_jump)

|| mirrors this with one extra unconditional Jump, deciding which side's value survives to become the result: jump past evaluating the right side entirely when the left was already truthy, otherwise fall through, discard the falsy left value, and evaluate the right side instead.

11.3 Statement codegen and jump patching

Most statements are direct: Stmt_Expr compiles its expression, then pops the unused result; Stmt_Var was shown in section 11.1. if and while are the chapter's real work, because their bodies are compiled after the jump instruction that has to skip over them, at the moment the compiler is emitting the jump, it doesn't yet know how far to jump.

Jump patching is the fix: emit the jump with a placeholder offset, remember where that placeholder is, keep compiling, then come back and overwrite it once the real target is known.

emit_jump :: proc(c: ^Compiler, op: Op_Code, line: int) -> int {
	chunk_write_op(c.chunk, op, line)
	chunk_write(c.chunk, 0xff, line)
	chunk_write(c.chunk, 0xff, line)
	return len(c.chunk.code) - 2  // the placeholder's own position, to patch later
}

patch_jump :: proc(c: ^Compiler, jump_pos: int) {
	offset := len(c.chunk.code) - (jump_pos + 2)
	c.chunk.code[jump_pos] = u8((offset >> 8) & 0xff)
	c.chunk.code[jump_pos + 1] = u8(offset & 0xff)
}

offset is measured from the byte right after the jump's own two operand bytes, so ip += offset (applied once the VM has already advanced past reading them, Chapter 13) lands exactly at "wherever compilation had gotten to" by the time patch_jump runs.

if/else needs two jumps: skip the then branch when the condition is false, and skip the else branch (having just run then) when it's true. Both branches need their own explicit Pop, since Jump_If_False never discards the condition itself:

case ^Stmt_If:
	compile_expr(c, node.cond)
	then_jump := emit_jump(c, .Jump_If_False, node.line)
	chunk_write_op(c.chunk, .Pop, node.line) // truthy path: discard cond, enter `then`
	compile_stmt(c, node.then_branch)
	else_jump := emit_jump(c, .Jump, node.line)
	patch_jump(c, then_jump)
	chunk_write_op(c.chunk, .Pop, node.line) // falsy path: discard cond, enter `else`
	if node.else_branch != nil do compile_stmt(c, node.else_branch)
	patch_jump(c, else_jump)

while needs one backward jump, back to re-check the condition, which is where a genuinely new trick appears: emit_loop reuses the same Jump opcode, just with a negative offset, so there's no separate "loop" instruction in Chapter 10's table at all.

case ^Stmt_While:
	loop_start := len(c.chunk.code)
	compile_expr(c, node.cond)
	exit_jump := emit_jump(c, .Jump_If_False, node.line)
	chunk_write_op(c.chunk, .Pop, node.line)
	compile_stmt(c, node.body)
	emit_loop(c, loop_start, node.line)
	patch_jump(c, exit_jump)
	chunk_write_op(c.chunk, .Pop, node.line)

A worked example

examples/if_demo.mus is small enough to trace by hand, offset by offset:

var x = 5
if (x < 10) {
    print(1)
} else {
    print(2)
}

./run.sh compile examples/if_demo.mus

== <script> ==
0000 0003 CONSTANT       0000 '5'
0002 0003 DEFINE_GLOBAL  0001
0004 0004 GET_GLOBAL     0002
0006 0004 CONSTANT       0003 '10'
0008 0004 LESS
0009 0004 JUMP_IF_FALSE  000011
0012 0004 POP
0013 0005 GET_GLOBAL     0004
0015 0005 CONSTANT       0005 '1'
0017 0005 CALL           0001
0019 0005 POP
0020 0004 JUMP           000008
0023 0004 POP
0024 0007 GET_GLOBAL     0006
0026 0007 CONSTANT       0007 '2'
0028 0007 CALL           0001
0030 0007 POP
0031 0000 NIL
0032 0000 RETURN

(Line numbers start at 3 because the real file opens with a two-line comment; the manuscript's own snippet above trims that away. The trailing NIL; RETURN is compile_program's own implicit return, appended once after every top-level statement, section 12.1 covers the matching one every compiled function gets.)

Follow the two jumps by hand; both are forward here, there's no loop in this example. JUMP_IF_FALSE at 0009 has its two operand bytes at 0010-0011, so emit_jump returned jump_pos = 10. patch_jump(then_jump) runs right after the else-branch's own JUMP has been fully emitted, at which point len(c.chunk.code) == 23. The stored offset is therefore 23 - (10 + 2) = 11, exactly what the listing shows, and the target it computes to is 12 + 11 = 23: the instruction right after the two operand bytes (12), plus 11, lands precisely on 0023's POP, the one that discards the condition on the falsy path and enters else. The unconditional JUMP at 0020 works the same way: its operand bytes sit at 0021- 0022, so jump_pos = 21; patch_jump(else_jump) runs once the whole else branch has compiled, len(c.chunk.code) == 31 at that point (compile_program's own trailing NIL; RETURN hasn't been appended yet; that only happens after this whole statement finishes compiling), giving 31 - (21 + 2) = 8, and 23 + 8 = 31 lands exactly on the NIL that begins the implicit return, correctly skipping past the else branch once then has already run. Both numbers check out against nothing but the byte offsets already printed; that agreement, not this paragraph, is what should convince you jump patching works.

11.4 Struct and enum codegen

A struct literal compiles each provided value, left to right, in the order the literal itself wrote them, then emits Make_Struct with a Struct_Layout constant recording where each pushed value lands: field_indices[i] is the declaring struct's index for the i-th value pushed, and an omitted field simply has no entry pointing at it, left nil at run time (section 10.6).

case ^Expr_Struct_Literal:
	for v in node.values {
		compile_expr(c, v)
	}
	layout := new(Struct_Layout)
	layout^ = Struct_Layout {
		type_name     = node.type_name,
		field_names   = node.all_fields,
		field_indices = node.field_indices,
	}
	idx := chunk_add_const(c.chunk, Const_Value(layout))
	chunk_write_op(c.chunk, .Make_Struct, node.line)
	chunk_write(c.chunk, idx, node.line)

Field access and assignment compile straight to Get_Field/Set_Field, the field's name as a constant-pool operand, no different in shape from Get_Local/Set_Local except what the operand means:

case ^Expr_Field_Access:
	if node.is_enum_member {
		idx := chunk_add_const(c.chunk, Const_Value(f64(node.enum_tag)))
		chunk_write_op(c.chunk, .Constant, node.line)
		chunk_write(c.chunk, idx, node.line)
	} else {
		compile_expr(c, node.object)
		idx := chunk_add_const(c.chunk, Const_Value(node.field))
		chunk_write_op(c.chunk, .Get_Field, node.line)
		chunk_write(c.chunk, idx, node.line)
	}

That is_enum_member branch is the whole of enum codegen: Chapter 7 already resolved Phase.Attacking to a plain integer tag, so compiling it is exactly like compiling a number literal, because by this point in the pipeline that's precisely what it is. No Make_Struct, no field lookup, nothing beyond Constant ever runs for an enum member, at compile time or at run time.

11.5 Array codegen

An array literal is Make_Struct's simpler sibling: compile every element, then emit Make_Array with the element count as its operand, no layout constant needed since there are no named fields to route values to.

case ^Expr_Array_Literal:
	for el in node.elements {
		compile_expr(c, el)
	}
	chunk_write_op(c.chunk, .Make_Array, node.line)
	chunk_write(c.chunk, u8(len(node.elements)), node.line)

Indexing compiles the object, then the index expression, then Get_Index, no operand at all: the index isn't known until this instruction actually runs, unlike a struct field's name, so there's nothing for the compiler to bake in ahead of time.

case ^Expr_Index:
	compile_expr(c, node.object)
	compile_expr(c, node.index)
	chunk_write_op(c.chunk, .Get_Index, node.line)

Expr_Index_Assign is the same shape with a third compile_expr for the assigned value, then Set_Index.

11.6 `for item in list`: desugaring at compile time

Chapter 6 promised for item in list would lower to "a hidden index counter plus a Get_Index/bounds-check/jump sequence," reusing this chapter's own jump-patching machinery rather than earning a dedicated opcode. Unlike the counting for (section 4.6), which desugars at parse time into ordinary while/var nodes, for item in list keeps its own Stmt_For_In node all the way to the compiler, because it needs two hidden locals (an index counter and the list itself) that have no source-level name for the resolver to have declared: declare_local is called directly, by the compiler, with names no Muspel identifier could ever collide with.

compile_expr(c, node.list)
declare_local(c, "@list")
list_slot, _ := resolve_local(c, "@list")

chunk_write_op(c.chunk, .Constant, node.line)
chunk_write(c.chunk, zero_idx, node.line) // push 0
declare_local(c, "@idx")
idx_slot, _ := resolve_local(c, "@idx")

chunk_write_op(c.chunk, .Nil, node.line)
declare_local(c, node.item_name) // reserve the item's own slot up front
item_slot, _ := resolve_local(c, node.item_name)

loop_start := len(c.chunk.code)
// idx < len(list)
chunk_write_op(c.chunk, .Get_Local, node.line); chunk_write(c.chunk, idx_slot, node.line)
chunk_write_op(c.chunk, .Get_Global, node.line); chunk_write(c.chunk, len_idx, node.line)
chunk_write_op(c.chunk, .Get_Local, node.line); chunk_write(c.chunk, list_slot, node.line)
chunk_write_op(c.chunk, .Call, node.line); chunk_write(c.chunk, 1, node.line)
chunk_write_op(c.chunk, .Less, node.line)

exit_jump := emit_jump(c, .Jump_If_False, node.line)
chunk_write_op(c.chunk, .Pop, node.line)

// item = list[idx]
chunk_write_op(c.chunk, .Get_Local, node.line); chunk_write(c.chunk, list_slot, node.line)
chunk_write_op(c.chunk, .Get_Local, node.line); chunk_write(c.chunk, idx_slot, node.line)
chunk_write_op(c.chunk, .Get_Index, node.line)
chunk_write_op(c.chunk, .Set_Local, node.line); chunk_write(c.chunk, item_slot, node.line)
chunk_write_op(c.chunk, .Pop, node.line)

compile_stmt(c, node.body)

// idx = idx + 1
chunk_write_op(c.chunk, .Get_Local, node.line); chunk_write(c.chunk, idx_slot, node.line)
chunk_write_op(c.chunk, .Constant, node.line); chunk_write(c.chunk, one_idx, node.line)
chunk_write_op(c.chunk, .Add, node.line)
chunk_write_op(c.chunk, .Set_Local, node.line); chunk_write(c.chunk, idx_slot, node.line)
chunk_write_op(c.chunk, .Pop, node.line)

emit_loop(c, loop_start, node.line)
patch_jump(c, exit_jump)
chunk_write_op(c.chunk, .Pop, node.line)

Three details worth pulling out explicitly. First, the bound check calls len the same way a script itself would, Get_Global "len" followed by Call 1, real bytecode a script author could have written by hand, not a special opcode reserved for this one construct. Second, the item slot is reserved once, before the loop starts (Nil pushed, then declared), and every iteration overwrites it with Set_Local rather than pushing a fresh value each time; get this backwards (push a new value per iteration instead of overwriting the reserved slot) and the compiler's own stack-slot bookkeeping silently drifts out of sync with the VM's actual stack by one slot per iteration. Third, the whole thing sits inside a begin_scope/end_scope pair (not shown above), exactly like while's own body, so @list, @idx, and the item binding are all popped cleanly the moment the loop's enclosing block ends.

Checkpoint

musc compile produces correct bytecode, verified by disassembly, for every construct through Chapter 6's grammar except functions and calls: variables, arithmetic, comparisons, &&/||, if/else, while, structs, enums, arrays, and for item in list. Functions and calls are Chapter 12's chapter, not this one's, on purpose: jump patching is enough new mechanism for one chapter to earn properly.

Exercises

Trace the worked example's byte offsets by hand, on paper, before checking them against the listing: compute where patch_jump should land then_jump and else_jump yourself, then confirm musc compile's actual output agrees.
Remove the else branch from the worked example and recompile. Confirm there's still exactly one POP reached on the falsy path (section 11.3 explains why: Jump_If_False never discards the condition on its own, else or not).
Write a while loop with a local variable declared inside its body and compile it. Confirm the local's slot number is the same on every disassembled pass through the loop, there's only one compiled body, executed repeatedly, not one compilation per iteration, which is exactly why this works.
a && b || c mixes both short-circuit operators in one expression. Compile it and trace, by hand, which of a, b, or c's value could end up as the final result for a few different truthy/falsy combinations of the first two.
Compile Vec2{ x: 1, y: 2 } and disassemble it. Confirm the Struct_Layout the disassembler prints has field_indices == [0, 1]; then compile Vec2{ y: 2 } alone and confirm it's [1], one entry, not two with a placeholder.
Compile examples/arrays.mus's for it in roster loop and count, from the disassembly, how many bytecode instructions run per iteration versus once total. Confirm the @list/@idx locals never appear by name anywhere in the output, only as bare slot numbers.