Arantium Maestum

プログラミング、囲碁、読書の話題

論文メモ：Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

論文メモ Lisp

John McCarthyの1960年に発表された論文Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iのメモ。

背景

「Artificial Intelligence」という用語の名付け親であるMcCarthyが、自身が助手らと作ったLISP言語を世に出した論文である。ちなみにPart IIは存在しない。

1960年ということはFORTRANやALGOL58はすでに出ているが、CやPASCALの登場の10年以上前（Cは1972、PASCALは1970）。COBOLの言語仕様が決定されたのも1960年だ。

LISPは開発が始まったのは1958年でギリギリCOBOLより先に実装されているので、FORTRANに次いで二番目に古い現存のプログラミング言語だと呼ばれている。FORTRAN、LISP、COBOLすべて時代とともにかなり変わってきているので、正直「今でも使われている」と言っていいのか微妙な気もするが・・・

概要

一言で言うならば、数値（のみ）ではなくシンボル（およびシンボルを組み合わせたデータ構造）を数学的な再帰関数を表す式で操作する、というプログラミングの方法を提唱した画期的な論文である。

COND式と再帰によるチューリング完全な計算、λ記法による無名関数式、言語の関数が関数の操作対象であるS式で表現できると言う自己言及性、LISP自身で書かれたLISPのmetacircular evaluator、高階関数、ガベージコレクションなど後のLISP方言や関数型プログラミング言語の重要な概念が詰まっている。

またLISPの特徴であるS式はもちろん登場するのだが、プログラミング記述言語としては（実際にはすぐに消えた）M式という記法が使われている。

各セクションの見出しは以下のとおり：

  1. Introduction
  2. Functions and Function Definitions
  3. Recursive Functions of Symbolic Expressions
  4. The LISP Programming System
  5. Another Formalism for Functions of Symbolic Expressions
  6. Flowcharts and Recursion
  7. Acknowledgments

このうち３、４、５が論文の根本部分。

詳細

各セクションを個別に見ていく。（ただしIntroductionとAcknowledgementsは割愛）

2. Functions and Function Definitions

そもそもどのような関数を実行できるシステム・言語を作りたいのか？という話がされている。

サブセクションは：

  1. Partial Functions
  2. Propositional Expressions and Predicates
  3. Conditional Expressions
  4. Recursive Function Definitions
  5. Functions and Forms
  6. Expressions for Recursive Functions

aとbは比較的簡単なことしか書いていないので省略。

cのConditional ExpressionsはLISPの新規性とのこと。（ちなみにセクション２はLISP言語そのものの定義ではなく、LISPで表現したい数学的な関数の定義である）

(p1 →e1,···,pn →en)のような形の式で、→の左側pnが条件式、その条件式が評価されて真なら→の右側enが評価されて式全体の結果となる。条件式が偽なら次の条件・結果ペアに移る。結果が真な条件式がない場合は式の結果が未定義。

今なら関数型言語で完全にお馴染みだが、この時点では新しかったらしい。その頃のFORTRANを見てみると、条件式の結果によって制御が特定のラベルの飛ぶGOTO的なIF文であって、評価されて全体として結果を返すIF式ではなかったようだ。

dのRecursive Function Definitionsでは、そのIF式（というかその拡張であるCOND式）を使うと再帰的な関数定義というのが一つの式で書ける、という話。

eのFunctions and Formsで任意の数式を「引数を適用できる関数」に変換するための記法としてChurchのλ記法が導入される。

最後にfで「λ記法だと再帰的な関数が表現できない」という話が出てくる。そのため、label(a, E )という記法で「Eという式全体をaという名前に束縛、ただしEの中でaという名前が出てくる場合は再帰」という式を表すようにしてある。Yコンビネータの話はまったく出てこないのが（現代からすると）意外。

ちなみにMcCarthyの書いたHistory of Lispでは後ほどDavid ParkがYコンビネータ的な理屈でlabelはいらないという指摘をしたらしい：

D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church’s Y-operator, albeit in a more complicated way.

3. Recursive Functions of Symbolic Expressions

このセクションで前述の数学的な関数を表現するための言語を定義していく。この論文の心臓部分。

サブセクションは以下のとおり：

  1. A Class of Symbolic Expressions
  2. Functions of S-expressions and the Expressions That Represent Them
  3. The Elementary S-functions and Predicates
  4. Recursive S-functions
  5. Representation of S-Functions by S-Expressions
  6. The Universal S-Function apply
  7. Functions with Functions as Arguments

aのA Class of Symbolic ExpressionsでS式を定義。CONSセルのネストによってリストを表現する、などのLISPERや関数型言語界隈ではお馴染みの話。

bのFunctions of S-expressions and the Expressions That Represent ThemでS式からS式への関数について解説し、それらを表現するためのメタ表現であるM式を定義。M式はcar[cons[(A · B); x]]のように表記される。

cのThe Elementary S-functions and PredicatesではS式に対する原始的な関数５つ、atom、eq、car、cdr、consを定義している。Elementaryというのはこの場合「Atomic」と同義だと思うが、すでにatomという単語を「S式の最小要素」を指すのに使っているので別の単語を使っているのだろうか。

dのRecursive S-functionsでは上記の５関数を条件分岐と再帰とで組み合わせることで定義できる関数の例を見ていく。理論的にはこれでチューリング完全になって計算可能なすべての関数が表現できる。

eのRepresentation of S-Functions by S-Expressionsでは、M式で表現されていた「S式からS式への関数」がS式で表現できる、ということを見ていく。

fのThe Universal S-Function applyでは「S式で表現された関数と引数となるS式を評価する関数」であるapplyとeval、そしてそのヘルパ関数がM式で定義されている。ここがこの論文の最も有名な箇所だろう。16ページの後半から17ページの終わりにかけてLISPのmetacircular evaluator（つまりその言語自身で書かれたインタプリタ）が定義されている。

最後のgのFunctions with Functions as Argumentsではいわゆる高階関数の話がされている。maplistやsearchなど「関数を引数にとる関数」の話だ。ちなみにTurnerのSome History of Functional Programming Languagesでは

The M-language of McCarthy (1960) is first order, as there is no provision to pass a function as argument or return a function as result.

There has been much confusion about this because McCarthy (1960) uses λ- abstraction — but in a completely different context from (Church 1941).

と書いてあるが、この「g. Functions with Functions as Arguments」の部分で：

One such function is maplist[x;f] with an S- expression argument x and an argument f that is a function from S-expressions to S-expressions. We define

maplist[x; f] = [null[x] → NIL; T → cons[f[x]; maplist[cdr[x]; f]]]

と書いてあるのでTurnerの誤解ではないだろうか？元々はM式で定義されるのはS式からS式への関数だとあるので、引数にM式の関数が取れるというのは唐突な話ではあるし、、M式自体は言語として実装されることもなくinformalな記法として使われるに留まったようなので、well-definedではないと言えばそのとおりだとは思うが・・・

4. The LISP Programming System

LISPをどうやってコンピュータ（IBM704）で実装するか。

サブセクションは：

  1. Representation of S-Expressions by List Structure.
  2. Association Lists
  3. Free-Storage List
  4. Elementary S-Functions in the Computer
  5. Representation of S-Functions by Programs
  6. Status of the LISP Programming System (February 1960)

S式は連結リストで表現できるよ、ついでにLISPでは連想リストでシンボルと他の何かを対応させるのを多用するよ、とまあ自明な話をした上で、cのFree-Storage Listではメモリのアロケーションとガベージコレクション（マーク＆スイープ）について解説している。

dのElementary S-Functions in the Computerはatom、eq、car、cdr、consの実装面ではあらかた自明だと思われるが、

“car” is a mnemonic for “contents of the address part of register.” “cdr” stands for “contents of the decrement part of register.”

というのが（LISPERの間では常識だと思うが）面白ポイント。

eのRepresentation of S-Functions by Programsについては、上記５つを組み合わせた関数の実装について。基本的に難しいのは再帰関数の部分で、これまではあまり一般的ではなかったPush-down List（Stackのこと）を使うことで「関数を表現するサブルーチンが使うレジスタの内容を安全に退避させる」という機能を実現している。

fのStatus of the LISP Programming System (February 1960)によると、論文がでた1960年の時点ですでにAPPLYはIBM 704上で実装されており、S式の評価、特定のS式で定義された関数の機械語へのコンパイル（60倍ほどの計算速度向上が見られたとのこと）、遅いながらも浮動小数点数の演算などが可能となっていたらしい。

（ちなみにIBM704はSystem 360以前なので1 byte = 6 bit、1 word = 36 bitなマシン）

5. Another Formalism for Functions of Symbolic Expressions

S式に似たL式という表現を紹介している。S式のようなネストしたリストではなく、ATOMが１文字な直線的な表現（なのでLinear Expressionの略でL式）。

S式におけるATOM、EQ、CAR、CDR、CONSなどに対応する形の関数が文字・文字列を対象として定義でき、そしてS式のそれらがL式の言語で実装できるのでS式言語はL式言語に含まれる、という主張らしい。詳しい解説がないのでちゃんと理解できているかは怪しいが、つまりL式言語の入力として「S式の文字列表現」は受け入れられるし、その上でS式言語のインタプリタをL式言語で実装できる、という話だと個人的には認識している。

この話は何が嬉しいのかはわからない・・・。

6. Flowcharts and Recursion

これまでは条件分岐や再帰を含んだ数学的な関数をどうやってコンピュータプログラムとして実行するかという話だったが、このセクションでは（非常に簡単に）任意のコンピュータプログラムをこのような数学的関数で表現できるのかという問題を見ていく。

理論的には全部チューリング完全なのだから対応しているはずだが、実際にはどう対応させるのか？というのがポイント。

コンピュータプログラムをフローチャートとして表現して、そのフローチャートが再帰関数の集まりで表現できるということを確認していく。

余談

論文の本文ではほぼ言及がないが、LISPはIPLという先行言語に影響を受けており、参考文献に「A. NEWELL AND J. C. SHAW, Programming the logic theory machine」という論文が載っているがこれがIPL言語の解説である。このIPLとFLPLというLISP前夜ともいうべき二つの言語については別途記事を書きたい。