SICP Exercise memo

なぜか突然 SICP の Exercise のメモ.全然ブログのネタにしてなかったけれど
http://d.hatena.ne.jp/Cryolite/20050714#p1
以来,鋭意継続中.目指せ全 Exercise 制覇.というか SICP はタダで全文見られるので,実はこれ結構面白い企画なのではないかと思った.興味のある方は
http://mitpress.mit.edu/sicp/full-text/book/book.html
にある Full Text と併読してどうぞ.
Exercise 2.5 でペアの car を実装するときに,自然数が2で最大何回割れるかを調べなきゃいけない.線形な探索は簡単だけれど,それだとちょー面白くないので,与えられた自然数から2の指数の上限が求まるので,あとは 0 からその上限の値の間でバイナリサーチすれば対数計算量になるよにゃー,とかまでは考える.
Exercise 2.6 は恐らく関数プログラミング的には超基本の問題なんだろうけれど,自分は初見.0 の定義が zero で,successor を得る操作が add-1 な感じか.実際やってみると見た目ほど難しくなくて,むしろ面白い.加算の定義は楽だけれど,それが本当に加算として定義されているのかの確認はどうするのかという疑問が挙がったので,zero や one を plus してみて,その演算結果が返す高階関数を自分で適当に定義した関数に適用してみて,きちんと期待される回数分 compose されてるかを確認すれば良いんじゃね?とか言ってみた.

; plus の定義忘れたw.後で確認.

; 2 を返す
(define (add1 x) (+ x 1))
(((plus one one) add1) 0)

; 4 を返す
(define (add2 x) (+ x 2))
(((plus one one) add2) 0)

Exercise 2.15 は「変数の数が少ない後者のほうが良い」という直感による説明を排除するべく,長時間式変形と格闘.結局,実際に interval の計算を2つとも全て展開して考察した結果,「この問題においては」後者の方が必ず良いことが証明できることを発見.証明は式変形がぐちゃぐちゃ長いので省略.しかし少なくとも「変数が少ないほうが必ず良い」は全く明らかじゃない.っていうか,それは Exercise 2.16 だけれど諦めた.っていうか,「変数が少ない」というのをどう数学的に書き下せというのか.でも問題としては凄く面白そう.誰か教えてくれにゃいかにゃー.
それにしても,interval arithmetic ってめちゃくちゃ面白そうなのなー.つーか,今まで Boost の Interval Arithmetic Library こと思いっきり誤解してた…….「区間の計算」っていうから,「積 = 区間の積集合」で「和 = 区間の和集合」みたいなこと想像してた.恥ずかしス.
Exercise 2.16 を後でちょこっとやったところ,(通常の計算では)等価な2式において interval arithmetic だと違いが生じる理由として,少なくとも interval arithmetic では和と積の間で分配則が一般に成り立たないことが挙げられることが分かる.