「入門Common Lisp」を読みました。 机の上にはRubyの本が置いてあるのですが、思ったより難しいので、現実逃避でLispの本に手を出してしまいました。

全般的にゆるい(*)本ですが、「8章 λ計算」だけが突然難しくなります。読者の想定レベルが不明な、某教科書みたいです。

(*)別にけなしているわけではありません。

Church符号化は目新しくありませんが、Lispのコードを示してくれるところは親切です。以下、全て(Common Lispではない)Emacs Lispでの動作例です。

(lambda (s x) x)  ;0
(lambda (s x) (funcall s x))  ;1
(lambda (s x) (funcall s (funcall s x)))  ;2
(lambda (s x) (funcall s (funcall s (funcall s x))))  ;3
...

こんな感じです。 名前をつけると次のようになります。

(defun zero (s x) x)
(defun one (s x) (funcall s x))
(defun two (s x) (funcall s (funcall s x)))
(defun three (s x) (funcall s (funcall s (funcall s x))))
(defun four (s x) (funcall s (funcall s (funcall s (funcall s x)))))
(defun five (s x) (funcall s (funcall s (funcall s (funcall s (funcall s x))))))
...

これらは2引数の関数です。このように定義した関数は自然数(*)のように見なせます。自然数のように見なせるの意味は、自然数と1対1に対応するように関数を定義できて、自然数のような演算を定義できる、という意味です。演算の代わりに、関数と言っても構いません。2項演算であれば、引数が2つの関数です。

(*) 0を含めます。

言うまでも無いですが、zeroやoneと名づけていることに本質的な意味はありません。reiやichiと名づけても体系に変化が無いことは、数を零や一と呼んでも、自然数の説明が可能であることから分かると思います。

関数定義と自然数を同一視するのに心理的抵抗がある、と思うかもしれません。しかし、自然数と同じ体系に従ってしまうなら、それらの関数定義を自然数のように見なしても別に不都合はありません。99という数値を「キュージューキュー」と呼ぼうが「ninety nine」と呼ぼうが、しょせん、ある規則の下での記号化です。同様に、上記の関数定義もしょせんある規則(λ計算)の下での記号化です。そして99+1の計算が、ある規則の下でできるように、上の関数同士の計算規則も作れてしまいます。

上の関数定義の意味を分かりやすくする、次のような解釈があります。

(zero '1+ 0)
0
(one '1+ 0)
1
(two '1+ 0)
2

引数sに関数1+、引数xに数値0を渡して呼び出すと、いわゆる普通の自然数が返ってくるという解釈です。これだけ見て、なるほど引数sは関数、引数xは数値、と思うのは早とちりです。数値0も常に値0を返す関数と見なしてください。引数sもxも、関数を渡すと見なします。更に言えば、関数から返るのも関数です。この世界では、関数しか無いと思う方が幸せになれます。

まあ、解釈は解釈として否定する必要もありません。初期値xに対して、1引数関数sをN回適用する関数定義が、自然数Nに対応する関数定義、という解釈です。zeroやoneと名づけることが関数に意味を与えないように、解釈もしょせん解釈で、関数に特別な意味を与えるものではありません。

加算(のようなもの)を考えます。Lisp上で(+ 1 2)を評価すれば3が返ってきますが、+という名前の関数がたまたまこのような動作をするだけで、 (lambda (s x) (funcall s x)) と (lambda (s x) (funcall s (funcall s x))) というふたつの関数を引数として、 (lambda (s x) (funcall s (funcall s (funcall s x))))という関数が返る関数を + と呼んでも何も悪いことはありません。

本に合わせて関数plusと名づけると、定義は次のようになります。

(defun plus (m n s x) (funcall m s (funcall n s x)))

このplus関数は、関数mと関数nを加算した結果の関数を返します。呪文のようですが、次のように動作を確認できます。

(plus 'one 'two '1+ 0)
3

だまされた気分になりますが、直感的な解釈は比較的簡単です。上記のzero,one,twoに連なる定義としてenu,emuを想定してみます。

(defun enu (s x) (funcall s (...)))  ;N
(defun emu (s x) (funcall s (...)))  ;M

関数plusの最初の2引数に関数enuと関数emuを渡したと考えてみます。引数nは関数enuに束縛され、(funcall n s x)は関数enuに2引数を渡して呼び出すことを意味します。Nらしきものが返りそうです。そして(funcall m s (略))のmは関数emuに束縛されているので、関数emuを2引数で呼び出します。引数の片方はNらしきもので、関数emuはMらしきものを足します。全体としてM+Nらしきものが返ります。

乗算は少し複雑です。Emacs Lispで書くと次のようになります(本と少し変えています)。

(require 'cl)
(defun multi (m n s x) 
  (funcall m ((lambda (n0 s0) 
                (lexical-let ((n1 n0) (s1 s0)) 
                  (lambda (x2) (funcall n1 s1 x2)))) n s) x))

次のように動きを確認できます。

(multi 'two 'three '1+ 0)
6

この乗算の直感的な解釈を試みると次のようになります。最初の (lambda ...) の部分が、2引数(n0とs0)を取って関数を返す、関数です。返る関数は1引数の関数です。2引数の関数にnとsを渡して呼び出します。繰り返しになりますが、変にnやsを数値だとか思わず、関数だと思う方が良いです。関数と数値を区別する方が却って混乱します。上の関数enuを再び使うと、この2引数関数は関数enuを束縛した1引数関数を返します。この1引数関数が(funcall m ...)で、関数emuの第一引数として渡ります。解釈の時に出した例を使うと、言わば '1+ の部分が 'N+ になるイメージです。N+ らしき計算がM回繰り返されて、M*N らしきものが返ります。

本では、最後の4ページに、これよりもっと難しいことが書かれています。興味のある人は、最後の4ページだけ本屋で立ち読みしてください。