純LISP

純LISP（じゅんりすぷ, テンプレート:Lang-en-short）とは、コンピュータ・プログラミング言語 LISP において、必要最小限の関数に絞り込んだ純粋形の事。1960年4月にジョン・マッカーシーが発表した論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」で導入された。基本的な関数とプリミティブのみしかないが、その言語の処理系をその言語で記述できるという性質を持っている。なお、論文とほぼ同時期に発表された、最初の LISP の実装である LISP I は約90個の組み込み関数があり、純LISPではない。

概要

純LISPには2種のデータ（リスト、アトム）、及び、関数はそれらを操作する5つの基本関数だけが存在する。

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

5つの基本関数とは、

関数	説明	記号的説明
atom	値がアトムなら T を返す。	atom[(A B)] → nil、 atom[nil] → T
eq	二つの値が同一のものなら T を返す。	eq[A;A] → T
car	リストの左値をとり出す。	car[(A . B)] → A
cdr（クダー）	リストの右値をとり出す。	cdr[(A . B)] → B
cons	二つの値からなるリストを作る。	cons[A;B] → (A . B)

以上のデータと関数の他に下記の特殊形式など（関数ではない）が必要である。

• cond
• quote
• lambda
• define

以上が最小構成の LISP であり、eval を理論上構成できることをマッカーシーは示した。ポール・グレアムが Common Lisp 流に書き直したサンプルがある。

関連項目

• チューリング完全

外部リンク

• テンプレート:Cite web - ジョン・マッカーシーが最初に純 LISP を導入した論文
• LISP I プログラマーズマニュアル