Hallo! Ich präsentiere Ihnen den dritten Teil meiner Übersetzung des Handbuchs zur Implementierung meiner JavaScript-Programmiersprache - PL Tutorial .

Vom Übersetzer

Wir werden unsere eigene Programmiersprache erstellen - λ-Sprache (im Original - λanguage). Während des Erstellungsprozesses werden wir viele interessante Techniken verwenden, wie z. B. rekursiven Abstieg, Kontrollübertragungsstil und grundlegende Optimierungstechniken. Es werden zwei Versionen des Interpreters erstellt - der reguläre und der CPS-Interpreter, der Transcompiler in JavaScript.

Der Autor des Originals ist Mihai Bazon , der Autor der berühmten UglifyJS-Bibliothek (ein Tool zum Minimieren und Formatieren von JS-Code).

PS Es gibt einen Fehler im Interpreter und Compiler: in Ausdrücken wie a() && b() oder a() || b() a() || b() beide Teile werden immer ausgeführt. Dies ist natürlich falsch, da a() für den Operator && falsch oder für || nicht falsch ist dann spielt der Wert von b() keine Rolle. Dies ist nicht schwer zu beheben.

CPS-Dolmetscher

Unsere λ-Sprache hat zwei Nachteile:

• Die Rekursion ist auf den JS-Stack beschränkt, daher haben wir keine normale Möglichkeit, Schleifen zu erstellen.
• Der Interpreter ist langsam, daher ist die Rekursion sehr langsam.

Jetzt werden wir den ersten Fehler korrigieren, ohne darauf zu achten, dass der Interpreter noch langsamer wird. Wir werden den Interpreter im CPS-Stil (Continuation-Passing Style) umschreiben.

Was ist eine "Fortsetzungstransfer"?

Sie tun dies die ganze Zeit in NodeJS:

 fs.readFile("file.txt", "utf8", function CC(error, data){ //   - "" //     'return', // 'readFile'  ,  . }); 

Bei jedem Schritt gibt es einen Rückruf, der aufgerufen wird, wenn Sie fortfahren müssen. Der Fortsetzungsübertragungsstil macht die Steuerelementübertragung „explizit“ - Sie verwenden weder return , throw , break noch continue . Es gibt keine impliziten Sprünge im Code. Sie können nicht einmal for- oder while Schleifen mit asynchronen Funktionen verwenden. Warum brauchen wir sie in diesem Fall in der Programmiersprache?

Das Schreiben von Code im Stil der Übertragung einer Fortsetzung ist schwierig und leicht zu machen, aber wir schreiben den Interpreter nur in diesem Stil neu.

Funktion evaluate

Die evaluate erhält drei Argumente: Ausdruck (AST), Kontext (Umgebung) und die Funktion, die aufgerufen wird, wenn das Ergebnis vorliegt. Hier ist der Code, für jedes Fragment gibt es eine Erklärung:

 function evaluate(exp, env, callback) { switch (exp.type) { 

Für Konstanten geben wir nur ihren Wert zurück. Denken Sie jedoch daran, dass wir keine return haben. Stattdessen rufen wir einfach den Rückruf auf und übergeben den Wert.

  case "num": case "str": case "bool": callback(exp.value); return; 

Der var Knoten ist ebenfalls einfach: Holen Sie sich die Variable aus dem Kontext und übergeben Sie sie an die Funktion:

  case "var": callback(env.get(exp.value)); return; 

Für das assign Knoten müssen wir den Wert des linken Ausdrucks ( right ) erhalten. Dazu rufen wir evaluate und übergeben eine Funktion, die das Ergebnis erhält (für die rechte Seite des Ausdrucks). Und dann rufen wir einfach den callback mit dem Variablenwert auf und setzen die Variable in den aktuellen Kontext:

  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; 

Fast das gleiche für Knoten vom Typ binary , aber hier müssen wir zuerst den Wert des left Feldes und erst dann den Wert des right Feldes erhalten. Dann rufen wir einfach den Rückruf auf und übergeben das Ergebnis der Operation:

  case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return; 

Der let Knoten sieht komplizierter aus, ist aber in der Tat einfach. Wir haben einige Variablen. Ihr def Feld (Anfangswert) kann leer sein. In diesem Fall setzen wir es auf false . Wenn es jedoch einen Wert gibt, müssen wir evaluate rekursiv aufrufen, um ihn zu erhalten.

Wenn Sie schon einmal mit NodeJS gearbeitet haben, haben Sie dies schon oft getan. Aufgrund der Rückrufe, die wir nicht verwenden können, müssen wir diese Ausdrücke einzeln interpretieren (stellen Sie sich die evaluate als asynchron vor). Die folgende loop (sofort aufgerufen) ruft den Kontext und die Nummer der Definition ab, die verarbeitet werden muss:

• Wenn diese Anzahl gleich der Anzahl der Variablen ( vars.length ) ist, bedeutet dies, dass wir bereits alle Ausdrücke definiert haben, damit wir den Hauptteil des Ausdrucks ausführen können. Bitte beachten Sie, dass wir diesmal keinen callback aufrufen, sondern ihn zur evaluate , der ihn dann aufruft.
• Wenn diese Zahl kleiner ist, müssen Sie die aktuelle Definition berechnen und eine Funktion übergeben, die die loop(scope, i + 1) aufruft, bevor Sie den Kontext kopieren.
  

    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; 

Der lambda Knoten wird wie zuvor in einer separaten Funktion verarbeitet:

  case "lambda": callback(make_lambda(env, exp)); return; 

Um zu interpretieren, if , interpretieren wir zuerst die Bedingung. Wenn es nicht falsch ist, interpretieren wir den Ausdruck then , in einem anderen Fall interpretieren wir else wenn es einen gibt, oder geben false wenn nicht. Nach wie vor und then wir den callback einfach als "Aktion nach Ausführung" des Ausdrucks:

  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; 

Der prog Knoten wird ähnlich wie der let Knoten interpretiert, jedoch mit dem Unterschied, dass wir den Kontext nicht kopieren oder Variablen definieren müssen. Und wieder haben wir eine loop , die eine Ausdrucksnummer akzeptiert. Wenn es gleich prog.length , haben wir alle Ausdrücke vervollständigt und geben einfach das Ergebnis des letzten Ausdrucks zurück (mit dem Wort "return" meine ich, wir rufen damit callback auf). Beachten Sie, dass wir uns den letzten Wert merken, indem wir ihn als Argument an die loop (am Anfang ist er false für den Fall, dass der Körper leer ist):

  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; 

Für einen Knoten vom Typ call wir func interpretieren und dann sind alle Argumente in Ordnung. Und wieder gibt es eine loop , die nach dem gleichen Prinzip wie let oder prog , mit dem Unterschied, dass sie jetzt ein Array erstellt:

  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; 

Nun, das Standardende: Wenn wir nicht wissen, was wir tun sollen, werfen Sie eine Ausnahme:

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

Möglicherweise stellen Sie fest, dass jeder der oben genannten case mit dem Schlüsselwort return endet. Es gibt jedoch keinen Rückgabewert - das Ergebnis wird immer an die callback .

Neue Funktion make_lambda

In diesem Interpreter erhalten alle Funktionen als erstes Argument eine „Fortsetzung“ - die Funktion, die wir aufrufen müssen, um das Ergebnis zu übergeben. Danach folgen die üblichen Funktionsargumente. Hier ist der neue Code für die Funktion 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; } 

Er ist nicht viel anders. Es fügt einem neuen Kontext neue Variablen hinzu. Wir müssen auch berücksichtigen, dass das erste Argument callback . Schließlich wird die evaluate verwendet, um den Funktionscode in einem neuen Kontext auszuführen, aber wie zuvor übergeben wir einen callback .

Dies ist übrigens der einzige Ort, an dem ich die for Schleife verwendet habe. Dies liegt daran, dass die Argumentwerte bereits berechnet wurden, als der Aufrufknoten verarbeitet wurde.

Native Funktionen

In diesem Interpreter erhalten native Funktionen als erstes Argument einen callback . Wir müssen uns daran erinnern, wenn wir native Funktionen definieren. Hier ist der Beispielcode für den neuen Interpreter:

 var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment(); // define the "print" primitive function globalEnv.def("print", function(callback, txt){ console.log(txt); callback(false); // call the continuation with some return value // if we don't call it, the program would stop // abruptly after a print! }); // run the evaluator evaluate(ast, globalEnv, function(result){ // the result of the entire program is now in "result" }); 

Kleiner Test

Versuchen wir noch einmal, die Fibonacci-Zahlen zu berechnen:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) ); 

Wenn wir jedoch versuchen, die 27. Zahl zu finden, erhalten wir einen Stapelüberlauf. Im Allgemeinen wächst der Stapel jetzt viel schneller, so dass sich herausstellte, dass wir die Fibonacci-Zahl jetzt nur bis zum 12. zählen können (zumindest in meinem Browser). Das ist nicht sehr gut, also musst du es irgendwie reparieren.

Wir schützen den Stapel

In einem CPS-Interpreter wächst der Stapel viel schneller, da der Interpreter Funktionen immer rekursiv aufruft und niemals ein Ergebnis zurückgibt. Obwohl wir im Dolmetscher zurückgekehrt sind, brauchen wir sie, aber im Falle einer sehr tiefen Rekursion erreichen wir sie nie.

Stellen wir uns vor, wie unser Stack nach einem sehr einfachen Programm aussieht. Ich werde den Pseudocode zeigen und env nicht hinzugefügt, da er hier keine Rolle spielt:

 print(1 + 2 * 3); ## : evaluate( print(1 + 2 * 3), K0 ) evaluate( print, K1 ) K1(print) #  'var',      evaluate( 1 + 2 * 3, K2 ) evaluate( 2 * 3, K3 ) evaluate( 2, K4 ) K4(2) # 2  ,      evaluate( 3, K5 ) #    3,      K5(3) K3(6) #  2*3 evaluate( 1, K6 ) #  ,  K6(1) K2(7) #  1+2*3 print(K0, 7) # ,     'print' K0(false) #  . 'print'  'false'. 

Erst nach dem letzten Aufruf reduziert eine lange Folge nutzloser return den Stapel. Wenn wir so viel Stapelspeicher für ein einfaches Programm verwenden, ist es schwer vorstellbar, was für fib(13) passieren wird.

Stapelschutz

In unserem neuen Interpreter wird der Stapel einfach nicht benötigt. Alles, was getan werden muss, nachdem ein Ausdruck in einem callback , der als Argument übergeben wird. Hier haben wir also eine Frage: Was wäre, wenn JavaScript es ermöglichen würde, den Stapel zu "sichern"? Dann können wir den Stapel fallen lassen und eine unendlich tiefe Rekursion wird funktionieren.

Stellen wir uns vor, wir haben eine GUARD Funktion, die dies kann. Es erhält zwei Werte: die aufzurufende Funktion und die Argumente, die übergeben werden müssen. Es wird überprüft: Wenn der Stapel zu tief ist, wird der Stapel gelöscht und die übergebene Funktion aufgerufen. In einem anderen Fall tut sie nichts.

Mit der neuen Funktion schreiben wir den Interpreter wie unten gezeigt neu. Ich werde nicht auf jeden Einzelfall GUARD , es gibt den Code, der zuvor beschrieben wurde, sondern mit der GUARD Funktion:

 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); } } 

Für anonyme Funktionen mussten wir einen Namen hinzufügen, damit wir sie an die GUARD Funktion übergeben konnten. Ich habe den Namen CC ( current continuation ) verwendet. Sie könnten arguments.callee , dies ist jedoch eine veraltete API.

Auch die gleiche Änderung in make_lambda :

 function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments); // <--  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; } 

Die Implementierung von GUARD sehr einfach. Wie komme ich aus einem tiefen Anruf heraus? Ausnahmen verwenden. Zu diesem Zweck gibt es eine globale Variable, die angibt, wie viel mehr Rekursion wir ausführen können. Wenn es Null erreicht, werfen wir das Continuation Objekt, in dem es eine Continuation-Funktion und Argumente gibt:

 var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; } 

Und am Ende brauchen wir eine Schleife, die Continuation Objekte Continuation . Wir müssen den Interpreter über diese Schleife aufrufen, damit alles funktioniert:

 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; } } 

Die Execute Funktion akzeptiert die Execute Funktion und die Argumente dafür. Es funktioniert in einer Schleife, aber achten Sie darauf, dass Sie return wenn die Funktion ohne Stapelüberlauf funktioniert. Wir hören sofort auf. STACKLEN jedes Mal zurückgesetzt, wenn wir eine Schleifeniteration starten. Ein Wert von 200 - passt gut. Wenn wir das Continuation Objekt abfangen, ersetzen wir eine neue Funktion und neue Argumente und setzen die Schleife fort. Aufgrund einer Ausnahme wird der Stapel auch gelöscht, damit wir fortfahren können.

Um den Interpreter zu starten, verwenden wir jetzt Execute :

 Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]); 

Test

Die fib Funktion funktioniert jetzt:

 fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) ); # 6765, ~300ms 

Schade, aber wenn Sie versuchen, fib(27) zu finden, fib(27) es ungefähr viermal so lange wie bei einem normalen Dolmetscher. Aber dann haben wir jetzt eine unendliche Rekursion:

 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 

Natürlich ist die λ-Sprache viel langsamer als JavaScript. Stellen Sie sich vor, jeder Zugriff auf eine Variable erfolgt über ein Environment . Es macht keinen Sinn zu versuchen, den Interpreter zu optimieren - wir werden keinen signifikanten Leistungsgewinn erzielen. Um die Leistung zu verbessern, gibt es eine Lösung: Kompilieren Sie die λ-Sprache in JS, und dies werden wir tun. Lassen Sie uns zunächst sehen, welche interessanten Dinge wir mit einem CPS-Interpreter tun können.

Fortsetzung

Nachdem der Interpreter im Stil der Übertragung von Fortsetzungen arbeitet und alle Funktionen, sowohl λ-Sprachfunktionen als auch native JS-Funktionen, die Fortsetzungsfunktion als erstes Argument erhalten, das das Ergebnis zurückgibt (dieses Argument ist für JavaScript-Funktionen erforderlich, obwohl es für λ-Sprachfunktionen unsichtbar ist).

Der variable callback bedeutet die Fortsetzung des gesamten Programms. Alles, was das Programm als nächstes tun wird. Wir werden diese Variable 'aktuelle Fortsetzung' oder k im Code nennen.

Wenn wir keine Fortsetzung verursachen, wird das Programm gestoppt. Wir können dies nicht aus der λ-Sprache heraus tun, da make_lambda sowieso die Fortsetzung aufruft. Aber wir können dies von einer nativen Funktion aus tun. Ich habe eine Funktion erstellt, um zu zeigen, wie dies funktioniert:

 globalEnv.def("halt", function(k){}); 

Dies ist eine Funktion, die nichts tut. Sie erhält die Fortsetzung ( k ), nennt sie aber nicht:

 println("foo"); halt(); println("bar"); 

Fazit:

 foo 

Wenn Sie den Aufruf von halt() löschen, println die Ausgabe: foo / bar / ***Result: false (da der letzte println false zurückgibt). Bei halt() nur foo . * Jetzt gibt es nicht einmal ein Ergebnis, da halt() keine Fortsetzung verursacht und daher der Rückruf, den wir zur evaluate - derjenige, der die Zeichenfolge ***Result anzeigt - niemals aufgerufen wird. Die Funktion, die evalu evaluate bemerkt nicht, dass das Programm gestoppt wurde. In NodeJS wäre das ein Schuss in den Fuß.

Stellen Sie sich vor, wir brauchen eine sleepe Funktion, die ein Programm stoppt, ohne den Browser zu stoppen (daher ohne dumme Schleifen). Wir können dies einfach mit einer nativen Funktion implementieren:

 globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]); //   ,  'false' }, milliseconds); }); 

Eine leichte Unannehmlichkeit ist, dass wir Execute , da setTimeout einen Rückruf verursacht, der dann Continuation setTimeout und niemand ihn setTimeout . So verwenden Sie es:

 let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done"); 

Fazit:

 0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false 

Beachten Sie, dass zwischen den einzelnen Zeilen eine geringfügige Verzögerung besteht. Sie können versuchen, diesen Code im Originalartikel auszuführen.

Dies ist bereits etwas, was Sie in normalem JavaScript nicht tun können, außer für die manuelle Übertragung der Fortsetzung (und Sie können auch keine for Schleife for ):

 (function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done"); //    } })(0); 

Stellen Sie sich vor, wie Sie die NodeJS-API in einer λ-Sprache verwenden können:

 globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){ // error handling is a bit more complex, ignoring for now Execute(k, [ data ]); // hope it's clear why we need the Execute }); }); globalEnv.def("writeFile", function(k, filename, data){ fs.writeFile(filename, data, function(err){ Execute(k, [ false ]); }); }); 

Verwendung:

 copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt"); 

Und das alles funktioniert asynchron. Keine Rückrufhölle mehr.

Hier ist ein interessanteres Beispiel. Ich habe die folgende native Funktion geschrieben:

 globalEnv.def("twice", function(k, a, b){ k(a); k(b); }); 

Das Programm verwendet zwei Argumente a und b und ruft die Fortsetzung zweimal auf, einmal für jedes Argument. Nennen wir es:

 println(2 + twice(3, 4)); println("Done"); 

Fazit:

 5 Done ***Result: false 6 Done ***Result: false 

Die Schlussfolgerung ist seltsam, wenn Sie noch nie mit der Weitergabe von Fortsetzungen gearbeitet haben, aber versuchen, diesen Code selbst zu verstehen. Ein kleiner Hinweis: Das Programm startet einmal, gibt aber das Ergebnis zweimal zurück.

Verallgemeinerung: CallCC

Wir haben mit dem Feuer gespielt, als wir native Funktionen geschrieben haben. In der Sprache λ gibt es keine Möglichkeit, die Ausführung der aktuellen Fortsetzung zu unterbrechen. CallCC hilft bei der Lösung dieses Problems. Der Name ist die Abkürzung für die Funktion aus Schema - call-with-current-continuation (im Schema normalerweise call / cc genannt).

 globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); }); 

Die aktuelle Fortsetzung wird in eine Funktion umgewandelt, die direkt aus der λ-Sprache aufgerufen werden kann. Diese Funktion ignoriert die ursprünglich discarded Fortsetzung und ruft stattdessen die Fortsetzung auf, die an die CallCC Funktion übergeben wurde.

Mit dieser Funktion können wir (bereits direkt in der λ-Sprache, nicht über native Funktionen!) Eine große Anzahl von Operatoren zur Steuerung des Ausführungsflusses implementieren, an die wir vorher noch nicht einmal gedacht haben - beginnend mit Ausnahmen und endend mit return . Beginnen wir mit dem letzten.

Implementierungsrückgabe

 foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo); 

Fazit:

 foo ***Result: DONE 

Die foo Funktion erhält ein Argument, das dasselbe wie die return von JavaScript tut (wird jedoch als reguläre Funktion aufgerufen). Es überspringt die aktuelle Fortsetzung (die 'bar' ausgeben würde) und beendet die Funktion, wobei der angegebene Wert zurückgegeben wird ("DONE"). Dies funktioniert natürlich nur, wenn Sie eine Funktion CallCC , die CallCC , um die Fortsetzung als return . Wir können einen Wrapper dafür erstellen:

 with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo(); 

Fazit:

 foo ***Result: DONE 

Der Vorteil dieser Methode ist, dass wir CallCC nicht mehr verwenden müssen, wenn wir foo aufrufen. Es wäre natürlich schön, wenn wir return als Argument akzeptieren oder die with-return Funktion verwenden müssten, aber in der Sprache gibt es keine Möglichkeit, syntaktischen Zucker direkt daraus hinzuzufügen, dafür müssen wir zumindest den Parser ändern (+1 für Lisp).

Übergänge

Zum Beispiel müssen wir ein Programm schreiben, das nach allen Paaren positiver Ganzzahlen bis zu 100 sucht, so dass, wenn ihre Multiplikation 84 ergibt. Dies ist keine schwierige Aufgabe, und Sie können sich sofort zwei verschachtelte Schleifen vorstellen, um sie zu lösen, aber hier gehen wir einen anderen Weg. Wir werden zwei Funktionen erstellen: guess und fail . Die erste wählt die Nummer aus und die zweite sagt ihr, "versuche es mit einer anderen Nummer". Wir werden sie so verwenden:

 a = guess(1); #  -  >= 1 b = guess(a); #  -  >= a if a * b == 84 { #    : print(a); print(" x "); println(b); }; fail(); #    `guess`     

:

 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"); })); #  EXIT 

• catch(TAG, function) , , TAG ', function .
• throw(TAG, value) , , TAG ' , value .

:

 ##  , 'throw'   . ##       `error`, ##     JavaScript.    . throw = λ(){ println("ERROR: No more catch handlers!"); halt(); }; catch = λ(tag, func){ CallCC(λ(k){ let (rethrow = throw, ret) { ##   ,     . throw = λ(t, val) { throw = rethrow; #   ,   . if t == tag then k(val) else throw(t, val); }; ##      . ret = func(); ##       (  'throw') ##    .   . throw = rethrow; # XXX ##  . ret; }; }); }; 

Ein Beispiel:

 # ... f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); })); 

catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .

. , catch . , throw , , catch , . Zum Beispiel:

 exit = false; #  . x = 0; # :   ,   'exit()'  CallCC( λ(k) exit = k ); ## 'exit()'   ... if x == 0 then catch("foo", λ(){ println("in catch"); x = 1; #  exit(); }); println("After catch"); throw("foo", "FOO"); 

Fazit:

 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()); # 1 println(foo()); # 2 println(foo()); # 3 println(foo()); # DONE 

yield , . , return . , , yield , .

:

 fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

fib . . yield . , , 50 , 50 .

, , , , .

, .

yield , , . , , return . , , yield , yield , . , . :

 with-yield = λ(func) { ## with-yield     λ() { CallCC(λ(kret){ # kret     let (yield) { ##  yield yield = λ(value) { # yield  ,    CallCC(λ(kyld){ # kyld    yield... func = kyld; # ...     kret(value); #  . }); }; ## , ,  ,   yield. func(yield); }; }); }; }; 

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); # 'return'  ,     }); #        . }; # λ(val) { # CallCC(λ(kret){ # return = kret; # <-  func(val || yield); }); }; }; }; 

, , 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()); ## yield 1 <-----------------  ---------------------------+ println(foo()); ## yield 2 | println(foo()); ## yield 3 | println(foo()); ##   "DONE",   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()); ##   : A. 1 B. 2 C. 3 D. DONE B. NO MORE CONTINUATIONS C. NO MORE CONTINUATIONS D. NO MORE CONTINUATIONS ***Result: false 

, : , , , , "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); }; }); ##   50   let loop (i = 0) { if i < 50 { println(fib()); loop(i + 1); }; }; 

 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) { ## 'yield'  'shift'     ##  'reset'.  ,   ,    ##   'func' — ,   `func()` ##    ,    . yield = λ(val) { shift(λ(k){ func = k; #    val; #    }); }; ##  `with-yield`      ##   'reset',    ,  ##   'yield' ( )    ##    λ(val) { reset( λ() func(val || 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()); #  1 println(foo()); #  2 println(foo()); #  3 println(foo()); #  DONE 

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)) ); })); 

Fazit:

 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 , .

Der interessanteste Teil dieses Codes ist, wie wir ihn implementiert gotohaben und warum wir ihn so gemacht haben (aber versuchen Sie es selbst herauszufinden):

 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); } }; 

Im nächsten Teil des Artikels werden wir mit der Arbeit am Compiler beginnen - jetzt funktioniert unser Code auch schnell!