# 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 };
Copied!
# 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; } }
Copied!
2
3
4
5
6
7
8
9
10
11
12
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) { /* ... */ } }
Copied!
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 ámbitoparentEnv
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 new window))
También podemos acceder al prototipo de un objeto mediante la propiedad __proto__
del mismo:
> (4).__proto__
Copied!
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]; }
Copied!
2
3
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); } }
Copied!
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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); }
Copied!
2
3
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; };
Copied!
2
3
4
5
6
7
8
9
10
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
Copied!
2
3
4
5
6
7
8
9
10
11
12
13
14
# "Normal" Calls
If it is a normal call, we evaluate the operator,
let op = this.operator.evaluate(env);
Copied!
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));
Copied!
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); }
Copied!
2
3
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;
Copied!
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}])
Copied!
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); } }
Copied!
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Line 7 op = this.operator.evaluate(env)
will leave in op
the entry of topEnv["+"]
which was accordingly initialized:
// 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);`); });
Copied!
2
3
4
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])