問題解答

問2.6
前回から引き続き、Church 数について。SICPを読む(39) 問題 2.6 Church数やselflearnウィキの内容が、思考の流れも含めてわかりやすいっぽいのでこれをそのままおっかけながら理解していく。

処理を言葉にしてみる
※一通りやってみた感じ、言葉で表現するのは意味がなさそう

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

(f を引数に取り、(x を引数に取りそのまま返す手続) を返す手続き) を返す

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

(n という手続を引数に取り、
(f を引数に取り、(x を引数に取り、
(f を n で評価した結果を用いて x を評価した結果) を f で評価する手続) を返す手続)
を返す手続き)

うむ。わからん。

zero : (lambda(x) x) なので、何もしない → 加算を行う上ではゼロと等価

((zero zero) 100)

これは 100 を返す。

add-1 の使い方がわからない。

(define inc (lambda (x) (+ x 1)))
(((add-1 zero) inc) 0)

らしいけど、いきなり inc とか定義してしまっていいものなのか？

Chrch 数の定義に戻って考えてみる。Church 数は“ある数は、ある関数fを何回 x に適用するか、という定義にしてしまうのである。”
とのこと。

これを念頭に最初に戻る。

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

zero は f を適用しない。これは判りやすい。

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

n に zero を代入して one を作ってみれば理解できそう。

(add-1 zero)

(add-1 (λ (g) (λ (z) z)))
※zero の引数を z と表記、f も g に置き換え

((λ (f) (λ (x) (f ((n f) x)))) [(λ (g) (λ (z) z))])
※zero をわかりやすいように [] で括った

(
 (λ (f) (λ (x) (f ((n f) x)))) [(λ (g) (λ (z) z))]
)

(
 (λ (x) (f (([(λ (g) (λ (z) z))] f) x)))
)

(
 (λ (x) (f (
             ([(λ (g) (λ (z) z))] f)
             x)))
)

((f (z x)))

式を展開していて感じたけど、lambda 式の展開が自分の中で曖昧。
簡単な式でおさらいしてみる。

((lambda (x) (+ x 1)) 0)

は

(define (add x) (+ x 1))
(add 0)

と等価。

((λ(x) (+ x 1)) 0)

を展開する。

(+ 0 1)

これだと直感的にできてしまう。エセマシン語で処理をもっと細かくしてみる

; ((λ(x) (+ x 1)) 0)
; (λ(x) (+ x 1)) : operator
; 0 : operand
push 0
call (λ(x) (+ x 1)) ; "x を引数にとって (+ x 1) を処理するための手続き"
  x = pop()

  ; + : operator
  ; x, 1 : operand
  push 1
  push x
  call +
    v2 = pop()
    v1 = pop()
    push (v1+v2)
  ret = pop()
  push ret

(+ 0 1) はカッコを含めて演算結果の 1 に置き替えられる。
((λ(x) (+ x 1)) 0) はカッコを含めて手続きの (+ 0 1) に置き替えられる。

同様な考え方で zero を展開してみる。

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

((zero g) 0)
(((lambda (f) (lambda (x) x)) g) 0)

(
 ((lambda (f) (lambda (x) x)) g)
 0)

(
 (lambda (x) x)
 0)

0

できてる気はするけど、何だか怪しい。置き替えモデルの復習が必要っぽい。

1.1.5 手続き作用の置き換えモデル を参考におさらい。

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
(f 5)

(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

これはすんなりできる。OK。

もう一回。

(define zero (λ(f) (λ(x) x)))
((zero g) 0)

(((λ(f) (λ(x) x)) g) 0)

; 処理するブロックをわかりやすくする
(
 ((λ(f) (λ(x) x)) g)
0)

; 置き替え
(
 (λ(x) x)
0)

; こういうこと
((λ(x) x) 0)

; 置き替え
0

結果は同じだけど前より処理がハッキリしている感じがする。
この勢いで (add-1 zero) もやってみる。

(define zero (λ(f) (λ(x) x)))
(define (add-1 n)
  (λ(f) (λ(x) (f ((n f) x)))))

(add-1 zero)

(add-1 [(λ(g) (λ(z) z))])

((λ(f) (λ(x) (f ((n f) x)))) [(λ(g) (λ(z) z))])

(λ(f) (λ(x) (f (([(λ(g) (λ(z) z))] f) x))))

((n f) x) この部分、n に代入された zero は f に関わらず x をそのまま返すので

(λ(f) (λ(x) (f x)))

つまり、x に対して f を一度演算する手続を返す。

うーん。何か怪しげ。

展開はちょっと置いておいて、Church 数の定義に則って zero, one, two を定義してみる。

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

((zero inc) 0)
((one inc) 0)
((two inc) 0)

zero, one, two という手続きと、0,1,2 という値は直接関係なくて、それらを繋ぐ(写像する)関数として inc を使っているという理解でいいのか。

(define (mult x) (* x x))

((zero mult) 2)
((one mult) 2)
((two mult) 2)

これなら 2^n になる。

また、先ほど展開した

(λ(f) (λ(x) (f x)))

と

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

を見比べると全く同じなことがわかる。

加算手続きを定義するには繰り返しを定義する必要がありそう。時間オーバーなので次回はここから。

処理の置き替えは、もうちょっと手を動かして慣れた方がよさそう。