LISP ── 関数型と AI の祖

LISP（Lisp） は、数値ではなく記号の式 ── 記号を入れ子にしたリスト ── を計算の対象にするプログラミング言語である。名は LISt Processor（リスト処理系）の略。John McCarthy が1958年秋に MIT で実装を始め、1960年4月の Communications of the ACM に論文「Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I」として設計を発表した。McCarthy 自身は1979年の文章で、LISP を FORTRAN に次いで2番目に古い、いまも広く使われているプログラミング言語だと書いている。

構想はコードより古い。McCarthy の『History of Lisp』は経緯を2つの時期に分ける。主要な着想のほとんどが生まれた1956年夏から1958年夏までと、言語が実装されて人工知能の問題に使われた1958年秋から1962年までである。

1956〜58年 ── AI のためのリスト言語を求めて

McCarthy の回想によれば、IBM 704 で人工知能の研究をするための「代数的なリスト処理言語」が欲しいと考えたのは、1956年夏の ダートマス会議 のときだった。そこで Allen Newell・Cliff Shaw・Herbert Simon が、Logic Theorist を書いたリスト言語 IPL 2 を紹介した。McCarthy はそれを真似る気にならなかった。IPL の形は JOHNNIAC という特定の計算機に縛られていたし、プログラムを代数式のように書く FORTRAN の発想のほうが魅力的だったからである。

MIT に移る前の3つの段階が、LISP の形を決めた。

FLPL には条件式も再帰も無く、IBM のグループはそれらを入れるための大きな変更を望まなかった。McCarthy は、FORTRAN をいじるのは技術的にも政治的にもきわめて難しかったと書いている。新しい言語が必要だった。

1958年秋 ── MIT の AI プロジェクト

1958年秋、McCarthy は MIT の助教授となり、Marvin Minsky とともに MIT 人工知能プロジェクトを始めた。提案書は一度も書かれていない。何が要るかと聞かれた2人が求めたのは、部屋1つ、プログラマー2人、秘書1人、キーパンチ1台だった。

実装はその秋に始まった。最初はコンパイラを作るつもりだったが大仕事だったため、関数を手でアセンブリ言語に変換するところから始めた。いまも残る2つの名前は、このときのハードウェアから来ている。IBM 704 のワードには「アドレス部」と「減分部」があり、それぞれを取り出す操作が car（Contents of the Address part of Register number）と cdr（Contents of the Decrement part of Register number）と名付けられた。

1960年の論文は目的をはっきり書いている。LISP は、提案中の Advice Taker ── 命令文だけでなく宣言文でも指示でき、それを実行するときに「常識」を示せる機械 ── の実験を支えるために設計された。論文はその提案を1958年11月としている。

eval と Steve Russell、そして括弧

McCarthy は、LISP がチューリング機械よりもすっきりと計算可能な関数を記述できることを示したかった。その証明が、LISP の式を受け取ってその値を計算する万能関数 eval である。eval を書くには LISP のプログラムを LISP のデータとして表す必要があり、そのために括弧のリスト ── S 式 ── の記法が考案された。McCarthy によれば、それを実際のプログラムを書くのに使うことはまったく想定していなかった。

人間が書くのは、角括弧を使う FORTRAN 風の M 式 のはずだった。ところが Steve Russell が、eval はそのまま LISP のインタプリタになると気づき、すぐに手でコードに起こした。こうしてプロジェクトは、インタプリタ付きの動く言語を手にした。

McCarthy は結果について率直である。思いがけず現れたインタプリタは言語の形を凍らせる方向に働き、論文のために軽い気持ちで決めた事柄 ── COND の記法や、空リスト NIL と偽の両方をゼロで表すこと ── まで固定された。M 式をきちんと定義する計画は、完成もしなければ明示的に捨てられもせず、ただ無期限の先へ遠のいていった。括弧が残った。

別の名前で書かれたガベージコレクション

1960年の論文は、使われなくなったリストのセルが自動で自由記憶リストに戻る仕組みを説明している。自由記憶が尽きると、基底レジスタから到達できるものすべてに印を付け、残りを回収する。論文はこれを reclamation（回収）のサイクルと呼ぶ。McCarthy がオンライン版に加えた注記によれば、当時すでに「garbage collection」と呼んでいたが、論文で使うのはためらったという。用語集の ガベージコレクション も参照。

その名はすぐに人目に触れた。『History of Lisp』は、MIT の産業界向けシンポジウムで行った最初のオンライン実演の最中に、Flexowriter が毎秒10文字の速さでガベージコレクタの統計を1ページ分打ち出し始め、持ち時間を食い尽くした出来事を回想している。

LISP I から LISP 1.5 へ

Software Preservation Group は、Phyllis Fox による LISP I Programmer's Manual を1960年3月1日付としている。McCarthy・Paul Abrahams・Daniel Edwards・Timothy Hart・Michael Levin による LISP 1.5 Programmer's Manual は1962年8月に MIT Press から出た。McCarthy によれば、その刊行後に多くの計算機で LISP が実装された。

その間に、属性リスト、アトムとして格納する数値、今日でいうレキシカルスコープのための Russell の FUNARG 機構、そして Hart と Levin による最初の実用的な LISP コンパイラが加わった。このコンパイラは LISP で書かれ、そのメモは、インタプリタで実行されて自分自身をコンパイルした最初のコンパイラだと述べている ── メモ自身の主張である。数値計算は遅いままで、McCarthy は初期の LISP の算術を FORTRAN の10〜100倍遅かったとしている。

その後

McCarthy は、LISP を広めようとした組織は一つも無かったと書いている。それでも広まった。彼の見立てでは最も重要な実装は DEC の PDP-6 と PDP-10 向けで、これらの機械のハーフワード命令とスタック命令は LISP の要求を念頭に置いて作られた。MACLISP と INTERLISP はそこで育った。後の方言には Scheme（1975年）、1994年に ANSI 規格となった Common Lisp、Java 仮想マシン上の Clojure がある。関数を値として扱う考え方は、関数型プログラミング 全般に通じている。

LISP が生き延びた理由について、McCarthy 自身の説明は風変わりである。プログラムがリストであること ── 自分を含めて誰もが欠点だと見なしてきた性質 ── こそが、生き残りの理由かもしれない、と。

同時代の言語の中での位置は プログラミング言語の年表 に、生みの親については John McCarthy にある。