こんにちは JavaScriptプログラミング言語を実装するためのガイドの翻訳の第3部であるPLチュートリアルを紹介します。

翻訳者から

独自のプログラミング言語-λ言語 （元の言語 -λanguage）を作成します。 作成のプロセスでは、再帰降下、コントロール転送スタイル、基本的な最適化手法など、多くの興味深い手法を使用します。 インタプリタの2つのバージョンが作成されます-通常のインタプリタとCPSインタプリタ、JavaScriptのトランスコンパイラ。

オリジナルの作者は、有名なUglifyJSライブラリ（JSコードを最小化およびフォーマットするためのツール）の作者であるMihai Bazonです。

PSインタプリタとコンパイラにバグがあります： a() && b()またはa() || b()ような式で a() || b()両方の部分が常に実行されます。 もちろん、これは間違ってa() &&演算子に対してa()偽であるか、 ||に対して偽ではないためです。 、 b()値は何の役割も果たしません。 これを修正するのは難しくありません。

CPSインタープリター

λ言語には2つの欠点があります。

• 再帰はJSスタックに限定されているため、ループを実行する通常の方法はありません。
• インタプリタは遅いため、再帰は非常に遅くなります。

ここで、インタプリタがさらに遅くなるという事実に注意を払うことなく、最初の欠陥を修正します。 インタプリタを「継続渡しスタイル」（CPS）スタイルに書き換えます。

「継続転送」とは

これは常にNodeJSで行います：

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

すべてのステップで、続行する必要があるときに呼び出されるコールバックがあります。 継続転送スタイルにより、コントロール転送が「明示的」になりますreturn 、 throw 、 breakまたはcontinueは使用しません。 コードには暗黙のジャンプはありません。 forまたはwhileループを非同期関数で使用することもできません。 この場合、なぜプログラミング言語でそれらが必要なのですか？

継続を送信するスタイルでコードを書くのは難しく、間違いを犯しやすいですが、インタープリターはそのスタイルでのみ書き換えます。

evaluate関数

evaluate関数は、式（AST）、コンテキスト（環境）、および結果が返されたときに呼び出される関数の3つの引数を受け取ります。 コードは次のとおりです。各フラグメントについて説明があります。

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

定数については、その値を返すだけです。 ただし、 returnはありません。代わりに、コールバックを呼び出して値を渡すだけです。

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

varノードも単純です-コンテキストから変数を取得し、関数に渡します：

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

assignノードの場合、左の式の値（ right ）を取得する必要があります。 これを行うには、 evaluateを呼び出して、結果を取得する関数を渡します（式の右側）。 そして、変数値でコールcallbackを呼び出し、現在のコンテキストで変数を設定します。

  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; 

binaryノードでもほぼ同じですが、ここではまずleftフィールドの値を取得し、次にrightフィールドの値を取得する必要があります。 次に、コールバックを呼び出して、操作の結果を渡します。

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

letノードはより複雑に見えますが、実際は単純です。 いくつかの変数があります。 それらのdefフィールド（初期値）は空かもしれません。その場合、 false設定しfalse 。 ただし、値がある場合は、それを取得するためにevaluate再帰的に呼び出す必要があります。

NodeJSを以前に使用したことがある場合は、すでにこれを何度も実行しています。 コールバックのため、 for使用することはできません。したがって、これらの式を一度に1つずつ解釈する必要があります（ evaluate関数を非同期と考えてください）。 以下のloop関数（すぐに呼び出されます）は、処理する必要のある定義とコンテキストを取得します：

• この数が変数の数（ vars.length ）に等しい場合、これは、式の本体を実行できるようにすべての式を既に定義していることを意味します。 今回はcallback呼び出さないことに注意してください。しかし、それをevaluateに渡し、それが次にそれを呼び出します。
• この数が少ない場合、現在の定義を計算し、コンテキストをコピーする前にloop(scope, i + 1)を呼び出す関数を渡す必要があります。
  

    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; 

前と同様に、ラムダノードは別の関数で処理されます。

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

ifを解釈するために、まず条件を解釈します。 falseでない場合、 then式を解釈し、別のケースではelseあればそれを解釈し、ない場合はfalse返しfalse 。 前と同じように、 thenおよびelseに対して、式の「実行後に実行するアクション」としてcallbackを渡すだけelse 。

  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; 

progノードはletノードと同様に解釈されますが、コンテキストをコピーしたり変数を定義したりする必要がないという違いがあります。 また、式番号を受け取るloop関数があります。 prog.lengthに等しい場合、すべての式が完成し、最後の式の結果が返されます（「return」という言葉で、コールcallbackを呼び出しcallback ）。 最後の値をloop関数への引数として渡すことで覚えていることに注意してください（最初は本体が空の場合はfalseです）：

  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; 

型callノードのfunc 、 funcを解釈する必要があり、すべての引数が順番に並んでいます。 また、 letまたはprogと同じ原理で動作するloop関数がありloop 、結果として配列を作成するという違いがあります：

  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; 

さて、標準的なエンディング：何をすべきかわからない場合は、例外をスローします：

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

上記の各caseがreturnキーワードで終わることに気付くかもしれません。 ただし、戻り値はありません。結果は常にcallback関数に渡されcallback 。

新しいmake_lambda関数

このインタープリターでは、すべての関数は最初の引数として「継続」を受け取ります。結果を渡すために呼び出す必要のある関数です。 その後は通常の関数引数です。 make_lambda関数の新しいコードは次の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; } 

彼はそれほど違いはありません。 新しいコンテキストに新しい変数を追加します。 また、最初の引数がcallbackであることを考慮する必要がありcallback 。 最後に、 evaluate関数は新しいコンテキストで関数コードを実行するために使用evaluateますが、前述のように、 callbackを渡しcallback 。

ちなみに、これはforループを使用した唯一の場所です。 これは、 callノードが処理されたときに引数値がすでに計算されているためです。

ネイティブ関数

このインタープリターでは、ネイティブ関数は最初の引数としてcallbackを受け取ります。 ネイティブ関数を定義するとき、これを覚えておく必要があります。 新しいインタープリターのサンプルコードを次に示します。

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

少しテスト

フィボナッチ数をもう一度計算してみましょう。

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

しかし、27番目の数値を見つけようとすると、スタックオーバーフローが発生します。 一般に、スタックは今よりずっと速く成長しているので、フィボナッチ数をカウントできるのは12日までです（少なくとも私のブラウザーでは）。 これはあまり良くないので、どうにか修正する必要があります。

スタックを保護します

CPSインタープリターでは、インタープリターは常に関数を再帰的に呼び出し、結果を返さないため、スタックは非常に速く成長します。 インタプリタにreturnますが、それらは必要ですが、非常に深い再帰の場合、それらに到達することはありません。

スタックが非常に単純なプログラムをどのように見えるか想像してみましょう。 擬似コードを表示しますが、ここでは何の役割も果たさないため、 env追加しませんでした。

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

最後の呼び出しの後のみ、無駄なreturn長いシーケンスはスタックを減らします。 単純なプログラムに非常に多くのスタック領域を使用する場合、 fib(13)何が起こるか想像するのは困難です。

スタック保護

新しいインタープリターでは、スタックは必要ありません。 何らかの式が引数として渡されるcallbackで発生した後に行う必要があるすべて。 ここで質問があります：JavaScriptがスタックを「ダンプ」することを可能にしたらどうなるでしょうか。 その後、スタックをドロップすると、無限に深い再帰が機能します。

これを行うことができるGUARD関数があると想像してみましょう。 2つの値を取得します。呼び出す関数と、渡す必要のある引数です。 スタックが深すぎる場合、スタックをクリアし、渡された関数を呼び出します。 別のケースでは、彼女は何もしません。

新しい関数を使用して、以下に示すようにインタープリターを書き換えます。 私は個々のケースについてコメントしません。前に説明したコードがありますが、 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); } } 

無名関数の場合、 GUARD関数に渡すことができるように名前を追加する必要がありました。 私は名前CC （ current continuation ）を使用しました。 arguments.callee使用できますが、これは時代遅れのAPIです。

また、 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; } 

GUARDの実装GUARD非常に簡単です。 ディープコールから抜け出すには？ 例外を使用します。 これを行うには、さらに多くの再帰を実行できることを示すグローバル変数があります。 ゼロに達した場合、 ContinuationオブジェクトをスローしますContinuationオブジェクトには、関数と引数の継続があります。

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

そして最後に、 Continuationオブジェクトをキャッチするループが必要です。 すべてが機能するように、このループを介してインタープリターを呼び出す必要があります。

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

Execute関数は、呼び出される関数とその引数を受け入れます。 ループ内で機能しますが、関数がスタックオーバーフローなしで機能する場合は、すぐに停止するように注意してください。 STACKLEN 、ループの反復を開始するたびにリセットされます。 値200-よく合います。 Continuationオブジェクトをキャッチすると、新しい関数と引数を置き換えて、ループを継続します。 また、例外のため、スタックはクリアされ、続行できます。

インタープリターを開始するには、 Executeを使用します。

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

テスト

fib関数が機能するようになりました：

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

残念ですが、 fib(27)を見つけようとすると、通常の通訳の約4倍の時間がかかります。 しかし、今では無限の再帰があります。

 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 

もちろん、λ言語はJavaScriptよりもはるかに遅いです。 想像してみてください。変数へのアクセスはすべて、 Environmentオブジェクトを経由します。 インタープリターを最適化しようとしても意味がありません。パフォーマンスが大幅に向上することはありません。 パフォーマンスを改善するための1つの解決策があります。λ言語をJSでコンパイルします。これが私たちがやることです。 最初に、CPSインタープリターで何ができるか見てみましょう。

継続

インタープリターは継続を送信するスタイルで動作し、すべての関数（λ言語関数とネイティブJS関数の両方）は、結果を返す最初の引数として継続関数を受け取ります（この引数は、λ言語関数には表示されませんが、JavaScript関数に必要です）。

変数callbackは、プログラム全体の継続を意味しcallback 。 プログラムが次に行うすべてのこと。 この変数を「現在の継続」またはコード内のkと呼びます。

また、継続を行わない場合、プログラムは停止します。 とにかくmake_lambdaは継続を呼び出すため、λ言語からこれを行うことはできません。 しかし、ネイティブ関数からこれを行うことができます。 どのように機能するかを示す関数を作成しました。

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

これは何もしない関数です。 彼女は継続（ k ）を受け取りますが、それを呼び出しません：

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

結論：

 foo 

halt()呼び出しを削除すると、出力は次のようになります： foo / bar / ***Result: false （最後のprintlnがfalse返すため）。 ただし、 halt() fooのみが出力されます。 * halt()は継続を引き起こさないため、結果もありません。したがって、 evaluateために渡したコールバック-文字列***Resultを表示するコールバックは呼び出されません。 evaluateを呼び出した関数は、プログラムが停止したことに気付きません。 NodeJSでは、それは足元でのショットになります。

ブラウザを停止せずに（したがって、愚かなループなしで）プログラムを停止するsleepe関数が必要だと想像してください。 ネイティブ関数を使用してこれを簡単に実装できます。

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

少し不便なのは、 setTimeoutがコールバックを引き起こし、それがContinuationをスローし、誰もキャッチしないため、 Executeを使用する必要があることです。 使用方法は次のとおりです。

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

結論：

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

各ライン間にわずかな遅延があることに注意してください。 元の記事でこのコードを実行してみてください 。

継続の手動送信を使用することを除いて、これはすでに通常のJavaScriptでは実行できないことです（また、 forループfor使用することもできません）。

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

NodeJS APIをλ言語で使用する方法を想像してください。

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

使用法：

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

そして、これはすべて非同期に機能します。 これ以上のコールバック地獄。

より興味深い例を次に示します。 次のネイティブ関数を作成しました。

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

プログラムは、2つの引数aとbを受け取り、引数ごとに1回、継続を2回呼び出します。 それを呼び出してみましょう：

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

結論：

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

これまでに継続の受け渡しに取り組んだことがないが、このコードを自分で理解しようとする場合、結論は奇妙です。 ちょっとしたヒント：プログラムは1回起動しますが、結果は2回返されます。

汎化： CallCC

ネイティブ関数を書くとき、私たちはかつて火で遊んでいました。 λ言語では、現在の継続の実行を中断する方法はありません。 CallCCはこの問題の解決に役立ちます。 名前は、Schemeの関数の省略形です-call call-with-current-continuation （通常、Schemeではcall / ccと呼ばれます）。

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

現在の継続を、λ言語から直接呼び出すことができる関数に具体化します。 この関数は、元のdiscarded継続を無視し、代わりにCallCC関数に渡された継続を呼び出します。

この関数を使用して、（ネイティブ関数ではなく、すでにλ言語で！）例外から開始してreturnで終了するreturnまで考えもしなかった実行フロー制御演算子の大きなセットを実装できます。 最後から始めましょう。

実装return

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

結論：

 foo ***Result: DONE 

foo関数は、JavaScriptからのreturnと同じ引数を受け取ります（ただし、通常の関数として呼び出されます）。 現在の継続（ 'bar'を出力する）をスキップし、関数を終了して、指定された値（ "DONE"）を返します。 もちろん、これはCallCCを使用して関数を呼び出し、継続をreturnとして渡す場合にのみ機能します。 これのラッパーを作成できます。

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

結論：

 foo ***Result: DONE 

このメソッドの利点は、 fooを呼び出すときにCallCCを使用する必要がなくなることです。 もちろん、引数としてreturnを受け入れるか、 with-return関数を使用する必要がない場合は良いでしょうが、言語では構文シュガーを直接追加する方法はありません。このため、少なくともパーサーを変更する必要があります（Lispの場合は+1）。

遷移

たとえば、乗算が84になる場合、100までの正の整数のすべてのペアを検索するプログラムを作成する必要があります。これは難しい作業ではなく、すぐに解決する2つのネストされたループを想像できますが、ここでは別の方法を説明します。 guessとfail 2つの関数を作成します。 最初の人は番号を選び、2番目の人は彼女に「別の番号を試してください」と伝えます。 次のように使用します。

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

例：

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

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

. , catch . , throw , , catch , . 例：

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

結論：

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

結論：

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

— !