Interpretación de los Nodos del AST

Introducción

En el fichero src/ast.js de la práctica egg-interpreter encontrará las clases Value, Word y Apply para los distintos tipos de nodos del AST. todos los tipos de nodo disponen de un método evaluate(env) que evalúa/interpreta el nodo en el contexto de la memoria asociativa local que se pasa en el parámetro env.

El fichero ast.js exporta las tres clases:

module.exports = { Value, Word, Apply };

La Clase Value

Por ejemplo el código para los nodos Value puede ser algo así:

class Value {
  constructor(token) {
    this.type = token.type;
    this.value = token.value;
  }
  evaluate() {
    return this.value;
  }
  getIndex() {
    return this.value;
  }
}

Evaluar/interpretar un node Value es simplemente retornar su atributo value.

La Clase Word

Este es un extracto de la clase Word:

class Word {
  constructor(token) {
    this.type = token.type || 'word';
    this.name = token.name;
  }
  
  evaluate(env) {
    if (this.name in env) {
      return env[this.name];
    } else {
      throw new ReferenceError(`Undefined variable: ${this.name}`);
    }
  }
 
  getIndex() {
    return this.name;
  }
 
  leftEvaluate(env) {
    /* ... */
  }
}

Evaluar un nodo Word es también (aparentemente) sencillo.

El operador in devuelve true si la propiedad especificada this.name está en el objeto env especificado o su prototipo. Si hay una entrada this.name en la memoria actual, devolvemos el valor almacenado: env[this.name]

Los objetos env son objetos JS que son tratados como hashes y funcionan como memoria asociativa en nuestro intérprete.
El objeto env representa el ámbito actual
Las funciones en Egg disponen de su propio ámbito para guardar en él los parámetros y las variables locales. Por tanto en un instante de la ejecución del programa pueden existir múltiples ámbitos env
En cada instante de la ejecución los objetos env se estructuran en una lista enlazada
Cada ámbito/memoria env está anidado en un ámbito parentEnv que es su prototipo
En JS, los objetos pueden tener un objeto prototipo, del cual heredan métodos y propiedades. Un objeto prototipo del objeto puede tener a su vez otro objeto prototipo y así sucesivamente: Esta es la cadena de prototipos.
Podemos acceder al prototipo de un objeto mediante parentEnv = Object.getPrototypeOf(env) (Véase getPrototypeOf (opens in a new tab))

También podemos acceder al prototipo de un objeto mediante la propiedad __proto__ del mismo:

 > (4).__proto__

En JS los objetos heredan las propiedades de su prototipo y los prototipos se estructuran en una jerarquía que eventualmente acaba en la clase Object:

Así pues este código tan simple

    if (this.name in env) {
      return env[this.name];
    }

supone un recorrido de la lista enlazada de prototipos de los ámbitos env en búsqueda de la propiedad almacenada en this.name.

La Clase Apply

const { specialForms } = require("./registry.js");
 
/* ... */
 
class Apply {
  constructor(tree) {
    this.type = tree.type;
    this.operator = tree.operator;
    this.args = tree.args;
  }
 
  evaluate(env) {
    if (this.operator.type == 'word' && this.operator.name in specialForms) {
      return specialForms[this.operator.name](this.args, env);
    }
 
    try { 
      let op = this.operator.evaluate(env);
      let argsProcessed = this.args.map((arg) => arg.evaluate(env));
 
      if ((typeof op === "function")) {
        return op(...argsProcessed);
      }
 
    }
    catch (err) {
      throw new TypeError('Applying not a function or method ' + err);
    }
  }

The interpretation of Apply nodes is more involved. We divided into two types of interpretation.

Specials nodes

If they are a special form, like is the case if this.operator.name is for example if, while, fun, etc. we pass the AST forest inside this.args, along with the current scope env, to a specific interpreter function specialForms[this.operator.name] that handles the current operation this.operator.name

    if (this.operator.type == 'word' && this.operator.name in specialForms) {
      return specialForms[this.operator.name](this.args, env);
    }

Notice that in such case is the handler function specialForms[while] the one that is in charge to evaluate and interpret the current AST includen its children. For instance, the interpretation of an apply node with operator type while will be:

specialForms['while'] = function(args, env) {
  if (args.length != 2) {
    throw new SyntaxError('Bad number of args to while');
  }
 
  while(args[0].evaluate(env) !== false) {
    args[1].evaluate(env);
  }
  return false;
};

that will correctly interpret an Egg program like:

➜  egg-interpreter-solution git:(master) ✗ cat examples/while.egg 
do(
    def(i,1),
    while(<(i,4),
      do(
          print(*(i,i)),
          def(i, +(i,1))
      )
    )
)                                                                                                                     
➜  egg-interpreter-solution git:(master) ✗ bin/egg.js examples/while.egg 
1
4
9

"Normal" Calls

If it is a normal call, we evaluate the operator,

let op = this.operator.evaluate(env);

Let me repeat again the question:

Is it true that this.operator is always a node of type word?

Then we evaluate the AST forest in this.args:

let argsProcessed = this.args.map((arg) => arg.evaluate(env));

last, we check that op contains a JavaScript function and if so, we call it with the already processed arguments

if (typeof op === "function") {
  return op(...argsProcessed);
}

We will use plain JavaScript function values to represent Egg’s function values. We will come back to this later, when we study the special interpreter/evaluator called fun.

Interpreting +(2,3)

We will use JavaScript function values to inject primitives in our interpreter to add functionality. for instance JS functions with names print, +, *, etc. are injected in the top level topEnv scope

topEnv['+'] = (a, b) => a + b;

For example a program like +(2,3) will be translated by your parser onto an AST like

apply(operator: word{name: '+'}, args: [ value{value: 2}, value{value:3}])

that when the apply is interpreted this.operator.type is 'word' but this.operator.name is + which isn't in specialForms skipping lines 2-4.

  evaluate(env) { // ... inside the Apply class
    if (this.operator.type == 'word' && this.operator.name in specialForms) {
      return specialForms[this.operator.name](this.args, env);
    }
 
    try { 
      let op = this.operator.evaluate(env);
      let argsProcessed = this.args.map((arg) => arg.evaluate(env));
 
      if ((typeof op === "function")) {
        return op(...argsProcessed);
      }
 
    }
    catch (err) {
      throw new TypeError('Applying not a function or method ' + err);
    }
  }

Line 7 op = this.operator.evaluate(env) will leave in op the entry of topEnv["+"] which was accordingly initialized:

src/eggvm.js

// Code from the file src/eggvm.js ULL-ESIT-PL-2122/private-egg branch private2122
[ '+',  '-', '*', '/', '**', ].forEach(op => {
  topEnv[op] = new Function('...s', `return s.reduce((a,b) => a ${op} b);`);
});

Since this.args contains the array [value{value: 2}, value{value:3}] the map will leave in argsProcessed the array [2, 3] and so line 11 return op(...argsProcessed); is interpreted as the call topEnv['+'](...[2,3])

Repl Interpretation Assignment Interpretation