53. Global variables in the VM

A VM with no memory

By the end of chapter 52 the VM is a good calculator. It compiles print (1 + 2) * 3; to bytecode and runs it. But try this:

let total = 10;
total = total + 5;
print total;

The compiler has no idea what let means, and the VM has nowhere to put total. In chapter 36 the tree-walker solved this with a Map from names to values. The VM will do the same thing, with one change: the table is the hash table you built in chapter 51, and its keys are the interned strings of chapter 52.

A name becomes a constant

A bytecode instruction can’t carry a string inside it: its operands are single bytes. So the compiler puts the variable’s name into the chunk’s constant pool, as a string, and the instruction refers to it by index. Here is the helper in compiler.ts:

const identifierConstant =
  (name: VmToken) =>
    makeConstant(
      heap.copyString(name.lexeme));

copyString interns the name, so every mention of total in the program becomes a pointer to the same string object. And here is how a let is compiled, slightly simplified:

function letDeclaration() {
  const global = parseVariable(
    'Expect variable name.');
  if (match('=')) expression();
  else emit(OP.NIL);
  consume(';', ...);
  emit(OP.DEFINE_GLOBAL, global);
}

parseVariable consumes the name and returns its constant index. Then the initializer is compiled, which leaves its value on top of the stack at run time. No initializer? Push nil. Finally, one instruction says “store the top of the stack under this name”.

Reading and assigning go through namedVariable. When a name isn’t a local (the next chapter), it becomes a global:

arg = identifierConstant(name);
if (canAssign && match('=')) {
  expression();
  emit(OP.SET_GLOBAL, arg);
} else {
  emit(OP.GET_GLOBAL, arg);
}

Here is the real disassembly of a four-line program:

let a = 1;
print a;
a = a + 2;
print a;

== script ==
0000    1 OP_CONSTANT         1 '1'
0002    | OP_DEFINE_GLOBAL    0 'a'
0004    2 OP_GET_GLOBAL       2 'a'
0006    | OP_PRINT
0007    3 OP_GET_GLOBAL       4 'a'
0009    | OP_CONSTANT         5 '2'
0011    | OP_ADD
0012    | OP_SET_GLOBAL       3 'a'
0014    | OP_POP
0015    4 OP_GET_GLOBAL       6 'a'
0017    | OP_PRINT
0018    5 OP_NIL
0019    | OP_RETURN

Look at the constant numbers after the global instructions: 0, 2, 4, 3, 6. Each mention of a added a new entry to the pool. They are all the same interned string, though, so the waste is a few slots of the pool, not a few copies of the text. (Constant 0 comes before constant 1 because the name is read before the initializer.) And a = a + 2 ends in POP: an assignment produces a value, and an expression statement throws it away.

Three instructions

Now the VM side, from the dispatch loop in vm.ts:

case OP.DEFINE_GLOBAL:
  this.globals.set(readString(),
    this.peek(0));
  this.pop();
  break;
case OP.GET_GLOBAL: {
  const name = readString();
  const v = this.globals.get(name);
  if (v === undefined)
    this.runtimeError(`Undefined ` +
      `variable '${name.chars}'.`);
  this.push(v);
  break;
}

readString reads the operand byte and fetches that constant. DEFINE_GLOBAL peeks at the value, stores it, and only then pops. That order looks fussy, but it keeps the value on the stack, where the garbage collector of chapter 58 can see it, until it is safely in the table. DEFINE_GLOBAL never complains about an existing name: like the tree-walker, Drip lets a second let at the top level simply replace the first.

The SET_GLOBAL trick

Assigning to a name that was never defined must be an error. The obvious code looks the name up, checks it is there, and then stores: two hash look-ups. The VM does it in one:

case OP.SET_GLOBAL: {
  const name = readString();
  if (this.globals.set(name,
      this.peek(0))) {
    this.globals.delete(name);
    this.runtimeError(`Undefined ` +
      `variable '${name.chars}'.`);
  }
  break;
}

Table.set returns true when the key was new. For a correct program that never happens, so the common case costs a single set. For a mistaken one, the VM has just created a variable that shouldn’t exist, so it deletes it again before reporting the error. A program that is about to stop anyway can afford the extra work. Notice also that there is no pop: the value stays, because print a = 3; needs it.

Step through the whole story, including a slot collision and the tombstone that chapter 51’s delete leaves behind:

0000 CONSTANT       '1'
0002 DEFINE_GLOBAL  'a'
0004 GET_GLOBAL     'a'
0006 PRINT
0007 GET_GLOBAL     'a'
0009 CONSTANT       '2'
0011 ADD
0012 SET_GLOBAL     'a'
0014 POP
0015 CONSTANT       '5'
0017 SET_GLOBAL     'b'

Found late, on purpose

A global is looked up by name when the instruction runs, not when it is compiled. That has a useful consequence. A function body can mention a global that doesn’t exist yet, as long as it exists by the time the function is called:

fn show() {
  print greeting;
}

let greeting = "hello";
show();
greeting = "bye";
show();

When show is compiled, greeting is just a string in its constant pool. By the time show() runs GET_GLOBAL, the let has run and the name is in the table. That is what lets two top-level functions call each other, whichever comes first in the file.

Your turn

The core exercise is a small VM loop: you write the three global instructions. The extra one is a Drip program for the real VM.

// Opcodes of a tiny VM.
const CONST = 0, POP = 1, PRINT = 2;
const ADD = 3, DEF = 4, GET = 5;
const SET = 6;

// set() returns true if k was new.
class Table {
  constructor() { this.m = new Map(); }
  get(k) { return this.m.get(k); }
  set(k, v) {
    const isNew = !this.m.has(k);
    this.m.set(k, v);
    return isNew;
  }
  delete(k) { this.m.delete(k); }
}

const undef = (n) => {
  throw new Error(
    `Undefined variable '${n}'.`);
};

function run(code, k, g) {
  const stack = [];
  const out = [];
  const top = () => stack.at(-1);
  let ip = 0;
  while (ip < code.length) {
    const op = code[ip++];
    if (op === CONST) {
      stack.push(k[code[ip++]]);
    } else if (op === POP) {
      stack.pop();
    } else if (op === PRINT) {
      out.push(String(stack.pop()));
    } else if (op === ADD) {
      const b = stack.pop();
      stack.push(stack.pop() + b);
    } else if (op === DEF) {
      // your code here
    } else if (op === GET) {
      // your code here
    } else if (op === SET) {
      // your code here
    }
  }
  return { out, left: stack.length };
}

fn tick() {
  // your code here
}

let count = 0;
tick();
tick();
tick();
print count;

What you learned

• The compiler stores a global’s name in the constant pool, and the global instructions take its index as their operand.
• The VM’s global table is a hash table keyed by interned strings.
• DEFINE_GLOBAL stores then pops. GET_GLOBAL pushes or reports Undefined variable. SET_GLOBAL stores and leaves the value on the stack.
• SET_GLOBAL sets first and deletes again if the key was new: one look-up for correct programs.
• Globals are found by name at run time, so a function can use a global defined after it.

Next: local variables, which skip the table entirely.