7

ウィキペディアの説明に基づいて、C＃でSECDマシンのシミュレーターを作成しています。基本的な操作は完了しましたが、命令の実装方法がわかりません。rap

ウィキペディアでは、次のように述べていrapます。

rapはapのように機能しますが、ダミー環境の発生を現在の環境に置き換えるだけで、再帰関数が可能になります。

そしてapそれは言う：

apは、スタックからクロージャとパラメータ値のリストをポップします。クロージャーは、その環境を現在の環境としてインストールし、その前にパラメーターリストをプッシュし、スタックをクリアし、Cをクロージャーの関数ポインターに設定することによってパラメーターに適用されます。S、Eの前の値、およびCの次の値がダンプに保存されます。

これが私の実装ですap

    public void ap() 
    { 
        Push(S, ref D); 
        Push(E, ref D); 
        Push(C, ref D); 
        List closure = Pop(ref S);
        List paramlist = Pop(ref S);
        E = closure.Tail;
        Push(paramlist, ref E);
        C = closure.Head;
        S = List.Nil;
    }

ListこれがLispスタイルの「cons」セルの実装であることに注意してください。

私を混乱させるのは、正確にどのようにrap違うのapですか？たとえば、環境レジスタ（E）は正確にどうなりますか？ウィキペディアの定義が少し曖昧で、それをうまく説明するものを他に見つけることができませんでした。

4

3 に答える 3

8

SECD は末尾再帰ではありませんが、末尾再帰 SECD マシン (PDF)を構築できます。

AP 命令は「let」バインディングをコンパイルするために使用され、RAP 命令は「letrec」バインディングをコンパイルするために使用されます。

'letrec' は 'let' とは異なります。なぜなら、再帰関数が定義されている環境を '見る' ことができるため、再帰的に呼び出すことができるからです (つまり、たとえば、'階乗' 関数を定義し、その環境で呼び出すことができます)。関数の本体)。

RAP は rplaca を呼び出すことによって環境を変更します (Scheme の setcar! に似ています)。前の DUM 命令は環境に「ダミー」車を追加し (これは決して使用されません)、RAP は環境内のこの「ダミー」「車」を削除し、適切な車に置き換えます。

状態遷移は次のようになります。

((c'.e')vs) e (AP.c) d =>
NIL (ve') c' (秒 cd)

((c'.e')vs) (?.e) (RAP.c) d =>
NIL (setcar! e',v) c' (秒 cd)

Revisiting SECD and the power of Lispも参照してください。

RAP 命令は、再帰関数呼び出しをサポートするために使用され、スタック上に以前に作成された OMEGA と呼ばれるダミー環境を、再帰スコープで表示されるすべての関数を含む環境に置き換えることによって機能します。仕様では、RPLACA を使用してその置換操作を示します。これは、SECD の Lisp 実装でも使用したものです: ...

と

Erlang で RAP を実装しようとしたとき、リストに破壊的な操作がないため行き詰まりました。標準 API にはなく、システム API にもないようです。したがって、Erlang SECD は良さそうに見えますが、実行されません。
于 2011-10-02T06:32:53.583 に答える
4

Peter Henderson の素晴らしい小さな本「Functional Programming Application and Implementation」を実際に手に取ってください。その中で、彼は細心の注意を払って SECD マシンと Lispkit Lisp を記述し、構築しています。

于 2011-10-02T17:21:42.947 に答える