LISP

LISP（リスプ）は、プログラミング言語の一種である。括弧を多用する独特の構文を持つ。名称「LISP」はリスト処理を意味する英語「list processing」に由来する。

LISPは比較的容易に実装できるため、非常に多くの方言が存在する。

関数型言語に分類されるが、ほとんどのLISP方言は、変数への束縛だけでなく、代入やデータ構造の破壊的操作も可能という、手続き型言語の性格ももっている。

LISPの特徴として以下のようなものがある。

• 動的な型付け（値には型情報を持つが変数は型を持たない）
• 前置記法
• コード自身を第一級（ファーストクラス）オブジェクトとして扱うことができる

LISPは、全てのプログラミング言語の中でも2番目に古い高級言語であり、現在でも広く使われている。ただし、最古の高級言語FORTRANと同様に、言語仕様は初期と比べて大きく変化している。

LISPの歴史

ジョン・マッカーシーによるLISPの着想は1956年夏の「Dartmouth summer research project on artificial intelligence」（人工知能についてのダートマス大学夏季研究プロジェクト）にさかのぼる。H. Gelernter、J. R. Hansen、C. L. GerberichがIBM 704上のFORTRANでリスト操作をおこなうサブルーチンのパッケージとして1958年にFLPL（FORTRAN list processing language）を実装した。プログラミング言語としてのLISPは1958年の秋に実装がはじまった。データ構造のS式やその関数は、実装するコンピュータに依存しないよう設計した。当初のLISPは、ソースの式を、その式の値を計算する機械語のプログラムに変換する、コンパイラとして実装された。1960年に論文 「Recursive functions of symbolic expressions and their computation by machine, Part I」（記号表現の再帰的関数とそれらを用いた機械計算、第一部）をACMの学会誌「Communications of the ACM」（コミュニケーションズ・オブ・ジ・ACM）に発表する。

LISPで書かれたLISPインタプリタ（w:Meta-circular evaluator）であるところのevalについて、マッカーシーはその概略を論文では示している。しかし実装可能であるとは考えていなかった。マッカーシーのもとで大学院生であったスティーブ・ラッセルは論文を読んで、evalを機械語に変換したコードを実装してみせ、マッカーシーを驚かせた。そうしてLISPインタプリタが生まれた。

evalの実現は、チューリングマシンにおける万能チューリングマシンに相当する。（当初LISPプログラムの表現法としていた）M式を、LISP自身が扱うデータ構造に変換したS式は、万能チューリングマシンの入力（テープの初期状態）として与えられるチューリングマシンの記述に相当する。マッカーシーはLISPプログラムのS式による表現を、evalを考えるための論文の中だけのものと考えており、実際のプログラムをS式で書くようになるとは考えていなかった。

LISPは当初IBM 704上で実装されたが、その計算機のレジスタを構成する部分の名前が、LISPの基本操作car(content of adress part of register)、cdr(content of decrement part of register)の由来となった。爾来、ほとんどのLISPの方言において、carとcdrはそれぞれlistの最初の要素と、最初の要素以外を返す関数の名前となっている。

その表現力と柔軟性によって、LISPは人工知能のコミュニティで人気を持つようになった。しかし、その実行には大量のメモリ空間を必要とし、ガベージコレクションを行う必要があるという弱点も持っている。この結果、LISPは貧弱なハードウェア上では実行が困難であった。

1970年代には、増加するユーザコミュニティと寛大な政府の資金提供によって、LISPプログラムの実行に特化したLISPマシンが開発された。

LISPは実装の容易さゆえに非常に多くの方言を生んだ。マクロを用いれば文法構造それ自体を拡張できるので、ある意味では利用者ごとに方言があるとさえいってよい。大きく分けてMACLISP系とInterlisp系の二つの主流が存在し、後のLISP方言に影響を与えている。

1980年代と1990年代には、たくさんのLISP方言を一つの言語に統合しようという努力がなされた。その結果として設計された新しい言語Common Lispは基本的にそれらの方言のスーパーセットであり、それらを置き換えることになった。1994年にANSIはCommon Lispの標準仕様「ANSI X3.226-1994 情報技術プログラミング言語 Common LISP」を出版した。しかし、このときまでには、全盛期に比べるとLISPの市場は小さくなっていた。

一方で1970年代中ごろには、LISPベースでプログラミングに必要な言語機能を極限まで抽象化したschemeが発生し、こちらも現在の主流の一つになっている。

LISPは現在でも広く使われている年代物の言語の一つである。

文法

LISPは「式指向」の言語である。他の多くの言語とは違って、式と文は区別されず、すべてのコードとデータは式として書き下される。式が評価されたとき、それは1つの値（または値のリスト）を生成する。式は他の式に埋め込まれることができる。

マッカーシーの1958年の論文では、2つのタイプの表現が導入されている。内部のデータ構造の表現であるS式（記号式、テンプレート:Lang-en-short、sexp）と、S式を引数に取りS式を返す関数を表す、外部表現であるM式(メタ式、テンプレート:Lang-en-short）である。マッカーシーは、S式はプログラムの処理対象のデータの表現に使い、LISPプログラムの表現にはM式を使った。S式によるプログラムの表現は論文の中のみのものと考えていた。しかし、S式で表現されたプログラムを評価するevalが実装され、S式で表現することでプログラムをプログラムで操作できるという利点があり、今日ではほとんどすべてのLISP言語でM式は使用されておらず、プログラムとデータの両方にS式を使用する。

LISPの用いる S式は括弧を大量に使用するため、批判を受けることもある。「LISP は 『lots of irritating superfluous parentheses』（過剰でいらいらさせる大量の括弧）に由来する」というジョークもある。しかし、S式による構文はLISPの能力を生み出してもいる。この構文は極めて正規化されているので、コンピュータによる操作が容易に行うことができる。

式への依存が、LISPに優れた柔軟性を与えている。LISPの関数は、それ自身がリストとして書かれており、データとまったく同様に扱うことができる。LISPのプログラムは他のLISPプログラムを処理するように書くことができる。これは、メタプログラミングと呼ばれる。多くの LISP方言はこの機能をマクロシステムで活用しており、言語自身の機能をほとんど際限なく拡張することを可能にしている。

LISPでのリストは空白と括弧で区切られた要素で記述される。たとえば、

(1 2 "foo")

は1, 2, "foo"の値を 要素として持つ1つのリストである。 これらの値は暗黙の型を持つ。 これらは2つの整数と1つの文字列であるが、 そのように宣言されている必要はない。 空のリスト()はnilとも書ける。

評価

現実の実装では、上記のリストを直接処理系に入力するとエラーが起きる。

CL-USER> (1 2 "foo")
; in: 1 2
;     (1 2 "foo")
; 
; caught ERROR:
;   illegal function call

これは、上の(1 2 "foo")は正しい式ではないからである。 処理系の中で上のリストを表現したい場合は、クオート「'」を用いて '(1 2 "foo")と書く必要がある。 このことを解説するため、ここでLispでの評価ルールについて述べる。

すべての式は前置記法のリストとして書かれる。 リストの最初の要素はフォーム（関数、演算子、マクロ、特殊フォームのいずれか） の名前である。 リストの残りは引数である。 たとえば、関数listはその引数をリストとして返す。つまり式

(list 1 2 "foo")

は評価されてリスト'(1 2 "foo")を返す。 このことを念頭に置いて、もう一度最初に挙げた式を振り返ると、

(1 2 "foo")
; 1 という関数名は存在しない

という仕組みでによりエラーが返されたことがわかるだろう。

もし引数のどれかが式であれば、それを含む式が評価される前にそれが再帰的に評価される。たとえば、

(list 1 2 (list 3 4))

はリスト(1 2 (3 4))に評価される。つまり、3番目の引数はリストであり、リストはネストできるのである。

算術演算も同様に処理される。式

(+ 1 2 3 4)

は10に評価される。この式は中置記法では"1+2+3+4"と等価である。

特殊形式（special form）は制御構造など、引数の位置にあるものを通常のようには評価しないような機能を提供する。たとえば、ifは3つの引数をとり、 第一引数の値が真なら第二引数に、偽なら第三引数に評価される。ここで真とはnil以外、偽とはnilのことである。したがって式

(if (evenp 5)
  (list 1 2 "foo")
  (list 3 4 "bar"))

は(3 4 "bar")に評価される。 evenpは、その第一引数が偶数であるときにtを、 奇数の時nilを返す関数である。5は奇数なので、 第一引数(evenp 5)を評価したifは、 その第三引数(list 3 4 "bar")を返す。

関数の定義には、特殊形式lambdaによって

(lambda (x y)
  (+ x y))

のようにして、関数を表現する。この例は、ラムダ計算における (λx y.(x + y))をLISPで表現したものである。

特殊形式defunで関数を定義すると、 関数に名前を付けて定義できる。 defunの引数は引数のリストと、関数として評価される式である。

最小のLISP

以下の5つの関数と特殊形式、他にシンボルのnilとt、などがあれば最小の機能を持つevalを実装することができることから、この5つの関数を基本関数と呼ぶことがある。 また、この実装されたevalは万能関数であり、自分自身をエミュレートできることはもちろんのこと、チューリングマシンと同等の計算能力を持つ。

• 関数
  • car
  • cdr
  • cons
  • eq
  • atom
• 特殊形式
  • cond
  • quote
  • define(label)

プログラム例

以下にいくつかのLISPのコード例を示す。これらは産業界における典型的なコードではないが、コンピュータサイエンスのコースで通常教えられる典型的なLISPコードである。

ここまでの議論で気づいていた読者もいると思うが、LISPの構文はそれ自身が再帰的定義に自然に適合している。それゆえ、再帰的に定義された集合を列挙するというような数学の問題をシンプルに表現できる。

以下の関数は引数の階乗に評価される。

(defun factorial (n)
  (if (<= n 1)
      1
    (* n (factorial (- n 1)))))

以下は別のやり方であり、末尾再帰になっているので末尾再帰の最適化を行う処理系であれば上記のバージョンよりも高速である。

(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
    (factorial (- n 1) (* acc n))))

再帰と対照的な概念である反復による計算の例として、Common Lispのloopマクロを使った例を示す。

(defun factorial (n)
  (loop for i from 1 to n
        for fac = 1 then (* fac i)
        finally (return fac)))

loopマクロはCommon Lisp標準の文法であり、手続き的なループを表現するための文法としてCommon Lisp以前のLisp方言から導入された。loopはマクロなので、コンパイル時に式変形され、これが分解されて「普通の」lispに翻訳されるものと考えてよい。

一方、このloopマクロには欠点もあった。 loopは「ANSI標準」として取り入れられているため 拡張することが許されていない点である。 ここに、ライブラリiterateが誕生した。 通常の言語では、ライブラリとは 手続き、関数、クラス定義などをまとめたものを指すが、 lispでは「新たな文法を与えてくれるライブラリ」というものが 普通のライブラリと同様に存在する。

(defun factorial (n)
  (iter (for i from 1 to n)
        (for fac initially 1 then (* fac i))
        (finally (return fac))))

以下の関数は引数にリストをとり、そのリストの要素の順番を逆にしたものに評価される（LISPは実際には同じことを行うビルトイン関数を普通持っている）。

(defun reverse (l &optional acc)
  (if (atom l)
      acc
    (reverse (cdr l) (cons (car l) acc))))

オブジェクト指向システム

以下を含む多種のオブジェクト指向あるいはモジュールがLISPの上に、あるいは併置して、あるいは組み込まれて設置されている。

• MITによるFlavors
• Flavorsの子孫であるCLOS(The Common Lisp Object System)

CLOSは多重継承と多重ディスパッチ（マルチメソッド）の機能を持ち、 強力なメソッド結合(method combination)のシステム(FIXME)を持つ。 CLOSを含めたCommon Lispは、 公式に標準化された最初のオブジェクト指向言語である。

系統と変種

• AutoLISP/Visual LISP - AutoCAD製品のカスタマイズ用の言語。
• Cambridge LISP - 当初、IBMのメインフレーム上で実装され、メタコムコによってAmiga用として発表された。
• Clojure - マルチスレッドプログラムの開発を容易化する汎用言語。
• Common Lisp - 主にZetaLISPとFranzの子孫であり、InterLISPの機能も導入された。
• Coral LISP - Macintosh用のLISP実装。
• ELisp -古いLISP実装のひとつ。 Emacs Lispとは別。
• Emacs Lisp - GNU Emacsエディターの拡張言語。
• Franz LISP - 元はバークレイのプロジェクトである。後にFranz, Incに移行。
• Gold Hill Common LISP - パーソナルコンピュータ用のLISPの初期の実装。
• InterLisp - MITで開発され、後にゼロックスのLISPマシンのための「東海岸LISP」として採用された。より小さいバージョンである「InterLISP 65」はAtariの6502ベースのコンピュータ用に発表された。
• LISP 1, LISP 1.5 - MITで開発されたマッカーシーのオリジナル版。
• Lispkit LISP - 純粋な関数型言語としての方言であり、仮想計算機SECDマシン上に実装された。関数型言語のコンセプトの実験用テストベッドとして使用された。
• Macintosh Common Lisp - デジツールによるMacintosh用のCommonLISP環境でMacintoshのToolboxにアクセスする機能を持つ。
• MACLisp - MITのプロジェクトMAC（アップルのMacintoshとは無関係）のために開発されたLISPの直系子孫。
• MockLisp - Gosling Emacs (Unipress Emacs) エディターの拡張言語。リストのないLISP。
• Oak LISP - Schemeベースのオブジェクト指向言語。
• Scheme - 当初教育目的で設計された最小主義的なLISP。ダイナミックスコープではなくレキシカルスコープをLISPとして初期頃に採用した。
• SKILL - ケイデンス・デザイン・システムズ社製の多くのEDA製品で使われる。
• ZetaLisp - LISPマシンのために使われた、MACLISPの直系子孫。
• 純LISP - 副作用のないLISP。
• xyzzy - Microsoft Windowsで動くエディタ。マクロ言語としてxyzzy Lispを実装している。

関連項目

• Macsyma、Maxima
• AutoCAD
• 人工知能
• SICP

外部リンク

• Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I) - マッカーシーによる最初のLISPの論文。