LISP

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
LISP
パラダイム マルチパラダイム関数型手続き型自己言及メタ
登場時期 1958年
設計者 ジョン・マッカーシー
開発者 スティーブ・ラッセル、ティモシー・P・ハート、マイク・レビン
型付け 強い動的型付け
方言 ArcAutoLISPClojureCommon LispEmacs LispEuLispFranz LispHyInterlispISLISPLe LispLFEMaclispMDLnewLISPNILPicoLisp
Portable Standard LispRacketRPLSchemeSKILLSpice LispTXLISPLisp Machine Lisp
影響を受けた言語 IPL
影響を与えた言語 CLIPSCLUCOWSELDylanFalcon
ForthHaskellIoIokeJavaScript
JuliaLOGOLuaMathematicaMDL
MLNuOPS5PerlPOP-2POP-11PythonRRebolRubySmalltalkTcl/Tk

LISPは、長い歴史を持ち、特徴的で完全に括弧で囲われたポーランド記法[1] によるプログラミング言語である。 1958年にはじめて設計され、LISPは今日、広範囲に使用される高水準プログラミング言語の中でFORTRANに次いで2番目に古い[2]ものであるが、FORTRAN同様LISPは初期から非常に大きな変化を続けている。 これまでに多数の方言が存在してきたが、今日最も広く知られるLISP方言は、Common LispSchemeである。

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

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

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

LISPの歴史[編集]

ジョン・マッカーシー(上)、スティーブ・ラッセル(下)

LISPは1958年にジョン・マッカーシーMITにいた期間に考案された。マッカーシーは1960年にACMの学会誌Communications of the ACMに "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"[4] という題名の論文(「パートII」が発表されることはなかった)を発表した。この論文において(それを言語とみなし純LISPとも言われるが)少数の単純な演算子と関数の表記法で、自分自身を評価するeval関数(超循環評価器、w:Meta-circular evaluator)を記述できることが示された。

1955年または1956年からはじまった、IPLは、最初の人工知能言語で、リスト処理や再帰などの多くの概念をすでに含んでいたが、その後すぐにそういった分野ではLISPが使われるようになった。

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

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

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

その発端からLISPは、人工知能研究のコミュニティ、特にPDP-10システムのユーザーには近しい存在であった。AIコミュニティでは、LISPはプログラミング言語の実装用言語としても用いられた。有名なAIシステムSHRDLUの実装言語のMicro Plannerは、MACLISPで実装されている。

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

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

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

一方で1970年代中ごろには、LISPベースでプログラミングに必要な言語機能を極限まで抽象化したSchemeが発生し、こちらも現在の主流の一つになっている。

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

文法[編集]

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

マッカーシーの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とも書ける。

評価[編集]

現実の実装では、上記のリストを直接処理系に入力するとエラーが起きる。

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に評価される。この式は中置記法では"1+2+3+4"と等価である。

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

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

純LISP[編集]

以下の5つの関数と特殊形式、他にシンボルのnilとt、などがあれば自分自身を解釈実行できる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)))

loopマクロはCommon Lisp標準の文法であり、手続き的なループを表現するための文法としてCommon Lisp以前のLISP方言から導入された。loopはマクロなので、コンパイル時に式変形され、これが分解されて「普通の」lispに翻訳されるものと考えてよい。

一方、このloopマクロには欠点もあった。 loopは「ANSI標準」として取り入れられているため 拡張することが許されていない点である。 ここに、ライブラリiterateが誕生した。 通常の言語では、ライブラリとは 手続き、関数、クラス定義などをまとめたものを指すが、 lispでは「新たな文法を与えてくれるライブラリ」というものが 普通のライブラリと同様に存在する。

(defun factorial (n)
  (iter (for i from 1 to n)
        (for fac initially 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は多重継承多重ディスパッチ(マルチメソッド)の機能を持ち、 強力なメソッド結合(method combination)のシステム(FIXME)を持つ。 CLOSを含めたCommon Lispは、 公式に標準化された最初のオブジェクト指向言語である。

系統と変種[編集]

  • AutoLISP/Visual LISP - AutoCAD製品のカスタマイズ用の言語。
  • Cambridge LISP - 当初、IBMメインフレーム上で実装され、メタコムコによってAmiga用として発表された。
  • Clojure - マルチスレッドプログラムの開発を容易化する汎用言語。
  • Common Lisp - 主にZetaLISPとFranzの子孫であり、InterLISPの機能も導入された。
  • Coral LISP - Macintosh用のLISP実装。
  • ELisp -古いLISP実装のひとつ。 Emacs Lispとは別。
  • Emacs Lisp - GNU Emacsエディターの拡張言語。
  • Franz LISP - 元はバークレイのプロジェクトである。後にFranz, Incに移行。
  • Gold Hill Common LISP - パーソナルコンピュータ用のLISPの初期の実装。
  • InterLisp - MITで開発され、後にゼロックスLISPマシンのための「東海岸LISP」として採用された。より小さいバージョンである「InterLISP 65」はAtari6502ベースのコンピュータ用に発表された。
  • LISP 1, LISP 1.5 - MITで開発されたマッカーシーのオリジナル版。
  • Lispkit LISP - 純粋な関数型言語としての方言であり、SECDマシン上に実装された。関数型言語のコンセプトの実験用テストベッドとして使用された。
  • Macintosh Common Lisp - デジツールによるMacintosh用のCommonLISP環境でMacintoshのToolboxにアクセスする機能を持つ。
  • MACLisp - MITのプロジェクトMACアップルMacintoshとは無関係)のために開発されたLISPの直系子孫。
  • MockLisp - Gosling Emacs (Unipress Emacs) エディターの拡張言語。リストのないLISP。
  • Oak LISP - Schemeベースのオブジェクト指向言語。
  • Scheme - ダイナミックスコープではなくレキシカルスコープにもとづき最設計されたLisp。
  • SKILL - ケイデンス・デザイン・システムズ社製の多くのEDA製品で使われる。
  • ZetaLisp - LISPマシンのために使われた、MACLISPの直系子孫。
  • 純LISP - 超循環評価機を記述可能な程度で、ごく小さいサブセットに機能を絞った方言。元々は「最初の論文」と呼ばれている論文中で理論的なものとして示されたが、実際に実装可能である。
  • xyzzy - Microsoft Windowsで動くエディタ。マクロ言語としてxyzzy Lispを実装している。

脚注・出典[編集]

  1. ^ Edwin D. Reilly (2003). Milestones in computer science and information technology. Greenwood Publishing Group. pp. 156–157. ISBN 978-1-57356-521-9. http://books.google.com/books?id=JTYPKxug49IC&pg=PA157. 
  2. ^ SICP: 序文”. 2015年10月20日閲覧。 “Lispはほぼ四半世紀の間使われた長命者である. 現役のプログラム言語ではFortranだけが先輩である.”
  3. ^ Paul Graham. “技術野郎の復讐”. 2015年10月20日閲覧。
  4. ^ John McCarthy. “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. 2015年10月30日閲覧。

関連項目[編集]

外部リンク[編集]