SICP 読み (2)

scheme SICP

続き。1.1.5 以降ですがスルー多用の予定。

1.1.7 例: Newton 法における平方根

結構ポイント高そうなんですが、問題 1.7 における_そうよいテストではない_な部分で明確なイメージができません。sqrt-iter で置き換えモデルを使ってみるとどうなるんだろうか。

(sqrt-iter 1.0 2)

(sqrt-iter 1.5 2)

(sqrt-iter 1.41666667 2)

(sqrt-iter 1.41421569 2)

ちなみに (* guess guess) と x の差分ですが以下

  • 1.0 の場合、1
  • 1.5 の場合、0.25
  • 1.41666667 の場合、0.0069
  • 1.41421569 の場合、0.00000602

しきい値が 0.001 になってるからこれでストップは当然か。

で、問題 1.7 にある_非常に小さい数の平方根をとる時には効果的ではない_な所以は容易に想像できるな。これは数学的素養がなくても類推可能。しきい値に近い数が処理対象になっている場合、誤差が大きくなる事が予想できます。

試してみると

guile> (sqrt 0.01)
0.100325785109606
guile> (sqrt 0.001)
0.0412454260749911
guile> (sqrt 0.0001)
0.0323084483304812
guile> (sqrt 0.00001)
0.0313564901077172
guile>

ちなみにプリミティブな sqrt はこうなる。

guile> (sqrt 0.01)
0.1
guile> (sqrt 0.001)
0.0316227766016838
guile> (sqrt 0.0001)
0.01
guile> (sqrt 0.00001)
0.00316227766016838

がしかし、_大きい数_なナニはちょっと微妙。_限られた精度_というのがヒントだと思いますがこれについては保留 (スルーと言った方が早いかも)。

問題 1.6 (new-if の定義と挙動の予測)

問題 1.5 ができていれば考えやすい。通常の処理系であれば「引数を評価し、作用させる」方法を使うので、条件の真偽に関わらず sqrt-iter が常に評価されてしまって大変なコトになるのではないか、と。

検証はしてません。

問題 1.8 (立方根の手続き実装)

これ、スルーしたいなぁ。面倒臭いが無理矢理。

(define (cube x)
  (define (cube-iter guess)
    (p guess)
    (if (good-enough? guess)
	guess
	(cube-iter (improve guess))))

  (define (good-enough? guess)
    (< (abs (- (* guess guess guess) x)) 0.001))

  (define (improve guess)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

  (define (average x y)
    (/ (+ x y) 2))

  (cube-iter 1.0))

一応、立方根は計算できている模様。

問題 1.9 (手続きの定義と置き換えモデルによる検証)

置き換えなソレを以下に、ってスペース勿体ナイのでポイントを以下に。

(define (+ a b) 
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(dec a) の値が 0 になるまで + は inc で置換えられる。再帰的。

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

呼び出し元に戻るまで何らかの処理が保留になる形になっていない。反復的。
どちらの例でも a はカウンタとして使われてますな。

問題 1.10 (要約不能)

どう収束するのかを検証するには紙が必要なのは分かりますが、地味な作業を嫌うあたりはおやぢ的かも。我慢してやってみた方が良いかな。高校時代にやっていない分、今やっておきなさい、とゆー事だと前向きに理解しつつ。

あ、これは展開と収束の練習か。先に式の値を机上で計算させて、数学的定義という形で収束させるのは良い練習かも。

Ackermann 関数の定義は以下。

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

まず、(A 1 10) ですが、こんな感じになる。

(A 1 10)

(A 0 (A 1 9))

(A 0 (A 0 (A 1 8)))

第一引数が 0 の場合 (* 2 y) になり、第二引数が 1 の場合、2 が返却、という事は、この式自体は 2 ^ 10 で 1024 が式の値になる。

次は (A 2 4) ですが、面倒ながらも第一引数が 2 の場合のナニを順に見てみる。

(A 2 0) ;; => 第二引数が 0 なので式の値は 0
(A 2 1) ;; => 第二引数が 1 なので式の値は 2

(A 2 2)
(A 1 (A 2 1)) ;; => (A 2 1) の式の値は 2 なので 2 ^ 2 が式の値

(A 2 3)
(A 1 (A 2 2)) ;; => (A 2 2) の式の値は 4 なので 2 ^ 4 が式の値

(A 2 4)
(A 1 (A 2 3)) ;; => (A 2 3) の式の値は 16 なので 2 ^ 16 が式の値

次は (A 3 3) ですが、これも順に見ていけば話が早いみたいです。

(A 3 0) ;; => 第二引数が 0 なので式の値は 0
(A 3 1) ;; => 第二引数が 1 なので式の値は 2

(A 3 2)
(A 2 (A 3 1)) ;; => (A 3 1) の値は 2
(A 2 2) ;; => (A 2 2) の値は 4

(A 3 3)
(A 2 (A 3 2)) ;; => (A 3 2) の値は 4
(A 2 4) ;; => (A 2 4) の値は 65536

で、これを数学的定義とゆーやつで纏めなきゃいけないワケですな。

  • (A 0 n) については 2n で OK かな
  • (A 1 n) は 2^n にしたいけど n = 0 の場合がダウト。scheme の定義としては以下??
(define (g n)
  (let gg ((n n))
    (if (= n 0)
        0
        (expt 2 n))))
  • (A 2 n) はどう書けば良いのか困る。scheme の定義的には以下か。
(define (h n)
  (if (= n 0)
      0
      (let hh ((n n))
	(if (= n 0)
	    1
	    (expt 2 (hh (- n 1)))))))

1.2.2 木構造再帰

まず、直感的に木構造再帰を使って設計せい、との事。フィボナッチ数の計算な手続きの例として、木構造再帰な手続きのサンプルの次に末尾再帰なサンプルが出ている。節末に「スマート翻訳系」と名前が付けられた手続きの検討の方法は scheme で勝負するのであれば身に付けておきたいアレかも。
しかも脚注 34 に memoization なるナニが紹介されてたりなんかして、順番を無視してそちら方面にジャンプしてしまいたい欲求にかられてたり (以下略

又、こうしたアルゴリズムを検討するという作業において興味深いというか参考になるのは以下の記述。

ある金額の両替の問題を、少ない種類の硬貨を使う少ない金額の問題へ再帰的に縮小させることが出来る。この縮小化を注意深く考察し、次の縮退した場合が規定できれば、アルゴリズムが書けることを確認せよ。


脚注 33 にある_5 セントと 1 セントを使って 10 セントの両替を作る場合を使い、縮小規則の働きを詳細に調べよ_というソレを試してみます。

(cc 残り 使用コイン)

(cc 10 5)
|(cc 10 1)
||(cc 10 0)           ;; => 0 return
||(cc (10 - 1) 1)
|||(cc 9 0)           ;; => 0 return
|||(cc (9 - 1) 1)
||||(cc 8 0)          ;; => 0 return
||||(cc (8 - 1) 1)
||    .....
||...||(cc 1 0)       ;; => 0 return
||...||(cc (1 - 1) 1) ;; => 1 return
|(cc (10 - 5) 5)
||(cc 5 1)
|||(cc 5 0)           ;; => 0 return
|||(cc (5 - 1) 1)
||||(cc 4 0)
||||(cc (4 - 1) 1)
||   .....
||...||(cc 1 0)       ;; => 0 return
||...||(cc (1 - 1) 1) ;; => 1 return
|||(cc (5 - 5) 5)     ;; => 1 return

10 セントを 1 セントと 5 セントで両替できるケースは

  • 1 セント 10 枚
  • 1 セント 5 枚と 5 セント 1 枚
  • 5 セント 2 枚

という合わせて 3 ケースとなる。

規則としては、

  • 残り(両替対象)が 0 になったら成功 (※ 0 未満とか駄目な
  • 両替対象で使用できるコインが無くなったら失敗
  • 手続きが起動されて上記シバリをスルーしたら
    • 一つ下位の両替コインで手続きを呼び出し (再帰
    • 残りから使用コインの額を引いて手続きを呼び出し (再帰

なのかなぁ。
明日は大晦日じゃん。スルーしなさ杉でハマるとは思わなんだ。
# てか、この後猛然とスルー攻撃しまくりそうな予感も。