純LISP

純LISP（じゅんりすぷ、英: pure LISP）とは、コンピュータ・プログラミング言語 LISP のうち、ごく基本的な要素だけからなる方言の一種。1960年のジョン・マッカーシーの論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」で示された^[1]。基本的な関数とプリミティブのみしかないが、その言語のインタプリタをその言語で記述できるという性質を持っている。なお、論文とほぼ同時期に発表された、最初のLISPの実装であるLISP Iは約90個の組み込み関数があり、純LISPではない。

概要

純LISPには2種のデータ型「アトム」と「ペア」、及び、関数はそれらを操作する5つの基本的な関数が存在する。

• 「ペア」はデータのペアを表現する。要素 A と B からなるペアは (A . B) のように表され、再帰的に連結することで任意のデータ構造を表現できる。便宜上 (A B C) を (A . (B . (C . nil))) というようなリスト的な構造の略記とみなす。
• 「アトム」はペアではないものである。上記 nil はリスト的な構造の終端を示すアトムである。他に真値Tもアトムである。
• 注: ペアのことをリストと言うこともあるが、nil を「空リスト」と考えると「ペアではないがリストではある」というややこしい点があるため、リストという表現はここでは可能な限り避ける。

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)

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

• condまたはif
• quote
• lambda
• define

以上の道具立てにより、自分自身を解釈実行できるeval（超循環評価器）を理論上構成できることをマッカーシーは示した。これはある意味で、万能チューリングマシンの構成と同様のことを行っており、現代的な見方からは一種の操作的意味論を与えたものとも言える。そのevalをポール・グレアムがCommon Lisp流に書き直したサンプルがある^[3]。また、このevalをそのままコンピュータプログラムとして実装すればLispインタプリタになると指摘し実装してみせたのはマッカーシー本人ではなくスティーブ・ラッセルだった、というエピソードがある^[4]。

なお、cons, car, cdr を次のように lambda を使って定義することも不可能ではないので（単純さのための便宜上Schemeで書いている）、

(define (my-cons a d) (lambda (f) (f a d)))
(define (my-car ad) (ad (lambda (a d) a)))
(define (my-cdr ad) (ad (lambda (a d) d)))

以上で説明したものが「最小」であるわけではないが、前述の5関数はLispで一般に最も多用されるリストの操作において公理のようなものと見ることができるため^[5]、基本関数と呼ばれることがある。

その他

論文中で理論的可能性として示されたものであるが、変数のスコープがいわゆる動的スコープであることなどは、こんにちでは一種のバグのようなものとして扱われることもある（理論的には静的スコープのほうが色々な意味で整合的である）。Lispの発展の過程で「FUNARG問題」などとしてその性質が論じられた。Lispkit Lisp（英語版）などの実装を指してPure Lispとされることもある（なお、Lispkit Lispは静的スコープである）。