SECDマシン

SECDマシンとは、関数型言語のコンパイラのターゲット（目的機械）を意図し、後に大きな影響を与えた抽象機械である。SECD は Stack（スタック）、Environment（環境）、Code（コード）、Dump（ダンプ）の略であり、それぞれ仮想機械にあるレジスタの名称となっている。これらのレジスタはメモリ上の連結リストを指している。

Peter J. Landinの考案によるもので、1964年のComputer Journal誌が初出である。ラムダ計算式を評価するものだが、Landin の発表した説明は非常に抽象的で、（操作的意味論のように）実装にかなりの自由度が与えられていた。SECDマシンはより詳細化された形態で説明されることが多く、例えば Peter Henderson の Lispkit Lisp コンパイラは SECDマシンをベースとして1980年に登場している。以降、いくつかの実験的コンパイラが SECDマシンをターゲットとして使用してきた。また、ISWIMを提案した "The Next 700 Programming Languages" でも参考文献として挙げられている。

1989年、カルガリー大学の研究者がSECDマシンをハードウェアで実装する研究を行った。

レジスタとメモリ

SECDマシンはスタックベースであり、関数（組み込み関数とユーザー定義関数）はスタックから引数を取り出す。一方、命令のオペランドは命令形式に含まれている。

他の内部データ構造と同様にスタックもリストとなっている。Sレジスタはそのリストの先頭を指している。リスト構造であるため、このスタックは連続したメモリブロックである必要がなく、リスト用のセルが空いていればスタックを伸ばすことができる。全てのセルが使用されている場合でも、ガベージコレクションで空きメモリが見つかる可能性がある。

Cレジスタは評価（実行）すべきコードのリストの先頭を指している。その命令を実行したら、Cはリスト上の次の命令を指す。これはちょうど通常のCPUの命令ポインタと同じだが、コード自体もリスト構造であるため、次の命令がメモリ上連続した位置にあることは滅多にない。

現在の変数の環境はEレジスタによって管理される。Eはリストのリストを指している。ここで、各リストは環境レベルを表しており、現在の関数の引数はそのリストの先頭にある。現在の環境では束縛されていないがそれを取り囲む関数では束縛されている変数は、その次のリストにある。

Dレジスタの指すダンプとは、他のレジスタの内容を一時的に保管するのに使われ、例えば関数呼び出しの際などに使われる。これは、いわゆるコールスタックの役目を果たしている。

SECDマシンのメモリ構成は多くの関数型言語インタプリタと同様である。多数のメモリセルが存在し、1個のセルには「アトム」を保持するか、空または空でないリストを表す。後者の場合、セルには2つのポインタが存在し、1つめのポインタがリストの先頭のセルを指し、2つめのポインタがリストの残りの部分を指す。これらは慣習的に car と cdr と名づけられている。セルには様々な型の値が保持できるが、これをタグ(tag)で識別する。アトムの値にも整数型や文字列型などがあるが、これらもタグで識別される。

1、2、3 という数を持つリストは "(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             ]

ここで、3番から5番のメモリセルはリストには属していない。リストに使用するセルはメモリ全体から無作為に選択される。セル 2 はリストの先頭であり、先頭の要素を保持するセル 1 とリストの残りを保持するセル 6 を指している。セル 6 は 2 を保持するセルとセル 7 を指し、セル 7 は 3 を保持するリストとなっている。リストの最後尾では空リストを表すセル 0 を cdr で指している。SECDマシンでは、セル 0 は空リストを常に表しており、空リストを表すためにタグの値を別途用意する必要はない（単にセル 0 を指せばよい）。

なお、cdr がリストを指すというのは説明を簡単にするための言い方であって、必ずしもそのような制限があるわけではない。car も cdr もアトムであるような形式も可能で、これを "(1 . 2)" などと表記する。

命令

nil: nilポインタをスタックにプッシュ
ldc: 定数オペランドをスタックにプッシュ
ld: 変数の値をスタックにプッシュ。変数はオペランドで環境レベルと順番で指定される。例えば "(1 . 3)" なら、現在の関数レベルで3番めの引数を意味する。
sel: 2つのリストをオペランドに持ち、スタックから値を1つポップする。ポップした値が nil でない場合、先頭のリストを実行し、そうでなければ2番めのリストを実行する。いずれかのリストへのポインタが Cレジスタに格納される前に、sel命令の次の命令へのポインタがダンプにセーブされる。
join: ダンプからリスト参照をポップし、それをCレジスタにセットする。これはsel命令で選択されたリストの実行が完了したときに実行される。
ldf: 関数を表す1つのリストをオペランドに持つ。クロージャ（関数と現在の環境のペア）を構築し、それをスタックにプッシュする。
ap: クロージャと引数（の値）リストをスタックからポップする。クロージャを現在の環境として設定し、引数に適用する。引数リストを環境に設定し、スタックをクリアしてCレジスタにクロージャ内にある関数ポインタをセットする。以前のSとEレジスタの値、Cの次の値はダンプにセーブしておく。
ret: スタックからリターン値をポップし、ダンプからS、E、Cをリストアする。そしてリターン値を新たな現在のスタックにプッシュする。
dum: ダミーを環境リストの先頭にプッシュする。ダミーとは空リストである。
rap: ap命令と類似しているが、ダミー環境と組み合わせて、再帰関数を実現するのに使われる。

car、cdr、リスト構築、整数の加算、入出力といった基本的な関数も命令として存在する。これらは必要な引数をスタックから得る。

参考文献

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