47. A stack-based VM

Where do the half-finished answers go?

The tree-walker never had to think about this. To evaluate 1 + 2 * 3 it called itself for 2 * 3, and the 6 came back as a return value, held in a JavaScript local until the + needed it. The host language’s call stack was quietly storing every half-finished answer.

Bytecode has no recursion to lean on. CONSTANT 1, CONSTANT 2, CONSTANT 3, MULTIPLY, ADD is a flat list, and the 1 has to wait somewhere while 2 * 3 happens. The answer is a stack the VM keeps for itself.

A stack of values

Drip’s stack is a big array plus a stack pointer, sp, the index of the next free slot. From companion/ts/src/vm/vm.ts:

readonly stack: Value[] =
  new Array(STACK_MAX).fill(null);
sp = 0;

push(v: Value) {
  this.stack[this.sp++] = v;
}
pop(): Value {
  return this.stack[--this.sp];
}
peek(distance: number): Value {
  return this.stack[this.sp - 1 - distance];
}

The array is made once, at full size. Pushing writes a slot and moves sp up; popping moves it down. Nothing is allocated or freed per value. peek(0) is the top, peek(1) the one below, without removing either.

The instruction pointer

The VM also needs to know where it is in the code. That’s one number:

const readByte = () => code[frame.ip++];
const readConstant = () =>
  constants[readByte()];

ip always holds the index of the next byte to read. Every read moves it on, so reading an instruction’s operand also steps over it. After OP_CONSTANT, ip has moved by two, and lands on the next opcode. (ip lives in frame because each function call will get its own, in chapter 56. For now there is one frame: the script.)

The dispatch loop

Now the heart of the VM. It reads an opcode and switches on it, forever, until an instruction tells it to stop. Step through it running the real chunk for print 1 + 2 * 3;:

for (;;) {
  const op = readByte();
  switch (op) {
    case OP.CONSTANT:
      push(readConstant()); break;
    case OP.ADD: {
      const b = pop(), a = pop();
      push(a + b); break;
    }
    case OP.MULTIPLY: {
      const b = pop(), a = pop();
      push(a * b); break;
    }
    case OP.PRINT:
      print(pop()); break;
    case OP.NIL: push(null); break;
    case OP.RETURN: return;
  }
}

Each case is short. Here is the real SUBTRACT:

case OP.SUBTRACT: {
  numbers();
  const b = this.pop() as number;
  const a = this.pop() as number;
  this.push(a - b);
  break;
}

Two details matter. b is popped first: the right operand was pushed last, so it’s on top. And numbers() checks the types with peek before anything is popped:

const numbers = () => {
  if (typeof this.peek(0) !== 'number' ||
      typeof this.peek(1) !== 'number') {
    this.runtimeError(
      'Operands must be numbers.');
  }
};

Checking in place leaves the stack untouched if the program fails, and later, when the garbage collector arrives, values still on the stack are safe from it. Try some arithmetic on the VM:

print 10 - 4 - 3;
print (1 + 2) * -3;
print 7 / 2;
print "con" + "cat";

Your turn

const OP = {
  CONST: 0, ADD: 1, SUB: 2, MUL: 3,
  NEG: 4, RETURN: 5,
};

function run(chunk) {
  const { code, constants } = chunk;
  const st = [];
  let ip = 0;
  for (;;) {
    const op = code[ip++];
    if (op === OP.CONST) {
      st.push(constants[code[ip++]]);
    } else if (op === OP.RETURN) {
      return st.pop();
    } else {
      throw new Error('bad op ' + op);
    }
  }
}

function maxDepth(code) {
  return 0;
}

What you learned

• A stack machine keeps intermediate values on a stack. Each instruction pops its inputs and pushes its result, so most need no operands.
• The stack is one preallocated array and sp, the next free slot. peek looks without popping.
• The instruction pointer is the index of the next byte; reading operands moves it past them.
• The dispatch loop fetches an opcode, switches on it and runs the case, forever. Right operands are popped first. Type checks peek before popping.

Next: the compiler that writes these bytes, straight from the source, with no tree in between.