SICPを読む6

Programming Scheme SICP

ちょっとずつでもやり続ければそのうち終わらーな。

問題1.17から1.19
まずは例で与えられた「*」手続きを末尾再帰で書いてみる。ついでにシンタックスシュガーっぽいの使わずにlambdaだらけで。

(define *
  (lambda (x y)
    ((lambda (f a x y) (f f a x y))
      (lambda (f a x y) (if (= y 0) a (f f (+ a x) x (- y 1)))) 0 x y)))

これを1.16と同じ手法で。

(define double (lambda (x) (* x 2)))
(define halve (lambda (x) (/ x 2)))
(define *
  (lambda (x y)
    ((lambda (f a x y) (f f a x y))
      (lambda (f a x y)
        (cond
	  ((= y 0) a)
	  ((even? y) (f f a (double x) (halve y)))
	  (else (f f (+ a x) x (- y 1)))))
      0 x y)))

問題1.18
1.17でやってた。ので再帰的プロセスをこっちで書いてみる。

(define *
  (lambda (x y)
    ((lambda (f x y) (f f x y))
      (lambda (f x y)
        (cond
	  ((= y 0) 0)
	  ((even? y) (f f (double x) (halve y)))
	  (else (+ x (f f x (- y 1))))))
      x y)))

あまり変わらない。

問題1.19
[tex:T_{pq}(a, b)=*1 \\ = ((p^{'}+q^{'})a+q^{'}b, q^{'}a+p^{'}b) \\ = T_{p^{'}q^{'}}]
p^{'}= p^2+q^2,q^{'}= q(2p+q)
で、
T^{2k}_{pq}(a, b) = T_{p^{(k)}q^{(k)}}が成り立つと仮定する。んでk+1の時にもごにょごにょ帰納法。
ちなみにp^{''} = p^{(2)}, p^{'''} = p^{(3)}ということです。
コードは

(define (fib n)
  (letrec 
    ((f (lambda (a b p q c)
        (cond
          ((= c 0) b)
          ((even? c) (f a b (+ (* p p) (* q q)) (* q (+ p p q)) (/ c 2)))
          (else (f (+ (* (+ p q) a) (* q b)) (+ (* q a) (* p b)) p q (- c 1)))))))
    (f 1 0 0 1 n)))

letrecで。なんか落ち着かない。lambdaで書いた方が安心するけど慣れればletrecの方が楽だと思う。

*1:p+q)a+qb, qa+pb)]と。なんかテキストの方では妙なくくり方しててわかりにくいですが。で、まあこれは再帰的に証明すれば良さげ。 [tex:T^2_{pq}(a, b) = T_{pq}T_{pq}(a, b) \\ = T_{pq}((p+q)a+qb, qa+pb) \\ = ((p+q)((p+q)a+qb)+q(qa+pb), q((p+q)a+qb)+p(qa+pb

test