SICP 問題2.6

対を手続きで表現することがそれほどの驚きでなければ, 手続きを操作出来る言語では, 0と, 1を足す演算を

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

と実装することで, (少なくとも非負の整数だけを問題とする限りは) 数を使わないで済せることが出来ることを考えよう.
この表現は発明者 Alonzo Church(λ算法を発明した論理学者)に従い, Church数(Church numerals)として知られている.
(zeroとadd-1を使わずに)oneとtwoを直接定義せよ.
(ヒント: (add-1 zero)を評価するのに, 置換えを使おう.)
(add-1の繰返し作用させず)加算手続き+を直接定義せよ.

(zeroとadd-1を使わずに)oneとtwoを直接定義せよ.

ヒントにある通り、 (add-1 zero) の置換えを考えてみる。

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f x)))

となる。

いまいち理解できてないが、zeroは (lambda (f) (lambda (x) x)) で、それに add-1 したものが (lambda (f) (lambda (x) (f x))) というのであれば、これが one なのだろう。

two を求めるには、推測上は、更にもう一回 f を適用すれば良さそうなので、

(lambda (f) (lambda (x) (f (f x))))

こうなるのかな？

とりあえず (add-1 one) の置き換えを考えてみる。

(define one (lambda (f) (lambda (x) (f x))))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))

; 見づらくてこんがらがりそうなので、まずは(one f)だけで考えてみる
(one f)
((lambda (f) (lambda (x) (f x))) f)
(lambda (x) (f x))

; 次に全体の(one f)のところを上のやつで置き換えて考える
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
(lambda (f) (lambda (x) (f (f x))))

予想と一致した。

ということはまとめると、one と two は下記ですね。

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

(add-1の繰返し作用させず)加算手続き+を直接定義せよ.

ふむ。

oneとtwoを見る限り、1増える毎に前の答えにfを適用してるので、+はその数分fの適用回数を増やしていけば良さそう。

ダメだ、できそうだけど、時間がかかっちゃって読み進められないのでスキップしよう。悔しい。
またそのうち戻ってくる。