Hola Les presento la tercera parte de mi traducción de la guía para implementar mi 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 de CPS
Nuestro lenguaje λ tiene dos inconvenientes:
- La recursión se limita a la pila JS, por lo que no tenemos una forma normal de hacer bucles.
- El intérprete es lento, por lo que la recursión es muy lenta.
Ahora corregiremos la primera falla sin prestar atención al hecho de que el intérprete será aún más lento. Reescribiremos el intérprete en el estilo de "estilo de paso de continuación" (CPS).
¿Qué es una "transferencia de continuación"?
Haces esto en NodeJS todo el tiempo:
fs.readFile("file.txt", "utf8", function CC(error, data){
En cada paso hay una devolución de llamada que se llamará cuando necesite continuar. El estilo de transferencia de continuación hace que la transferencia de control sea "explícita": no se utiliza return , throw , break o continue . No hay saltos implícitos en el código. Ni siquiera puede usar bucles for o while con funciones asincrónicas. En este caso, ¿por qué los necesitamos en el lenguaje de programación?
Escribir código al estilo de transmitir una continuación es difícil y fácil de cometer errores, pero solo reescribiremos al intérprete en ese estilo.
evaluate función
La función de evaluate recibirá tres argumentos: expresión (AST), contexto (Entorno) y la función que se llamará cuando el resultado sea. Aquí está el código, para cada fragmento hay una explicación:
function evaluate(exp, env, callback) { switch (exp.type) {
Para las constantes, solo devolveremos su valor. Pero recuerde, no tenemos return ; en su lugar, solo llamamos a la devolución de llamada y pasamos el valor.
case "num": case "str": case "bool": callback(exp.value); return;
El nodo var también es simple: obtenga la variable del contexto y páselo a la función:
case "var": callback(env.get(exp.value)); return;
Para assign nodos, necesitamos obtener el valor de la expresión izquierda ( right ). Para hacer esto, llamamos a evaluate , pasando una función que obtendrá el resultado (para el lado derecho de la expresión). Y luego solo llamamos a la callback con el valor de la variable, estableciendo la variable en el contexto actual:
case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(right){ callback(env.set(exp.left.value, right)); }); return;
Casi lo mismo para los nodos de tipo binary , pero aquí necesitamos primero obtener el valor del campo left , y solo luego el valor del campo right . Luego simplemente llamamos a la devolución de llamada, pasando el resultado de la operación:
case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return;
El nodo let parece más complicado, pero de hecho es simple. Tenemos cierto número de variables. Su campo def (valor inicial) puede estar vacío, en cuyo caso lo configuraremos como false . Pero si hay un valor, entonces necesitamos llamar a evaluate recursiva para obtenerlo.
Si ha trabajado con NodeJS anteriormente, ya lo ha hecho muchas veces. Debido a las devoluciones de llamada, no podemos usar for , por lo tanto, debemos interpretar estas expresiones de una en una (imagine la función de evaluate como asíncrona). La siguiente función de loop (llamada de inmediato) obtiene el contexto y el número de la definición que debe procesarse:
- Si este número es igual al número de variables (
vars.length ), significa que ya hemos definido todas las expresiones para poder ejecutar el cuerpo de la expresión. Tenga en cuenta que esta vez no llamamos a la callback , sino que la pasamos a evaluate , que luego la llamará. - Si este número es menor, debe calcular la definición actual y pasar una función que llamará a
loop(scope, i + 1) , antes de copiar el contexto.
case "let": (function loop(env, i){ if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function(value){ var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return;
El nodo lambda se procesará en una función separada, como antes:
case "lambda": callback(make_lambda(env, exp)); return;
Para interpretar if , primero interpretamos la condición. Si no es falso, entonces interpretamos la expresión de then , en otro caso, interpretamos si no existe, o devolvemos false si no. Como antes, para then y de lo else simplemente pasamos la callback como la "acción a realizar después de la ejecución" de la expresión:
case "if": evaluate(exp.cond, env, function(cond){ if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return;
El nodo prog se interpreta de manera similar al nodo let , pero con la diferencia de que no necesitamos copiar el contexto o definir variables. Y nuevamente, tenemos una función de loop que toma un número de expresión. Cuando es igual a prog.length , entonces hemos completado todas las expresiones y simplemente devolvemos el resultado de la última expresión (por la palabra "return" quiero decir que llamamos callback con ella). Tenga en cuenta que recordamos el último valor pasándolo como argumento a la función de loop (al principio es false para el caso cuando el cuerpo está vacío):
case "prog": (function loop(last, i){ if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){ loop(val, i + 1); }); else { callback(last); } })(false, 0); return;
Para un nodo de tipo call necesitamos interpretar func y luego todos los argumentos están en orden. Y de nuevo, hay una función de loop que funciona según el mismo principio que let o prog , con la diferencia de que ahora genera una matriz como resultado:
case "call": evaluate(exp.func, env, function(func){ (function loop(args, i){ if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){ args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return;
Bueno, el final estándar: si no sabemos qué hacer, lanza una excepción:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Puede notar que cada case anterior termina con la palabra clave return . Pero no hay valor de retorno: el resultado siempre se pasa a la función de callback .
Nueva función make_lambda
En este intérprete, todas las funciones recibirán una "continuación" como primer argumento, la función que debemos llamar para pasar el resultado. Después están los argumentos habituales de la función. Aquí está el nuevo código para la función make_lambda :
function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; }
El no es muy diferente. Agrega nuevas variables a un nuevo contexto. Además, debemos considerar que el primer argumento es la callback . Finalmente, la función de evaluate se usa para ejecutar el código de función en un nuevo contexto, pero, como antes, pasamos una callback .
Por cierto, este es el único lugar donde utilicé el bucle for . Esto se debe a que los valores del argumento ya se calcularon cuando se procesó el nodo de call .
Funciones nativas
En este intérprete, las funciones nativas reciben una callback como primer argumento. Debemos recordar esto cuando definimos funciones nativas. Aquí está el código de muestra para el nuevo intérprete:
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment();
Pequeña prueba
Intentemos calcular los números de Fibonacci nuevamente:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) );
Pero, si tratamos de encontrar el número 27, obtenemos un desbordamiento de pila. En general, la pila ahora está creciendo mucho más rápido, por lo que resultó que ahora podemos contar el número de Fibonacci solo hasta el 12 (al menos en mi navegador). Esto no es muy bueno, por lo que debe solucionarlo de alguna manera.
Protegemos la pila
En un intérprete de CPS, la pila crece mucho más rápido porque el intérprete siempre llama a las funciones de forma recursiva, sin devolver nunca un resultado. Aunque hemos return en el intérprete, los necesitamos, pero en el caso de una recursión muy profunda, nunca los alcanzamos.
Imaginemos cómo nuestra pila busca un programa muy simple. Mostraré el pseudocódigo y no env porque no juega ningún papel aquí:
print(1 + 2 * 3);
Solo después de la última llamada, una secuencia larga de return inútil reduce la pila. Si usamos tanto espacio de pila para un programa simple, es difícil imaginar lo que sucederá con fib(13) .
Protección de la pila
En nuestro nuevo intérprete, la pila simplemente no es necesaria. Todo lo que debe hacerse después de que se produzca alguna expresión en una callback , que se pasa como argumento. Así que aquí tenemos una pregunta: ¿qué pasaría si JavaScript hiciera posible "volcar" la pila? Entonces podemos soltar la pila, y funcionará una recursión infinitamente profunda.
Imaginemos que tenemos una función GUARD que puede hacer esto. Obtiene dos valores: la función para llamar y los argumentos que necesita pasar. Comprueba: si la pila es demasiado profunda, la borrará y llamará a la función pasada. En otro caso, ella no hace nada.
Usando la nueva función, reescribimos el intérprete como se muestra a continuación. No comentaré sobre cada caso individual, existe el código que se describió anteriormente, pero usando la función GUARD :
function evaluate(exp, env, callback) { GUARD(evaluate, arguments); switch (exp.type) { case "num": case "str": case "bool": callback(exp.value); return; case "var": callback(env.get(exp.value)); return; case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(env.set(exp.left.value, right)); }); return; case "binary": evaluate(exp.left, env, function CC(left){ GUARD(CC, arguments); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(apply_op(exp.operator, left, right)); }); }); return; case "let": (function loop(env, i){ GUARD(loop, arguments); if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function CC(value){ GUARD(CC, arguments); var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; case "lambda": callback(make_lambda(env, exp)); return; case "if": evaluate(exp.cond, env, function CC(cond){ GUARD(CC, arguments); if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; case "prog": (function loop(last, i){ GUARD(loop, arguments); if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){ GUARD(CC, arguments); loop(val, i + 1); }); else { callback(last); } })(false, 0); return; case "call": evaluate(exp.func, env, function CC(func){ GUARD(CC, arguments); (function loop(args, i){ GUARD(loop, arguments); if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){ GUARD(CC, arguments); args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; default: throw new Error("I don't know how to evaluate " + exp.type); } }
Para las funciones anónimas, necesitábamos agregar un nombre para poder pasarlas a la función GUARD . Usé el nombre CC ( current continuation ). Podrías usar arguments.callee , pero esta es una API desactualizada.
Además, el mismo cambio en make_lambda :
function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments);
La implementación de GUARD muy simple. ¿Cómo salir de una llamada profunda? Usando excepciones. Para hacer esto, habrá una variable global que indicará cuánta más recursividad podemos hacer. Si llega a cero, arrojamos el objeto Continuation , en el que habrá una continuación - función y argumentos:
var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; }
Y al final, necesitamos un bucle que atrape los objetos de Continuation . Debemos llamar al intérprete a través de este bucle para que todo funcione:
function Execute(f, args) { while (true) try { STACKLEN = 200; return f.apply(null, args); } catch(ex) { if (ex instanceof Continuation) f = ex.f, args = ex.args; else throw ex; } }
La función Execute acepta la función que se llamará y los argumentos para ello. Funciona en un bucle, pero preste atención para return si la función funciona sin desbordamiento de pila, nos detenemos de inmediato. STACKLEN restablece cada vez que comenzamos una iteración de bucle. Un valor de 200 : encaja bien. Cuando atrapamos el objeto Continuation , sustituimos una nueva función y argumentos, y continuamos el ciclo. Además, debido a una excepción, la pila se borra, para que podamos continuar.
Para iniciar el intérprete, ahora usamos Execute :
Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]);
Prueba
La función fib ahora funcionará:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) );
Es una pena, pero si intentas encontrar fib(27) , te tomará aproximadamente cuatro veces más que un intérprete habitual. Pero ahora tenemos una recursión infinita:
sum = λ(n, ret) if n == 0 then ret else sum(n - 1, ret + n); # compute 1 + 2 + ... + 50000 time( λ() println(sum(50000, 0)) ); # 1250025000, ~700ms
Por supuesto, el lenguaje λ es mucho más lento que JavaScript. Imagínese, cada acceso a una variable pasa por un objeto de Environment . No tiene sentido tratar de optimizar el intérprete; no obtendremos un aumento significativo en el rendimiento. Para mejorar el rendimiento, hay una solución: compilar el lenguaje λ en JS, y esto es lo que haremos. Al principio, veamos qué cosas interesantes podemos hacer con un intérprete de CPS.
Continuación
Ahora que el intérprete trabaja en el estilo de transmisión de continuación, y todas las funciones, tanto las funciones de lenguaje λ como las funciones nativas de JS, reciben la función de continuación como el primer argumento para devolver el resultado (este argumento es necesario para las funciones de JavaScript, aunque es invisible para las funciones de lenguaje λ).
La callback variable significa la continuación de todo el programa. Todo lo que el programa hará a continuación. Llamaremos a esta variable 'continuación actual', o k en el código.
Además, si no causamos una continuación, el programa se detendrá. No podemos hacer esto desde el lenguaje λ porque make_lambda invoca la continuación de todos modos. Pero podemos hacer esto desde una función nativa. Hice una función para mostrar cómo funciona esto:
globalEnv.def("halt", function(k){});
Esta es una función que no hace nada. Ella recibe la continuación ( k ), pero no la llama:
println("foo"); halt(); println("bar");
Conclusión
foo
Si elimina la llamada halt() , la salida será: foo / bar / ***Result: false (porque la última println devuelve false ). Pero con halt() esto solo genera foo . * Ahora ni siquiera hay un resultado porque halt() no causa una continuación y, por lo tanto, la devolución de llamada que pasamos para evaluate , la que muestra la cadena ***Result , nunca se llama. La función que llamó evaluate no nota que el programa se ha detenido. En NodeJS, eso sería un disparo en el pie.
Imagina que necesitamos una función de sleepe que detiene un programa sin detener el navegador (por lo tanto, sin bucles estúpidos). Podemos implementar esto fácilmente usando una función nativa:
globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]);
Un pequeño inconveniente es que tenemos que usar Execute , ya que setTimeout provocará una devolución de llamada, que luego arrojará Continuation , y nadie lo detectará. Aquí se explica cómo usarlo:
let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done");
Conclusión
0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false
Tenga en cuenta que hay un ligero retraso entre cada línea. Puede intentar ejecutar este código en el artículo original .
Esto ya es algo que no puede hacer en JavaScript normal, excepto para usar la transmisión manual de continuación (y tampoco puede usar un bucle for ):
(function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done");
Imagine cómo puede usar la API NodeJS en un idioma λ:
globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){
Uso:
copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt");
Y todo esto funciona de forma asíncrona. No más callback infierno.
Aquí hay un ejemplo más interesante. Escribí la siguiente función nativa:
globalEnv.def("twice", function(k, a, b){ k(a); k(b); });
El programa toma dos argumentos b y llama a continuación dos veces, una para cada argumento. Intentemos llamarlo:
println(2 + twice(3, 4)); println("Done");
Conclusión
5 Done ***Result: false 6 Done ***Result: false
La conclusión es extraña si nunca antes ha trabajado con pasadas continuas, pero intente comprender este código usted mismo. Una pequeña pista: el programa comienza una vez, pero devuelve el resultado dos veces.
Generalización: CallCC
Solíamos jugar con fuego cuando escribíamos funciones nativas. No hay forma en el lenguaje λ de interrumpir la ejecución de la continuación actual. CallCC ayudará a resolver este problema. El nombre es la abreviatura de la función de Scheme - call-with-current-continuation (que generalmente se llama call / cc en Scheme).
globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); });
Reifica la continuación actual en una función que se puede invocar directamente desde el lenguaje λ. Esta función ignorará su continuación discarded original y en su lugar llamará a la continuación que se pasó a la función CallCC .
Usando esta función, podemos implementar (¡ya directamente en el lenguaje λ, no a través de funciones nativas!) Un gran conjunto de operadores de control de flujo de ejecución en los que ni siquiera pensamos antes, comenzando por las excepciones y terminando con el return . Comencemos desde el último.
Implementación return
foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo);
Conclusión
foo ***Result: DONE
La función foo recibe un argumento que hace lo mismo que el return de JavaScript (pero se llama como una función regular). Omite la continuación actual (que generaría 'barra') y sale de la función, devolviendo el valor dado ("HECHO"). Por supuesto, esto solo funciona si llama a una función usando CallCC para pasar la continuación como return . Podemos crear un contenedor para esto:
with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo();
Conclusión
foo ***Result: DONE
La ventaja de este método es que ya no necesitamos usar CallCC cuando llamamos a foo . Sería bueno, por supuesto, si no tuviéramos que aceptar return como argumento o usar la función with-return , pero en el lenguaje no hay forma de agregar azúcar sintáctico directamente, para esto necesitamos al menos modificar el analizador (+1 para Lisp).
Transiciones
Por ejemplo, necesitamos escribir un programa que busque todos los pares de enteros positivos hasta 100, de modo que si su multiplicación produce 84. Esta no es una tarea difícil e inmediatamente podría imaginar dos bucles anidados para resolverlo, pero aquí vamos de una manera diferente. Crearemos dos funciones: guess y fail . El primero elegirá el número, y el segundo le dice "intente con otro número". Los usaremos así:
a = guess(1);
:
fail = λ() false; guess = λ(current) { CallCC(λ(k){ let (prevFail = fail) { fail = λ(){ current = current + 1; if current > 100 { fail = prevFail; fail(); } else { k(current); }; }; k(current); }; }); }; a = guess(1); b = guess(a); if a * b == 84 { print(a); print(" x "); println(b); }; fail();
, , a , 84 , b , 84 / a . guess : start end — . , .
try catch Common Lisp
— catch throw . :
f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); }));
catch(TAG, function) , , TAG ', function .throw(TAG, value) , , TAG ' , value .
:
Un ejemplo:
catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .
. , catch . , throw , , catch , . Por ejemplo:
exit = false;
Conclusión
After catch After catch ERROR: No more catch handlers!
'After catch' , 'ERROR: No more catch handlers!'. - , 'After catch' , . , '' , catch . , 'XXX' catch , throw , catch .
( , .)
CallCC (, , CallCC ). , — CallCC .
Yield
, , yield :
foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo());
yield , . , return . , , yield , .
:
fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; });
fib . . yield . , , 50 , 50 .
, , , , .
, .
yield , , . , , return . , , yield , yield , . , . :
with-yield = λ(func) {
yield , . , , , "DONE".
, . , - , , 4 :
println(foo()); foo();
.
№1: yield
, , , , yield ( kyld , , ) :
yield(2); yield(3); "DONE";
yield ? yield , , yield . , . , yield return , :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value);
, , yield , yield ( ). yield .
, , println(foo()) :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; func(val || yield); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo());
, . , print(foo()); foo() . , println(foo()) ? ...
№2: WTF?
. : , foo() . , ? — .
println(foo());
with-yield :
func(val || yield);
yield , , #... . , , ( "DONE" ), , "DONE" , . foo() , "DONE" . :
println(foo()); println("bar"); println(foo()); println(foo()); foo();
: 1, bar, 2, 3, DONE, bar, DONE, bar, ... .
func - , . , "no more continuations" :
val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val);
:
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); println(foo());
, :
1 2 3 DONE NO MORE CONTINUATIONS NO MORE CONTINUATIONS NO MORE CONTINUATIONS ***Result: false
1, 2, 3, DONE , "NO MORE CONTINUATIONS" . , :
print("A. "); println(foo()); print("B. "); println(foo()); print("C. "); println(foo()); print("D. "); println(foo());
, : , , , , "B." .
, yield , :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; });
Conclusión 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 ***Result: false
, (, ), " ".
: reset shift
yield : reset shift . " " — , . reset , shift , CallCC .
, reset shift — . reset , shift , reset .
, with-yield :
with-yield = λ(func) { let (yield) {
, reset . , , , reset . , . , .
:
with-yield = λ(func) { let (yield) { yield = λ(val) { shift(λ(k){ func = k; val; }); }; λ(val) { reset( λ() func(val || yield) ); }; } }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo());
reset shift
, . . . , , , . Scheme ( — Oleg Kiselyov ). .
, ( CallCC ) . :
var pstack = []; function _goto(f) { f(function KGOTO(r){ var h = pstack.pop(); h(r); }); } globalEnv.def("reset", function(KRESET, th){ pstack.push(KRESET); _goto(th); }); globalEnv.def("shift", function(KSHIFT, f){ _goto(function(KGOTO){ f(KGOTO, function SK(k1, v){ pstack.push(k1); KSHIFT(v); }); }); });
, reset , shift _goto , — . . _goto ( KGOTO ). , f ( CallCC ) - KGOTO , . , f , , KGOTO , , .
reset ( KRESET ) _goto(th) . , , , _goto . , , KGOTO KRESET .
, shift KGOTO , KGOTO pstack , SK , , shift ( shift — KSHIFT ). SK — — ( k1 ) . , shift2 , , pstack.push(k1); :
println(reset(λ(){ 1 + shift( λ(k) k(k(2)) ); })); println(reset(λ(){ 1 + shift2( λ(k) k(k(2)) ); }));
Conclusión
4 3 ***Result: false
shift ( k ), reset . — 1 shift :
1 + [?]
k , ? . — k(k(2)) . 2 , k(2) 3. , k(3) 3 , 4.
shift2 : k(2) .
CallCC
, , CallCC , . , JS, , , . , CallCC , .
La parte más interesante de este código es cómo lo implementamos gotoy por qué lo hicimos de esta manera (pero trate de resolverlo usted mismo):
pstack = NIL; goto = false; reset = λ(th) { CallCC(λ(k){ pstack = cons(k, pstack); goto(th); }); }; shift = λ(f) { CallCC(λ(k){ goto(λ(){ f(λ(v){ CallCC(λ(k1){ pstack = cons(k1, pstack); k(v); }); }); }); }); }; let (v = CallCC( λ(k){ goto = k; k(false) } )) { if v then let (r = v(), h = car(pstack)) { pstack = cdr(pstack); h(r); } };
En la siguiente parte del artículo, comenzaremos a trabajar en el compilador, ¡ahora nuestro código también funcionará rápidamente!