35. Evaluating expressions

A tree is not an answer

After eight chapters of scanning and parsing, 1 + 2 * 3 - 4 has become a beautiful tree: (- (+ 1 (* 2 3)) 4). But nobody asked for a tree. They asked for 3. The parser is the front end of the pipeline. This chapter starts the back end, and in a tree-walking interpreter the back end is surprisingly small.

Walking the tree

That is the whole algorithm. A node’s value depends only on its children’s values, so ask the children first, then combine:

function evaluate(e) {
  switch (e.kind) {
    case 'literal':
      return e.value;
    case 'binary': {
      const l = evaluate(e.left);
      const r = evaluate(e.right);
      return apply(e.operator, l, r);
    }
  }
}

Here is the core of it, simplified from evaluate in companion/ts/src/interpreter.ts:

function evaluate(e: Expr): Value {
  switch (e.kind) {
    case 'literal':
      return e.value;
    case 'grouping':
      return evaluate(e.expression);
    case 'unary': {
      const right = evaluate(e.right);
      if (e.operator.type === '!')
        return !isTruthy(right);
      return -num(e.operator, right);
    }
    case 'binary': {
      const l = evaluate(e.left);
      const r = evaluate(e.right);
      return binary(e.operator, l, r);
    }
  }
}

One case per kind of node, and TypeScript’s narrowing on kind knows which fields each case may touch. A grouping node does nothing of its own: the parentheses already did their work when the tree was shaped.

What a value looks like

While a Drip program runs, its values have to live somewhere. The interpreter is written in TypeScript, so the easiest home is a TypeScript value:

// runtime.ts (functions, classes: later)
type Value = null | boolean | number
  | string | DripCallable | DripInstance;

Drip         in the interpreter
nil          null
true         true
12.5         the number 12.5
"hi"         the string 'hi'

Borrowing the host’s values means + on two Drip numbers is just + on two JavaScript numbers. print needs one small adjustment, made by stringify: null must print as nil.

print 7;
print 10 / 4;
print "drip" + "!";
print nil;
print 2 < 3;
print !0;
print !nil;
print !"";

What counts as true

! needs to know whether a value is “true enough”, and so will if and while in chapter 38. Drip’s rule fits on one line:

const isTruthy = (v: Value) =>
  v !== null && v !== false;

Only nil and false are false. Everything else, including 0 and the empty string "", is true. That is not JavaScript’s rule, where 0 and '' are also falsy. The example above shows it: !0 printed false, because 0 is truthy in Drip.

When the types are wrong

Drip is dynamically typed: nothing checks "1" - 1 before the program runs. So the interpreter checks while it runs, right before it applies each operator:

case '+':
  if (typeof l === 'number' &&
      typeof r === 'number') return l + r;
  if (typeof l === 'string' &&
      typeof r === 'string') return l + r;
  throw new RuntimeError(op,
    'Operands must be two numbers or ' +
    'two strings.');
case '-':
  nums(op, l, r); // throws if not numbers
  return l - r;

Try '1' - 1 in JavaScript and you get 0: the string is quietly converted. Drip refuses. RuntimeError carries the operator’s token, and the token knows its line, so the message can say where:

print 1 + 2;
print "1" - 1;
print "never printed";

The first print ran and printed 3. The second stopped the program. Drip prints the message, then [line 2], and exits with code 70: not 65, because this program was perfectly valid Drip. It went wrong while running.

Your turn

Write the evaluator yourself, in plain JavaScript, with Drip’s type rules and truthiness. The extra one is stringify.

function isTruthy(v) {
  return v !== null && v !== false;
}

function evaluate(e) {
  switch (e.kind) {
    case 'literal':
      return e.value;
    case 'unary': {
      // '!' and '-'
      return undefined;
    }
    case 'binary': {
      // '+', '-', '*', '/'
      return undefined;
    }
  }
}

function stringify(v) {
  return String(v);
}

What you learned

• To evaluate a tree, evaluate the children, then combine their values. Values flow from the leaves up to the root.
• A tree-walking interpreter does exactly that, with one recursive function and one case per kind of node.
• Drip’s runtime values are JavaScript values: nil is null, and booleans, numbers and strings are themselves.
• Truthiness in Drip: only nil and false are false. 0 and "" are true.
• Operators check their operand types as they run. A mismatch is a runtime error: a message, the line, and exit code 70.

Next: statements, which do things instead of producing values, and the variables they remember.