「スタックレス」インタプリタ言語をどのように実装しますか?

2011年05月13日に質問されました。  ·  閲覧回数 2.9k回  ·  ソース

salvador p picture
2011年05月13日

私は独自のLispのようなインタプリタ言語を作成しており、末尾呼び出しの最適化を行いたいと思っています。 インタプリタをCスタックから解放して、関数から関数への独自のジャンプと、TCOを達成するための独自のスタックマジックを管理できるようにしたいと思います。 (私は実際にはスタックレスそのものを意味するのではなく、呼び出しがCスタックにフレームを追加しないという事実だけです。末尾呼び出しで成長しない独自のスタックを使用したいと思います)。 Stackless Pythonのように、Rubyや...標準のPythonとは異なります。

しかし、私の言語はLisp派生語であるため、S式のすべての評価は現在再帰的に行われています(これは、この非線形で高度に階層化されたプロセスを実行するために私が考えた最も明白な方法であるため)。 関数呼び出しが発生するたびにLambda :: apply関数を呼び出すeval関数があります。 次に、apply関数はevalを呼び出して、関数の本体を実行します。 相互スタックに飢えた非テールC再帰。 私が現在使用している唯一の反復部分は、連続するS式の本体を評価することです。

(defun f (x y)
    (a x y)) ; tail call! goto instead of call. 
             ; (do not grow the stack, keep return addr)

(defun a (x y)
    (+ x y))

; ...

(print (f 1 2)) ; how does the return work here? how does it know it's supposed to
                ; return the value here to be used by print, and how does it know
                ; how to continue execution here??

では、C再帰の使用を回避するにはどうすればよいですか? または、c関数間をジャンプするある種のgotoを使用できますか? longjmp、おそらく? 本当にわかりません。 我慢してください、私はほとんど自己(インターネット)プログラミングで教えられています。

回答

Daniel Ralston picture
2011年05月13日
13

1つの解決策は、「トランポリンスタイル」と呼ばれることもあります。 トランポリンは、戻る前に計算の小さなステップを実行する小さな関数にディスパッチするトップレベルのループです。

私はここに30分近く座って、良い短い例を考案しようとしました。 残念ながら、私は役に立たないことをして、あなたをリンクに送る必要があります:

http://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Section_5

この論文は「Scheme:拡張ラムダ計算のインタープリター」と呼ばれ、セクション5はLispの古い方言で作業スキームインタープリターを実装します。 秘密は、スタックの代わりに** CLINK **をどのように使用するかにあります。 他のグローバルは、CPUのレジスタなどの実装関数間でデータを渡すために使用されます。 ** QUEUE **、** TICK **、および** PROCESS **はスレッド化と偽の割り込みを処理するため、無視します。 ** EVLIS **と** UNEVLIS **は、具体的には、関数の引数を評価するために使用されます。 未評価の引数は、評価されて** EVLIS **に出力されるまで、** UNEVLIS **に保存されます。

注意を払うべき機能、いくつかの小さなメモ:

MLOOP:MLOOPは、インタプリタ、つまり「トランポリン」のメインループです。 ** TICK **を無視すると、その唯一の仕事は** PC **にある関数を呼び出すことです。 何度も何度も。

SAVEUP:SAVEUPは、すべてのレジスタを** CLINK **にまとめます。これは、Cが関数呼び出しの前にレジスタをスタックに保存する場合と基本的に同じです。 ** CLINK **は、実際には通訳者にとっての「継続」です。 (継続は単なる計算の状態です。保存されたスタックフレームは技術的にも継続です。したがって、一部のLispはスタックをヒープに保存してcall / ccを実装します。)

RESTORE:RESTOREは、** CLINK **に保存された「レジスタ」を復元します。 これは、スタックベースの言語でスタックフレームを復元するのと似ています。 したがって、一部の関数が戻り値を** VALUE **に明示的に固定していることを除いて、基本的には「戻り値」です。 (** VALUE **は明らかにRESTOREによって破壊されません。)また、RESTOREは必ずしも呼び出し元の関数に戻る必要はないことに注意してください。 一部の関数は、実際にはまったく新しい計算を保存し、RESTOREはそれを喜んで「復元」します。

AEVAL:AEVALはEVAL関数です。

EVLIS:EVLISは、関数の引数を評価し、それらの引数に関数を適用するために存在します。 再帰を回避するために、EVLIS-1を保存します。 EVLIS-1は、コードが再帰的に記述されている場合、関数適用後の通常の古いコードになります。 ただし、再帰とスタックを回避するために、これは別個の「継続」です。

お役に立てば幸いです。 私の答え(そしてリンク)がもっと短かったらいいのにと思います。

Greg Hewgill picture
2011年05月13日
10

あなたが探しているのは継続渡しスタイルと呼ばれています。 このスタイルは、実行するコードの次のビットを指定する追加の項目を各関数呼び出しに追加します(必要に応じて、パラメーターと考えることができます)(継続kは関数と考えることができます)それは単一のパラメータを取ります)。 たとえば、CPSで例を次のように書き直すことができます。

(defun f (x y k)
    (a x y k))

(defun a (x y k)
    (+ x y k))

(f 1 2 print)

実装+の和計算するxおよびy 、その後に結果を渡す、 kのような一種の(k sum)

その場合、メインのインタプリタループは再帰的である必要はまったくありません。 ループ内で、各関数適用を次々に適用し、継続を渡します。

これに頭を包むには少し手間がかかります。 優れたSICPなどの読み物をお勧めします。

Adam picture
2011年05月13日
6

末尾再帰は、現在呼び出し元に使用しているのと同じスタックフレームを呼び出し先に再利用することと考えることができます。 したがって、引数をリセットして、関数の先頭に移動するだけで済みます。