The Stack-Based VM

A stack-based virtual machine executes bytecode instructions using a stack for operands and intermediate results. This is the most common VM architecture — used by the JVM, CPython, Lua, and CLR (.NET).

Stack vs Register VMs

Stack-based VMs (JVM, CPython, Lua 4.0): operands are implicit on the stack. ADD pops two values and pushes the result.

Register-based VMs (Lua 5.0+, Dalvik): operands are explicit register numbers. ADD R1, R2, R3 adds R2 and R3, stores in R1.

Stack VMs produce more instructions but each instruction is simpler. Register VMs produce fewer instructions but each is more complex. We build a stack VM because it is simpler to implement and understand.

The VM Structure

VM {
    chunk:   Chunk           // the bytecode to execute
    ip:      int             // instruction pointer (index into code)
    stack:   Value[256]      // operand stack (fixed size)
    sp:      int             // stack pointer (index of next free slot)
}

The Execution Loop

The heart of the VM is the fetch-decode-execute loop:

run():
    while true:
        instruction = chunk.code[ip++]     // fetch
        switch instruction:                 // decode & execute
            case OP_CONSTANT:
                index = chunk.code[ip++]
                push(chunk.constants[index])
            case OP_ADD:
                b = pop()
                a = pop()
                push(a + b)
            case OP_RETURN:
                print pop()
                return

Tracing Execution

For debugging, print the stack contents before each instruction:

          [ 1 ][ 2 ]
0004  OP_ADD
          [ 3 ]
0005  OP_RETURN
3

This makes it easy to verify that the VM is computing correctly.

Stack Overflow and Underflow

Overflow: pushing when the stack is full (too many nested expressions). Underflow: popping from an empty stack (compiler bug). Both should be detected and reported as errors rather than causing undefined behavior.

How CPython's VM Works

CPython's ceval.c contains the main evaluation loop — a giant switch statement with about 120 opcodes. The stack holds Python objects (PyObject pointers). Local variables are stored in a separate "fastlocals" array for performance, not on the operand stack.

Your Task

Build a stack-based VM with push, pop, arithmetic instructions, and a fetch-decode-execute loop. Add stack tracing for debugging.