LISP

LISP

LISPのロゴ
パラダイム	関数型プログラミング、手続き型プログラミング、メタプログラミング、マルチパラダイムプログラミング、リフレクション
登場時期	1958年 (1958)
設計者	ジョン・マッカーシー
開発者	スティーブ・ラッセル、ティモシー・P・ハート、マイク・レビン
型付け	強い動的型付け
方言	Arc、AutoLISP、Clojure、Common Lisp、Egison、Emacs Lisp、EuLisp、Franz Lisp、Hy、Interlisp、ISLISP、Le Lisp、LFE、Maclisp、MDL、newLISP、NIL、PicoLisp、 Portable Standard Lisp、Racket、Scheme、SKILL、Spice Lisp、T、XLISP、Lisp Machine Lisp
影響を受けた言語	Information Processing Language
影響を与えた言語	CLIPS、CLU、COWSEL、Dylan、Falcon、 Forth、Haskell、Io、Ioke、JavaScript、 Julia、LOGO、Lua、Mathematica、MDL、 ML、Nu、OPS5、Perl、POP-2、POP-11、Python、R、Rebol、RPL、Ruby、Smalltalk、Tcl/Tk

LISP（リスプ）は、プログラミング言語である。前置記法などが特徴である。

1958年にはじめて設計されたLISPは、現在広範囲に使用されている高水準プログラミング言語の中でもFORTRANに次いで2番目に古い。ただし、FORTRANと同様に、現在のLISPは初期のものから非常に大きく変化している。

これまでに多数の方言が存在してきたが、今日最も広く知られるLISP方言は、Common LispとSchemeである。

元々、LISPは、アロンゾ・チャーチのラムダ計算表記法に影響を受け、コンピュータープログラムのための実用的かつ数学的な表記法として作られた。そして、すぐに人工知能研究に好まれるプログラミング言語になった。最初期のプログラミング言語として、LISPは計算機科学にて、木構造、ガベージコレクション、動的型付け、条件分岐、高階関数、再帰、セルフホスティング、コンパイラを含む多くのアイディアを切り開いた。

LISPの名前は、「list processor」に由来している。リストはLISPの主要なデータ構造であり、LISPソースコードはそれ自体がリストからできている。その結果、LISPプログラムはソースコードをデータとして操作することができ、プログラマーは、マクロ・システムで新しい構文やLISP埋め込みの新しいDSLを作成できる。

コードとデータの互換性は、LISPにそのすぐに認識できる構文を与える。すべてのプログラム・コードはS式または入れ子のリストとして書かれる。関数呼び出しまたは構文は先頭が関数または演算子の名前で、その続きが引数であるリストとして書かれる。具体的には、3つの引数を取る関数fは、(f arg1 arg2 arg3)として呼び出される。

LISPの歴史

ジョン・マッカーシー(上)、スティーブ・ラッセル(下)

LISPは1958年にジョン・マッカーシーがMITにいた期間に考案された。マッカーシーは1960年にACMの学会誌Communications of the ACMに「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」という題名の論文（「パートII」が発表されることはなかった）を発表した。この論文において、M-expression（Meta expression）と呼ばれる少数の単純な演算子と関数の表記法で、自分自身を評価するeval関数（超循環評価器）を記述できることが示された。

1955年または1956年からはじまった、IPLは、最初の人工知能言語で、リスト処理や再帰などの多くの概念をすでに含んでいたが、その後すぐにそういった分野ではLISPが使われるようになった。

前述の超循環評価器はLISP自身で実装されているが、ひとたびLISP以外の言語で実装すればそれは実際にLISPを解釈実行できるインタプリタとなる。マッカーシーは自分の論文中にある評価器は単なる理論上の存在で、そのようにしてインタプリタを実装可能であると考えていなかった。しかし、マッカーシーのもとで大学院生であったスティーブ・ラッセルは論文を読んだ後、機械語でそれを実装してみせ、マッカーシーを驚かせた。そうしてLISPインタプリタが生まれた。

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

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

その発端からLISPは、人工知能研究のコミュニティ、特にPDP-10システムのユーザーには近しい存在であった。PDPの計算機の設計目標の一つにLispの実装があり、PDP-6は当初、1ワード24bitの計算機として設計されていたが、Lisp1.5を移植しやすくするために36bitに変更された。人工知能コミュニティでは、LISPはプログラミング言語の実装用言語としても用いられた。有名なAIシステムSHRDLUの実装言語のMicro Plannerは、MACLISPで実装されている。

また、1970年代には、LISPで実装されたREDUCEや、Macsyma等の数式処理システムの需要が高まるにつれ高速なLISPの処理系の需要も高まり、LISPを高速に処理するいわゆるLISPマシンの動機の一つとなった。LISPマシンは、タグアーキテクチャや、ハードウェアスタック等LISP向けのハードウェア機構により、型のディスパッチや関数呼出し、ガベージコレクションの高速化を実現した。

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

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

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

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

文法

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

マッカーシーの1958年の論文では、2つのタイプの表現が導入されている。内部のデータ構造の表現であるS式（記号式、英: symbolic expression、sexp）と、S式を引数に取りS式を返す関数を表す、外部表現であるM式(メタ式、英: meta expression）である。マッカーシーは、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

→詳細は「純LISP」を参照

1980年代、LISPのサブセットの純粋関数型である純LISPと、その処理系であるLispkit Lispが、関数型プログラミングのテストベッド用に、SECDマシン上で開発された。 その仕様としては、遅延評価を評価戦略に採り、レキシカルスコープを採用している。 以下の5つの関数と特殊形式、他にシンボルのnilとt、などがあれば自分自身を解釈実行できる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はマクロであり、これが展開されて最終的にはプリミティブな構文の組み合わせに翻訳される。

以下の関数は引数にリストをとり、そのリストの要素の順番を逆にしたものに評価される（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)を持つ。LISPを含めたCommon Lispは、公式に標準化された最初のオブジェクト指向言語である。

→詳細は「Common Lisp Object System」を参照

系統と変種

• AutoLISP/Visual LISP - AutoCAD製品のカスタマイズ用の言語。
• Cambridge LISP - 当初、IBMのメインフレーム上で実装され、メタコムコによってAmiga用として発表された。
• Clojure - マルチスレッドプログラムの開発を容易化する汎用言語。
• Common Lisp - 主にZetaLISPとFranz Lispの子孫であり、InterLISPの機能も導入された。
• Coral LISP - Macintosh用のLISP実装。
• Egison - パターンマッチの拡張性が特徴の言語。
• ELisp -古いLISP実装のひとつ。 Emacs Lispとは別。
• Emacs Lisp - GNU Emacsエディタの拡張言語。
• Franz LISP - 元はバークレイのプロジェクトである。後にFranz, Incに移行。
• Gold Hill Common LISP - パーソナルコンピュータ用のLISPの初期の実装。
• InterLisp - BBN社で開発され、初期にはBBN LISPと呼ばれた。後に開発者グループがゼロックスのパロアルト研究所に移動した際にInterLispと改名され、ゼロックスのLISPマシンにもInterLisp-Dとして採用された。強力な対話型開発ツールが特徴。より小さいバージョンである「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ベースのオブジェクト指向言語。
• RPL - 「Reverse Polish LISP」(逆ポーランド記法式LISP)の名を冠した言語。逆ポーランド記法・スタック指向を採用するなど、Forthの影響も大きい。ヒューレット・パッカード社製の関数電卓に組み込まれることを想定して開発された。
• Scheme - ダイナミックスコープではなく静的スコープにもとづき再設計されたLISP。
• SKILL - ケイデンス・デザイン・システムズ社製の多くのEDA製品で使われる。
• ZetaLisp - LISPマシンのために使われた、MACLISPの直系子孫。
• 純LISP - 超循環評価機を記述可能な程度で、ごく小さいサブセットに機能を絞った方言。元々は「最初の論文」と呼ばれている論文中で理論的なものとして示されたが、実際に実装可能である。
• xyzzy - Microsoft Windowsで動くエディタ。マクロ言語としてxyzzy Lispを実装している。

関連項目

• Macsyma、Maxima
• AutoCAD
• 人工知能
• SICP
• シェーキー

外部リンク

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