LISP

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動： 案内, 検索
曖昧さ回避 この項目では、プログラミング言語の一種であるLISPについて説明しています。
LISP
パラダイム マルチパラダイム：
関数型、手続き型
登場時期 1958年
設計者 ジョン・マッカーシー
開発者 スティーブ・ラッセル、ティモシー・P・ハート、マイク・レビン
型付け 強い動的型付け
方言 Common Lisp, Emacs Lisp, ISLISP, Scheme
影響を与えた言語 LOGO, Perl, Python, Smalltalk, Ruby, Dylan, Mathematica, C#
テンプレートを表示

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マシンが開発された。日本でも富士通のFACOMα、青山学院大学で開発されたALPS/1などがある。

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式を引数に取り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とも書ける。

式は前置記法のリストとして書かれる。最初の要素はフォーム（関数、演算子、マクロ、特殊フォームのいずれか）の名前である。リストの残りは引数である。たとえば、関数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"と等価である。

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

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

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

特殊形式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)))

以下の関数は引数にリストをとり、そのリストの要素の順番を逆にしたものに評価される（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/w/index.php?title=LISP&oldid=40178046」より作成
個人用ツール
名前空間
変種
操作
案内
ヘルプ
ツールボックス
他の言語