SICP 読書ノート#5 - 2.1 データ抽象入門 (pp.45-52)
「§2.1 データ抽象入門」から
データ抽象とは
かんたんに言うと、データ構造を階層化して抽象化しましょうってことかな？
- 公認インターフェース(conventional interface)とかデータ主導プログラミング(data-directed programming)とか聞き慣れない用語が。後から出てくると思うのでその時理解する
- 「加法的に(additively)(つまり修正なしに)組み合わる」というのがキーになりそう
問題 2.1
負の有理数の場合は、分子を負数とするmake-ratを定義する。
(define (make-rat n d) (let ((sign (if (>= (* n d) 0) 1 -1))) (cons (* sign (abs n)) (abs d))))
問題 2.2
(define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) (define (make-segment start-point end-point) (cons start-point end-point)) (define (start-segment segment) (car segment)) (define (end-segment segment) (cdr segment)) (define (midpoint-segment segment) (make-segment (/ (+ (x-point (start-segment segment)) (x-point (end-segment segment))) 2) (/ (+ (y-point (start-segment segment)) (y-point (end-segment segment))) 2))) ; テスト (define seg (make-segment (make-point 1 2) (make-point 4 6))) (midpoint-segment seg) ; => '(5/2 . 4)
問題 2.3
x-point, y-pointをうまく活用する。
(define (make-rect top-left-point bottom-right-point) (cons top-left-point bottom-right-point)) (define (top-left-point-rect rect) (car rect)) (define (bottom-right-point-rect rect) (cdr rect)) (define (width-rect rect) (abs (- (x-point (top-left-point-rect rect)) (x-point (bottom-right-point-rect rect))))) (define (height-rect rect) (abs (- (y-point (top-left-point-rect rect)) (y-point (bottom-right-point-rect rect))))) (define (perimeter rect) (+ (* 2 (width-rect rect)) (* 2 (height-rect rect)))) (define (area rect) (* (width-rect rect) (height-rect rect)))
データとは何か
cons、car、cdrの実装例について。しれっとクロージャを使っている。学生の頃に読んだ時はどうしてこれが動くのか理解できなかった。
(define (cons x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y) (else (error "Argument not 0 or 1 -- CONS" m)))) dispatch) ;; => dispatchはx,yを参照することができる手続きオブジェクト (define (car z) (z 0)) (define (cdr z) (z 1))
評価してみる。
racket@> (define x 1) racket@> (define y 2) racket@> (define z (cons x y)) racket@> z #<procedure:dispatch> racket@> (car z) 1 racket@> (cdr z) 2
問題 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)))
評価してみる。
racket@> (define x 1) racket@> (define y 2) racket@> (define z (cons 1 2)) racket@> z #<procedure> racket@> (car z) 1 racket@> (cdr z) 2
問題 2.6
λ算法およびチャーチ数の問題。正直まだ理解できていない。
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
が与えられるとして、one, two を直接定義せよ。また加算手続きを定義せよ。
まずは、add-1にzeroを適用した置き換えモデルを考える。
(add-1 zero) -> (lambda (f) (lambda (x) (f ((zero f) x)))) -> (lambda (f) (lambda (x) (f ((lambda (x) x) x)))) -> (lambda (f) (lambda (x) (f x))) ;; one
oneはf,xを引数にとりf(x)を返す手続き。
次に、add-1にoneを適用する。
(add-1 one) -> (lambda (f) (lambda (x) (f ((one f) x)))) -> (lambda (f) (lambda (x) (f ((lambda (x) (f x) x)))) -> (lambda (f) (lambda (x) (f (f x)))) ;; two
twoはf,xを引数にとりf(f(x))を返す手続き。
よって直接定義すると以下の通り。ついでにthreeも。
(define one (lambda (f) (lambda (x) (f x)))) (define two (lambda (f) (lambda (x) (f (f x))))) (define three (lambda (f) (lambda (x) (f (f (f x))))))
fにf(x)=(x+1)、xに0を適用すると自然数に変換できるらしい。
(define inc (lambda (x) (+ x 1))) ((zero inc) 0) ; => 0 ((one inc) 0) ; => 1 ((two inc) 0) ; => 2 ((three inc) 0) ; => 3
確かに動く。すごい。
で、次に加算手続き。fを適用する回数を足せばよいのだけど思いつかない...
でも、さっきのWikipediaのリンク先にもう答えがあって。
(define add (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((m f) ((n f) x))))))) ;; または (define (add m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
とすればよいらしい。同じく自然数に変換してみる。
((((add one) two) inc) 0) ; => 3 ((((add two) three) inc) 0) ; => 5
ここで、置き換えモデルで書いてみようと思ったけど括弧だらけですごく書きづらい。
そこで以下を参考に、λ算法でやってみた。
one -> λfx.f x two -> λfx.f (f x) three -> λfx.f (f (f x)) add -> λmnfx.m f (n f x)
とすると、
add one two -> λmnfx.m f (n f x) -> λfx.(λfx.f x) f ((λfx.f (f x)) f x) -> λfx.(λfx.f x) f ((λx.f (f x)) x) -> λfx.(λfx.f x) f (f (f x)) -> λfx.(λx.f x) (f (f x)) -> λfx.(f (f (f x))) add two three -> λmnfx.m f (n f x) -> λfx.(λfx.f (f x) f ((λfx.f (f (f x))) f x) -> λfx.(λfx.f (f x) f ((λx.f (f (f x))) x) -> λfx.(λfx.f (f x) f (f (f (f x))) -> λfx.(λx.f (f x)) (f (f (f x))) -> λfx.(f (f (f (f (f x)))))
何となくできてる気がする。
ちなみにこういう正規化みたいな作業を簡約(simplify)というらしい。
ついでに積算は、
(define mul (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((n (m f)) x))))))
λ算法で書くと
mul -> λmnfx.(n (m f)) x
two,threeを適用して簡約すると、
mul three two -> λmnfx.(n (m f)) x -> λfx.(λfx.(f (f x)) (λfx.f (f (f x)) f))) x -> λfx.(λfx.(f (f x)) λx.f (f (f x))) x -> λfx.(λx.(λx.f (f (f x)) (f (f (f x))))) x -> λfx.(λx.(f (f (f (f (f (f x))))))) x -> λfx.f (f (f (f (f (f x)))))
できた。
と、できた気はするんだけど加算や積算手続きを自分で編み出せた訳ではないので、 本当に理解できているかはすごく微妙。 とは言えいまの実力だとこんなもんかなと思うので、ひとまず次へ進む。
次は「§2.1.4 拡張問題：区間算出演算」から。
