こんにちは 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); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

— !