プログラミング言語における再帰の初出はLISPではなかった
ポール・グレハムの記事の一つにWhat Makes Lisp Different?というものがある：
ポール・グレハムらしくよく書かれていて、C言語などと比較した場合のLispの特徴をうまく捉えているように思う。
その中の一つが
こうある通り、私も今まで深く考えたこともなく「プログラミングにおける再帰はLispが由来」と考えていたのだが、前回の記事を書くときに「そういえば再帰って本当にLispが初出？」と疑問に思ったので調べてみた。
結論から言うと違った。関数（というかコンピュータ上のサブルーチン）の再帰的定義とそれを可能とする関数スタックを持つ言語はLISPの先にあり、そしてMcCarthyはLISPを作るにあたってその言語に明確に影響を受けている。
その言語はIPL（Information Processing Language）である。
IPL
1950年代のAI研究の一環として、RAND CorpでLogic Theory Machineという定理証明系が実験的に開発されていた。そのLogic Theory Machineを実装するための言語として作られたIPLは、扱うデータ構造として数値ではなくシンボルと任意のネストが可能なリスト構造を持っていた。そして数学的な定理を形式仕様として記述できるようにするため、再帰的な定義ができるということが非常に重視されていたようだ。Programming the logic theory machineという論文で解説されている。（Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iの５つしかない参考文献の１つ）。
McCarthyのHistory of LISPも話はIPLから始まる。
My desire for an algebraic list processing language for artificial intelligence work on the IBM 704 computer arose in the summer of 1956 during the Dartmouth Summer Research Project on Artificial Intelligence which was the first organized study of AI. During this meeting, Newell, Shaw and Simon described IPL 2, a list processing language for Rand Corporation’s JOHNNIAC computer in which they implemented their Logic Theorist program.
ただしこのMcCarthyの論文ではIPLの機能についてはあまり触れられておらず、上記の文の続きは：
There was little temptation to copy IPL, because its form was based on a JOHNNIAC loader that happened to be available to them, and because the FORTRAN idea of writing programs algebraically was attractive.
となっている。
実際IPLのWikipediaページでも
IPL is an assembly language for manipulating lists
と書かれており、コードサンプルをみるかぎりその通りだと思う。
しかし、それにしても「リスト処理」だけではなく「再帰」「スタック」の概念がIPLからきているというのはかなり重要なポイントだと思われる。
Brief History of the Stackという論文からの孫引きになってしまうが、KnuthのThe Art of Computer Programmingに：
The programming of stacks in linked form appeared first in IPL, as stated above; the name ”stack” stems from IPL terminology (although ”pushdown list” was the more official IPL wording) and it was also independently introduced in Europe by E.W. Dijkstra.
と書いてあるとのこと。ただしサブルーチンの戻り先をスタックとして保持するというアイデアはA.M. Turingのグループが1947年に発表していたらしい。
余談だが数あるLISP関連の名著のうちの一つParadigms of Artificial Intelligence Programmingで紹介されているGeneral Problem Solverは元々IPL開発者たちによってIPLで書かれたAIプログラムである。
さてIPLはシンボリックなリスト処理に特化していて再帰や関数スタックを備えていた言語ではあったのだが、特定マシンのアセンブリに近い構文、ガベージコレクションの欠如、そして実験的実装ということでのプログラム実行効率の悪さなどの問題も多かった。
特定処理以外では「FORTRANの方が高級言語」というレベルだったようだ。McCarthyはIBM社へのコンサルタント業の一環として、FORTRANにリスト処理機能を追加した言語の実装を提言する。
FLPL
その結果IBM社内で実装されたのがFORTRAN-Compiled List Processing Language(FLPL)である。1960年に（McCarthyのLISP論文が出たのと同年）IBMからスバリそのものな論文A Fortran-Compiled List-Processing Language が出ている。
Faced with this program, Newell, Shaw, and Simon, in programming a heuristic theorem-proving system for the propositional calculus, simulated (by programming) a kind of associative memory (henceforth referred to as an NSS memory) in which lists of arbitrary length and organization could be generated by annexing registers from a common store [5].
（Newell, Shaw, SimonというのはIPLの開発者たちである）
When the present authors embarked upon their effort to simulate a geometry theorem-proving machine, it was early decided that an NSS organization of memory would best serve their purpose, and consideration was given to the translation of a Johnniac IPL for use with the IBM 704 computer. However, J. McCarthy, who was then consulting for the project, sugested that FORTRAN could be adapted to serve the same purpose. He pointed out that the nesting of functions that is allowed within the FORTRAN format makes possible the construction of elaborate information-processing subroutines with a single statement.
リスト処理機能が使えるアセンブリ言語であるIPLよりも、ネストした関数などをサポートする高級言語であるFORTRANにリスト処理を追加したほうが便利だ、とMcCarthyが提言したとある。
FLPLで個人的に特に面白かったのはこの箇所：
The following are examples of this class : XCDRF(J), XCARF(J), XCPRF(J), XCSPF(J), XCTRF(J)
Extract contents of the (decrement, address, prefix, signed prefix, tag) register of the word stored in location J.
よく見ると、最初の二つはCDRとCARだ。ちなみにCONSはそのままでは存在せず、XDWORDFとXLWORDFという関数を組み合わせて新しいCONSセルをリストの先頭に追加するようになっていたようだ。
LISPの語源がLISt Processingの略であることは有名な話だが、LISPが作られる直前に、LISP開発者のMcCarthyの提言でIBMが「List Processing」を名前に含み、CARとCDRを持つFORTRAN拡張を作っていた、というのは面白い。
ではなぜMcCarthyはFLPLを使わずLISPを作ったのか？
While expressions could be handled easily in FLPL, and it was used successfully for the Geometry program, it had neither conditional expressions nor recursion, and erasing list structure was handled explicitly by the program.
そして
At this point a new language was necessary, since it was very difficult both technically and politically to tinker with Fortran, and neither conditional expressions nor recursion could be implemented with machine language Fortran functions - not even with “functions” that modify the code that calls them. Moreover, the IBM group seemed satisfied with FLPL as it was and did not want to make the vaguely stated but obviously drastic changes required to allow conditional expressions and recursive definition. As I recall, they argued that these were unnecessary.
とある。（Conditional expressionはMcCarthyはFORTRANで関数として実装したことはあったらしいが、引数が関数に渡される前に評価されてしまうので嬉しくなかったらしい）
そういうわけで1958年にMcCarthyはMITでAI研究を始めるにあたって、それに最適な再帰や条件分岐式を持ち、リスト処理に長けた高級言語を開発する。FORTRANに似せた構文であるM式で記述された、S式で表されるシンボルとデータを扱うためのLISt Processing言語LISPである。その後M式は打ち捨てられ、S式でコードもデータも統一的に記述する形に洗練されたのはよく知られているとおり。
メインストリームへの影響
C言語などのメインストリームな言語で再帰や三項演算子があるのはALGOLで採用されたからだと思うが、ALGOLに両者を加えるべきだと最初にいったのはMcCarthyのようだ（再帰が最終的にALGOLに加えられたのはDijkstra、Wijngaarden、Naurが最後の最後にAmsterdam Plotで他の委員会メンバーに気付かれずにLanguage Reportに入れたからだが）
なのでIPL -> FLPL -> LISP -> ALGOL -> ... -> Cという流れで再帰と条件分岐式がメインストリーム言語につながっていったわけだ。
数学における再帰的定義の歴史
余談ではあるがRobert SoareのComputability and Recursionによると数学的帰納法を利用した再帰的な定義は19世紀以前から使われており、それが厳密な定義であると証明したのはデデキント（1888年）、そしてその上でペアノがペアノ数に関する定義を1889~1891の間に書き上げた、とのこと。
1930年代にゲーデル、チャーチ、クリーネ、チューリングらがPrimitive RecursiveやGeneral Recursiveといった関数の集まりと計算可能性の関連を研究していき、その結果RecursionとComputabilityが数学的論理学の用語として混同（というと強すぎるかもしれないが）され出した、という経緯があるらしい。
