LISP

提供: testwiki
ナビゲーションに移動 検索に移動

テンプレート:Otheruseslist テンプレート:出典の明記

テンプレート:Infobox プログラミング言語

テンプレート:Lang（リスプ）は、関数型プログラミング言語である。S式と前置記法などが特徴である。

1958年秋から開発が開始され[1]、1960年3月にLISP Iとしてマニュアルが書かれ[2]、1960年4月に初めて論文が発表された[3]テンプレート:Langは、現在でも広く使用されている高水準プログラミング言語の中では、テンプレート:Lang、COBOLに次いで3番目に古い[4]。

これまでに多数の方言が存在してきたが、今日広く使われているテンプレート:Lang方言は、[[Common Lisp|テンプレート:Lang]]、[[Scheme|テンプレート:Lang]]、Clojureなどである。

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

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

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

古くから使われているが、テンプレート:Langと同様に、現在のテンプレート:Langは初期のものから変化している。しかし、FORTRANと比べると変化は小さく、1960年のLISP Iの時点で大半の機能は実装済で[2]、ガーベジコレクションやquoteでコードの中にコードを埋め込みevalで実行する仕組みも最初から存在し、その後実装された主なものは静的スコープ（LISP Iは親スコープの変数束縛がおかしく動的スコープだった[6]）とマクロと継続である。また、標準ライブラリには永続データ構造が片方向リストしかなかった[2]。マクロは1963年に実装された[7]。静的スコープは研究され続け、1975年のSchemeでクロージャを使用する形で完全に解決した[8][9]。

LISPの歴史

テンプレート:Multiple image テンプレート:Langは1958年秋にジョン・マッカーシーがMITのコミュニケーション科学の助教授に就任し開発が始まった[1][10]。マッカーシーは1960年にACMの学会誌テンプレート:Langに「テンプレート:Lang」[3]という題名の論文（「パートII」が発表されることはなかった）を発表した。この論文における重要な点はいくつかあるが、そのひとつは、自分自身を eval できる meta-circular evaluator（en:Meta-circular evaluator）を記述できる、ということを示したことである 。1955年または1956年から開発が始まったIPLは、最初の人工知能言語で、リスト処理や再帰などの多くの概念をすでに含んでいたが、その後すぐにそういった分野ではテンプレート:Langが使われるようになった。

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

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

テンプレート:Langは当初IBM 704上で実装されたが、その計算機のレジスタを構成する部分の名前が、対を分解する関数car[注釈 1]、cdr[注釈 2]の名前の由来となった。爾来、ほとんどのテンプレート:Langの方言において、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]。

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

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

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

1975年にテンプレート:Langベースでプログラミングに必要な言語機能を極限まで抽象化した[[Scheme|テンプレート:Lang]]が開発され、こちらも現在の主流の一つになっている。Schemeで変数のスコープ問題が完全解決し、クロージャを使用する静的スコープが実装された[8][9]。Schemeにて基本的な言語仕様が確定する。関数型言語のグループではMLが1973年に開発され、これが、Standard ML、Ocaml、Haskellなどへと発展していく。

1980年代と1990年代には、たくさんのテンプレート:Lang方言を一つの言語に統合しようという努力がなされた。その結果として1984年に設計された新しい言語[[Common Lisp|テンプレート:Lang]]は基本的にそれらの方言のスーパーセットであり、それらを置き換えることになった。1994年に[[ANSI|テンプレート:Lang]]はテンプレート:Langの標準仕様「テンプレート:Lang」を出版した。しかし、このときまでには、全盛期に比べるとテンプレート:Langの市場は小さくなっていた。

テンプレート:Langは現在でも広く使われている年代物の言語の一つである。

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

文法

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

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

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

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

テンプレート:Langでのリストは空白と括弧で区切られた要素で記述される。たとえば、 

(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")と書く必要がある。このことを解説するため、ここでテンプレート:Langでの評価ルールについて述べる。

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

特殊形式（テンプレート:Lang）は制御構造など、引数の位置にあるものを通常のようには評価しないような機能を提供する。たとえば、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))をテンプレート:Langで表現したものである。

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

純LISP

テンプレート:Main 1980年代、LISPのサブセットの純粋関数型である純LISPと、その処理系であるLispkit Lispが、関数型プログラミングのテストベッド用に、SECDマシン上で開発された。その仕様としては、遅延評価を評価戦略に採り、レキシカルスコープを採用している。以下の5つの関数と特殊形式、他にシンボルのnilとt、などがあれば自分自身を解釈実行できるevalを実装できる。このことはある意味で万能チューリングマシンと同様のことであると言える。

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

プログラム例

以下にいくつかのテンプレート:Lang (特にCommon Lisp) のコード例を示す。これらは産業界における典型的なコードではないが、コンピュータサイエンスのコースで通常教えられる典型的なテンプレート:Langコードである。

テンプレート:Langの構文はそれ自身が再帰的定義に自然に適合している。それゆえ、再帰的に定義された集合を列挙するというような数学の問題をシンプルに表現できる。

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

(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))))

再帰と対照的な概念である反復による計算の例として、テンプレート:Langの代表的な繰り返し構文であるLOOPを使った例を示す。 

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

LOOPはマクロであり、最終的にはプリミティブな構文の組み合わせに展開される。

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

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

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

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

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

テンプレート:Main

系統と変種

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist

出典

テンプレート:Reflist

関連項目

外部リンク

テンプレート:Commons-inline テンプレート:Wikibooks

テンプレート:LISP系言語 テンプレート:プログラミング言語一覧 テンプレート:Normdaten

  1. ↑ 1.0 1.1 テンプレート:Cite web
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 テンプレート:Cite web
  3. ↑ 3.0 3.1 3.2 テンプレート:Cite web
  4. ↑ テンプレート:Cite web
  5. ↑ テンプレート:Cite web
  6. ↑ テンプレート:Cite web
  7. ↑ テンプレート:Cite report
  8. ↑ 8.0 8.1 テンプレート:Cite report
  9. ↑ 9.0 9.1 テンプレート:Cite journalテンプレート:要購読
  10. ↑ テンプレート:Cite book
  11. ↑ テンプレート:Cite web
  12. ↑ テンプレート:Cite web
  13. ↑ テンプレート:Cite web
  14. ↑ REDUCE: The First Forty Years


引用エラー: 「注釈」という名前のグループの <ref> タグがありますが、対応する <references group="注釈"/> タグが見つかりません

「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=LISP&oldid=160」から取得