LISP

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

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は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年の論文^[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でのリストは空白と括弧で区切られた要素で記述される。たとえば、

(12"foo")

は1, 2, "foo"の値を要素として持つ1つのリストである。これらの値は暗黙の型を持つ。これらは2つの整数と1つの文字列であるが、そのように宣言されている必要はない。空のリスト()はnilとも書ける。

ここでは Lisp の方言の一つである Common Lisp を例に説明する。現実の実装では、上記のリストを直接処理系に入力するとエラーが起きる。

CL-USER>(12"foo")
; in: 1 2
; (1 2 "foo")
; 
; caught ERROR:
; illegal function call

これは、上の(1 2 "foo")は正しい式ではないからである。処理系の中で上のリストを表現したい場合は、クオート「'」を用いて'(1 2 "foo")と書く必要がある。このことを解説するため、ここでLISPでの評価ルールについて述べる。

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

(list12"foo")

は評価されてリスト'(1 2 "foo")を返す。このことを念頭に置いて、もう一度最初に挙げた式を振り返ると、

(12"foo")
; 1 という関数名は存在しない

という仕組みでによりエラーが返されたことがわかるだろう。

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

(list12(list34))

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

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

(+1234)

は10に評価される。この式は中置記法では「${\displaystyle 1+2+3+4}${\displaystyle 1+2+3+4}」と等価である。

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

(if(evenp5)
(list12"foo")
(list34"bar"))

は(3 4 "bar")に評価される。evenpは、その第一引数が偶数であるときにtを、 奇数の時nilを返す関数である。5は奇数なので、第一引数(evenp 5)を評価したifは、その第三引数(list 3 4 "bar")を返す。

関数の定義には、特殊形式lambdaによって

(lambda(xy)(+xy))

のようにして、関数を表現する。この例は、ラムダ計算における (λx y.(x + y))をLISPで表現したものである。

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

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

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

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

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

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

(defunfactorial(n)
(if(<=n1)
1
(*n(factorial(-n1)))))

下記は別のやり方であり、末尾再帰になっている。

(defunfactorial(n&optional(acc1))
(if(<=n1)
acc
(factorial(-n1)(*accn))))

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

(defunfactorial(n)
(loopforifrom1ton
forfac=1then(*faci)
finally(returnfac)))

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

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

(defunreverse(l&optionalacc)
(if(atoml)
acc
(reverse(cdrl)(cons(carl)acc))))

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

• MITによるFlavors
• Flavorsの子孫であるCLOS(The Common Lisp Object System)

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

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

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

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

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

• ZetaLisp - LISPマシンのために使われた、MACLISPの直系子孫。
• 純LISP - 超循環評価機を記述可能な程度で、ごく小さいサブセットに機能を絞った方言。元々は「最初の論文」と呼ばれている論文中で理論的なものとして示されたが、実際に実装可能である。
• xyzzy - Microsoft Windowsで動くエディタ。マクロ言語としてxyzzy Lispを実装している。

• Macsyma、Maxima
• AutoCAD
• 人工知能
• SICP
• シェーキー

ウィキメディア・コモンズには、LISPに関するメディアがあります。

• 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 の沿革

• LISP
• プログラミング言語
• 関数型プログラミング言語
• アメリカ合衆国の発明

• 出典を必要とする記事/2023年11月
• FAST識別子が指定されている記事
• BNE識別子が指定されている記事
• BNF識別子が指定されている記事
• BNFdata識別子が指定されている記事
• GND識別子が指定されている記事
• J9U識別子が指定されている記事
• LCCN識別子が指定されている記事
• NKC識別子が指定されている記事
• SUDOC識別子が指定されている記事