week 4 · day 29

Capstone: A Tiny Stack Machine

The full brief — you architect and build it

Hard 45 min 180 xp

After this you can

› Design a bytecode virtual machine: opcodes, an operand stack, and a fetch-decode-execute loop
› Implement it in C using everything from the spine — arrays, structs, control flow, functions
› Understand your VM by seeing it mirror the real CPU you studied
› Produce a working interpreter you can extend, and read its own assembly

The build that ties it all together

Thirty days ago a byte was a mystery. Now you'll build a computer inside a computer: a tiny stack machine — a virtual CPU that executes its own little bytecode. This is the capstone because it uses *everything*: an array (the program and the stack), a struct (the machine state), control flow (the fetch-decode-execute loop), functions, and the exact mental model of a CPU you learned in week 1. When it runs, you'll realize you're not just using the machine — you understand it well enough to *build one*.

What a stack machine is

A stack machine is a CPU whose instructions operate on an operand stack instead of registers. PUSH 5 puts 5 on the stack; ADD pops the top two, pushes their sum. It's how the JVM, Python's bytecode, and WebAssembly work — and it's simpler to build than a register machine, so it's the perfect first VM. Your machine has three pieces, mirroring the real CPU (day 3):

an operand stack (an array + a stack pointer) — like the CPU's stack (day 11),
a program (an array of bytecode) and a program counter (index of the next instruction) —
like memory + rip,
a fetch-decode-execute loop — exactly the CPU's cycle (day 3).

The instruction set (you can extend it)

Define an opcode enum. A minimal but real set:

vm.h (the design)c

1typedef enum {
2    OP_PUSH,   // next byte is a value -> push it
3    OP_ADD,    // pop b, pop a, push a+b
4    OP_SUB,    // pop b, pop a, push a-b
5    OP_MUL,    // pop b, pop a, push a*b
6    OP_PRINT,  // pop and print the top
7    OP_HALT    // stop the machine
8} OpCode;
9 
10typedef struct {
11    int  stack[256];   // the operand stack
12    int  sp;           // stack pointer: index of the next free slot
13    const unsigned char *code;  // the bytecode program
14    int  pc;           // program counter: index of the next opcode
15    int  running;      // 1 while executing
16} VM;

The heart: fetch, decode, execute

The whole machine is one loop. Fetch the opcode at pc, advance pc, decode it (a switch), execute its effect on the stack. This *is* the CPU cycle from day 3, written in C:

vm.c (the loop — a sketch)c

1void run(VM *vm) {
2    while (vm->running) {
3        unsigned char op = vm->code[vm->pc++];   // FETCH (and advance pc)
4        switch (op) {                            // DECODE
5        case OP_PUSH: {
6            int v = vm->code[vm->pc++];           // operand follows the opcode
7            vm->stack[vm->sp++] = v;              // EXECUTE: push
8            break;
9        }
10        case OP_ADD: {
11            int b = vm->stack[--vm->sp];
12            int a = vm->stack[--vm->sp];
13            vm->stack[vm->sp++] = a + b;          // pop 2, push sum
14            break;
15        }
16        // OP_SUB, OP_MUL similar...
17        case OP_PRINT:
18            printf("%d\n", vm->stack[vm->sp - 1]);
19            break;
20        case OP_HALT:
21            vm->running = 0;
22            break;
23        }
24    }
25}

Key idea

Look at what you're doing: vm->pc is your rip, vm->code is your instruction memory, vm->sp and vm->stack are your rsp and stack, the switch is the CPU's instruction decoder, and the while is the fetch-decode-execute cycle. You are re-implementing, in C, the exact machine you spent a month learning — which is the surest possible proof that you understand it. The stack-pointer push/pop logic is day 11; the opcode dispatch is a cousin of day 20's dispatch table.

A program for your machine

Bytecode to compute (2 + 3) * 4 and print it — hand-assembled:

programc

1unsigned char prog[] = {
2    OP_PUSH, 2,      // stack: [2]
3    OP_PUSH, 3,      // stack: [2, 3]
4    OP_ADD,          // stack: [5]
5    OP_PUSH, 4,      // stack: [5, 4]
6    OP_MUL,          // stack: [20]
7    OP_PRINT,        // prints 20
8    OP_HALT
9};

Predict first

Trace the operand stack for this program: PUSH 10, PUSH 4, SUB, PUSH 2, MUL, PRINT, HALT. Note that SUB pops b then a and pushes a−b. What does it print?

finished reading?

Your task, you write the code

Build the stack machine

Implement the full VM in vm.c: the OpCode enum, the VM struct, an init function, and the run() fetch-decode-execute loop handling PUSH, ADD, SUB, MUL, PRINT, and HALT. Write at least two hand-assembled bytecode programs (including (2+3)*4 and one of your own) and run them, verifying the output by tracing the stack yourself first. Run under valgrind for a clean report and -fsanitize=address to catch any stack over/underflow. This is YOUR architecture — you may name opcodes and extend as you like, but it must correctly execute the programs. Draw on days 3, 11, 17, 18, 20.

deliverable: vm.c (+ your bytecode programs and hand-traces)

build & run

$ gcc -O0 -g -Wall -fsanitize=address vm.c -o vm && ./vm
$ valgrind ./vm

self-review before running

› The fetch-decode-execute loop correctly runs (2+3)*4 and prints 20
› Your own second program produces the output you traced by hand
› SUB does a−b in the right order (you got the pop order right)
› Clean valgrind / ASan report — no stack overflow or invalid access

stretchAdd more power: OP_DUP (duplicate top), OP_SWAP, an OP_JMP / OP_JZ (conditional jump using pc — now your VM has control flow, like day 9/10!), and a simple text 'assembler' that turns a string like "PUSH 2 PUSH 3 ADD PRINT" into bytecode. With jumps, your toy can compute loops — you've built a Turing-capable machine from a month of first principles.

Self-check

01In a stack machine, how does ADD work?

02The VM's fetch-decode-execute loop corresponds to what real hardware concept?

03In the VM, what plays the role of the CPU's rip (instruction pointer)?

04Why is building this VM strong evidence you understand the machine?

0/4 correct · 0/4 checked