LISP

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

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

これまでに多数の方言が存在してきたが、今日広く使われている方言は、、、Clojureなどである。

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

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

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

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

LISPの歴史

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

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

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

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

1960年にLISP Iがリリースされ、1962年にLISP 1.5がリリースされた。1960年のLISP Iの時点で既にガベージコレクションは実装されている。また、1960年のLISP Iの時点から、M式で apply[f;x;p] とマニュアルに記載されているものであっても、パンチカードでは f x p と空白区切りでS式で入力することとなっている。1964年の書籍 The Programming Language LISP: Its Operation and Applications では既にM式表記はなくなり現代と同じく空白区切りのS式で表記されている。

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

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

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

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

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

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

LISP処理系と派生言語のタイムライン + LISP系言語の大まかな流れ 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2020LISPLISP I, 1.5, 2MaclispMaclispInterlispInterlispZetaLispLisp Machine LispSchemeSchemeNILNILCommon LispCommon LispTTEmacs LispEmacs LispAutoLISPAutoLISPISLISPISLISPEuLispEuLispPicoLispPicoLispRacketRacketArcArcClojureClojureLFELFEHyHy

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

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

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

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

でのリストは空白と括弧で区切られた要素で記述される。たとえば、

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

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

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

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

純LISP

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

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

プログラム例以下にいくつかの (特にCommon 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))))

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

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

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

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

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

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

MITによるの子孫である()

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

系統と変種 / - 製品のカスタマイズ用の言語。 - 当初、IBMのメインフレーム上で実装され、メタコムコによって用として発表された。 - Java仮想マシン上で動作するLISP。マルチスレッドプログラムの開発を容易化する汎用言語。 - 主にとの子孫であり、の機能も導入された。

-古い実装のひとつ。とは別。 - エディタの拡張言語。 - 元はバークレイのプロジェクトである。後にに移行。

- BBN社で開発され、初期にはBBN LISPと呼ばれた。後に開発者グループがゼロックスのパロアルト研究所に移動した際にInterLispと改名され、ゼロックスのマシンにもInterLisp-Dとして採用された。強力な対話型開発ツールが特徴。より小さいバージョンである「 65」はの6502ベースのコンピュータ用に発表された。 KLISP - 1967年に中西正和がTOSBAC-3400上で開発し、日本のLISP研究と教育に貢献した。、 - MITで開発されたマッカーシーのオリジナル版。 - 純粋な関数型言語としての方言であり、SECDマシン上に実装された。関数型言語のコンセプトの実験用テストベッドとして使用された。

- MITのプロジェクトMAC（Appleのとは無関係）のために開発されたLISPの直系子孫。 - () エディタの拡張言語。リストのない。 - ベースのオブジェクト指向言語。 RPL - 「Reverse Polish LISP」(逆ポーランド記法式LISP)の名を冠した言語。逆ポーランド記法・スタック指向を採用するなど、Forthの影響も大きい。ヒューレット・パッカード社製の関数電卓に組み込まれることを想定して開発された。 - ダイナミックスコープではなく静的スコープにもとづき再設計された。 - ケイデンス・デザイン・システムズ社製の多くのEDA製品で使われる。

- マシンのために使われた、の直系子孫。純 - 超循環評価機を記述可能な程度で、ごく小さいサブセットに機能を絞った方言。元々は「最初の論文」と呼ばれている論文中で理論的なものとして示されたが、実際に実装可能である。 - で動くエディタ。マクロ言語としてを実装している。 Orion - LISPの構文を具備する関数型プログラミング言語、GPL-3.0ライセンス。

脚注

注釈

出典

Źródło i licencja