Bonjour Je vous présente la troisième partie de ma traduction du guide d'implémentation de mon langage de programmation JavaScript - PL Tutorial .
Du traducteur
Nous allons créer notre propre langage de programmation - langage λ (dans l'original - λanguage). Dans le processus de création, nous utiliserons de nombreuses techniques intéressantes, telles que la descente récursive, le style de transfert de contrôle et les techniques d'optimisation de base. Deux versions de l'interpréteur seront créées - les interprètes standard et CPS, le trans-compilateur en JavaScript.
L'auteur de l'original est Mihai Bazon , l'auteur de la célèbre bibliothèque UglifyJS (un outil pour minimiser et formater le code JS).
PS Il y a un bug dans l'interpréteur et le compilateur: dans des expressions comme a() && b() ou a() || b() a() || b() deux parties sont toujours exécutées. Bien sûr, cela est faux car a() faux pour l'opérateur && , ou pas faux pour le || , alors la valeur de b() ne joue aucun rôle. Ce n'est pas difficile à résoudre.
Interprète CPS
Notre langue λ présente deux inconvénients:
- La récursivité est limitée à la pile JS, nous n'avons donc pas de méthode normale pour faire des boucles.
- L'interpréteur est lent, donc la récursivité est très lente.
Nous allons maintenant corriger la première faille sans prêter attention au fait que l'interprète deviendra encore plus lent. Nous réécrirons l'interpréteur dans le style "style de passage continu" (CPS).
Qu'est-ce qu'un "transfert de continuation"
Vous faites cela dans NodeJS tout le temps:
fs.readFile("file.txt", "utf8", function CC(error, data){
À chaque étape, il y a un rappel qui sera appelé lorsque vous devrez continuer. Le style de transfert de continuation rend le transfert de contrôle «explicite» - vous n'utilisez pas return , throw , break ou continue . Il n'y a pas de sauts implicites dans le code. Vous ne pouvez même pas utiliser for boucles for ou while avec des fonctions asynchrones. Dans ce cas, pourquoi en avons-nous besoin dans le langage de programmation?
Écrire du code dans le style de transmission d'une suite est difficile et facile à faire des erreurs, mais nous ne réécrirons l'interprète que dans ce style.
evaluate fonction
La fonction d' evaluate recevra trois arguments: expression (AST), contexte (Environnement) et la fonction qui sera appelée lorsque le résultat est. Voici le code, pour chaque fragment il y a une explication:
function evaluate(exp, env, callback) { switch (exp.type) {
Pour les constantes, nous retournerons simplement leur valeur. Mais rappelez-vous, nous n'avons pas de return - au lieu de cela, nous appelons simplement le rappel et passons la valeur.
case "num": case "str": case "bool": callback(exp.value); return;
Le nœud var est également simple - récupérez la variable à partir du contexte et passez-la à la fonction:
case "var": callback(env.get(exp.value)); return;
Pour assign nœuds, nous devons obtenir la valeur de l'expression gauche ( right ). Pour ce faire, nous appelons evaluate , en passant une fonction qui obtiendra le résultat (pour le côté droit de l'expression). Et puis nous appelons simplement le callback avec la valeur de la variable, définissant la variable dans le contexte actuel:
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;
Presque la même chose pour les nœuds de type binary , mais ici, nous devons d'abord obtenir la valeur du champ left , puis seulement la valeur du champ right . Ensuite, nous appelons simplement le rappel, en passant le résultat de l'opération:
case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return;
Le nœud let air plus compliqué, mais en fait c'est simple. Nous avons un certain nombre de variables. Leur champ def (valeur initiale) peut être vide, auquel cas nous le définirons sur false . Mais s'il y a une valeur, alors nous devons appeler récursivement pour l'obtenir.
Si vous avez déjà travaillé avec NodeJS, vous l'avez déjà fait plusieurs fois auparavant. En raison des rappels, nous ne pouvons pas utiliser for , par conséquent, nous devons interpréter ces expressions une par une (imaginez la fonction d' evaluate comme asynchrone). La fonction de loop ci-dessous (immédiatement appelée) obtient le contexte et le numéro de la définition à traiter:
- Si ce nombre est égal au nombre de variables (
vars.length ), cela signifie que nous avons déjà défini toutes les expressions afin de pouvoir exécuter le corps de l'expression. Veuillez noter que cette fois, nous n'appelons pas le callback , mais le transmettons pour evaluate , qui l'appellera ensuite. - Si ce nombre est inférieur, vous devez alors calculer la définition actuelle et passer une fonction qui appellera
loop(scope, i + 1) , avant de copier le contexte.
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;
Le nœud lambda sera traité dans une fonction distincte, comme précédemment:
case "lambda": callback(make_lambda(env, exp)); return;
Afin d'interpréter if , nous interprétons d'abord la condition. Si elle n'est pas fausse, alors nous interprétons l'expression then , dans un autre cas, interpréterons else s'il y en a une, ou retournons false sinon. Comme précédemment, pour then et else nous passons juste le callback comme «action à faire après exécution» de l'expression:
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;
Le nœud prog est interprété de manière similaire au nœud let , mais avec la différence que nous n'avons pas besoin de copier le contexte ou de définir des variables. Et encore une fois, nous avons une fonction de loop qui prend un numéro d'expression. Quand il est égal à prog.length , alors nous avons terminé toutes les expressions et nous retournons simplement le résultat de la dernière expression (par le mot "return" je veux dire que nous appelons callback avec lui). Veuillez noter que nous nous souvenons de la dernière valeur en la passant comme argument à la fonction de loop (au début c'est false pour le cas où le corps est vide):
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;
Pour un nœud de type call nous devons interpréter func et tous les arguments sont en ordre. Et encore une fois, il existe une fonction de loop qui fonctionne sur le même principe que let ou prog , à la différence qu'il construit désormais un tableau en conséquence:
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;
Eh bien, la fin standard: si nous ne savons pas quoi faire, jetez une exception:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Vous pouvez remarquer que chaque case ci-dessus se termine par le mot-clé return . Mais il n'y a pas de valeur de retour - le résultat est toujours transmis à la fonction de callback .
Nouvelle fonction make_lambda
Dans cet interpréteur, toutes les fonctions recevront une «continuation» comme premier argument - la fonction que nous devons appeler pour passer le résultat. Après, ce sont les arguments habituels de la fonction. Voici le nouveau code de la fonction 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; }
Il n'est pas très différent. Il ajoute de nouvelles variables à un nouveau contexte. Aussi, nous devons considérer que le premier argument est le callback . Enfin, la fonction d' evaluate est utilisée pour exécuter le code de la fonction dans un nouveau contexte, mais, comme précédemment, nous passons un callback .
Au fait, c'est le seul endroit où j'ai utilisé la boucle for . En effet, les valeurs d'argument sont déjà calculées lors du traitement du nœud d' call .
Fonctions natives
Dans cet interpréteur, les fonctions natives reçoivent un callback comme premier argument. Nous devons nous en souvenir lorsque nous définissons des fonctions natives. Voici l'exemple de code pour le nouvel interprète:
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment();
Petit test
Essayons à nouveau de calculer les nombres de Fibonacci:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) );
Mais, si nous essayons de trouver le 27e nombre, nous obtenons un débordement de pile. En général, la pile augmente maintenant beaucoup plus rapidement, il s'est donc avéré que maintenant nous ne pouvons compter le nombre de Fibonacci que jusqu'au 12 (au moins dans mon navigateur). Ce n'est pas très bon, vous devez donc le réparer d'une manière ou d'une autre.
Nous protégeons la pile
Dans un interpréteur CPS, la pile se développe beaucoup plus rapidement car l'interpréteur appelle toujours les fonctions de manière récursive, sans jamais retourner de résultat. Bien que nous ayons un return dans l'interpréteur, nous en avons besoin, mais dans le cas d'une récursion très profonde, nous ne les atteignons jamais.
Imaginons à quoi ressemble notre pile pour un programme très simple. Je vais montrer le pseudo code et je n'ai pas ajouté d' env car il ne joue aucun rôle ici:
print(1 + 2 * 3);
Ce n'est qu'après le dernier appel qu'une longue séquence de return inutiles réduit la pile. Si nous utilisons autant d'espace de pile pour un programme simple, il est difficile d'imaginer ce qui se passera pour fib(13) .
Protection contre la pile
Dans notre nouvel interprète, la pile n'est tout simplement pas nécessaire. Tout ce qui doit être fait après qu'une expression se soit callback dans un callback , qui est passé en argument. Nous avons donc ici une question: et si JavaScript permettait de "vider" la pile. Ensuite, nous pouvons supprimer la pile et une récursion infiniment profonde fonctionnera.
Imaginons que nous ayons une fonction GUARD qui peut le faire. Il obtient deux valeurs: la fonction à appeler et les arguments qu'elle doit être passés. Il vérifie: si la pile est trop profonde, il effacera la pile et appellera la fonction passée. Dans un autre cas, elle ne fait rien.
En utilisant la nouvelle fonction, nous réécrivons l'interpréteur comme indiqué ci-dessous. Je ne commenterai pas sur chaque cas individuel, il y a le code qui a été décrit précédemment, mais en utilisant la fonction 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); } }
Pour les fonctions anonymes, nous devions ajouter un nom afin de pouvoir les passer dans la fonction GUARD . J'ai utilisé le nom CC ( current continuation ). Vous pouvez utiliser arguments.callee , mais il s'agit d'une API obsolète.
En outre, le même changement dans 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 mise en œuvre de GUARD très simple. Comment sortir d'un appel profond? Utilisation d'exceptions. Pour ce faire, il y aura une variable globale qui indiquera combien de récursions supplémentaires nous pouvons faire. S'il atteint zéro, nous lançons l'objet Continuation , dans lequel il y aura une continuation - fonction et arguments:
var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; }
Et à la fin, nous avons besoin d'une boucle qui attrapera les objets Continuation . Nous devons appeler l'interprète via cette boucle pour que tout fonctionne:
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 fonction Execute accepte la fonction à appeler et ses arguments. Cela fonctionne en boucle, mais attention à return si la fonction fonctionne sans débordement de pile, on s'arrête tout de suite. STACKLEN réinitialisé à chaque démarrage d'une itération de boucle. Une valeur de 200 - correspond bien. Lorsque nous interceptons l'objet Continuation , nous substituons une nouvelle fonction et de nouveaux arguments et continuons la boucle. De plus, en raison d'une exception, la pile est effacée, afin que nous puissions continuer.
Pour démarrer l'interpréteur, nous utilisons maintenant Execute :
Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]);
Test
La fonction fib fonctionnera désormais:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) );
Dommage, mais si vous essayez de trouver fib(27) , cela prendra environ quatre fois plus de temps qu’un interprète habituel. Mais nous avons maintenant une récursion infinie:
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
Bien sûr, le langage λ est beaucoup plus lent que JavaScript. Imaginez, chaque accès à une variable passe par un objet Environment . Cela n'a aucun sens d'essayer d'optimiser l'interpréteur - nous n'obtiendrons pas un gain de performances significatif. Pour améliorer les performances, il existe une solution: compiler le langage λ en JS, et c'est ce que nous allons faire. Dans un premier temps, voyons quelles choses intéressantes nous pouvons faire avec un interpréteur CPS.
Continuation
Maintenant que l'interpréteur fonctionne dans le style de transmission de continuation, et toutes les fonctions, à la fois les fonctions de langage λ et les fonctions natives JS, reçoivent la fonction de continuation comme premier argument pour renvoyer le résultat (cet argument est requis pour les fonctions JavaScript, bien qu'il soit invisible pour les fonctions de langage λ).
Le callback variable signifie la poursuite de tout le programme. Tout ce que le programme fera ensuite. Nous appellerons cette variable «continuation actuelle», ou k dans le code.
De plus, si nous ne provoquons pas de suite, le programme s'arrêtera. Nous ne pouvons pas le faire à partir du langage λ car make_lambda invoque quand même la continuation. Mais nous pouvons le faire à partir d'une fonction native. J'ai créé une fonction pour montrer comment cela fonctionne:
globalEnv.def("halt", function(k){});
C'est une fonction qui ne fait rien. Elle reçoit la suite ( k ), mais ne l'appelle pas:
println("foo"); halt(); println("bar");
Conclusion:
foo
Si vous supprimez l'appel halt() , la sortie sera: foo / bar / ***Result: false (car le dernier println retourne false ). Mais avec halt() cela ne produit que foo . * Maintenant, il n'y a même plus de résultat car halt() ne provoque pas de continuation et, par conséquent, le rappel que nous avons passé pour evaluate - celui qui affiche la chaîne ***Result , n'est jamais appelé. La fonction qui a appelé evaluate ne remarque pas que le programme s'est arrêté. Dans NodeJS, ce serait une balle dans le pied.
Imaginez que nous ayons besoin d'une fonction sleepe qui arrête un programme sans arrêter le navigateur (donc sans boucles stupides). Nous pouvons facilement implémenter cela en utilisant une fonction native:
globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]);
Un léger inconvénient est que nous devons utiliser Execute , car setTimeout provoquera un rappel, qui lancera ensuite Continuation , et personne ne l'attrapera. Voici comment l'utiliser:
let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done");
Conclusion:
0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false
Remarque, il y a un léger délai entre chaque ligne. Vous pouvez essayer d'exécuter ce code dans l' article d'origine .
C'est déjà quelque chose que vous ne pouvez pas faire en JavaScript normal, sauf pour utiliser la transmission manuelle de la continuation (et aussi, vous ne pouvez pas utiliser for boucle for ):
(function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done");
Imaginez comment vous pouvez utiliser l'API NodeJS dans un langage λ:
globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){
Utilisation:
copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt");
Et tout cela fonctionne de manière asynchrone. Plus d'enfer de rappel.
Voici un exemple plus intéressant. J'ai écrit la fonction native suivante:
globalEnv.def("twice", function(k, a, b){ k(a); k(b); });
Le programme prend deux arguments a et b et appelle la continuation deux fois, une fois pour chaque argument. Essayons de l'appeler:
println(2 + twice(3, 4)); println("Done");
Conclusion:
5 Done ***Result: false 6 Done ***Result: false
La conclusion est étrange si vous n'avez jamais travaillé avec des continuations de passage auparavant, mais essayez de comprendre ce code vous-même. Un petit indice: le programme démarre une fois, mais renvoie le résultat deux fois.
Généralisation: CallCC
Nous avions l'habitude de jouer avec le feu lorsque nous écrivions des fonctions natives. Il n'y a aucun moyen en langage λ d'interrompre l'exécution de la suite en cours. CallCC aidera à résoudre ce problème. Le nom est l'abréviation de la fonction de Scheme - call-with-current-continuation (qui est généralement appelée call / cc dans Scheme).
globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); });
Il réifie la suite actuelle en une fonction qui peut être appelée directement à partir du langage λ. Cette fonction ignorera sa continuation discarded origine et appellera à la place la continuation qui a été transmise à la fonction CallCC .
En utilisant cette fonction, nous pouvons implémenter (déjà directement dans le langage, pas via des fonctions natives!) Un grand ensemble d'instructions de contrôle pour le flux d'exécution auquel nous n'avions même pas pensé auparavant - à partir d'exceptions et se terminant par return . Commençons par le dernier.
return implémentation
foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo);
Conclusion:
foo ***Result: DONE
La fonction foo reçoit un argument qui fait la même chose que le return de JavaScript (mais est appelé comme une fonction régulière). Il saute la suite en cours (qui afficherait 'bar') et quitte la fonction, renvoyant la valeur donnée ("DONE"). Bien sûr, cela ne fonctionne que si vous appelez une fonction en utilisant CallCC pour passer la continuation en return . Nous pouvons créer un wrapper pour cela:
with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo();
Conclusion:
foo ***Result: DONE
L'avantage de cette méthode est que nous n'avons plus besoin d'utiliser CallCC lorsque nous appelons foo . Ce serait bien, bien sûr, si nous n'avions pas besoin d'accepter return comme argument ou d'utiliser la fonction with-return , mais dans le langage il n'y a aucun moyen d'ajouter du sucre syntaxique directement à partir de lui, pour cela nous devons au moins modifier l'analyseur (+1 pour Lisp).
Transitions
Par exemple, nous devons écrire un programme qui recherchera toutes les paires d'entiers positifs jusqu'à 100 de sorte que si leur multiplication donne 84. Ce n'est pas une tâche difficile et vous pourriez immédiatement imaginer deux boucles imbriquées pour le résoudre, mais ici, nous allons dans une direction différente. Nous allons créer deux fonctions: guess et fail . La première choisira le numéro, et la seconde lui dira «essayez un autre numéro». Nous les utiliserons comme ceci:
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 exemple:
catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .
. , catch . , throw , , catch , . Par exemple:
exit = false;
Conclusion:
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); }; });
Conclusion 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)) ); }));
Conclusion:
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 , .
— goto , ( ):
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); } };
— !