LISP
meta-circular evaluator は、ある意味で、チューリングマシンにおける万能チューリングマシンに相当する。(当初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で実装されている。
ここでは Lisp の方言の一つである Common Lisp を例に説明する。現実の実装では、上記のリストを直接処理系に入力するとエラーが起きる。
これは、上の(1 2 "foo")は正しい式ではないからである。処理系の中で上のリストを表現したい場合は、クオート「'」を用いて'(1 2 "foo")と書く必要がある。このことを解説するため、ここでLISPでの評価ルールについて述べる。
すべての式は前置記法のリストとして書かれる。リストの最初の要素はフォーム(関数、演算子、マクロ、特殊フォームのいずれか)の名前である。リストの残りは引数である。たとえば、関数listはその引数をリストとして返す。つまり式
は評価されてリスト'(1 2 "foo")を返す。このことを念頭に置いて、もう一度最初に挙げた式を振り返ると、
という仕組みでによりエラーが返されたことがわかるだろう。
もし引数のどれかが式であれば、それを含む式が評価される前にそれが再帰的に評価される。たとえば、
はリスト(1 2 (3 4))に評価される。つまり、3番目の引数はリストであり、リストはネストできるのである。
LISP(リスプ)は、プログラミング言語である。前置記法などが特徴である。
1958年にはじめて設計されたLISPは、現在広範囲に使用されている高水準プログラミング言語の中でもFORTRANに次いで2番目に古い。ただし、FORTRANと同様に、現在のLISPは初期のものから非常に大きく変化している。
これまでに多数の方言が存在してきたが、今日最も広く知られるLISP方言は、Common LispとSchemeである。
元々、LISPは、アロンゾ・チャーチのラムダ計算表記法に影響を受け、コンピュータプログラムのための実用的かつ数学的な表記法として作られた。そして、すぐに人工知能研究に好まれるプログラミング言語になった。最初期のプログラミング言語として、LISPは計算機科学にて、木構造、ガベージコレクション、動的型付け、条件分岐、高階関数、再帰、セルフホスティング、コンパイラを含む多くのアイディアを切り開いた。
LISPの名前は、「list processor」に由来している。リストはLISPの主要なデータ構造であり、LISPソースコードはそれ自体がリストからできている。その結果、LISPプログラムはソースコードをデータとして操作することができ、プログラマは、マクロ・システムで新しい構文やLISP埋め込みの新しいDSLを作成できる。
コードとデータの互換性は、LISPにそのすぐに認識できる構文を与える。すべてのプログラム・コードはS式または入れ子のリストとして書かれる。関数呼び出しまたは構文は先頭が関数または演算子の名前で、その続きが引数であるリストとして書かれる。具体的には、3つの引数を取る関数fは、(f arg1 arg2 arg3)として呼び出される。