記号式の再帰関数
およびその機械による計算 第I部
John McCarthy, Massachusetts Institute of Technology, Cambridge, Mass. ∗
1960年4月
1 序論
LISP（LISt Processor）と呼ばれるプログラミングシステムが、M.I.T.の人工知能グループによってIBM 704コンピューター用に開発された。このシステムは、Advice Takerと呼ばれる構想中のシステムに関する実験を容易にするために設計されたものである。Advice Takerでは、機械に宣言文だけでなく命令文も扱うよう指示でき、命令を実行する際に「常識」を発揮させることができる。Advice Takerの最初の提案 [1] は1958年11月になされた。主な要件は、形式化された宣言文および命令文を表す式を操作するためのプログラミングシステムであり、それによってAdvice Takerシステムが推論を行えるようにすることであった。
開発の過程で、LISPシステムはいくつかの簡略化の段階を経て、最終的には、あるクラスの記号式の部分再帰関数を表現するための方式に基づくものとなった。この表現はIBM 704コンピューターにも、その他のいかなる電子計算機にも依存しないものであり、現在では、S式と呼ばれる式のクラスおよびS関数と呼ばれる関数から始めてこのシステムを説明するのが適切であると思われる。
∗ Putting this paper in L A supported by ARPA (ONR) grant N00014-94-1-0775
TEXpartly 1962年以来John McCarthyが在籍しているStanford Universityへ。この論文は、若干の記法上の変更を加えてCACM, April 1960から複写したものである。正確な組版を確認したい場合は、そちらを参照されたい。