LISP
LISPの歴史
LISPは1958年にジョン・マッカーシーがMITにいた期間に考案された。マッカーシーは1960年にACMの学会誌Communications of the ACMに「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」という題名の論文（「パートII」が発表されることはなかった）を発表した。この論文において、M-expression（Meta expression）と呼ばれる少数の単純な演算子と関数の表記法で、自分自身を評価するeval関数（超循環評価器）を記述できることが示された。
1955年または1956年からはじまった、IPLは、最初の人工知能言語で、リスト処理や再帰などの多くの概念をすでに含んでいたが、その後すぐにそういった分野ではLISPが使われるようになった。
前述の超循環評価器はLISP自身で実装されているが、ひとたびLISP以外の言語で実装すればそれは実際にLISPを解釈実行できるインタプリタとなる。マッカーシーは自分の論文中にある評価器は単なる理論上の存在で、そのようにしてインタプリタを実装可能であると考えていなかった。しかし、マッカーシーのもとで大学院生であったスティーブ・ラッセルは論文を読んだ後、機械語でそれを実装してみせ、マッカーシーを驚かせた。そうしてLISPインタプリタが生まれた。
超循環評価器は、チューリングマシンにおける万能チューリングマシンに相当する。（当初LISPプログラムの表現法としていた）M式を、LISP自身が扱うデータ構造に変換したS式は、万能チューリングマシンの入力（テープの初期状態）として与えられるチューリングマシンの記述に相当する。マッカーシーはやはり、LISPプログラムのS式による表現はevalを考えるための論文の中だけのものと考えており、実際のプログラムをS式で書くようになるとは考えていなかった。
LISPは当初IBM 704上で実装されたが、その計算機のレジスタを構成する部分の名前が、対を分解する関数car、cdrの名前の由来となった。爾来、ほとんどのLISPの方言において、carとcdrはそれぞれlistの最初の要素と、最初の要素以外を返す関数の名前となっている。
その発端からLISPは、人工知能研究のコミュニティ、特にPDP-10システムのユーザーには近しい存在であった。PDPの計算機の設計目標の一つにLispの実装があり、PDP-6は当初、1ワード24bitの計算機として設計されていたが、Lisp1.5を移植しやすくするために36bitに変更された。人工知能コミュニティでは、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に評価される。この式は中置記法では「」と等価である。
特殊形式（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のコード例を示す。これらは産業界における典型的なコードではないが、コンピュータサイエンスのコースで通常教えられる典型的な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はマクロであり、これが展開されて最終的にはプリミティブな構文の組み合わせに翻訳される。
以下の関数は引数にリストをとり、そのリストの要素の順番を逆にしたものに評価される（LISPは実際には同じことを行うビルトイン関数を普通持っている）。
(defun reverse (l &optional acc)
  (if (atom l)
    acc
    (reverse (cdr l) (cons (car l) acc))))