20

私はC/C ++の不潔な組み合わせで小さなSchemeインタープリターを作成しましたが、適切な末尾呼び出しをまだ実装していません。

私はMTAアルゴリズムの古典的なチェイニーを知っていますが、これを実装する他の素晴らしい方法はありますか？スキームスタックをヒープに置くことができることは知っていますが、標準では無制限の数のアクティブな末尾呼び出しをサポートする必要があるため、それでも適切な除去にはなりません。

私もlongjmpsをいじりましたが、これまでのところ、相互再帰的でない末尾呼び出しに対してのみうまく機能すると思います。

主要なCベースのスキームはどのように適切な末尾再帰を実装しますか？

4

3 に答える 3

13

コンパイラとVMを作成するよりも簡単なのは、インタプリタを登録してトランポリンすることです。コンパイラではなくインタプリタがあるので（私が思うに）、末尾呼び出しを適切にサポートするには、いくつかの簡単な変換だけが必要です。

最初にすべてを継続渡しスタイルで作成する必要があります。これは、C /C++で考えて実行するのは奇妙かもしれません。Dan FriedmanのParentheCチュートリアルでは、高レベルの再帰プログラムをCに機械変換可能な形式に変換する手順を説明します。

最後に、基本的に単純なVMを実装します。ここでは、通常の関数呼び出しを使用してevalやapplyProcなどを実行する代わりに、グローバル変数を設定して引数を渡しgoto、次の引数にaを実行します（またはトップレベルを使用します）。ループおよびプログラムカウンター）..。

return applyProc(rator, rand)

になります

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

つまり、通常は相互に再帰的に呼び出すすべての関数は、再帰しないコードのブロックである疑似アセンブリに縮小されます。トップレベルのループがプログラムを制御します。

for(;;) {
  switch(reg_pc) {
    case EVAL:
      eval();
      break;
    case APPLY_PROC:
      applyProc();
      break;
    ...
  }
}

編集： JavaScriptで書かれた趣味のSchemeインタープリターでも同じプロセスを実行しました。多くの匿名の手順を利用しましたが、具体的な参考になるかもしれません。2011-03-13（ 30707a0432563ce1632a ）から2011-03-15（5dd3b521dac582507086）までのFoxSchemeのコミット履歴を見てください。

Edit ^ 2：スタックにない場合でも、非末尾再帰はメモリを消費します。

于 2011-05-15T01:50:36.767 に答える
6

あなたが何を持っているかを知らなくても、それを行う最も簡単な（そして最も啓発的な）方法は、Dybvigの「Schemeの3つの実装モデル」からスキ​​ームコンパイラとVMを実装することだと思います。
私はここでJavascriptでそれを行いました（DybvigのPDFのコピーもあります）：https ：//github.com/z5h/zb-lisp

src / compiler.js：compileCons、およびsrc/vm.jsの「opcodes」の実装を確認してください

于 2011-05-14T20:44:40.850 に答える
6

通訳者の実装技術に興味があるなら、ChristianQueinnecによる本「LiSP-LispinSmallPieces」を回避する方法はありません。完全なコードを使用してSchemeシステムを実装するすべての側面を非常に徹底的に説明します。素晴らしい本です。

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

ただし、ReadScheme.orgの論文を確認することを忘れないでください。

セクション

コンパイラテクノロジ/実装手法と最適化 http://library.readscheme.org/page8.html

末尾呼び出しの最適化に関するかなりの数の論文があります。

とりわけ、非常によく書かれているディブヴィグの論文（古典）へのリンクがあります。それは非常に明確な方法ですべてを説明し、動機づけます。

于 2011-05-15T10:59:43.833 に答える