LISP

出典: フリー百科事典『ウィキペディア（Wikipedia）』

（Lisp から転送）
LISP
パラダイム マルチパラダイム：
関数型、手続き型
登場時期 1958年
設計者 ジョン・マッカーシー
開発者 スティーブ・ラッセル、ティモシー・P・ハート、マイク・レビン
型付け 強い動的型付け
方言 Common Lisp, Emacs Lisp, ISLISP, Scheme
影響を与えた言語 LOGO, Perl, Python, Smalltalk, Ruby, Dylan, Mathematica
 表・話・編・歴 

LISP（リスプ、LISt Processingの略）は、関数型プログラミング言語の一種。括弧を多用する独特な文法を持つ。

LISP の実装は比較的容易なため、非常に多くの（方言）が存在し、厳密には、「LISP方言」と呼ばれるそれらの方言の集まりを指して LISP と呼ぶ。ただし、一般的に「Lisp」というときは Common Lisp のことを指している場合が多い。なお、方言の中には、変数への値の代入（束縛）も可能な、手続き型言語の性格をもっているものもある。

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

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

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

目次

[編集] LISPの歴史

LISP は 1958年にMITにいたジョン・マッカーシーによって発明された。当初 LISP はラムダ算法の計算モデルを紙の上で表現するための記法として考案されたもので、コンピューター言語を意図して設計されたわけではない。しかし、当時マッカーシーの教え子だったスティーブ・ラッセルがそれを FORTRAN 上に移植し、初の LISP インタープリタが誕生した。

当初の LISP は FORTRAN 上で動くリスト処理用のライブラリであり、FLPL (Fortran List Processing Language) と呼ばれていた。そして1960年にマッカーシーの論文「再帰関数のS式表現とその計算機上での実行 第一部」がCACMで発表され、広く普及するに至る。

LISPは当初IBM 704上で実装されたが、その計算機上の2つの命令がLISPの基本操作car(Contents of Address Register)、cdr(Contents of Decrement Register)になった。ほとんどのLISPの方言において、carとcdrはそれぞれlistの最初の要素と、最初の要素以外を返す操作である。

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

1970年代には、増加するユーザコミュニティと寛大な政府の資金提供によって、LISPプログラムの実行に特化したLISPマシンが開発された。日本でも青山学院大学で開発されたALPS-1などがある。これは、8080の特定の命令実行を横取りし、ハードウェアでデータを処理させる、という仕組みであった。

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式(Symbolic Expression, シンボル式、sexp）と、S式の関数を表すM式(Meta Expression, メタ式）である。M式には利点がなかったため、今日ではほとんどすべてのLISP言語でM式は使用されておらず、コードとデータの両方の操作にS式のみを使用する。

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とも書ける。

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

(list 1 2 "foo")

は評価されてリスト(1 2 "foo")を返す。

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

(list 1 2 (list 3 4))

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

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

(+ 1 2 3 4)

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

「特殊フォーム」はLISPの制御構造を提供する。たとえば、特殊フォームifは3つの引数をとり、 第一引数の値が真なら第二引数に、偽なら第三引数に評価される。ここで真とはnil以外、偽とはnilのことである。したがって式

(if nil
  (list 1 2 "foo")
  (list 3 4 "bar"))

は(3 4 "bar")に評価される。言うまでもないが、nilのところに自明でない式が来ることによって有用になる。

その他の特殊形式defunは、関数を定義するために用いられる。defunの引数は引数のリストと、関数として評価される式である。

[編集] 最小のLISP

最小のLISPは、以下に示す関数だけを必要とする。

  • car
  • cdr
  • cons
  • quote
  • eq
  • atom
  • cond
  • defun等、関数を定義する命令

他の全ての関数は、これらの関数によってに定義できるため、これらの関数をCや機械語で記述すれば、後はLISP自身によって言語全体を記述できる。ただし、処理速度等の関係から主要な関数はCや機械語で記述することも多い。

[編集] プログラム例

以下にいくつかの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)))

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

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

[編集] オブジェクト指向システム

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

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

[編集] 系統と変種

[編集] 関連項目

[編集] 外部リンク

"http://ja.wikipedia.org/wiki/LISP" より作成