call / ccとは何ですか？

https://stackoverflow.com/questions/612761

03-07-2019
|

質問

継続および call / cc 。すべての試みは失敗でした。誰かが私にこれらの概念を説明してもらえますか。理想的には、ウィキペディアや他のSOの投稿よりも現実的な例があります。

WebプログラミングとOOPのバックグラウンドがあります。また、6502アセンブリを理解し、Erlangとマイナーなランデブーをしました。しかし、それでもcall / ccに頭を包むことはできません。

解決

見てください。このトピックに関する継続パッシングスタイルの最良の説明を見つけました。 p>

その記事の詳細コピーを削除します：

著者：Marijn Haverbeke   日付：2007年7月24日

Schemeのcall-with-current-continuation関数は、計算、コールスタックの状態をキャプチャし、後で同じ状態を再開することを可能にします。このようなプリミティブの上に、さまざまな形式の例外処理とCのようなlongjmpトリックを実装できます。
function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);
これは、次のように変換できます。すべての関数に追加の引数を追加し、関数の継続を渡すために使用します。この継続は、関数が「戻る」後に発生しなければならないアクションを表す関数値です。（呼び出し）スタックは、継続渡しスタイルでは廃止されます＆＃8213;関数が別の関数を呼び出すとき、それが最後のことです。呼び出された関数が戻るのを待つのではなく、後で実行したいすべての作業を継続に入れて、関数に渡します。
function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});
大文字にするための膨大なドキュメントがあるとします。一度に移動するのに5秒かかりますが、ブラウザを5秒間フリーズするのはやや悪いスタイルです。 capitaliseTextのこの単純な変更を検討してください（globalいグローバルに注意を払わないでください）：
var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}
現在、20ノードごとに、計算は100ミリ秒間中断され、ユーザー入力に応答するための時間をブラウザインターフェイスに与えます。スレッド化の非常に原始的な形式＆＃8213;このように複数の計算を同時に実行することもできます。

これのより一般的に有用なアプリケーションは、XMLHttpRequests、またはそれらをシミュレートするために使用されるさまざまなIFRAMEおよびSCRIPTタグハックに関連しています。これらは常に、サーバーが送り返すデータを処理するために、何らかのコールバックメカニズムを操作する必要があります。簡単なケースでは、簡単な関数が機能します。または、いくつかのグローバル変数を使用して、データが戻った後に再開する必要がある計算の状態を保存できます。複雑な場合、たとえば、呼び出し元に値を返す必要のある関数がデータを使用している場合、継続は物事を大幅に簡素化します。継続をコールバックとして登録するだけで、リクエストが終了すると計算が再開されます。

他のヒント

Cと比較すると、現在の継続はスタックの現在の状態に似ています。実行を再開できるように、現在の関数の結果が完了するのを待っているすべての関数があります。現在の継続としてキャプチャされた変数は、指定された値を取得して待機中のスタックに返すことを除いて、関数のように使用されます。この動作は、スタックの下部にすぐに戻ることができるC関数 longjmp に似ています。。

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Cスタックと継続の重要な違いの1つは、スタックの状態が変更された場合でも、プログラムのどの時点でも継続を使用できることです。これは、スタックの以前のバージョンを基本的に復元して何度も使用できることを意味し、独自のプログラムフローをもたらします。

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

プログラムの状態を保存および復元する機能は、マルチスレッドと多くの共通点があります。実際、こちら。

継続を使用する簡単な例は、シングルプロセッサマシンにスレッド（必要に応じてファイバー）マネージャーを実装することです。スケジューラーは実行フローを定期的に中断し（または、ファイバーの場合はコードのさまざまな戦略的ポイントで呼び出されます）、継続状態（現在のスレッド）、別の継続状態（状態が以前に保存された別のスレッドに対応）に切り替えます。

アセンブリの背景を参照すると、継続状態は、命令ポインタ、レジスタ、スタックコンテキスト（ポインタ）などの詳細をキャプチャし、自由に保存および復元します。

継続を使用する別の方法は、代わりに継続コンテキストを使用して制御を相互に渡すことで、（メソッド呼び出しを複数のスレッドのようなエンティティで置き換える（実行中または一時停止中）を置き換えることを考える）「クラシック」 call パラダイムの。パラメータに依存するのではなく、グローバル（共有）データを操作します。これは、スタックが終了してから終了する必要がないという意味で call よりもある程度柔軟です（ call は入れ子にされた）が、コントロールは任意に渡すことができます。

Cなどの言語でこの概念を視覚化しようとする、単一の switch（continuation_point）{case point1：...} ステートメントで1つの大きなループを想像してください、各 case は継続保存ポイントに対応し、各 case 内のコードは continuation_point の値を変更し、その制御を放棄できます continuation_point を switch から break して、ループの次の反復を実行します。

質問の背景は何ですか？興味のある特定のシナリオはありますか？特定のプログラミング言語はありますか？上記のスレッド/ファイバーの例で十分ですか？

私を助けたのは、関数呼び出しを行う従来の言語では、関数呼び出しを行うたびに暗黙的に継続を渡すという考えです。

関数のコードにジャンプする前に、いくつかの状態をスタックに保存します（つまり、リターンアドレスをプッシュすると、スタックには既にローカルが含まれています）。これは本質的に継続です。関数が終了したら、実行フローの送信先を決定する必要があります。スタックに保存された継続を使用して、リターンアドレスをポップしてそこにジャンプします。

他の言語は、この継続の考え方を一般化し、関数呼び出しが行われた場所から暗黙的に継続するのではなく、コード実行を継続する場所を明示的に指定できます。

コメントに基づく編集：

継続は完全な実行状態です。実行の任意の時点で、プログラムを2つの部分（時間ではなく、スペース）に分割できます-この時点までに実行された部分と、ここから実行されるすべての部分です。「現在の継続」は、「ここから実行されるすべてのもの」です。（これは、プログラムの残りの部分が行うすべてを実行する関数のようなものと考えることができます）。したがって、 call / cc に提供する関数には、 call / cc が呼び出されたときに現在の継続が渡されます。この関数は、継続を使用して call / cc ステートメントに実行を返すことができます（継続を他の何かに渡しますが、直接使用すると、代わりに単純な戻りを行うことができるため、）。

call / ccを理解しようとしたときに、 call-with-current-continuation-for-C-programmers ページは役に立ちました。

私が見た中で最も良い説明は、Paul Grahamの本 Lisp 。

スクリプトがビデオゲームのステージであると想像してください。 Call / ccはボーナスステージのようなものです。

タッチするとすぐにボーナスステージ（つまり、call / ccに引数として渡される関数の定義[この場合はf]）に転送されます。

ボーナスステージは通常のステージとは異なります 。通常、これらのステージには要素（つまり、call / ccに渡される関数の引数）があります。そして、通常のステージに戻されます。

だから、多くの args があっても、そのうちの1つに到達しても問題ありません。したがって、実行は（arg 42）に達し、合計（+ 42 10）に戻ります。

また、注目に値する発言もあります：

call / ccですべての機能を使用できるわけではありません。期待しているので継続（関数）の場合、次のようなfは使用できません。 （define f（lambda（k）（+ k 42））、 sum a 関数。

また、（define f（lambda（k）（f 42 10））） 継続は1つの引数のみを予期するためです。

終了できます touching なしで終了します。この場合、関数は次のように進みます通常の関数（例：（define f（lambda（k）42）が終了し、 42）を返します。

call / ccを理解するには複数のレベルがあります。まず、用語とメカニズムの仕組みを理解する必要があります。次に、「実生活」でcall / ccがいつどのように使用されるかを理解します。プログラミングが必要です。

CPSを調べることで最初のレベルに到達できますが、代替案。

第2レベルでは、フリードマンの次の古典をお勧めします。

ダニエル・P・フリードマン。＆quot;継続申請書：招待チュートリアル＆quot;。 1988プログラミング言語の原則（POPL88）。 1988年1月。

FSchemeのcall / ccの説明と実装をご覧ください： http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx

命令的な観点から継続を理解するために使用したモデルは、次の命令へのポインターと組み合わされた呼び出しスタックのコピーです。

Call / ccは、継続を引数として（引数として渡された）関数を呼び出します。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow