継続を実装するにはどうすればよいですか?
https://stackoverflow.com/questions/6512
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は C で書かれた Scheme インタープリターに取り組んでいます。現在、C ランタイム スタックを独自のスタックとして使用していますが、継続の実装に関して小さな問題が発生しています。私の現在の解決策は、Cスタックを手動でヒープにコピーし、必要に応じてコピーして戻すことです。標準の C ではないことを除けば、このソリューションは理想的とは言えません。
C で Scheme の継続を実装する最も簡単な方法は何ですか?
解決
あなたに役立つかもしれない記事を読んだことを覚えています。 M.T.A.のチェイニー :-)
私が知っている Scheme の実装には、次のようなものがあります。 SISC, 、呼び出しフレームをヒープに割り当てます。
@オーリー:すべての呼び出しフレームがヒープ上にある場合は、ホイスティングを行う必要はありません。もちろん、パフォーマンスにはトレードオフがあります。ホイストにかかる時間と、ヒープ上のすべてのフレームを割り当てるために必要なオーバーヘッド。おそらく、インタープリターで調整可能な実行時パラメーターにする必要があります。:-P
他のヒント
優れた要約は次の場所にあります。 一流の継続のための実装戦略, 、Clinger、Hartheimer、Ost による記事。特に Chez Scheme の実装に注目することをお勧めします。
スタックのコピーはそれほど複雑ではなく、パフォーマンスを向上させるために利用できる、よく理解されているテクニックが多数あります。ヒープ割り当てフレームの使用も非常に簡単ですが、明示的な継続を使用しない「通常の」状況ではオーバーヘッドが発生するというトレードオフが発生します。
入力コードを継続渡しスタイル (CPS) に変換すると、スタックを完全に削除するだけで済みます。ただし、CPS はエレガントですが、フロントエンドに別の処理ステップが追加され、特定のパフォーマンスへの影響を克服するために追加の最適化が必要になります。
ゼロから始める場合は、Continuation Passing Style (CPS) 変換を検討する必要があります。
良い情報源としては、「LISP in small Pieces」や マーク・フィーリーのスキームを 90 分間で説明するプレゼンテーション.
Dybvig の論文については今のところ言及されていないようです。読んでいてとても楽しいです。ヒープベースのモデルは実装が最も簡単ですが、スタックベースのスタックはより効率的です。文字列ベースのモデルは無視します。
R.ケント・ディブヴィグ。「スキームの 3 つの実装モデル」。http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
ReadScheme.org で実装に関する文書も確認してください。http://library.readscheme.org/page8.html
要約は次のとおりです。
この論文では、スキームプログラム言語の3つの実装モデルを紹介します。RSTは、これまでのほとんどのスキーム実装で何らかの形で使用されるヒープベースのモデルです。2つ目は、ほとんどのプログラムを実行する際のヒープベースのモデルよりもかなり環境に優しい新しいスタックベースのモデルです。3つ目は、スキームの複数プロセッサの実装で使用することを目的とした新しい文字列ベースのモデルです。
ヒープベースのモデルは、実際のパラメーターリスト、バインディング環境、呼び出しフレームなど、ヒープ内のいくつかの重要なデータ構造を割り当てます。
スタックベースのモデルは、可能な限りこれらの同じ構造をスタックに割り当てます。これにより、ヒープの割り当てが少なくなり、メモリの参照が少なく、命令シーケンスが短くなり、ごみ収集が少なくなり、メモリの方が効力的に使用されます。
文字列ベースのモデルは、これらの構造のバージョンをプログラムテキストに割り当てます。これは、一連のシンボルとして表されます。文字列ベースのモデルでは、スキームプログラムはスキームをサポートするために特別に設計されたFFP言語に翻訳されます。この言語のプログラムは、複数のプロセッサの文字列削減コンピューターであるFFPマシンによって直接実行されます。
スタックベースのモデルは、すぐに実用的な利益をもたらします。これは、著者のChezスキームシステムが使用するモデルであり、スキームの高性能実装です。文字列ベースのモデルは、マシンが実現したら、FFPマシンのFFPの高レベルの代替品としてスキームを提供するのに役立ちます。
これまでに得た素晴らしい回答のほかに、Andrew Appel の回答もお勧めします。 継続を使用したコンパイル. 。これは非常によく書かれており、C を直接扱っているわけではありませんが、コンパイラ作成者にとって非常に優れたアイデアの源となっています。
Chicken Wiki には、次のような非常に興味深いページもあります。 内部構造 そして コンパイルプロセス （CPSについて実際のコンパイル例を用いて説明しています）。
継続は問題ではありません。CPS を使用すると、これらを通常の高階関数で実装できます。単純なスタック割り当ての問題は、末尾呼び出しが決して最適化されないことです。つまり、スキーム化できないことです。
スキームのスパゲッティ スタックをスタックにマッピングする現在の最良のアプローチは、トランポリンを使用することです。基本的に、非 C ライクな呼び出しとプロシージャからの終了を処理するための追加のインフラストラクチャです。見る トランポリンスタイル (ps).
あるよ いくつかのコード これら両方のアイデアを説明します。
伝統的な方法は次のように使用します setjmp そして longjmp, ただし、注意点があります。
ここにあります かなり良い説明
継続は基本的に、コンテキスト切り替え時点でのスタックと CPU レジスタの保存された状態で構成されます。少なくとも、切り替えるときにスタック全体をヒープにコピーする必要はなく、スタック ポインターをリダイレクトするだけで済みます。
継続はファイバーを使用して簡単に実装されます。 http://en.wikipedia.org/wiki/Fiber_%28computer_science%29。慎重にカプセル化する必要があるのは、パラメータの受け渡しと戻り値だけです。
Windows では、ファイバーは CreateFiber/SwitchToFiber ファミリーの呼び出しを使用して実行されます。Posix 準拠のシステムでは、makecontext/swapcontext を使用して実行できます。
boost::coroutine には、実装の参照ポイントとして機能する C++ 用のコルーチンの実用的な実装が含まれています。
代わりに明示的なスタックを使用してください。
Patrick の言うとおりです。実際にこれを行う唯一の方法は、インタプリタで明示的なスタックを使用し、継続に変換する必要があるときにスタックの適切なセグメントをヒープにホイストすることです。
これは基本的に、クロージャをサポートする言語でクロージャをサポートするために必要なものと同じです (クロージャと継続は多少関連しています)。
として soegaard 指摘されていますが、主な参照は残ります これです
考え方としては、継続とは、その評価制御スタックを保持するクロージャであるということです。制御スタックは、次を使用して継続が作成された瞬間から評価を継続するために必要です。 call/cc.
継続を呼び出すと実行時間が長くなり、重複したスタックでメモリがいっぱいになることがよくあります。私がこの愚かなコードを書いたのは、mit-scheme ではスキームがクラッシュすることを証明するためです。
コードは最初の 1000 個の数値を合計します。 1+2+3+...+1000.
(call-with-current-continuation
(lambda (break)
((lambda (s) (s s 1000 break))
(lambda (s n cc)
(if (= 0 n)
(cc 0)
(+ n
;; non-tail-recursive,
;; the stack grows at each recursive call
(call-with-current-continuation
(lambda (__)
(s s (- n 1) __)))))))))
1000 から 100 000 に切り替えるとコードに 2 秒かかり、入力数値を大きくするとクラッシュします。
