The Machine That Runs the Machine

Part 4 of 7. Part 3 covered building the Smalltalk heap from a JSON blueprint. This part covers the bytecode interpreter: execution contexts, method lookup, non-local returns, and the most consequential bug in the project.

The heap is a static artifact. It contains objects — class definitions, compiled methods, global variables, all correctly linked — but nothing moves. Nothing executes. To make a Smalltalk-80 system run, you need the thing the Blue Book calls “the interpreter”: a program that reads bytecode from CompiledMethod objects, manipulates a stack, dispatches message sends, and controls flow.

The Smalltalk-80 interpreter is not complicated in the way a JIT compiler is complicated. It is complicated in the way a puzzle is complicated: every piece interacts with every other piece in precise ways, and the failure mode for getting any of it wrong is usually “works until it doesn’t, in a way that’s hard to connect to the original error.”

The Execution Model

In Smalltalk-80, every executing method has a corresponding MethodContext object on the heap. This is not a stack frame in the traditional sense — it’s an actual Smalltalk object, allocated in the same heap as everything else, with a class pointer and OOP. It has the following fields:

The CompiledMethod being executed (an OOP)
The receiver (self — the object that received the message)
The sender context (the context that sent the message that activated this one)
The instruction pointer (a SmallInteger OOP — offset into the bytecode array)
The stack pointer
The arguments and temporary variables (stored in the context’s variable-length fields)
The evaluation stack (also in the variable-length fields, above the temps)

When a message is sent, a new MethodContext is allocated and pushed as the active context. When a method returns, its sender context becomes the active context again. The sender chain is the call stack, except it lives on the Smalltalk heap rather than in a memory-mapped stack region.

This heap-allocated context model is fundamental to several important Smalltalk behaviors: you can capture contexts, resume them, pass them around, and inspect them. The debugger — Smalltalk’s interactive debugger, which is itself written in Smalltalk — works by accessing the context chain directly, because the contexts are ordinary objects.

Block Closures

The interesting variant is BlockContext.

A block — the [ ... ] syntax — is a deferred computation: a sequence of statements that can be evaluated later, at a different point in the program, possibly multiple times. Blocks appear everywhere in Smalltalk: as the then-branch of conditionals, as iteration bodies, as callbacks.

count := 0.
1 to: 10 do: [:i | count := count + i].

The [:i | count := count + i] is a block. When to:do: evaluates it for each integer from 1 to 10, it needs access to the variable count — which is a local variable of the enclosing method, not of the block itself.

Blocks in Smalltalk-80 are closures: they close over the variables of their defining context. A BlockContext object has all the fields of a MethodContext plus one additional field: homeContext. The home context is the MethodContext in which the block was created. When the block accesses a variable that isn’t one of its own arguments or temporaries, it looks it up in the home context.

This is elegant. It is also, in an interpreter, the source of a class of bugs that are particularly hard to track down.

Non-Local Returns

Before getting to the bugs, the other interesting thing about blocks: the ^ return operator inside a block.

In a method, ^expr returns from the method. But what does ^expr inside a block mean? In most languages, a return from within a closure returns from the closure. In Smalltalk-80, it returns from the enclosing method — the method that created the block. This is called a non-local return.

findFirst: aBlock in: aCollection
    aCollection do: [:each |
        (aBlock value: each) ifTrue: [^each]].
    ^nil

The ^each inside the inner block does not return from the block. It returns from the findFirst:in: method. If aBlock value: each is true for some element, the method returns that element immediately, unwinding whatever stack depth the do: iteration had accumulated.

Implementing this requires the interpreter to unwind the context stack to the home method context when it encounters a non-local return bytecode. It also requires handling the error case: if the home context has already returned (because the method completed normally and some block captured during its execution is being evaluated later), a non-local return would try to return from a method that’s already gone. Smalltalk-80 defines specific behavior for this case — a BlockContext error.

Both the normal and error cases needed to be correct before the interpreter could handle real Smalltalk code, because ifTrue:, ifFalse:, whileTrue:, and essentially every control structure in the system uses blocks.

The Bytecode Set

The Smalltalk-80 bytecode set has 256 possible values. The Blue Book documents them in Chapters 26-30 of Part III. A quick survey of the categories:

Push instructions (bytecodes 0-127, with extended forms): push a receiver variable, a temp variable, a literal, nil, true, false, or self onto the evaluation stack.

Store instructions: pop the top of stack and store it to a receiver variable or temp variable.

Send instructions: send a message to the object on top of the stack. Short forms exist for common single-character selectors. Extended forms allow any selector from the method’s literal frame with any argument count.

Return instructions: return from the current method or block. Special short forms for ^self, ^nil, ^true, ^false (these are common enough to warrant dedicated opcodes).

Jump instructions: unconditional and conditional (pop and test top of stack) forward jumps, with short and extended offset forms.

Primitive invocations: these don’t appear as a separate bytecode category in the compiled output — instead, the method header word encodes a primitive number, and the interpreter checks this before starting to execute the method’s bytecode. If the primitive succeeds, the bytecode is never executed. If it fails (integer overflow, wrong argument type, etc.), execution falls through to the bytecode, which is the Smalltalk fallback implementation.

Getting the primitive numbers right was its own adventure. The Blue Book specifies them, but the original Xerox implementation had some inconsistencies between the specified numbers and the actual numbers used in the source code. The compiler generated primitive number annotations from the method source (<primitive: 60>) and I had to match those numbers to C# implementations. A batch of primitives in the 12-17 range had an off-by-one mapping error that caused a class of failures — certain system operations would silently execute the wrong C# handler — and took some time to track down.

Method Lookup

When the interpreter encounters a send bytecode, it must find the method to execute. The lookup algorithm:

Get the receiver’s class (dereference the receiver OOP to get its object table entry, read the class OOP field, dereference that).
Look in that class’s method dictionary for the selector.
If found, activate it. If not, follow the class’s superclass pointer and repeat.
If the superclass chain is exhausted (we’ve reached nil), the message is not understood. Create a Message object describing the failed send and send doesNotUnderstand: to the original receiver.

For a message sent to a class object (rather than an instance), the same algorithm applies, but starting from the class’s metaclass. This is where the metaclass structure from Part 1 becomes load-bearing code.

Suppose you write OrderedCollection new. The receiver is the OrderedCollection class object. To look up new, the interpreter reads OrderedCollection’s class pointer — which is OrderedCollection class, the metaclass — and begins searching there. OrderedCollection class has a method new (inherited from Behavior), so it’s found there.

Now suppose you write OrderedCollection name. Same process: look in OrderedCollection class. Not found there? Follow OrderedCollection class’s superclass pointer to Collection class, then Object class. Still not found? Continue up: Object class’s superclass is Class, then Behavior, then Object. Eventually you find name in Behavior (a method that returns the class’s name as a string).

The metaclass chain and the class chain eventually converge at Object. The lookup algorithm doesn’t need to handle them specially — it just keeps following superclass pointers until it either finds the method or runs off the end of the chain into nil.

The BlockClosure HomeContext Bug

November 3rd: “CRITICAL FIX: BlockClosure homeContext bug causing instance variable access errors.”

This was the most significant interpreter bug, and finding it took longer than it should have.

The symptom: methods that used blocks to access instance variables would, intermittently, read wrong values or produce type errors. A method like:

counter
    "Answer the current count."
    ^count

would work fine. But a method using a block to access the same variable:

increment
    "Increment the count by the given amount via a block."
    [:x | count := count + x] value: 1

would fail unpredictably. Sometimes the right thing happened. Sometimes count was read as nil, or as a SmallInteger from a completely unrelated slot, or the assignment would store to the wrong receiver.

The intermittency was the first clue. If the bug were in the block creation code, it would always fail. If it were in the variable access code, it would fail for every block that accessed outer variables. But it only failed sometimes, and the failures seemed to correlate with context depth and garbage collection cycles.

The bug was in how the homeContext pointer was maintained through context reuse.

The interpreter reused MethodContext objects to reduce allocation pressure — rather than allocating a new context for every method call, a pool of contexts was maintained and reused after a context completed. When a context was returned to the pool, its fields were cleared.

The problem: when a block was created inside a method, the block’s homeContext pointer was set to the MethodContext object. When that method completed and its context was returned to the pool and subsequently reused for a different method call, the BlockContext still held its homeContext pointer — pointing to the same memory, which now contained a completely different method’s receiver and variables.

If the block was evaluated after the home context had been reused, reading instance variables through homeContext was reading from the wrong method’s receiver. The receiver was some other object entirely.

The fix was to not reuse context objects that had live block references. A context is “live” for reuse purposes only when no BlockContext still holds a reference to it as its home context. This required reference counting on contexts used as home contexts, which added overhead but was necessary for correctness.

After this fix, a comprehensive test suite was written specifically for block context behavior: closures capturing variables at different depths, non-local returns from deeply nested blocks, blocks evaluated after their home method returned (expecting the BlockContext error), blocks passed to other methods and evaluated there. 188 tests, all passing by November 9th.

The Architecture Decision: Trampoline Interpreter

One structural decision worth mentioning: the interpreter is implemented as a trampoline.

A naive recursive interpreter calls C# methods to implement message dispatch: send foo to x → call the C# ExecuteMethod function → which may send bar → which calls ExecuteMethod again → and so on. This produces deep C# call stacks for any significant Smalltalk computation, and blows the C# stack on anything recursive.

A trampoline interpreter inverts this. The main interpreter loop runs in a single C# stack frame. When a message send needs to activate a new method, instead of recursing, the interpreter updates its internal active-context pointer to the new MethodContext and continues looping. When a method returns, it restores the sender context and continues. The “call stack” lives entirely in the Smalltalk heap, as the MethodContext sender chain. The C# stack is always flat.

This matches how the Blue Book describes the interpreter: it is an iterative machine, not a recursive one. The active context is a register. Message sends and returns are context switches.

The trampoline implementation was cleaner and more faithful to the specification, at the cost of some additional complexity in how non-local returns are handled (since a non-local return has to pop the entire block’s context chain to get back to the home method context, all within one iteration of the main loop).

Hitting 188 Tests

By mid-November, the interpreter handled:

All push, store, and return bytecodes
All message send forms (unary, binary, keyword, super sends)
Conditional and unconditional jumps (which implement ifTrue:, whileTrue:, etc. at the primitive level)
Block creation and evaluation (value, value:, etc.)
Non-local returns, including the error case for dead home contexts
Primitive dispatch with fallback, for arithmetic, comparisons, object identity, class testing
SmallInteger arithmetic, including overflow detection (overflow falls through to LargeInteger fallback methods)

The 188-test block context suite was the most thorough validation of the interpreter’s correctness. Passing all 188 tests meant the core execution model was right.

But the interpreter running in isolation wasn’t the goal. The goal was to run the Smalltalk-80 system code — the hundreds of global init expressions that needed to execute against the live heap. That turned out to be a different challenge entirely, with problems that had nothing to do with the interpreter.

Those are in Part 5.