純LISP

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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インタプリタになると指摘し実装してみせたのはマッカーシー本人ではなく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は静的スコープである)。

脚注[ソースを編集]

  1. ^ なお、論文における記述をはじめとして、初期のLispの実装は動的スコープで、(実は、世間でしばしば言われる評判とは異なって)理論的なそういった綺麗ではない点もあるにはある(理論的には静的(レキシカル)スコープのほうが整合性がある)。これは後に、実は、望んでいたものはレキシカルスコープだったのだが、得られたものは動的スコープだったのだ( In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. http://www-formal.stanford.edu/jmc/history/lisp/node4.html より)、と自ら述べている。
  2. ^ : special form
  3. ^ ep.yimg.com/ty/cdn/paulgraham/jmc.lisplambdadefun により暗黙のうちに使われている)
  4. ^ 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.」
  5. ^ 『初めての人のためのLISP [増補改訂版]』p. 55

外部リンク[ソースを編集]