SICP 読み (4)

新年を無事に迎える。昨晩は遅かったんですが、がき達が異様な早起きで仕方が無いので本読みを。(と、言いつつ着手は結局晩だったり)
問題 1.19 はスルー。別途、暇を見つつ着手はしたいです。年内中に 1.2 節が終われば、と思ってたなぁ、と思いつつ 1.2.5 節をぱらぱらっと眺めているんですが、ここは別途に、とゆー事にしてスルーを決定。面白そうだけに違う瞬間での現実トウヒに効果的に使える (?) かな、と。

問題 1.30

1.29 はスルーで、できれば別途。ただし「積分」なナニを再度学習する必要あり。
で、実装は以下で OK のはず。

(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (+ result (term a)))))
  (iter a 0))

これ式の書き換えは簡単にできるようになったんですが、数学なソレが (以下略

問題 1.31

ここから 1.33 まではスルーしちゃ駄目な感じ。なんとなく 1.3 節の完了で冬休みが終わればラッキーなナニと言っても過言ではないかも。
まず、a ですが、ある範囲の積を返す手続きを product が返せば良いのかな。
factorial な定義は確か以下。

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
	product
	(fact-iter (* counter product)
		   (+ counter 1)
		   max-count)))
  (fact-iter 1 1 n))

あるいは例示されている pi-sum の実装を。

(define (pi-sum max)
  (let f ((s 3) (e max) (result 1))
    (if (> s e)
	(* 4 result)
	(f (+ 2 s) e 
	   (* result (* (/ (- s 1) s) (/ (+ s 1) s)))))))

くそ。つい癖で、ですね。factorial の定義にアワせてみます。(result の初期値が 1 って微妙??)

(define (pi-sum max)
  (define (iter s e result)
    (if (> s e)
	(* 4 result)
	(iter (+ 2 s) e
	      (* result (* (/ (- s 1) s) (/ (+ s 1) s))))))
  (iter 3 max 1))

共通したナニを整理してみれば良いのかな。

• ui な引数は一個で処理終了な目印を指定
• 内部定義なメソドの引数は三つでこれも意味的に同様
  • sum な例では初期値と最終値は引数指定しているな
• 終了判定した時に返却するナニが微妙に違うが、意味的には一緒と考えて OK
• カウンタ増分と処理結果へ積算する値の計算方法は異っている

まず、上記を元に factorial を返す product を考えてみる。lambda を返せば良いんだよな。

(define product
  (lambda (n)
    (define (fact-iter product counter max-count)
      (if (> counter max-count)
	  product
	  (fact-iter (* counter product)
		     (+ counter 1)
		     max-count)))
    (fact-iter 1 1 n)))

こんなんでも大丈夫か (ただし引数限定

(define (product n)
  (lambda ()
    (define (fact-iter product counter max-count)
      (if (> counter max-count)
	  product
	  (fact-iter (* counter product)
		     (+ counter 1)
		     max-count)))
    (fact-iter 1 1 n)))

整理したソレを元に共通化してみるか。

(define (product init term next)
  (lambda (max)
    (define (iter c result)
      (if (> c max)
	  result
	  (iter (next c) (* (term c) result))))
    (iter init 1)))

動作確認を。

guile> (define factorial (product 1 (lambda (x) x) (lambda (x) (+ x 1))))
guile> (factorial 6)
720
guile>

ここまでやって分かったんですが、ちょっと何かが違うな。sum は手続きを返しているとゆーよりもテンプレート的に見える。上記の解だと max しか設定できませんが、sum の例だと初期値と最大値の指定が可能だな。修正してみる。(1 返却がなんか微妙)

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product term (next a) next b))))

動作を。

guile> (define (factorial a b) (product (lambda (x) x) a (lambda (x) (+ x 1)) b))
guile> (factorial 1 6)
720
guile> 

一応正常動作な模様。反復なソレにしておこう。

(define (product term a next b)
  (let f ((a a) (result 1))
    (if (> a b)
	result
	(f (next a) 
	   (* result (term a))))))

これもとりあえず factorial な動作確認を。

guile> (define (factorial a b) (product (lambda (x) x) a (lambda (x) (+ x 1)) b))
guile> (factorial 1 6)
720
guile> 

次は例示された pi-sum を。

(define (pi-sum a b)
  (product (lambda (x) (* (/ (- x 1) x) (/ (+ x 1) x)))
	   a
	   (lambda (x) (+ x 2))
	   b))

試験。

guile> (* 4 (pi-sum 3 1000))
3.14316384241919
guile> 

試験において出てくる数値が微妙で emacs の scratch で一旦入力して guile にコピペしたら上記の通り動作。何が悪いのか、と guile のコンソールを睨みたおしてたら next な引数の指定で (lambda (x) (+ x 3)) としているのを発見。いかんなぁ。
しかも a と b を分けて、と思ってたんですが夢中になって色々試している内に、反復版と再帰版を作成している。でも再帰版の試験はしてないのかな。

て、再帰版で pi-sum の動作試験したら stack-overflow って orz

ため息をつきつつ一服していて stack を突き破っている事に気がつく。

guile> (pi-sum 3 1000)
ERROR: Stack overflow
ABORT: (stack-overflow)
guile> (pi-sum 3 100) 
0.78933492230439
guile> (* 4 (pi-sum 3 100))
3.15733968921756
guile> 

一応、lambda なソレも動作確認をしておく。

(define (product term next)
  (lambda (init max)
    (define (iter c result)
      (if (> c max)
	  result
	  (iter (next c) (* (term c) result))))
    (iter init 1)))

動作確認を。

guile> (define pi-sum (product (lambda (x) (* (/ (- x 1) x) (/ (+ x 1) x))) (lambda (x) (+ x 2))))
guile> (pi-sum 3 1000)
0.785790960604798
guile> (* 4 (pi-sum 3 1000))
3.14316384241919
guile> (define factorial (product (lambda (x) x) (lambda (x) (+ x 1))))
guile> (factorial 1 6)
720
guile>

今頃気がついたのですが、どちらも手続き返してるんだな。(駄目

問題 1.32 (accumulate)

うーん。a の解。

(define (accumulate combiner null-value term a next b)
  (let f ((a a) (result null-value))
    (if (> a b)
	result
	(f (next a) (combiner result (term a))))))

(define (factorial a b)
  (accumulate (lambda (x y) (* x y))
	      1
	      (lambda (x) x)
	      a
	      (lambda (x) (+ x 1))
	      b))

(define (pi-sum a b)
  (accumulate (lambda (x y) (* x y))
	      1
	      (lambda (x) (* (/ (- x 1) x) (/ (+ x 1) x)))
	      a
	      (lambda (x) (+ x 2))
	      b))

動作確認。

guile> (factorial 1 6)
720
guile> (factorial 1 3)
6
guile> (factorial 1 4)
24
guile> (factorial 1 5)
120
guile> (* 4 (pi-sum 3 1000))
3.14316384241919
guile> 

あってるのかなぁ。b も。

(define (accumulate combiner null-value term a next b)
  (let f ((a a))
    (if (> a b)
	null-value
	(combiner (term a) (f (next a))))))

(define (factorial a b)
  (accumulate (lambda (x y) (* x y))
	      1
	      (lambda (x) x)
	      a
	      (lambda (x) (+ x 1))
	      b))

(define (pi-sum a b)
  (accumulate (lambda (x y) (* x y))
	      1
	      (lambda (x) (* (/ (- x 1) x) (/ (+ x 1) x)))
	      a
	      (lambda (x) (+ x 2))
	      b))

うーん ...

guile> (factorial 1 2)
2
guile> (factorial 1 3)
6
guile> (factorial 1 4)
24
guile> (factorial 1 5)
120
guile> (factorial 1 6)
720
guile> (* 4 (pi-sum 3 500))
3.14473581546695
guile> 

一応動いてます。
# ってか凄いな。

結構アセり気味で進めてるんで、明日もっかい見てみた方が良いな。確か accumulate は数え上げ、と訳していたような記憶あり。

追記

数え上げ、は enum だな。(とほほ