純Lisp

純Lispは、ラムダ計算をモデルに考案された理論上のプログラミング言語。1960年にジョン・マッカーシーによって導入された。データは二種(リスト、アトム)と、関数はそれらを操作する五つの基本関数だけから成る。他にquoteやlambdaやcondやdefunのような特殊形式が必要。

二種のデータ

• 「リスト」データのペアで、値A,Bからなるリストは (A . B)のように表され、リストを再帰的に連結することで任意のデータ構造を表現できる。
• 「アトム」リストではないもので、上記nilはリストの終端を示すアトムである他、真値Tもアトムである。

五つの基本関数

• car リストの左値をとり出す。(car[(A . B)] -> A)
• cdr リストの右値をとり出す。(cdr[(A . B)] -> B)
• cons 二つの値からなるリストを作る。(cons[A;B] -> (A . B))
• atom 値がアトムならTを返す。(atom[(A B)] -> nil, atom[nil] -> T)
• eq 二つの値が同じ物ならTを返す (eq[A;A] -> T)

その他特殊形式

以上が最小構成のLispであり、マッカーシーはこれらによってevalが理論的には構成できるとした（マッカーシーは実際に実装できると考えていなかった。その予測を覆し、実際に計算機で動くevalを実装したのはスティーブ・ラッセルである）。