48. Compiling expressions

A tree nobody needs

In Part III, 1 + 2 * 3 - 4 went through three stages. The scanner made a full list of tokens, the parser built a tree from them, and the interpreter walked the tree. If you now compiled that tree to bytecode, you would build it, walk it once to write bytes, and throw it away.

Drip’s bytecode compiler skips the middle. It parses and writes bytes in the same breath, so the tree never exists. From the outside it looks like any other compiler: source in, a chunk out.

One pass, one token at a time

The compiler doesn’t even ask for all the tokens. Its scanner, in companion/ts/src/vm/scanner.ts, hands out one token each time scanToken() is called. The compiler keeps just two: current, the lookahead, and previous, the one it just consumed:

function advance() {
  previous = current;
  for (;;) {
    current = scanner.scanToken();
    if (current.type !== 'error') break;
    errorAtCurrent(current.lexeme);
  }
}

A scan error comes back as a token of type 'error', whose lexeme is the message, so the compiler reports it and keeps going.

Emit

Writing bytes is one small function in compiler.ts:

const emit = (...bytes: number[]) => {
  for (const b of bytes)
    chunk().write(b, previous.line);
};
const emitConstant = (v: Value) =>
  emit(OP.CONSTANT, makeConstant(v));

Each byte is tagged with the line of previous, the token just consumed, which is how chapter 46’s error found line 3. emitConstant puts the value in the pool (checking the 256 limit) and writes the two bytes of OP_CONSTANT.

Pratt rules that write bytes

The compiler parses expressions with chapter 33’s Pratt loop, but each rule emits code instead of returning a node. A table gives every token type a prefix rule, an infix rule and a precedence:

'-': { prefix: unary, infix: binary,
       prec: Prec.TERM },
'+': { prefix: null, infix: binary,
       prec: Prec.TERM },
'*': { prefix: null, infix: binary,
       prec: Prec.FACTOR },
number: { prefix: number, infix: null,
          prec: Prec.NONE },

The rules themselves are tiny:

const number = () =>
  emitConstant(Number(previous.lexeme));

const unary = () => {
  const op = previous.type;
  parsePrecedence(Prec.UNARY);
  emit(op === '!' ? OP.NOT : OP.NEGATE);
};

const binary = () => {
  const op = previous.type;
  parsePrecedence(getRule(op).prec + 1);
  emit(OPCODE_FOR[op]); // simplified
};

Look where the emit is. unary and binary compile their operand first and emit their own opcode after. That’s chapter 45’s children-first order, falling out of the order of two lines of code. grouping emits nothing: it compiles the inside and consumes the ).

And the loop, nearly verbatim:

function parsePrecedence(prec: Prec) {
  advance();
  const prefix =
    getRule(previous.type).prefix;
  if (!prefix) {
    error('Expect expression.');
    return;
  }
  prefix();
  while (
    prec <= getRule(current.type).prec
  ) {
    advance();
    getRule(previous.type).infix!();
  }
}

It’s chapter 33’s loop in different clothes. There, pratt(minBp) stopped when bp <= minBp; here the loop continues while prec <= rule.prec, and binary asks for one level tighter than its own. Both make operators of equal strength group to the left. (The real code also passes a canAssign flag, for chapter 53.) Watch it compile print 1 + 2 * 3 - 4;:

The real disassembly agrees:

0000    1 OP_CONSTANT         0 '1'
0002    | OP_CONSTANT         1 '2'
0004    | OP_CONSTANT         2 '3'
0006    | OP_MULTIPLY
0007    | OP_ADD
0008    | OP_CONSTANT         3 '4'
0010    | OP_SUBTRACT
0011    | OP_PRINT

Fewer opcodes, and a catch

There’s no OP_GREATER_EQUAL. binary builds a >= b as “not (a < b)”, LESS then NOT, and <= and != the same way. One less case in the dispatch loop, at the cost of one extra instruction.

Statements are a few lines more. print compiles its expression and emits OP_PRINT. An expression statement like 1 + 2; emits OP_POP afterwards, so its unused value doesn’t stay on the stack. And the script ends with OP_NIL, OP_RETURN.

print 1 + 2 * 3 - 4;
print -(1 + 2) * 3;
print !(2 >= 3);
print "a" + "b" == "ab";
1 + 2; // compiled, then popped

Your turn

const OP = {
  CONST: 0, ADD: 1, SUB: 2, MUL: 3,
};
const PREC = { '+': 1, '-': 1, '*': 2 };
const OPCODE = {
  '+': OP.ADD, '-': OP.SUB, '*': OP.MUL,
};

function compile(tokens) {
  const code = [];
  const consts = [];
  let i = 0;
  const emit = (b) => code.push(...b);
  function parse(min) {
    consts.push(tokens[i++]);
    emit([OP.CONST, consts.length - 1]);
    while (PREC[tokens[i]] >= min) {
      const op = tokens[i++];
      // right operand, then the opcode
    }
  }
  parse(1);
  return { code, consts };
}

fn atLeast(a, b) {
  return a >= b;
}

let nan = 0 / 0;
print atLeast(2, 1);
print atLeast(1, 1);
print atLeast(0, 1);
print atLeast(nan, 1);

What you learned

• A single-pass compiler parses and generates code in the same read of the source. Drip’s never builds a syntax tree.
• The compiler pulls one token at a time and keeps only previous and current.
• To emit is to append bytes to the chunk, tagged with the line of the previous token. Emission order is execution order.
• Pratt rules emit their operands first and their opcode last, so the bytes come out children-first without a tree.
• >=, <= and != are two instructions each, which saves opcodes but gets NaN wrong for >= and <=.

Next: what a Drip value actually looks like inside the VM.