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)" などと表記する。
命令.
car、cdr、リスト構築、整数の加算、入出力といった基本的な関数も命令として存在する。これらは必要な引数をスタックから得る。