SICP 問題2.6

2017-10-06

対を手続きで表現することがそれほどの驚きでなければ, 手続きを操作出来る言語では, 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))))

予想と一致した。

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

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

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

ふむ。

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

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