問題解答

問2.5

(define (icons a b)
  (* (expt 2 a) (expt 3 b)))

(define (icar v)
  (define (iter t)
    (if (= (gcd t 3) 1)
        t
        (iter (/ t 3))))

  (log (iter v) 2))

(define (icdr v)
  (define (iter t)
    (if (= (gcd t 2) 1)
        t
        (iter (/ t 2))))

  (log (iter v) 3))

(define v (icons 5 8))
(icar v)
(icdr v)

gosh> 5.0
gosh> 8.0

整数で与えているのに浮動小数になってしまっているのが気に入らない。
log を使わずに、地道に徐余を求めながら割っていく方がいいっぽい。

問2.6
置換えを使っての展開が全然できない。。。。
そもそも Church 数がわけわからないので先人の知恵を拝借。

この問題、さくっと載ってるけどかなり大事なことを表そうとしている感じ。 Church 数はちゃんと勉強した方がよさそうなので引き続き明日もここからやることにする。

問題解答

問2.3
対角上の二点を指定する方法で表現。

(define (make-rectangle lb rt)
  (cons lb rt))

(define (rect-lb rect)
  (car rect))

(define (rect-rt rect)
  (cdr rect))

(define (w rect)
  (- (x-point (rect-rt rect)) (x-point (rect-lb rect))))

(define (h rect)
  (- (y-point (rect-rt rect)) (y-point (rect-lb rect))))

(define (perimeter rect)
  (* (+ (w rect) (h rect)) 2))

(define (area rect)
  (* (w rect) (h rect)))

(define rect (make-rectangle (make-point 0 0) (make-point 1 1)))
(display (perimeter rect))
(display (area rect))

基点と幅、高さを指定する方法で表現

(define (make-rectangle base w h)
  (cons base (cons w h)))

(define (w rect)
  (car (cdr rect))

(define (h rect)
  (cdr (cdr rect))

(define rect (make-rectangle (make-point 0 0) 1 1))
(display (perimeter rect))
(display (area rect))

構成子と選択子は表現にあわせて用意し、計算は共通のものを使用できている。

本文

2.1.3 データとは何か
cons, car, cdr を実装してみる。 cons で手続きを返すことで実現。

問題

問2.4

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

(car (cons 1 2))
(cdr (cons 1 2))

置換えモデルを使用して動作を確認

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
1

問題解答

問 2.2

(define (make-point x y)
  (cons x y))

(define (x-point point)
  (car point))

(define (y-point point)
  (cdr point))

(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment segment)
  (car segment))

(define (end-segment segment)
  (cdr segment))

(define (midpoint-segment segment)
  (make-point (/ (+ (x-point (start-segment segment))
                    (x-point (end-segment segment))) 2)
              (/ (+ (y-point (start-segment segment))
                    (y-point (end-segment segment))) 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(define p1 (make-point 0.0 0.0))
(define p2 (make-point 1.0 1.0))
(define s (make-segment p1 p2))
(define m (midpoint-segment s))
(print-point m)

これは手を動かすだけなので簡単だった。

本文

2.1.1 有理数の算術演算

cons を使用して対(pair)を作ることができる

(define x (cons 1 2))
(car x)
(cdr x)

問題解答

問2.1

(define (make-rat n d)
	(let ((sign (/ (* n d) (* (abs n) (abs d))))
				(g (gcd (abs n) (abs d))))
		(cons (* sign (/ (abs n) g)) (/ (abs d) g))))

(define v (make-rat  1  2))
(print-rat v)
(define v (make-rat -1  2))
(print-rat v)
(define v (make-rat  1 -2))
(print-rat v)
(define v (make-rat -1 -2))
(print-rat v)

何だかイケテナイ感。参考解答だとこんな感じ。

(define (make-rat n d)
  (let ((g (abs (gcd n d))))
     (if (< d 0)
         (cons (/ (- n) g) (/ (- d) g))
         (cons (/ n g) (/ d g)))))

うむ。たしかにー。

本文

2.1.2 抽象の壁
データを扱う際に、対象のレイヤ毎に抽象化をおこない、インターフェースを通して対象を操作することでプログラムの修正・維持が楽になったり柔軟性を保ち続ける助けになる。

今日はここまで。うーん、ちょっとよそ事をしたりダラダラしてしまって時間を無駄にしている。
もっと時間を有効に使わないと。

引き続き第二章へ突入。

本文

2 データによる抽象の構築

合成データオブジェクト:
単純なデータだけでは、ものごとを表現することが大変なので、複数のデータを組み合わせて一つの塊として扱うことができるようにする

データ抽象:
合成データを使用してプログラムの部品度を増やし、プログラム本体とデータの扱いをする部分に分離する

合成データを形成する鍵:

• 閉包(closure)
• 公認インターフェース

言語の表現力→記号式を使って論じる

プログラムの場所によって異なった表現をされているデータの扱い→汎用演算

• データ主導プログラミングの導入

2.1 データ抽象入門
データ抽象: 合成オブジェクトの使い方を基本データの細部から分離して抽象化する

“2.1.1 有理数を扱う算術演算”はちょっと長そうなので今日はここまで。

SICP 第一章も最後の問題。サクサクいきます。

問題解答

問1.46

(define (iterative-improbe iterator checker)
  (lambda(x) (let ((next (iterator x)))
               (if (checker x next)
                   next
                   ((iterative-improbe iterator checker) next)))))

(define tolerance 0.00001)
(define (fixed-point f)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  ((iterative-improbe f close-enough?) 1.0))

(fixed-point cos)


(define (average v1 v2)
  (/ (+ v1 v2) 2))
(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y)))))

(sqrt 2)

とりあえずできたけど、三角い感じがする。答えあわせをすると随分スッキリ書かれている。

(define (iterative-improve test improve)
  (lambda (g)
    (define (iter g)
      (if (test g) g
          (iter (improve g))))
  (iter g)))

。。。と思ったけど、やっていることは変わらないっぽい。
問題はとりあえずできたけど、まだまだヨチヨチ歩き感がある感じ。

何はともあれ、第一章終了～。ぱちぱちぱちぱち。

第一章も遂に最後のページで、あとは問題を残すのみ。今日中におわれるか?

問題解答

問1.42

(define (inc x) (+ x 1))
(define (square x) (* x x))

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

((compose square inc) 6)

問1.43

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

  (it n))

((repeated square 2) 5)

ヒントにある compose を使っていない&無駄な it を定義していた。回答では以下のようになっていた。

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

((repeated square 2) 5)

問1.44

(define (n-fold-smooth f n)
  ((repeated smooth n) f))

今日はここまで。最後の二問は明日に持ち越し。

昨日追い切れなかった問題 1.41 からの続き。

問題解答

問1.41
結局、自力で完全に展開するのは無理だったので答えを写経しながら展開。それでも必ずどこかで間違える。

まあ、大体の流れは把握できたので OK とする。

休日やら差し込み仕事やらで気づいたら間が結構空いてしまいました。気を取り直して再開。

本文

1.3.4 値として返される手続き
不動点の探索、平均緩和法、y→x/y を使って平方根や立方根を求めるコードを導き出している。

Newton 法
1.1.7 の例と比べると格段にシンプルな記述になっている。

抽象と第一級手続き

問題解答

問1.40

(define (cubic a b c)
  (newtons-method (lambda (x)
                    (+ (* x x x) (* a x x) (* b x) c))
                   1.0))

こんな感じ?

問1.41

(define (double f)
  (display f)(newline)
  (lambda (x) (f (f x))))

(define (inc x)
  (display x)(newline)
  (+ x 1))

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

実行すると 16 回 inc が呼ばれるが、8 回しか呼ばれないはずなのになぜ?
→解答を見ながら手で展開してみるも、挫折。明日再チャレンジしてみる。