Loading article…
SECDマシンは、関数型プログラミング言語のコンパイラのターゲットとして設計された、影響力のある仮想マシンおよび抽象マシンです。文字はそれぞれ、マシンの内部レジスタである、、、、を表します。レジスタ、、、はスタック(のいくつかの実装) を指し、は連想配列(のいくつかの実装) を指します。stackenvironmentcontroldumpstackcontroldumpenvironment
この機械は、ラムダ計算式を評価するために特別に設計された最初の機械でした。これは、 1964年にピーター・ランディンによって「式の機械的評価」で初めて説明されました。 [ 1 ]ランディンによって発表された説明はかなり抽象的で、多くの実装の選択肢が残されていました（操作的意味論など）。
Lispkit LispはSECDマシンをベースにしたコンパイラであり[ 2 ]、SECDマシンはLisp / 370などの他のシステムのターゲットとして使用されてきました[ 3 ]。1989年、カルガリー大学の研究者たちは、 Lispマシンに関連する高水準言語のコンピュータアーキテクチャと同じ論理に基づいて、マシンのハードウェア実装に取り組みました[ 4 ]。
DA Turner (2012) [ 5 ]は、 ALGOL 60プログラミング言語では他の関数から関数を返すことができなかった (関数が第一級ではなくなった) と指摘しています。別の関数の中にネストされた関数は、外側の関数のスタック上に存在する変数を参照することができました。ネストされた関数が外側の関数から返された場合、それはもはや存在しないスタック フレーム内の変数を参照することになります。Turner は、Landin の SECD マシンはこの問題を解決した (関数が関数を返すことができるようになった) と指摘しています。関数の値は、スタック上で何が起こるかに関係なく、使用すべき変数の環境を格納できるヒープ上のクロージャで表現されるようになったためです。[ 5 ]
式の評価が開始されると、その式は唯一の制御要素としてロードされますC。環境E、スタックS、ダンプはD最初は空です。
評価中は、(適用用) が唯一の演算子として、逆ポーランド記法(RPN)Cに変換されます。たとえば、式(単一のリスト要素) はリスト に変更されます。apF (G X)X:G:ap:F:ap
の評価は、C他の RPN 式と同様に行われます。 の最初の項目Cが値の場合、それがスタックにプッシュされますS。より正確には、項目が識別子の場合、スタックにプッシュされる値は、現在の環境におけるその識別子のバインディングになりますE。項目が抽象化の場合、その自由変数 ( に含まれる) のバインディングを保持するためのクロージャが構築されE、このクロージャがスタックにプッシュされます。
項目が の場合ap、スタックから 2 つの値がポップされ、適用が完了します (最初の値が 2 番目の値に適用されます)。適用結果が 値の場合、その値がスタックにプッシュされます。
ただし、適用が値への抽象化である場合、結果としてラムダ計算式が生成されますが、この式自体が（値ではなく）適用である可能性があり、スタックにプッシュすることはできません。この場合、、、およびの現在の内容がSダンプE（CこれらDの3つ組のスタック）にプッシュされ、Sは空に再初期化され、は、この式の自由変数の環境を含むC適用結果にE、適用によって生じたバインディングを追加して再初期化されます。その後、評価は上記のように進められます。
評価が完了すると、Cスタックが空になります。この場合、結果はスタック上に格納されますS。次に、スタックに保存された最後の評価状態Dがポップされ、完了した評価の結果がスタックにプッシュされますD。スタックの内容はから復元されます。復元された状態の評価は、上記のように続行されます。
Cと の両方が空の場合D、全体的な評価が完了し、結果がスタック上にありますS。
SECDマシンはスタックベースです。関数はスタックから引数を取得します。組み込み命令の引数は、命令ストリーム内で命令の直後にエンコードされます。
すべての内部データ構造と同様に、スタックはリストであり、Sレジスタはリストの先頭、つまり先頭を指しています。リスト構造のため、スタックは連続したメモリブロックである必要はなく、空きメモリセルが1つでも存在すればスタック領域は利用可能です。すべてのセルが使用済みであっても、ガベージコレクションによって追加の空きメモリが得られる場合があります。もちろん、SECD構造の特定の実装では、スタックを標準的なスタック構造として実装することができ、スタックのサイズに厳密な制限を設けることで、仮想マシンの全体的な効率を向上させることができます。
このレジスタは、評価されるコードまたは命令リストCの先頭を指します。そこにある命令が実行されると、このレジスタはリスト内の次の命令を指すようになります。これは、従来のコンピュータにおける命令ポインタ（またはプログラムカウンタ）に似ていますが、従来のコンピュータのように後続の命令がデフォルトで後続のメモリ位置に格納されるのではなく、常に実行中に指定される点が異なります。C
現在の変数環境はE、リストのリストを指すレジスタによって管理されます。各リストは、1 つの環境レベルを表します。現在の関数のパラメータはリストの先頭にあり、現在の関数では自由だが周囲の関数によって束縛されている変数は、リストの他の要素にありますE。
レジスタが指すダンプはD、例えば関数呼び出し時などに、他のレジスタの値を一時的に格納するために使用されます。これは、他のマシンのリターンスタックに例えることができます。
SECD マシンのメモリ構成は、ほとんどの関数型言語インタプリタで使用されるモデルと似ています。つまり、複数のメモリセルがあり、各セルはアトム(単純な値、例えば13 ) を保持するか、空または空でないリストを表すことができます。後者の場合、セルは他のセルへの 2 つのポインタを保持します。1 つは最初の要素を表し、もう 1 つは最初の要素を除くリストを表します。2 つのポインタは従来、それぞれcarとcdrと呼ばれていましたが、より現代的な用語であるheadとtailがよく使用されます。セルが保持できる値の異なるタイプは、タグによって区別されます。多くの場合、異なるタイプのアトム (整数、文字列など) も区別されます。
したがって、 1、2、3という数字を含むリスト（通常は と表記される）は、(1 2 3)次のように表される可能性があります。
アドレスタグの内容（整数の場合は値、リストの場合はcarとcdr） 9 [整数 | 2] 8 [整数 | 3] 7 [ リスト | 8 | 0 ] 6 [リスト | 9 | 7] ... 2 [リスト | 1 | 6] 1 [整数 | 1] 0 [ なし ]
メモリセル 3 から 5 はリストに含まれておらず、リストのセルはメモリ全体にランダムに分布させることができます。セル 2 はリストの先頭であり、最初の要素の値を保持するセル 1 と、2と3のみを含むリスト(セル 6 から始まる) を指しています。セル 6 は、2 を保持するセルと、3のみを含むリストを表すセル 7 を指しています。これは、値3を含むセル 8 を指し、cdr として空のリスト ( nil ) を指すことによって実現されます。SECD マシンでは、セル 0 は常に暗黙的に空のリストを表すため、空のリストを示す特別なタグ値は必要ありません (それを必要とするものはすべて、単にセル 0 を指すだけで済みます)。
リストセル内の cdr が別のリストを指していなければならないという原則は、単なる慣例です。car と cdr の両方がアトムを指している場合、通常は次のように記述されるペアが生成されます。(1 . 2)
nilnilポインタをスタックにプッシュするldc定数引数をスタックにプッシュするld変数の値をスタックにプッシュします。変数は引数（ペア）で示されます。ペアのcarはレベルを、cdrは位置を指定します。したがって、(1 . 3)現在の関数（レベル1）の3番目のパラメータを取得します。sel2 つのリスト引数を期待し、スタックから値をポップします。ポップされた値が nil でない場合は最初のリストが実行され、そうでない場合は 2 番目のリストが実行されます。これらのリストポインタのいずれかが作成される前はC、次の命令へのポインタである新しい が作成されます。ダンプファイルに保存されます。
joinダンプからリスト参照をポップし、これを の新しい値にしますC。この命令は、 のどちらの選択肢の最後にも発生しますsel。ldf関数を表すリスト引数を1つ受け取ります。クロージャ（関数と現在の環境を含むペア）を構築し、それをスタックにプッシュします。apスタックからクロージャとパラメータ値のリストを取り出します。クロージャは、その環境を現在の環境としてインストールし、パラメータリストをその前にプッシュし、スタックをクリアし、Cクロージャの関数ポインタSを設定することによって、パラメータに適用されます。 、 、の以前の値Eと、 の次の値はCダンプに保存されます。retスタックから戻り値を 1 つポップし、ダンプから、 、Sを復元し、戻り値を現在のスタックにプッシュします。ECdum環境リストの前に「ダミー」、つまり空のリストを挿入します。rapのように働くただし、ダミー環境の出現を現在の環境に置き換えることで、再帰関数が可能になります。car、cdr、リスト構築、整数加算、I/Oなどの基本機能には、追加の命令が多数存在します。これらの命令はすべて、必要なパラメータをスタックから取得します。
