純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 を返す。 |
|
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インタプリタになると指摘し実装してみせたのはマッカーシー本人ではなくSteve Russell(en:Steve Russell)だった、というエピソードがある[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(en:Lispkit Lisp)などの実装を指してPure Lispとされることもある(なお、Lispkit Lispは静的スコープである)。
脚注
[編集]- ^ なお、論文における記述をはじめとして、初期のLispの実装は動的スコープで、(実は、世間でしばしば言われる評判とは異なって)理論的なそういった綺麗ではない点もあるにはある(理論的には静的(レキシカル)スコープのほうが整合性がある)。これは後に、実は、望んでいたものはレキシカルスコープだったのだが、得られたものは動的スコープだったのだ( In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. http://www-formal.stanford.edu/jmc/history/lisp/node4.html より)、と自ら述べている。
- ^ 英: special form
- ^ ep
.yimg .com /ty /cdn /paulgraham /jmc .lisp( lambda
はdefun
により暗黙のうちに使われている) - ^ http://www-formal.stanford.edu/jmc/history/lisp/node3.html より「S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.」
- ^ 『初めての人のためのLISP [増補改訂版]』p. 55
外部リンク
[編集]- ジョン・マッカーシー (April 1960). “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. 2022年2月16日閲覧。 - ジョン・マッカーシーが最初に純 LISP を導入した論文
- LISP I プログラマーズマニュアル