私はCで書かれたSchemeインタープリターに取り組んでいます。現在、Cランタイムスタックを独自のスタックとして使用していますが、継続の実装に小さな問題があります。私の現在の解決策は、Cスタックをヒープに手動でコピーし、必要に応じてコピーして戻すことです。標準 C ではないことを除けば、このソリューションは理想的とは言えません。
CでSchemeの継続を実装する最も簡単な方法は何ですか?
Kyle
質問する
9374 次
12 に答える
29
優れた要約は、Clinger、Hartheimer、および Ost による記事、Implementation Strategies for First-Class Continuationsにあります。特に Chez Scheme の実装を見ることをお勧めします。
スタックのコピーはそれほど複雑ではなく、パフォーマンスを向上させるために利用できる十分に理解された手法が多数あります。ヒープ割り当てフレームの使用もかなり単純ですが、明示的な継続を使用していない「通常の」状況では、オーバーヘッドが発生するというトレードオフがあります。
入力コードを継続渡しスタイル (CPS) に変換すると、スタックを完全になくすことができます。ただし、CPS は洗練されていますが、フロントエンドに別の処理ステップが追加され、特定のパフォーマンスへの影響を克服するために追加の最適化が必要になります。
于 2008-08-31T05:02:30.977 に答える
18
I remember reading an article that may be of help to you: Cheney on the M.T.A. :-)
Some implementations of Scheme I know of, such as SISC, allocate their call frames on the heap.
@ollie: You don't need to do the hoisting if all your call frames are on the heap. There's a tradeoff in performance, of course: the time to hoist, versus the overhead required to allocate all frames on the heap. Maybe it should be a tunable runtime parameter in the interpreter. :-P
于 2008-08-09T02:49:25.903 に答える
14
ゼロから始める場合は、Continuation Passing Style (CPS) 変換を検討する必要があります。
良い情報源には、"LISP in small pieces" やMarc Feeley の Scheme in 90 minutes presentationなどがあります。
于 2008-12-05T08:00:30.907 に答える
10
Dybvig の論文は今のところ言及されていないようです。読んでいて楽しいです。ヒープ ベースのモデルは実装が最も簡単ですが、スタック ベースのモデルはより効率的です。文字列ベースのモデルは無視してください。
R.ケント・ディビグ。「Scheme の 3 つの実装モデル」。 http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
また、ReadScheme.org の実装に関する論文もチェックしてください。 https://web.archive.org/http://library.readscheme.org/page8.html
アブストラクトは次のとおりです。
この論文では、Scheme プログラミング言語の 3 つの実装モデルを紹介します。1 つ目は、これまでのほとんどの Scheme 実装で何らかの形で使用されているヒープベースのモデルです。2 つ目は新しいスタック ベースのモデルで、ほとんどのプログラムの実行においてヒープ ベースのモデルよりもかなり効率的です。3 つ目は、Scheme のマルチプロセッサ実装での使用を目的とした新しい文字列ベースのモデルです。
ヒープ ベースのモデルでは、実際のパラメーター リスト、バインド環境、呼び出しフレームなど、いくつかの重要なデータ構造がヒープに割り当てられます。
スタックベースのモデルは、可能な限りこれらの同じ構造をスタックに割り当てます。これにより、ヒープ割り当て、メモリ参照、命令シーケンスの短縮、ガベージ コレクションの削減、およびメモリのより効率的な使用が実現します。
文字列ベースのモデルは、シンボルの文字列として表されるプログラム テキスト内にこれらの構造のバージョンを割り当てます。文字列ベースのモデルでは、Scheme プログラムは、Scheme をサポートするために特別に設計された FFP 言語に変換されます。この言語のプログラムは、複数プロセッサの文字列削減コンピュータである FFP マシンによって直接実行されます。
スタックベースのモデルは、すぐに実際に役立ちます。これは、Scheme の高性能な実装である著者の Chez Scheme システムで使用されるモデルです。文字列ベースのモデルは、マシンが実現されると、FFP マシン上で FFP の高レベルの代替手段として Scheme を提供するのに役立ちます。
于 2011-10-30T15:31:12.843 に答える
8
これまでに得た素晴らしい回答に加えて、Andrew Appel の Compiling with Continuationsをお勧めします。非常によく書かれており、C を直接扱っているわけではありませんが、コンパイラの作成者にとっては非常に優れたアイデアの源です。
Chicken Wiki には、内部構造やコンパイル手順 (実際のコンパイル例を示して CPS が説明されている)など、非常に興味深いページもあります 。
于 2010-06-08T00:25:17.440 に答える
7
継続は問題ではありません。CPSを使用して、通常の高階関数で継続を実装できます。ナイーブなスタック割り当ての問題は、末尾呼び出しが最適化されないことです。つまり、スキームを作成することはできません。
スキームのスパゲッティスタックをスタックにマッピングするための現在の最善のアプローチは、トランポリンを使用することです。これは、Cに似ていない呼び出しを処理し、プロシージャを終了するための基本的に追加のインフラストラクチャです。トランポリンスタイル（ps）を参照してください。
これらのアイデアの両方を説明するコードがいくつかあります。
于 2009-12-03T13:04:35.363 に答える
7
伝統的な方法はsetjmpandを使用することlongjmpですが、注意点があります。
ここにかなり良い説明があります
于 2008-08-28T10:05:19.227 に答える
5
継続は基本的に、コンテキスト スイッチの時点でのスタックと CPU レジスタの保存された状態で構成されます。少なくとも、切り替え時にスタック全体をヒープにコピーする必要はありません。スタック ポインターのみをリダイレクトできます。
継続は、ファイバーを使用して自明に実装されます。http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . 注意深いカプセル化が必要なのは、パラメーターの受け渡しと戻り値だけです。
Windows では、ファイバーは CreateFiber/SwitchToFiber ファミリーの呼び出しを使用して行われます。Posix 準拠のシステムでは、makecontext/swapcontext で実行できます。
boost::coroutine には、実装の参照ポイントとして機能する C++ 用のコルーチンの実用的な実装があります。
于 2010-01-04T10:33:52.340 に答える
1
Patrick is correct, the only way you can really do this is to use an explicit stack in your interpreter, and hoist the appropriate segment of stack into the heap when you need to convert to a continuation.
This is basically the same as what is needed to support closures in languages that support them (closures and continuations being somewhat related).
于 2008-08-09T02:55:01.947 に答える
1
代わりに明示的なスタックを使用してください。
于 2008-08-09T01:29:33.537 に答える