LISP
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/12 07:43 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2023年11月) |
 LISPのロゴ | |
| パラダイム |
関数型プログラミング、手続き型プログラミング、メタプログラミング、マルチパラダイムプログラミング、リフレクション  |
|---|---|
| 登場時期 | 1960年[1][2][3] |
| 設計者 | ジョン・マッカーシー |
| 開発者 | スティーブ・ラッセル、ティモシー・P・ハート、マイク・レビン |
| 型付け | 強い動的型付け |
| 方言 |
Arc、AutoLISP、Clojure、Common Lisp、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 |
1958年秋から開発を始め[1]、1960年3月にLISP Iのマニュアルが書かれ[2]、1960年4月[3]に初めて論文発表されたLISPは、現在でも広範囲に使用されている高水準プログラミング言語の中ではFORTRAN、COBOLに次いで3番目に古い[4]（世界で3番目に作られたプログラミング言語という意味では無く、他の言語が使われなくなったという意味）。
これまでに多数の方言が存在してきたが、今日広く使われているLISP方言は、Common Lisp、Scheme、Clojureなどである。
元々、LISPは、アロンゾ・チャーチのラムダ計算表記法に影響を受け、コンピュータプログラムのための実用的かつ数学的な表記法として作られた。そして、すぐに人工知能研究に好まれるプログラミング言語になった。最初期のプログラミング言語として、LISPは計算機科学にて、木構造、ガベージコレクション、動的型付け、条件分岐、高階関数、再帰、セルフホスティング、コンパイラを含む多くのアイディアを切り開いた[5]。
LISPの名前は、「list processor」に由来している。リストはLISPの主要なデータ構造であり、LISPソースコードはそれ自体がリストからできている。その結果、LISPプログラムはソースコードをデータとして操作することができ、プログラマは、マクロ・システムで新しい構文やLISP埋め込みの新しいDSLを作成できる。
コードとデータの互換性は、LISPにそのすぐに認識できる構文を与える。すべてのプログラム・コードはS式または入れ子のリストとして書かれる。関数呼び出しまたは構文は先頭が関数または演算子の名前で、その続きが引数であるリストとして書かれる。具体的には、3つの引数を取る関数fは、(f arg1 arg2 arg3)として呼び出される。
古くから使われているが、FORTRANと同様に、現在のLISPは初期のものから変化している。しかし、FORTRANと比べると変化は小さく、1960年のLISP Iの時点で大半の機能は実装済で[2]、ガーベジコレクションやquoteでコードの中にコードを埋め込みevalで実行する仕組みも最初から存在し、その後実装された主なものは静的スコープ（LISP Iは親スコープの変数束縛がおかしく動的スコープだった[6]）とマクロと継続である。また、標準ライブラリには永続データ構造が片方向リストしかなかった[2]。マクロは1963年に実装された[7]。静的スコープは研究され続け、1975年のSchemeでクロージャを使用する形で完全に解決した[8][9]。
LISPの歴史
LISPは1958年秋にジョン・マッカーシーがMITのコミュニケーション科学の助教授に就任し開発が始まった[1][10]。マッカーシーは1960年にACMの学会誌Communications of the ACMに「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」[3]という題名の論文（「パートII」が発表されることはなかった）を発表した。この論文における重要な点はいくつかあるが、そのひとつは、自分自身を eval できる meta-circular evaluator（en:Meta-circular evaluator）を記述できる、ということを示したことである 。1955年または1956年から開発が始まったIPLは、最初の人工知能言語で、リスト処理や再帰などの多くの概念をすでに含んでいたが、その後すぐにそういった分野ではLISPが使われるようになった。
前述の meta-circular evaluator はLISP自身で実装されているが、ひとたびLISP以外の言語で実装すればそれは実際にLISPを解釈実行できるインタプリタとなる。マッカーシーは自分の論文中にある評価器は単なる理論上の存在で、そのようにしてインタプリタを実装可能であると考えていなかった。しかし、マッカーシーのもとで大学院生であったスティーブ・ラッセルは論文を読んだ後、機械語でそれを実装してみせ、マッカーシーを驚かせた。そうしてLISPインタプリタが生まれた。
meta-circular evaluator は、ある意味で、チューリングマシンにおける万能チューリングマシンに相当する。（当初LISPプログラムの表現法としていた）「M式」を、LISP自身が扱うデータ構造に変換した「S式」は、万能チューリングマシンの入力（テープの初期状態）として与えられるチューリングマシンの記述に相当する。マッカーシーはやはり、LISPプログラムのS式による表現はevalを考えるための論文の中だけのものと考えており、実際のプログラムをS式で書くようになるとは考えていなかった。
LISPは当初IBM 704上で実装されたが、その計算機のレジスタを構成する部分の名前が、対を分解する関数car[注釈 1]、cdr[注釈 2]の名前の由来となった。爾来、ほとんどのLISPの方言において、carとcdrはそれぞれlistの最初の要素と、最初の要素以外を返す関数の名前となっている。
1960年にLISP Iがリリースされ[2]、1962年にLISP 1.5がリリースされた[11]。1960年のLISP Iの時点で既にガベージコレクションは実装されている[2]。また、1960年のLISP Iの時点から、M式で apply[f;x;p] とマニュアルに記載されているものであっても、パンチカードでは f x p と空白区切りでS式で入力することとなっている[2]。1964年の書籍 The Programming Language LISP: Its Operation and Applications では既にM式表記はなくなり現代と同じく空白区切りのS式で表記されている[12]。
その発端からLISPは、人工知能研究のコミュニティ、特にPDP-10システムのユーザーには近しい存在であった。PDPの計算機の設計目標の一つにLISPの実装があり、PDP-6は当初、1ワード24bitの計算機として設計されていたが、LISP 1.5を移植しやすくするために36bitに変更された[13]。人工知能コミュニティでは、LISPはプログラミング言語の実装用言語としても用いられた。有名なAIシステムSHRDLUの実装言語のMicro Plannerは、MACLISPで実装されている。
また、1968年にLISPで実装されたREDUCE[14]やMacsyma等の数式処理システムが登場し、需要が高まるにつれ高速なLISPの処理系の需要も高まり、LISPを高速に処理するいわゆるLISPマシンの動機の一つとなった。LISPマシンは、タグアーキテクチャや、ハードウェアスタック等LISP向けのハードウェア機構により、型のディスパッチや関数呼出し、ガベージコレクションの高速化を実現した。
LISPは実装の容易さゆえに非常に多くの方言を生んだ。マクロを用いれば文法構造それ自体を拡張できるので、ある意味では利用者ごとに方言があるとさえいってよい。1970年代から1980年代にかけては、大きく分けてMACLISP系とInterlisp系の二つの主流が存在し、後のLISP方言に影響を与えている。
1975年にLISPベースでプログラミングに必要な言語機能を極限まで抽象化したSchemeが開発され、こちらも現在の主流の一つになっている。Schemeで変数のスコープ問題が完全解決し、クロージャを使用する静的スコープが実装された[8][9]。Schemeにて基本的な言語仕様が確定する。関数型言語のグループではMLが1973年に開発され、これが、Standard ML、Ocaml、Haskellなどへと発展していく。
1980年代と1990年代には、たくさんのLISP方言を一つの言語に統合しようという努力がなされた。その結果として1984年に設計された新しい言語Common Lispは基本的にそれらの方言のスーパーセットであり、それらを置き換えることになった。1994年にANSIはCommon Lispの標準仕様「ANSI X3.226-1994 American National Standard for Programming Language Common LISP」を出版した。しかし、このときまでには、全盛期に比べるとLISPの市場は小さくなっていた。
LISPは現在でも広く使われている年代物の言語の一つである。
LISP処理系と派生言語のタイムライン
| 1960 | 1965 | 1970 | 1975 | 1980 | 1985 | 1990 | 1995 | 2000 | 2005 | 2010 | 2015 | 2020 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LISP | LISP I, 1.5, 2 | ||||||||||||
| Maclisp | Maclisp | ||||||||||||
| Interlisp | Interlisp | ||||||||||||
| ZetaLisp | Lisp Machine Lisp | ||||||||||||
| Scheme | Scheme | ||||||||||||
| NIL | NIL | ||||||||||||
| Common Lisp | Common Lisp | ||||||||||||
| T | T | ||||||||||||
| Emacs Lisp | Emacs Lisp | ||||||||||||
| AutoLISP | AutoLISP | ||||||||||||
| ISLISP | ISLISP | ||||||||||||
| EuLisp | EuLisp | ||||||||||||
| PicoLisp | PicoLisp | ||||||||||||
| Racket | Racket | ||||||||||||
| Arc | Arc | ||||||||||||
| Clojure | Clojure | ||||||||||||
| LFE | LFE | ||||||||||||
| Hy | Hy | ||||||||||||
文法
LISPは「式指向」の言語である。他の多くの言語とは違って、式と文は区別されず、すべてのコードとデータは式として書き下される。式が評価されたとき、それは値（または値のリスト）を生成する。式は他の式に埋め込める。
マッカーシーの1960年の論文[3]では、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とも書ける。
評価
ここでは Lisp の方言の一つである Common Lisp を例に説明する。現実の実装では、上記のリストを直接処理系に入力するとエラーが起きる。
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に評価される。この式は中置記法では「
要購読契約)
関連項目
外部リンク
- Recursive Functions of Symbolic Expressions and their Computation by Machine (Part I) - マッカーシーによる1960年の最初のLISPの論文。
- ホーム → projects → lisp → Books — Software Preservation Group - 1960年代のLISPのマニュアル
- Programs with Common Sense - Professor John McCarthy - マッカーシーによる LISP を考案する際の元となった、「家に机がある」を at(desk, home) の様に論理式で情報を表現することを提案した1958年の論文。
- History of Lisp - 1979年にジョン・マッカーシーが書いた1960年前後の LISP の沿革
- 1 LISPとは
- 2 LISPの概要
固有名詞の分類
- LISPのページへのリンク
