SECDマシン

SECDマシンとは

SECDマシンは、関数型言語のコンパイラが生成する中間コードの実行を目的として設計された抽象機械です。1960年代にPeter J. Landinによって提唱され、関数型言語の実行モデルとして重要な役割を果たしました。SECDは、Stack（スタック）、Environment（環境）、Code（コード）、Dump（ダンプ） の頭文字を取ったもので、これらの4つのレジスタが仮想機械の中核を担っています。

SECDマシンの構成要素

Sレジスタ (Stack): 値を格納するスタックを指します。関数への引数や演算結果などが一時的に保存されます。スタックはリスト構造で実装されており、必要に応じて拡張できます。
Eレジスタ (Environment): 変数の束縛情報を保持する環境を指します。環境はリストのリストで表現され、各リストは環境のレベルに対応しています。これにより、静的スコープを持つ関数型言語の変数を適切に管理できます。
Cレジスタ (Code): 実行する命令列を指します。命令はリスト構造で格納され、Cレジスタは次に実行する命令を指し示します。命令ポインタと似た役割を持ちますが、命令がメモリ上で連続しているとは限りません。
Dレジスタ (Dump): 関数呼び出し時などに、他のレジスタの値を一時的に退避するためのスタックです。いわゆるコール[[スタック]]のような働きをします。関数から戻る際に、退避したレジスタの値を復元するために利用されます。

メモリモデル

SECDマシンのメモリは、関数型言語インタプリタと同様に、多数のメモリセルから構成されます。各セルはアトム（整数や文字列などの基本データ）またはリストを格納します。リストは、`car`と`cdr`という2つのポインタを持ち、`car`はリストの先頭要素を指し、`cdr`は残りのリストを指します。リストは、`(1 2 3)`のように表現され、内部的には以下のような構造で表現されます。


アドレス タグ 内容（integer の場合は値、list の場合は car と cdr）
9 [ integer | 2 ]
8 [ integer | 3 ]
7 [ list | 8 | 0 ]
6 [ list | 9 | 7 ]
...
2 [ list | 1 | 6 ]
1 [ integer | 1 ]
0 [ nil ]


リストの要素はメモリ上の連続した場所に配置される必要はなく、空きセルが利用されます。`car`と`cdr`は必ずしもリストを指す必要はなく、アトムを指すこともあります。例えば、`(1 . 2)` のようにドット対の記法で表される構造も扱えます。

命令セット

SECDマシンには、以下のような基本的な命令が用意されています。

nil: `nil`ポインタをスタックにプッシュします。
ldc: 定数オペランドをスタックにプッシュします。
ld: 環境から変数の値をスタックにプッシュします。変数の場所は、環境レベルと順番で指定します。
sel: 条件分岐を行う命令です。スタックから値をポップし、その値が`nil`でなければ、1つ目のリストを実行し、そうでなければ2つ目のリストを実行します。
join: `sel` 命令で分岐したコードの実行終了後に、`D`レジスタに退避していた `C` レジスタを復元します。
ldf: 関数（クロージャ）を生成し、スタックにプッシュします。クロージャは、関数のコードと、その関数が定義された時点での環境を組み合わせたものです。
ap: クロージャを呼び出す命令です。クロージャと引数のリストをスタックからポップし、クロージャのコードを実行します。この際、現在の環境やスタックはダンプに保存され、クロージャ内で使われる新しい環境が設定されます。
ret: 関数から戻る命令です。スタックから戻り値をポップし、ダンプに保存していたS, E, Cレジスタを復元します。そして、戻り値を現在のスタックにプッシュします。
dum: ダミーの環境を環境リストの先頭にプッシュします。これにより、再帰関数を実現します。
rap: `ap`命令と似ていますが、再帰関数で使われる環境設定を行います。

さらに、`car`、`cdr`、リスト構築、整数の加算、入出力といった基本的な関数も命令として存在します。

SECDマシンの歴史と影響

Peter J. Landinの論文 (1964) で発表されて以来、SECDマシンは関数型言語の実装において重要な役割を果たしてきました。その抽象的な設計は、様々な実装の可能性を残しており、後にPeter HendersonのLispkit Lispコンパイラ（1980年）など、多くの実験的なコンパイラで採用されました。また、ISWIMというプログラミング言語を提唱した論文である「The Next 700 Programming Languages」でも参考文献として言及されています。1989年には、カルガリー大学でSECDマシンをハードウェアで実装する研究が行われました。SECDマシンの設計は、現在の多くの仮想機械やインタプリタに影響を与えており、その概念は今でも重要な意味を持っています。

参考文献

Peter J. Landin. The Mechanical Evaluation of Expression. Computer Journal, 6, pp.308-320. 1964.
Peter M. Kogge: The Architecture of Symbolic Computers. ISBN 0-07-035596-7
Peter Henderson, Functional Programming: Application and Implementation. Prentice Hall, 1980. ISBN 0-13-331579-7
Anthony J. Field and Peter G. Harrison: Functional Programming. Addison-Wesley, 1988. ISBN 0-201-19249-7
神林靖「SECDマシン再訪」NAID 110000534424
Olivier Danvy: A Rational Deconstruction of Landin's SECD Machine. BRICS research report RS-04-30, 2004. ISSN 0909-0878

外部リンク

* SECD collection

もう一度検索