Hola Le presento la segunda parte de mi traducción de la guía para implementar su lenguaje de programación JavaScript: PL Tutorial .
Del traductor
Crearemos nuestro propio lenguaje de programación - lenguaje λ (en el idioma original - λ). En el proceso de creación, utilizaremos muchas técnicas interesantes, como el descenso recursivo, el estilo de transferencia de control y las técnicas básicas de optimización. Se crearán dos versiones del intérprete: los intérpretes regulares y los de CPS, el transcompilador en JavaScript.
El autor del original es Mihai Bazon , autor de la famosa biblioteca UglifyJS (una herramienta para minimizar y formatear el código JS).
PD Hay un error en el intérprete y el compilador: en expresiones como a() && b() o a() || b() a() || b() ambas partes siempre se ejecutan. Esto, por supuesto, está mal porque a() falso para el operador && , o no es falso para el || , entonces el valor de b() no juega ningún papel. Esto no es difícil de arreglar.
Intérprete simple
En la parte anterior, escribimos 3 funciones: InputStream , TokenStream y parse . Para obtener el AST del código, usamos el siguiente código:
var ast = parse(TokenStream(InputStream(code)));
Escribir un intérprete es más fácil que un analizador sintáctico: simplemente atravesamos recursivamente el árbol y ejecutamos las expresiones en su orden normal.
Contexto ( Environment )
Para la correcta ejecución del código, necesitamos un contexto: un objeto que contenga todas las variables en una ubicación determinada. Se pasará como argumento a la función de evaluate .
Cada vez que ingresamos al nodo lambda , debemos agregar nuevas variables al contexto - argumentos de función. Si el argumento se superpone a la variable del bloque externo, debemos restaurar el valor anterior de la variable después de salir de la función.
La forma más fácil de hacer esto es usar el prototipo de herencia de JavaScript. Cuando ingresamos a una nueva función, creamos un nuevo contexto, establecemos el contexto externo como su prototipo y llamamos a la función en el nuevo contexto. Gracias a esto, no tenemos nada: en el contexto externo, todas sus variables permanecerán.
Aquí está la implementación del objeto Environment :
function Environment(parent) { this.vars = Object.create(parent ? parent.vars : null); this.parent = parent; } Environment.prototype = { extend: function() { return new Environment(this); }, lookup: function(name) { var scope = this; while (scope) { if (Object.prototype.hasOwnProperty.call(scope.vars, name)) return scope; scope = scope.parent; } }, get: function(name) { if (name in this.vars) return this.vars[name]; throw new Error("Undefined variable " + name); }, set: function(name, value) { var scope = this.lookup(name);
El objeto Environment tiene un campo parent que apunta al contexto externo. Será null para el contexto global. Tiene un campo vars en el que hay todas las variables que pertenecen a este contexto. Para un contexto global, es inmediatamente igual a un objeto vacío ( Object.create(null) ) y una copia de las variables del contexto primario ( Object.create(parent.vars) ) para uno no global.
Tiene varios métodos:
extend() : copia el contexto actual.lookup(name) : busca el contexto en el que name define la variable llamada name .get(name) : obtiene el valor de una variable llamada name . Lanza una excepción si la variable no se ha definido.set(name, value) : establece el valor de una variable. Este método busca el contexto en el que se define la variable. Si no está definido, y no estamos en un contexto global, se lanzará una excepción.def(name, value) : crea (o superpone o anula) una variable en el contexto actual.
evaluate función
Ahora que tenemos el objeto Environment , podemos pasar a resolver el problema principal. Esta función será un gran bloque de switch , que realizará alguna acción dependiendo del tipo de nodo transmitido:
function evaluate(exp, env) { switch (exp.type) {
Para literales, simplemente devolvemos su valor:
case "num": case "str": case "bool": return exp.value;
Las variables se toman del contexto (el nombre de la variable está contenido en el campo de value ):
case "var": return env.get(exp.value);
Para asignar, debemos asegurarnos de que en el lado izquierdo tengamos el nombre de la variable (nodo var ). Si no es así, simplemente lanzamos una excepción (no admitimos la asignación a otra cosa que no sean variables). A continuación, establecemos el valor de la variable usando env.set . Tenga en cuenta que el lado derecho de la expresión debe calcularse utilizando la llamada recursiva para evaluate :
case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); return env.set(exp.left.value, evaluate(exp.right, env));
Para un nodo de tipo binary debemos aplicar el operador para ambos operandos. Escribiremos la función apply_op más tarde. Además, llamamos evaluate para ambas partes de la expresión:
case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env));
Un nodo de tipo lambda devolverá un cierre de JavaScript normal, por lo que puede llamarse como una función normal incluso desde JavaScript. make_lambda función make_lambda , que mostraré más adelante:
case "lambda": return make_lambda(env, exp);
La ejecución del nodo if bastante simple: primero encontramos el valor de la condición. Si no es falso, devuelve el valor de la rama then . De lo contrario, si hay una rama else , entonces su valor, o false :
case "if": var cond = evaluate(exp.cond, env); if (cond !== false) return evaluate(exp.then, env); return exp.else ? evaluate(exp.else, env) : false;
El nodo prog es una secuencia de expresiones. Simplemente ejecutamos todas las expresiones en orden y tomamos el valor de esta última (el valor de la secuencia vacía es false ):
case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val;
Para un nodo de tipo call necesitamos llamar a una función. Antes de eso, encontraremos el valor de la función en sí, encontraremos los valores de todos los argumentos y llamaremos a la función usando apply :
case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); }));
Nunca llegaremos aquí, pero en caso de que agreguemos un nuevo tipo de nodo al analizador y olvidemos agregarlo al intérprete:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Esta fue la parte principal del intérprete. Arriba, utilizamos dos funciones que aún no hemos implementado, así que comencemos:
apply_op :
function apply_op(op, a, b) { function num(x) { if (typeof x != "number") throw new Error("Expected number but got " + x); return x; } function div(x) { if (num(x) == 0) throw new Error("Divide by zero"); return x; } switch (op) { case "+" : return num(a) + num(b); case "-" : return num(a) - num(b); case "*" : return num(a) * num(b); case "/" : return num(a) / div(b); case "%" : return num(a) % div(b); case "&&" : return a !== false && b; case "||" : return a !== false ? a : b; case "<" : return num(a) < num(b); case ">" : return num(a) > num(b); case "<=" : return num(a) <= num(b); case ">=" : return num(a) >= num(b); case "==" : return a === b; case "!=" : return a !== b; } throw new Error("Can't apply operator " + op); }
Recibe el tipo de operador y los argumentos. switch simple e intuitivo. A diferencia de JavaScript, que puede tomar cualquier valor, como variables, incluso aquellas que no tienen sentido. Requerimos que los operandos de los operadores aritméticos sean números y no permitan la división por cero. Para las cuerdas, llegaremos a algo más tarde.
make_lambda :
function make_lambda(env, exp) { function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; }
Como puede ver arriba, devuelve una función JavaScript normal que utiliza el contexto pasado y las funciones AST. Todo el trabajo se realiza solo cuando se llama a la función en sí: se crea un contexto, se establecen argumentos (si no son suficientes, se vuelven false ). Entonces el cuerpo de la función simplemente se ejecuta en un nuevo contexto.
Funciones nativas
Como puede ver, no teníamos forma de interactuar con JavaScript desde nuestro idioma. Solía usar las funciones print e println , pero no las println en ningún lado. Necesitamos escribirlos en JavaScript y simplemente agregarlos al contexto global.
Aquí hay un ejemplo de dicho código:
Código completo
Puede descargar todo el código que hemos escrito todo este tiempo. Se puede iniciar con NodeJS. Simplemente pase el código a la secuencia estándar:
echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js
Ejemplos de código
Nuestro lenguaje de programación, aunque simple, puede (en teoría) resolver cualquier problema que una computadora pueda resolver. Esto se debe a que algunos tipos más inteligentes que nunca seré, Alonzo Church y Alan Turing, una vez demostraron que el cálculo λ (cálculo lambda) es equivalente a una máquina Turing, y nuestro lenguaje λ implementa cálculo λ.
Esto significa que incluso si nuestro idioma no tiene ninguna oportunidad, podemos ser capaces de darnos cuenta utilizando lo que ya tenemos. O, si esto es difícil de hacer, podemos escribir un intérprete para otro idioma en este.
Ciclos
Los bucles no son un problema si tenemos recurrencia. Ya he mostrado un ejemplo de un bucle implementado además de la recursividad. Intentémoslo de nuevo.
print_range = λ(a, b) if a <= b { print(a); if a + 1 <= b { print(", "); print_range(a + 1, b); } else println(""); }; print_range(1, 10);
Pero aquí tenemos un problema: si aumentamos el número de iteraciones, digamos, a 1000. Por ejemplo, aparece el error "Tamaño máximo de la pila de llamadas excedido" después de 600. Esto sucede porque el intérprete es recursivo y la recursividad alcanza la máxima profundidad.
Este es un problema grave, pero hay una solución. Me gustaría agregar nuevas construcciones para la iteración ( for o while ), pero intentemos prescindir de ellas. La recursión se ve hermosa, así que dejémoslo. Más adelante veremos cómo sortear esta limitación.
Estructuras de datos (falta de ellas)
Hay tres tipos de datos en nuestro idioma λ: números, cadenas y tipos booleanos. Puede parecer que no puede crear tipos complejos, como matrices u objetos. Pero esto no es un tatuaje, tenemos un tipo más: función. Resulta que si seguimos el cálculo λ, entonces podemos crear cualquier estructura de datos, incluidos los objetos, incluso con herencia.
Lo mostraré en el ejemplo de las listas. Imaginemos que tenemos una función cons que crea un objeto que contiene dos valores. Llamemos a este objeto "celda" o "par". Vamos a nombrar uno de los valores "auto" y el otro "cdr". Solo porque se llaman así en Lisp. Ahora, si tenemos un objeto "celda", entonces podemos obtener sus valores usando las funciones car y cdr :
x = cons(10, 20); print(car(x));
Ahora podemos definir fácilmente una lista:
Una lista es un par que contiene el primer elemento en `car` y los elementos restantes en` cdr`. ¡Pero `cdr` puede contener solo un valor! Este valor será una lista. Una lista es un par que contiene el primer elemento en `car` y los elementos restantes en` cdr`. ¡Pero `cdr` puede contener solo un valor! Este valor será una lista. [...]
Este es un tipo de datos recursivo. Pero queda un problema: ¿cuándo debe detenerse? Lógicamente, deberíamos parar cuando cdr es una lista vacía. Pero, ¿qué es una lista vacía? Para hacer esto, agreguemos un nuevo objeto llamado "NIL". Se puede usar como pareja (podemos usar car y cdr en él, pero su resultado será NIL ). Ahora creemos una lista de los elementos 1, 2, 3, 4, 5:
x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x));
Se ve horrible cuando no hay una sintaxis especial para esto. Pero solo quería mostrar que esto se puede hacer usando las características del lenguaje λ existentes. Aquí está la implementación:
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL);
Cuando vi por primera vez cons / car / cdr hechos de esta manera, me sorprendió que no necesitaran un solo if (pero esto es extraño dado el hecho de que no está en el cálculo λ original). Por supuesto, ningún lenguaje de programación hace esto de esta manera, porque es extremadamente ineficiente, pero no hace que los cálculos λ sean menos hermosos. En un lenguaje claro, este código hace lo siguiente:
- la función
cons toma dos valores ( a y b ) y devuelve la función que los contiene. Esa función es el objeto mismo de la pareja. Ella toma un argumento y lo llama para ambos valores de la pareja. - La función
car llama al argumento pasado, pasando una función que devuelve el primer argumento. - la función
cdr hace lo mismo que la función car , pero la única diferencia es que la función pasada devuelve el segundo argumento. - la función
NIL funciona igual que cons , pero devuelve un par con dos valores iguales a NIL.
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); println(car(x));
Hay muchos algoritmos en las listas que se pueden implementar de forma recursiva y tener un aspecto lógico. Por ejemplo, aquí hay una función que llama a la función pasada para cada elemento de la lista:
foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println);
Y aquí hay otro que crea una lista para un rango de números:
range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL;
Las listas que implementamos anteriormente son inmutables (no podemos cambiar car o cdr después de que se haya creado la lista). La mayoría de Lisp tiene funciones para cambiar un par. En Scheme se les llama set-car! / set-cdr! . En Common Lisp, rplaca / rplacd . Esta vez usamos los nombres de Scheme:
cons = λ(x, y) λ(a, i, v) if a == "get" then if i == 0 then x else y else if i == 0 then x = v else y = v; car = λ(cell) cell("get", 0); cdr = λ(cell) cell("get", 1); set-car! = λ(cell, val) cell("set", 0, val); set-cdr! = λ(cell, val) cell("set", 1, val);
Esto muestra que podemos implementar estructuras de datos mutables. No profundizaré en cómo funciona, está claro en el código.
Podemos ir más allá e implementar los objetos, pero sin cambios en la sintaxis será difícil de hacer. Otra forma es implementar una nueva sintaxis en el tokenizador / analizador y agregar su procesamiento en el intérprete. Todos los lenguajes de programación más importantes hacen esto, y es necesario lograr un rendimiento normal. Agregaremos una nueva sintaxis en la siguiente parte del artículo.
[Del traductor: si está interesado en el cálculo lambda, hay un artículo interesante sobre Habré dedicado a este tema: cálculo Lambda en JavaScript .]
Nuevas construcciones de sintaxis
Nuestro lenguaje λ tiene bastantes construcciones sintácticas. Por ejemplo, no hay una forma directa de agregar nuevas variables. Como dije antes, debemos usar IIFE, por lo que se ve así:
(λ(x, y){ (λ(z){
Agregaremos la palabra clave let . Esto nos permitirá escribir algo como esto:
let (x = 2, y = 3, z = x + y) print(x + y + z);
Para cada variable en el bloque let , las variables anteriores deberían estar disponibles incluso desde el mismo bloque. Por lo tanto, el código anterior será equivalente a lo siguiente:
(λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2);
Estos cambios pueden realizarse directamente en el analizador y luego no requerirán cambios en el intérprete. En lugar de agregar un nuevo nodo let , podemos convertirlo en nodos call y lambda . Esto significa que no hicimos ningún cambio semántico en nuestro idioma, esto se llama "azúcar sintáctico", y la operación de convertir esto en nodos AST que existía antes se llama "sin azúcar" (original: "desugaring").
Sin embargo, debemos cambiar el analizador de todos modos. Agreguemos un nuevo nodo "let" porque se puede interpretar de manera más eficiente (no es necesario crear cierres y llamarlos de inmediato, solo necesitamos copiar y cambiar el contexto).
Además, agregaremos soporte para "let named", que estaba en Scheme. Facilita la creación de bucles:
print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0);
Este es un ciclo "recursivo" que cuenta la suma de 10 + 9 + ... + 0. Anteriormente, tendríamos que hacerlo así:
print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })());
Además, para facilitar esto, agregaremos la sintaxis de "funciones con un nombre". Se verá así:
print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10));
Modificaciones que deben hacerse para esto:
- Soporte para nombre opcional después de la palabra clave
lambda . Si está presente, entonces debemos agregar una variable al contexto actual que apunte a la función misma. Esto es exactamente lo mismo que las funciones con un nombre en JavaScript. - Soporte para la nueva palabra clave
let . Luego viene un nombre opcional y una lista (posiblemente vacía) de definiciones de variables en esta forma: foo = EXPRESSION , separadas por comas. El cuerpo de la expresión let es una expresión única (que, por supuesto, puede ser una secuencia de expresiones).
Cambios de analizador
Primero, un pequeño cambio en el tokenizador, agregue la palabra clave let a la lista de palabras clave:
var keywords = " let if then else lambda λ true false ";
Cambie la función parse_lambda que lea un nombre opcional:
function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null,
Ahora agregue una función que analice la expresión let :
function parse_let() { skip_kw("let"); if (input.peek().type == "var") { var name = input.next().value; var defs = delimited("(", ")", ",", parse_vardef); return { type: "call", func: { type: "lambda", name: name, vars: defs.map(function(def){ return def.name }), body: parse_expression(), }, args: defs.map(function(def){ return def.def || FALSE }) }; } return { type: "let", vars: delimited("(", ")", ",", parse_vardef), body: parse_expression(), }; }
Esto maneja dos casos. Si después de let hay un token de tipo var , este se let con un nombre. Además, leemos la lista de definiciones usando la función delimited , ya que están entre paréntesis y separadas por comas, y usamos la función parse_vardef , que se muestra a continuación. A continuación, devolvemos un nodo de tipo call , que llama inmediatamente a una función llamada (IIFE). Los argumentos de la función son las variables definidas por let , y el nodo de call pasará los valores como argumentos. Y, por supuesto, el cuerpo de la función se lee usando parse_expression() .
Si es un let simple, entonces devolvemos un nodo de tipo let con los campos vars y body . El campo vars contiene una matriz de variables en el siguiente formato: { name: VARIABLE, def: AST } , que se analizan mediante la siguiente función:
function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; }
Además, debe agregar una verificación para un nuevo tipo de expresión en la función parse_atom :
Cambios de intérprete
Dado que decidimos cambiar la estructura del AST en lugar de "descifrarlo" en los viejos tipos de nodos, debemos agregar el procesamiento de la nueva lógica al intérprete.
Para agregar soporte para el nombre de la función opcional, modificamos la función make_lambda :
function make_lambda(env, exp) { if (exp.name) {
Si la función tiene un nombre, cuando creamos el cierre, hacemos una copia del contexto y agregamos la función al contexto. El resto sigue igual.
Y finalmente, para procesar un nodo de tipo let , agregamos el siguiente caso al intérprete:
case "let": exp.vars.forEach(function(v){ var scope = env.extend(); scope.def(v.name, v.def ? evaluate(v.def, env) : false); env = scope; }); return evaluate(exp.body, env);
Tenga en cuenta que para cada variable se crea un nuevo contexto en el que se agrega una nueva variable. Después de eso, simplemente ejecutamos el cuerpo en el último contexto.
Ejemplos
println(let loop (n = 100) if n > 0 then n + loop(n - 1) else 0); let (x = 2, y = x + 1, z = x + y) println(x + y + z);
— .
. , , , . JavaScript λ.
:
globalEnv.def("fibJS", function fibJS(n){ if (n < 2) return n; return fibJS(n - 1) + fibJS(n - 2); }); globalEnv.def("time", function(fn){ var t1 = Date.now(); var ret = fn(); var t2 = Date.now(); println("Time: " + (t2 - t1) + "ms"); return ret; });
time , , , .
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); print("fib(10): "); time( λ() println(fib(10)) ); print("fibJS(10): "); time( λ() println(fibJS(10)) ); println("---");
, Google Chrome, n (27), λ , , JS 4 . , , .
λ JavaScript. , for / while ; JS. ? JS , .
, , JavaScript, , JavaScript.
, , . , .
Conclusión
, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).
, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.
: JavaScript. Parte 3: intérprete de CPS