Building a Language: The Evaluator

The parser already hands over a tree that says what goes with what. The most satisfying part is still missing: making that tree do something. That's the job of the evaluator.

Walking the tree

The evaluator walks the tree and, at every node, does what that node means. A number evaluates to itself. An addition evaluates its left side, then its right side, and adds the results. An si (if) evaluates its condition and, depending on the result, evaluates one branch or the other.

Since nodes contain other nodes, the evaluator calls itself. It's a chain of cases, one per node type (simplified):

export const evaluate = (node, env) => {
  if (node instanceof ast.Program) {
    return evaluateProgram(node, env);
  } else if (node instanceof ast.Number) {
    return new NumberObj(node.value);
  } else if (node instanceof ast.Infix) {
    const left = evaluate(node.left, env);
    const right = evaluate(node.right, env);
    return evaluateInfixExpression(node.operator, left, right);
  }
  // … one case per node type …
  else {
    return NULL;
  }
};

It's the most direct way to write an interpreter, and it works. The first things it evaluated were numbers and booleans; then operators, si, procedures. It can now compute fib(10) recursively, and gets 55.

A single kind of number

One of the first decisions was to remove a distinction. Up to this point the lexer only read integers (INT). Adding decimals meant choosing: two kinds of number, like Python or Pascal, or just one, like JavaScript.

I chose one: the token became NUM. In many courses the first language is C or Java, where 7 / 2 is 3 because both are integers: a rule with a good reason that nobody understands yet when they're starting out. In Codexivo, 7 / 2 is 3.5. Someone who's learning shouldn't have to fight the language before getting to the logic, or wonder why 3 and 3.0 are different things. If integer division is ever needed, it can be an operation with its own name.

Where variables live

A variable doesn't live in the tree. It lives in an environment: a dictionary of names to values that, when it can't find a name, asks the environment outside it.

get(name: string): Object | undefined {
  const obj = this.store.get(name);
  if (obj) {
    return obj;
  }
  if (this.outer) {
    return this.outer.get(name);
  }
  return undefined;
}

Every time a procedure is called, the evaluator creates a new environment with its parameters. The important question is which environment that new one points to on the outside. Codexivo's answer: the one where the procedure was created, not the one it's called from. That's why this works (procedimiento is procedure, regresa is return):

variable contador = procedimiento(inicio) {
  regresa procedimiento(paso) {
    regresa inicio + paso;
  };
};
variable desde_diez = contador(10);
desde_diez(5);

It evaluates to 15. When desde_diez (from ten) is called, contador (counter) has already finished, but the inner procedure still remembers its environment, and in that environment inicio (start) is 10. Nothing special had to be written for this: it came for free from storing, next to every procedure, the environment where it was born.

How a regresa gets out

regresa was harder than it looked. In this procedure:

variable a = procedimiento(n) {
  si (n > 0) {
    si (n > 1) { regresa 10; }
    regresa 1;
  }
};
a(5);

the regresa 10 is two blocks deep. When the evaluator finds it, finishing the inner si's block isn't enough: it has to get out of the outer si and the whole procedure.

The fix is to wrap the value. regresa 10 doesn't produce a 10, but a Return object holding the 10. Every block that sees a Return stops running its remaining statements and passes it up without opening it. Only the procedure call unwraps it. a(5) is 10, and regresa 1 never runs.

Errors in Spanish

Errors follow the same idea: they're just another value. If an addition gets a number and a boolean, it doesn't throw a JavaScript exception; it returns an error object with its message, in Spanish, with line and column:

ERROR: tipo de operando desconocido: NUMBER + BOOLEAN en la linea 1 columna 3

"Unknown operand type: NUMBER + BOOLEAN on line 1, column 3." The type names are still in English and the message doesn't say what to do, but it already says where.

Strings came in with that too, along with the first procedure in the library, longitud (length). longitud("año") is 3: the ñ is one letter, not two bytes.

What stays

The evaluator is where the language means something. The lexer decides what a word is, the parser decides what goes with what, but this is where it's decided what happens: that 7 / 2 is 3.5, that a procedure remembers where it was born, that a regresa gets out of everything.

Each of those decisions is small, and they all point the same way: whoever is learning should wrestle with the logic of their problem, not with the language. A number that behaves like it did in school, a regresa that gets out where you expect, an error that says where it is.

Try it

This is the Codexivo interpreter with the procedure that remembers where it was born. The memory view shows the environments: step through it and watch which environment stays alive after contador has finished.

variable contador = procedimiento(inicio) {
  regresa procedimiento(paso) {
    regresa inicio + paso
  }
}
variable desde_diez = contador(10)
imprimir(desde_diez(5))

Next time: arrays, which I've already started.