SECDマシンでは「ラップ」はどのように機能しますか？

Question

description on Wikipediaで案内されているC＃でsimulator of the SECD machineと書いています。基本的な操作は完了しましたが、rap命令の実装方法がわかりません。

ラップが可能再帰関数

そして用を作り、それが現在のものとダミー環境の発生を置き換えるだけで、APのように動作します：それはおよそrapが言うウィキペディアで

apと書かれています。

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

ListはLispのスタイル "短所" は、細胞の私の実装であることを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; 
    } 

注意の私の実装です。

私が混乱しているのは、rapがapとどのように違うのですか？たとえば、環境レジスタ（E）には何が起こりますか？私はWikipediaの定義が少し曖昧で、それをうまく説明できるものは何も見つかりませんでした。

Answer 1

SECDはテール再帰的ではありませんが、a tail recursive SECD machine (PDF)を構築できます。

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

'letrec'は、再帰関数を定義する環境を「見る」ことができるため、再帰的に呼び出すことができるため、 'let'とは異なります（たとえば、 '階乗'関数を定義し、関数の本体で呼び出すことができます）。

RAPはrplacaを呼び出すことで環境を変更します（Schemeのsetcar！と同様）。以前のDUM命令は環境に "ダミー"カーを追加し（使用されない）、RAPは環境内のこの "ダミー"カーを削除し、それを適切なものに置き換えます。

状態遷移は非常に似ています。また、

 
((c'.e')v.s) e    (AP.c) d   => 
NIL   (v.e')   c'  (s e c.d) 

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

参照Revisiting SECD and the power of Lisp、引用：

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

と

ErlangでRAPを実装しようとするとリストには破壊的な操作がないので、私が捕まってしまいました。標準APIではなく、一見システムAPIにもありません。だから、Erlang SECDは素晴らしく、実行されません。

Answer 2

ピーター・ヘンダーソンの素敵な小冊子 "Functional Programming Application and Implementation"のコピーを実際に手に入れてください。その中で、彼はSECDマシンとLispkit Lispを細かく記述し、構築します。

Answer 3

優れた回答に加えて、なぜrapが必要なのかをもっと詳しく説明したいと思います。

環境（SECDでE）店舗持続エンティティのすべて（関数、定数、変数など）。 Eは本質的にリストのスタックです。 EのものはスタックSにロードされ、Cのコマンドで実行または使用されます。 Eのすべてには、後で参照できるようにidが与えられます。このIDは、通常、タプル(x,y)であり、xはスタック上のリストの位置を表し、yはそのリスト内の位置を表します。典型的な関数呼び出しで

、新しいリストがEにプッシュされ、現在は任意のローカル変数は|E|がEの大きさを表し(|E|, y)などのIDを持つことができます。ただし、再帰関数では非常に問題があります。なぜなら、各関数呼び出しでスタックのサイズが大きくなるため、ローカル変数に使用可能なIDを割り当てる方法がないからです。 rapが行うap物事のほとんどを行い、この問題を解決するために

、代わりに環境スタックに新しいリストをプッシュするのではなく、新しい環境リストでEの先頭にあるものは何でも置き換えられます。