計算機プログラムの構造と解釈(SICP)

• 1.39

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

(define (cont-frac f n d k)
  (define (cont-frac-iter f n d k i)
    (if (= k i)
        (/ (n i) (d i))
        (/ (n i) (f (d i) (cont-frac-iter f n d k (+ i 1))))))
  (cont-frac-iter f n d k 1))

(define (tan-cf x k)  
  (cont-frac -
             (lambda (i) (pow x i))
             (lambda (i) (- (* i 2) 1))             
             k))

(tan-cf 1.3 1000)
;-> 3.9510575177074583

• 1.40

(define (fixed-point f first-guess)
  (define tolerance 0.0000001)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (deriv g)
  (define dx 0.00001)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (cubic a b c)
  (lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))

(newtons-method (cubic 1 2 3) 1)
;-> -1.275682203650985

((cubic 1 2 3) -1.275682203650985)
;-> 0.0

• 1.41

(define (inc x) (+ x 1))
(define (double f) (lambda (x) (f (f x))))

;(((double (double double)) inc) 5)

;(((double (lambda (x) (double (double x)))) inc) 5)

;(((lambda (x) ((lambda (y) (double (double y))) ((lambda (z) (double (double z))) x))) inc) 5)

;(((lambda (y) (double (double y))) ((lambda (z) (double (double z))) inc)) 5)

;((lambda (z) (double (double z))) inc) = Aとする

;(((lambda (y) (double (double y))) A) 5)

;((double (double A)) 5)

;((double (lambda (x) (A (A x)))) 5)

;(lambda (x) (A (A x))) = Bとする

;((double B) 5)

;((lambda (a) (B (B a))) 5)

;((lambda (a) ((lambda (x) (A (A x))) ((lambda (x) (A (A x))) a))) 5)

;ここでAを展開する。
;(lambda (c) ((lambda (b) (inc (inc b))) ((lambda (b) (inc (inc b))) c)))
;(lambda (c) (inc (inc (inc (inc c)))))

;よって
;((lambda (a) ((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) ((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) a))) 5)
;((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) ((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) 5))
;((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) 5)))
;((lambda (x) ((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) x))) ((lambda (c) (inc (inc (inc (inc c))))) (inc (inc (inc (inc 5))))))
;((lambda (c) (inc (inc (inc (inc c))))) ((lambda (c) (inc (inc (inc (inc c))))) (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))
;((lambda (c) (inc (inc (inc (inc c))))) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))))))
;(inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5))))))))))))))))

;21

;コレはすごい。
;死ぬかと思った。

(((double (double double)) inc) 5)
;-> 21

;予想通り。

;計算として考えてみることも出来る
;(double double)
;はdoubleを2回させるので 2^2=4
;(double (double double))は(double double)を2回作用させるので、
;4^2=16
;5+16=21

• 1.42

(define (square x)
  (* x x))
(define (inc x)
  (+ x 1))
(define (compose f g)
  (lambda (x) (f (g x))))

((compose square inc) 6)

;-> 49
;なんだこの簡単な問題？？

• javascript版

//久しぶりにjs版
var square = function(x){return x*x;};
var inc = function(x){return x+1;};
var compose = function(f,g){return function(x){return f((g(x)));}};
compose(square,inc)(6);
//-> 49

//jsだと少し煩雑に見える。
//functionという単語がながいのとreturnをいちいち書くのが億劫だ。
//今度function->fと最後の文がreturnされるjsを作るかｗ

• 1.43

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

(define (repeated f n)
  (lambda (x) (f (if (<= n 1)
                     x
                     ((repeated f (- n 1)) x)))))

((repeated square 2) 5)
;-> 625

;これはおもしろい、関数を再帰的につくってるｗきもいｗ
;再帰的なので、反復的にもしてみよう。
;SICPによるとcomposeを使うといいらしい。

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (define (repeated-iter f n p)
    (if (<= n 0)
        p
        (repeated-iter f (- n 1) (compose p f))))
  (repeated-iter f n (lambda (x) x)))

;((repeated square 2) 5)
;-> 625

;すばらしい。

• もう一回javascript版

//ではコレをjsでかけるのか？
//まず初めの再帰的手続き
var square = function(x){return x*x;};
var repeated = function(f,n){
  return function(x){
    return f(
      ((n<=1)?x:repeated(f,(n-1))(x))
    );
  };
};

//repeated(square,2)(5);
//-> 625
//うごいた! すげぇｗ

//では反復的なほう。

var repeated = function(f,n){
  var compose = function(f,g){return function(x){return f((g(x)));}};
  var p = function(x){return x};
  for(var i=n;i>0;i--) p = compose(p,f);
  return p;
};

//repeated(square,2)(5);
//-> 625
//うごいた。いいね。
//でもschemeの方が大分考えやすいなー

• 1.44

;問題の意味がよくわからない。

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

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (define (repeated-iter f n p)
    (if (<= n 0)
        p
        (repeated-iter f (- n 1) (compose p f))))
  (repeated-iter f n (lambda (x) x)))

;平滑化関数
(define (smooth f)
  (define d 0.0000001)
  (lambda (x) (/ (+ (f (- x (* d x))) (f x) (f (+ x (* d x)))) 3)))

;n重平滑化関数
(define (fold-smooth f n)
  ((repeated smooth n) f))

;とりあえず以上のようなものでいいのか？

;((fold-smooth square 5) 5)
;25.000000000000835

;((fold-smooth square 10) 5)
;25.000000000001666

• とりあえずここまで。
• 今回のは簡単だったなー。高階関数は結構好き。
• あと2問でやっと2章にいける（＾＾）