[SICP] 問題 1.09 : 反復的プロセスと再帰的プロセス

次の二つの手続きはどちらも, 引数を1増やす手続きincと, 引数を1減らす手続きdecを使って, 二つの正の整数を足す方法を定義している.

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

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

置換えモデルを使い, それぞれの手続きが(+ 4 5)を評価する時に生成するプロセスを示せ. そのプロセスは反復的か再帰的か.

置き換えモデルを使い, 生成するプロセスを書いてみます. まず1つ目の手続きが生成するプロセスです.

  (+ 4 5)
= (inc (+ 3 5))
= (inc (inc (+ 2 5)))
= (inc (inc (inc (+ 1 5))))
= (inc (inc (inc (inc (+ 0 5)))))
= (inc (inc (inc (inc 5))))
= (inc (inc (inc 6)))
= (inc (inc 7))
= (inc 8)
= 9

次に, 2つ目の手続きが生成するプロセスです.

  (+ 4 5)
= (+ 3 6)
= (+ 2 7)
= (+ 1 8)
= (+ 0 9)
= 9

処理系を使って生成するプロセスを確認します. 問題文の手続きを定義します. 手続き「+」は定義済みのため, １つ目の手続きを「+#」, ２つ目の手続きを「+$」としています. また, 手続きが生成するプロセスを観察するためにtraceを使用します.

(require (lib "racket/trace.ss"))

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

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

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

(trace +# +$)

実行結果は次のようになりました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (+# 4 5)
>(+# 4 5)
> (+# 3 5)
> >(+# 2 5)
> > (+# 1 5)
> > >(+# 0 5)
< < <5
< < 6
< <7
< 8
<9
9
> (+$ 4 5)
>(+$ 4 5)
>(+$ 3 6)
>(+$ 2 7)
>(+$ 1 8)
>(+$ 0 9)
<9
9

実行結果から, +#は再帰的プロセスを生成し, +$は反復的プロセスを生成することが分かります. +$の定義が末尾再帰的であるため, +$は反復的プロセスを生成します.

+#は, aが0でなかったとき+#を呼び出し, その結果をincの引数として与えています. このことから, +#は再帰的プロセスを生成します.

一方, +$では, aが0でなかったとき+$を呼び出しますが, その結果を使って計算する式となっていません. つまり, 末尾再帰の形をしています. よって, +$は再帰的プロセスを生成します.

[筋トレ] 2014.10.13の週

出勤前に筋トレをしました。その記録です。

10/14（火）
　スクワット　　　２０
　リアレイズ　　　１０、１０　（5kgの鉄アレイ）
　クランチ　　　　２０

10/15（水）
　プッシュアップ　１２　　　　（膝をついた状態）
　ナロースタンス　　４　　　　（手を重ねた状態）
　アームカール　　１５　　　　（5kgの鉄アレイ）

10/17（金）　74.05kg
　スクワット　　　２０、２０
　リアレイズ　　　１２、１０　（5kgの鉄アレイ）
　クランチ　　　　２０、２０

10/18（土）　75.10kg
　プッシュアップ　１２、　５　（膝をついた状態）
　ナロースタンス　　０　　　　（手を重ねた状態）
　アームカール　　２０、２０　（5kgの鉄アレイ）

[SICP] 問題 1.08 : 立方根の計算

立方根をとるNewton法はyがxの立方根の近似値なら, よりよい近似は

 x / y^2 + 2y  
--------------
      3 

の値で与えられるという事実によっている. この式を使い平方根の手続きと似た立方根の手続きを実装せよ. (1.3.4節で平方根と立方根の手続きの抽象化として, 一般的なNewton法の実装法を学ぶ.)

平方根を求めるプログラムを修正して, 立方根を求めるプログラムに作り変えます. 立方根を求められるように手続きimproveを修正します. また, 手続き名に現れるsqrtをcubeに変更します. プログラムの全体は次のようになります.

(define (square x)
  (* x x))

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

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

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

(define (cube x)
  (cube-iter 1.0 x))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (cube 8)
2.000004911675504
> (cube 10)
2.1544959251533746
> (cube 27)
3.001274406506175
> 

[SICP] 問題 1.07 : good-enough?の改良

平方根の計算で使ったgood-enough?テストは, 非常に小さい数の平方根をとる時には効果的ではない. また, 実際の計算機では, 算術演算は殆んどの場合, 限られた精度で実行される. それでわれわれのテストは非常に大きい数にも不適切である. 小さい数, 大きい数の場合, どのようにテストが失敗するかの例を使ってこのことを説明せよ. good-enough?を実装するもう一つの戦略は, ある繰返しから次へのguessの変化に注目し, 変化が予測値に比べ非常に小さくなった時に止めるのである. こういう終了テストを使う平方根手続きを設計せよ. これは小さい数, 大きい数に対してうまく働くか.

問題文にあるように, 小さい数と大きい数の平方根を求め, 組み込みの平方根を求める手続きの結果と比較します。

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 10000.01)
100.00005025489767
> (sqrt 10000.01)
100.0000499999875
> (my-sqrt 0.0001)
0.03230844833048122
> (sqrt 0.0001)
0.01
> 

大きな数の場合は、組み込みの手続きと同等の結果が得られていますが, 小さな数の場合は正しい結果といえません.

ループの回数を調べるためにtraceを使います. 手続きsqrt-iterの呼び出され方を調べてみます. プログラムは次のようになります. １行目でtraceのためのライブラリを呼び出し, 最後の行でトレースする手続きを指定しています。

(require (lib "racket/trace.ss"))

(define (square x)
  (* x x))

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

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

(define (improve guess x)
  (average guess (/ x guess)))

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

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

(trace sqrt-iter)

平方根を求めると次のような結果が得られました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 10000.01)
>(sqrt-iter 1.0 10000.01)
>(sqrt-iter 5000.505 10000.01)
>(sqrt-iter 2501.252400010099 10000.01)
>(sqrt-iter 1252.6252005857104 10000.01)
>(sqrt-iter 630.3042212483191 10000.01)
>(sqrt-iter 323.08479587589 10000.01)
>(sqrt-iter 177.0182267724306 10000.01)
>(sqrt-iter 116.75482057222084 10000.01)
>(sqrt-iter 101.20223735102081 10000.01)
>(sqrt-iter 100.00719042723898 10000.01)
>(sqrt-iter 100.00005025489767 10000.01)
<100.00005025489767
100.00005025489767
> (my-sqrt 0.0001)
>(sqrt-iter 1.0 0.0001)
>(sqrt-iter 0.50005 0.0001)
>(sqrt-iter 0.2501249900009999 0.0001)
>(sqrt-iter 0.12526239505846617 0.0001)
>(sqrt-iter 0.06303035962394366 0.0001)
>(sqrt-iter 0.03230844833048122 0.0001)
<0.03230844833048122
0.03230844833048122
> (my-sqrt 0.000001)
>(sqrt-iter 1.0 1e-006)
>(sqrt-iter 0.5000005 1e-006)
>(sqrt-iter 0.250001249999 1e-006)
>(sqrt-iter 0.12500262498950004 1e-006)
>(sqrt-iter 0.06250531241075212 1e-006)
>(sqrt-iter 0.031260655525445276 1e-006)
<0.031260655525445276
0.031260655525445276
> 

実行結果から, 小さい数の場合は手続きの呼び出し回数に差がないことが分かります. 手続きgood-enough?は, 予測値guessの二乗と被開平数xの差が0.001より小さい場合に「十分よい」と判定しています. 被開平数が基準となる0.001より小さい場合, good-enough?の判定に与える影響が少なくなります. 例えば, 被開平数を0.000001, guessを0.03としgood-enough?を計算してみます.

  (< (abs (- (square guess) x)) 0.001)
= (< (abs (- (square 0.03) 0.000001)) 0.001)
= (< (abs (- (square 0.03) 0.000001)) 0.001)
= (< (abs (- 0.0009 0.000001)) 0.001)
= (< (abs 0.000899) 0.001)
= (< 0.000899 0.001)
= #t

この結果から, 被開平数が0.0001より小さいと予測値を2乗した結果だけで「十分よい」と判断し, 約0.03を求める平方根として返してしまいます.

問題文にあるように予測値の変化に着目し, 変化が少なくなった時に「十分に良い」と判定するように手続きを修正します. i番目の予測値の値をg_iとすると, 予測値の変化が次の式を満たせば予測値の変化が小さくなったと言えます.

| (gi+1 - gi) / gi | < 0.001

この式を使って手続きgood-enough?を改良します。 上の式でg_iはguessに相当し, g_i+1は手続きimproveを用いて計算出来ます. プログラムの全体は次のようになります.

(require (lib "racket/trace.ss"))

(define (square x)
  (* x x))

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

(define (improve guess x)
  (average guess (/ x guess)))

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

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

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

(trace sqrt-iter)

実行結果は次のようになりました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 0.0001)
>(sqrt-iter 1.0 0.0001)
>(sqrt-iter 0.50005 0.0001)
>(sqrt-iter 0.2501249900009999 0.0001)
>(sqrt-iter 0.12526239505846617 0.0001)
>(sqrt-iter 0.06303035962394366 0.0001)
>(sqrt-iter 0.03230844833048122 0.0001)
>(sqrt-iter 0.017701806998329746 0.0001)
>(sqrt-iter 0.011675473894984788 0.0001)
>(sqrt-iter 0.010120218365353947 0.0001)
>(sqrt-iter 0.010000714038711746 0.0001)
<0.010000714038711746
0.010000714038711746
> (my-sqrt 0.000001)
>(sqrt-iter 1.0 1e-006)
>(sqrt-iter 0.5000005 1e-006)
>(sqrt-iter 0.250001249999 1e-006)
>(sqrt-iter 0.12500262498950004 1e-006)
>(sqrt-iter 0.06250531241075212 1e-006)
>(sqrt-iter 0.031260655525445276 1e-006)
>(sqrt-iter 0.015646322308953218 1e-006)
>(sqrt-iter 0.007855117545897352 1e-006)
>(sqrt-iter 0.003991211544161647 1e-006)
>(sqrt-iter 0.0021208810160681787 1e-006)
>(sqrt-iter 0.0012961915927068783 1e-006)
>(sqrt-iter 0.0010338412392442034 1e-006)
>(sqrt-iter 0.0010005538710539446 1e-006)
<0.0010005538710539446
0.0010005538710539446
> (my-sqrt 0.00000001)
>(sqrt-iter 1.0 1e-008)
>(sqrt-iter 0.500000005 1e-008)
>(sqrt-iter 0.25000001249999987 1e-008)
>(sqrt-iter 0.12500002624999892 1e-008)
>(sqrt-iter 0.06250005312499106 1e-008)
>(sqrt-iter 0.03125010656242753 1e-008)
>(sqrt-iter 0.015625213280668165 1e-008)
>(sqrt-iter 0.007812926635966154 1e-008)
>(sqrt-iter 0.003907103283034967 1e-008)
>(sqrt-iter 0.001954831361974762 1e-008)
>(sqrt-iter 0.0009799734463768973 1e-008)
>(sqrt-iter 0.0004950889022510404 1e-008)
>(sqrt-iter 0.0002576436474057565 1e-008)
>(sqrt-iter 0.00014822847335384218 1e-008)
>(sqrt-iter 0.00010784594750729777 1e-008)
>(sqrt-iter 0.00010028540197249 1e-008)
>(sqrt-iter 0.00010000040611237676 1e-008)
<0.00010000040611237676
0.00010000040611237676
> 

期待通りの結果が得られました.

[SICP] 問題 1.06 : ifが特殊形式である理由

Alyssa P. Hackerはifが特殊形式である理由が分らない. 「cond を利用し, 普通の手続きとして定義してはいけないの?」と聞いた. Alyssaの友人のEva Lu Atorはそうすることはもちろん出来るといって, ifの新版を定義した:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

EvaはAlyssaにプログラムを見せた:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Alyssaは喜び, 平方根のプログラムを書き直すのにnew-ifを使った:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

Alyssaが平方根を計算するのにこれを使おうとすると, 何が起きるか, 説明せよ.

new-ifを使って平方根を求める手続きを定義します. 手続き名sqrtは解釈系で定義済みであるため, my-sqrtとしています.

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (square x)
  (* x x))

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

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

この手続を使って平方根を求めてみると, 解釈系は停止しません. その理由は, new-ifが特殊形式ではなく, 解釈系が作用的順序で評価しているためです.

new-ifは特殊形式ではないため, new-ifを評価するために三つの引数を評価します. ３つ目の引数でsqrt-iterを呼び出しているため無限ループに入り, 解釈系は停止しません.

ifは特殊形式であるため, まずguessの値が「十分よい」か判定します. 「十分よい」を場合は, sqrt-iterを評価せずguessを返すので解釈系は停止します.

[SICP] 問題 1.05 : 作用的順序と正規順序

Ben Bitdiddleは, 彼の対面している解釈系が, 作用的順序の評価を使っているか, 正規順序の評価を使っているか決定するテストを発明した. 次の二つの手続きを定義した:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

彼は次に式

(test 0 (p))

を評価してみた. 作用的順序の評価を使う解釈系で, Benはどういう振舞いを見るか. 正規順序の評価を使う解釈系で, 彼はどういう振舞いを見るか. 説明せよ. (特殊形式ifの評価規則は, 解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする: 述語式を最初に評価し, その結果が帰結式と代替式のいずれを評価するかを決める.)

問題文の手続きを定義します.

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

式(test 0 (p))を評価すると, 解釈系は停止しません. その理由を考えます.

まず, この問題を理解するためには, 手続きpが無限ループを表していることに気づかなくてはなりません. 手続きpの本体で式(p)を呼び出しているので, 式(p)を評価すると式(p)を評価し続けるため, 解釈系は停止しません.

作用的順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 引数である0と(p)を評価します.
3. 式(p)を評価すると無限ループに入ります.
4. その結果, 解釈系は停止しません.

正規順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 手続きの定義に従いif式に展開します.
   (if (= 0 0) 0 (p))
3. if式は特殊形式であるため, まず述語部分を評価します.
4. 述語部は(= 0 0)であるためtrueとなります.
5. 述語部がtrueであるため, 帰結部のみが評価されます.
6. 帰結部は0であるため, 0を返します.

引数yの値は式(p)ですがif式の代替部に相当し, 述語部がtureとなるため評価されません. そのため、解釈系が正規順序で評価するのであれば, 無限ループに入らず評価結果として0を返します.

[SICP] 問題 1.04 : 合成式を演算子として使う

われわれの評価モデルは, 演算子が合成式である組合せでも使えることを観察せよ. それに従って, 次の手続きの振舞いを述べよ.

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

問題文の手続きをエディタに入力します.

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

「+」などの演算子が入る箇所にif式が入っているので、奇妙な感じがします. この手続を評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (a-plus-abs-b 4 3)
7
> (a-plus-abs-b 4 -3)
7
> 

評価結果から, aにbの絶対値を加えていることが分かります. こういう事ができるからといって, 何が嬉しいのかは今の時点ではよくわかりませんが, テキストを読み進めると, こういうことができないと苦労する例が出てきます＼(^o^)／