問題解答

引き続き Church 数と格闘。今日は加算手続き + の定義。

加算手続き (+ a b) は “a に対して手続きを b 回繰り返す手続き”。

普通に書くとこうなる

(define (add a b)
  (define (add-iter f n)
    (if (= n 0)
        ((lambda (x) (x))
        ((lambda (x) (f (add-iter (a b f (- n 1)))))))))

  (add-iter f b))

ここで、置き替えないといけないのは if, True, False

404 Blog Not Found の記事を見ていたので、うろ覚えなのをしっかり理解する。

まずは記事中の記法の確認。

0 := λ f x . x
1 := λ f x . f x
2 := λ f x . f f x
(define zefo (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

λ式の展開が怪しいので手を動かしてみる

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

(define (inc n)
  (+ n 1))
(define (to-s z)
  ((z inc) 0))

(to-s zero)
(to-s (lambda (f) (lambda (x) x))) ;;zero を展開
(((z inc) 0) (lambda (f) (lambda (x) x))) ;;to-s を展開
(((lambda (f) (lambda (x) x)) inc) 0) ;;z に代入
(
 ((lambda (f) (lambda (x) x)) inc)
0) ;;ブロックをわかりやすくした
((lambda (x) x) 0) ;;f に代入
0 ;;x に代入

(to-s one)
(to-s (lambda (f) (lambda (x) (f x))))
(((z inc) 0) (lambda (f) (lambda (x) (f x))))
(((lambda (f) (lambda (x) (f x))) inc) 0)
((lambda (x) (inc x)) 0)
(inc 0)
((lambda (n) (+ n 1)) 0)
(+ 0 1)
1

(to-s two)
(to-s (lambda (f) (lambda (x) (f (f x)))))
(((z inc) 0) (lambda (f) (lambda (x) (f (f x)))))
(((lambda (f) (lambda (x) (f (f x)))) inc) 0)
((lambda (x) (inc (inc x))) 0)
(inc (inc 0))
((lambda (n) (+ n 1)) ((lambda (n) (+ n 1)) 0))
((lambda (n) (+ n 1)) (+ 0 1))
((lambda (n) (+ n 1)) 1)
(+ 1 1)
2

うーん。まあ慣れてきた。。。かな?

記事中の SUCC の復習。

SUCC := λ n f x . f(n f x)
2 := (λn f x . f(n f x)) 1
2 := λ f x . f(1 f x)
2 := λ f x . f(f x)

試しに 3 もやってみる。。。と思ったらうまくいかない。
ラムダ計算でよく出てくる謎の記法、これは何だ?

Wikipedia に載っていた。
“BNFで書かれた以下の文脈自由文法によって定義される。”

OK.もう一回やってみる。

3 := (λn f x . f(n f x)) 2
3 := λf x . f(2 f x)
3 := λf x . f(λ a b . a(a b) f x)
3 := λf x . f(f(f x))


4 := (λn f x . f(n f x)) 3
4 := λf x . f(3 f x)
4 := λf x . f(λa b . a(a(a b)) f x)
4 := λf x . f(f(f(f x)))

カッコの扱いにちょっと慣れてきた。あと、lambda ではなくて λ と書けるのがありがたい。

SUCC の求め方も謎だったけど、思考を追った記事発見。これも手を動かして理解する。

ONE : λ f x.f x
SUCC : λ n f x.f n

(SUCC ONE) とした結果、TWO が得られれば OK.

(SUCC ONE)
(SUCC λ f x.f x)
(λ n f x.f n λ f x.f x)
λ f x.f λ a b.a b

“ここでα変換したλa.λb.a bを数ではなく、ひとつの函数*2として捉えると、どうやったら(f x)になるのかが見えてきます。”

見えてこないよ!! λ f x を展開するのか?

(a b) f x ;; λ a b.a b を二つの引数を取る関数とみなす
(f x)

ONE に ONE を作用させたい場合、こうなるらしい。謎。

SUCC : λ n f x.f (n f x)
(SUCC ONE)
(λ n f x.f (n f x) ONE)
(λ n f x.f (n f x) λ f x.f x)
λ f x.f (λ a b.a b f x)
λ f x.f (f x)

結論。理解できなかった。。。orz
泥沼化してるし、どこまで攻めるべきか。ちょっと考える必要がありそう。

そもそも SICP の先生を探したほうがいいのかも。

問題解答

問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))))

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

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

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

問題解答

問2.5

(define (icons a b)
  (* (expt 2 a) (expt 3 b)))

(define (icar v)
  (define (iter t)
    (if (= (gcd t 3) 1)
        t
        (iter (/ t 3))))

  (log (iter v) 2))

(define (icdr v)
  (define (iter t)
    (if (= (gcd t 2) 1)
        t
        (iter (/ t 2))))

  (log (iter v) 3))

(define v (icons 5 8))
(icar v)
(icdr v)

gosh> 5.0
gosh> 8.0

整数で与えているのに浮動小数になってしまっているのが気に入らない。
log を使わずに、地道に徐余を求めながら割っていく方がいいっぽい。

問2.6
置換えを使っての展開が全然できない。。。。
そもそも Church 数がわけわからないので先人の知恵を拝借。

この問題、さくっと載ってるけどかなり大事なことを表そうとしている感じ。 Church 数はちゃんと勉強した方がよさそうなので引き続き明日もここからやることにする。

問題解答

問2.3
対角上の二点を指定する方法で表現。

(define (make-rectangle lb rt)
  (cons lb rt))

(define (rect-lb rect)
  (car rect))

(define (rect-rt rect)
  (cdr rect))

(define (w rect)
  (- (x-point (rect-rt rect)) (x-point (rect-lb rect))))

(define (h rect)
  (- (y-point (rect-rt rect)) (y-point (rect-lb rect))))

(define (perimeter rect)
  (* (+ (w rect) (h rect)) 2))

(define (area rect)
  (* (w rect) (h rect)))

(define rect (make-rectangle (make-point 0 0) (make-point 1 1)))
(display (perimeter rect))
(display (area rect))

基点と幅、高さを指定する方法で表現

(define (make-rectangle base w h)
  (cons base (cons w h)))

(define (w rect)
  (car (cdr rect))

(define (h rect)
  (cdr (cdr rect))

(define rect (make-rectangle (make-point 0 0) 1 1))
(display (perimeter rect))
(display (area rect))

構成子と選択子は表現にあわせて用意し、計算は共通のものを使用できている。

本文

2.1.3 データとは何か
cons, car, cdr を実装してみる。 cons で手続きを返すことで実現。

問題

問2.4

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

(car (cons 1 2))
(cdr (cons 1 2))

置換えモデルを使用して動作を確認

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
1

問題解答

問 2.2

(define (make-point x y)
  (cons x y))

(define (x-point point)
  (car point))

(define (y-point point)
  (cdr point))

(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment segment)
  (car segment))

(define (end-segment segment)
  (cdr segment))

(define (midpoint-segment segment)
  (make-point (/ (+ (x-point (start-segment segment))
                    (x-point (end-segment segment))) 2)
              (/ (+ (y-point (start-segment segment))
                    (y-point (end-segment segment))) 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(define p1 (make-point 0.0 0.0))
(define p2 (make-point 1.0 1.0))
(define s (make-segment p1 p2))
(define m (midpoint-segment s))
(print-point m)

これは手を動かすだけなので簡単だった。

本文

2.1.1 有理数の算術演算

cons を使用して対(pair)を作ることができる

(define x (cons 1 2))
(car x)
(cdr x)

問題解答

問2.1

(define (make-rat n d)
	(let ((sign (/ (* n d) (* (abs n) (abs d))))
				(g (gcd (abs n) (abs d))))
		(cons (* sign (/ (abs n) g)) (/ (abs d) g))))

(define v (make-rat  1  2))
(print-rat v)
(define v (make-rat -1  2))
(print-rat v)
(define v (make-rat  1 -2))
(print-rat v)
(define v (make-rat -1 -2))
(print-rat v)

何だかイケテナイ感。参考解答だとこんな感じ。

(define (make-rat n d)
  (let ((g (abs (gcd n d))))
     (if (< d 0)
         (cons (/ (- n) g) (/ (- d) g))
         (cons (/ n g) (/ d g)))))

うむ。たしかにー。

本文

2.1.2 抽象の壁
データを扱う際に、対象のレイヤ毎に抽象化をおこない、インターフェースを通して対象を操作することでプログラムの修正・維持が楽になったり柔軟性を保ち続ける助けになる。

今日はここまで。うーん、ちょっとよそ事をしたりダラダラしてしまって時間を無駄にしている。
もっと時間を有効に使わないと。

引き続き第二章へ突入。

本文

2 データによる抽象の構築

合成データオブジェクト:
単純なデータだけでは、ものごとを表現することが大変なので、複数のデータを組み合わせて一つの塊として扱うことができるようにする

データ抽象:
合成データを使用してプログラムの部品度を増やし、プログラム本体とデータの扱いをする部分に分離する

合成データを形成する鍵:

• 閉包(closure)
• 公認インターフェース

言語の表現力→記号式を使って論じる

プログラムの場所によって異なった表現をされているデータの扱い→汎用演算

• データ主導プログラミングの導入

2.1 データ抽象入門
データ抽象: 合成オブジェクトの使い方を基本データの細部から分離して抽象化する

“2.1.1 有理数を扱う算術演算”はちょっと長そうなので今日はここまで。

SICP 第一章も最後の問題。サクサクいきます。

問題解答

問1.46

(define (iterative-improbe iterator checker)
  (lambda(x) (let ((next (iterator x)))
               (if (checker x next)
                   next
                   ((iterative-improbe iterator checker) next)))))

(define tolerance 0.00001)
(define (fixed-point f)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  ((iterative-improbe f close-enough?) 1.0))

(fixed-point cos)


(define (average v1 v2)
  (/ (+ v1 v2) 2))
(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))))

(sqrt 2)

とりあえずできたけど、三角い感じがする。答えあわせをすると随分スッキリ書かれている。

(define (iterative-improve test improve)
  (lambda (g)
    (define (iter g)
      (if (test g) g
          (iter (improve g))))
  (iter g)))

。。。と思ったけど、やっていることは変わらないっぽい。
問題はとりあえずできたけど、まだまだヨチヨチ歩き感がある感じ。

何はともあれ、第一章終了～。ぱちぱちぱちぱち。

第一章も遂に最後のページで、あとは問題を残すのみ。今日中におわれるか?

問題解答

問1.42

(define (inc x) (+ x 1))
(define (square x) (* x x))

(define (compose f g)
  (lambda(x) (f (g x))))

((compose square inc) 6)

問1.43

(define (repeated f n)
  (define (it i)
    (if (= i 1)
        (lambda(x) (f x))
        (lambda(x) (f ((it (- n 1)) x)))))

  (it n))

((repeated square 2) 5)

ヒントにある compose を使っていない&無駄な it を定義していた。回答では以下のようになっていた。

(define (repeated f n)
  (if (= n 0)
      (lambda(x) x)
      (compose f (repeated f (- n 1)))))

((repeated square 2) 5)

問1.44

(define (n-fold-smooth f n)
  ((repeated smooth n) f))

今日はここまで。最後の二問は明日に持ち越し。