アーカイブ

2015 年 2 月 のアーカイブ

SICP を読んでみる #31 第二章 p.52

2015 年 2 月 27 日 コメントはありません

問題解答

問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 数はちゃんと勉強した方がよさそうなので引き続き明日もここからやることにする。

カテゴリー: SICP タグ:

SICP を読んでみる #30 第二章 pp.50-52

2015 年 2 月 26 日 コメントはありません

問題解答

問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
カテゴリー: SICP タグ:

SICP を読んでみる #29 第二章 p.50

2015 年 2 月 24 日 コメントはありません

問題解答

問 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)

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

カテゴリー: SICP タグ:

SICP を読んでみる #28 第二章 pp.46-50

2015 年 2 月 20 日 コメントはありません

本文

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

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

カテゴリー: SICP タグ:

SICP を読んでみる #27(2) 第二章 pp.45-46

2015 年 2 月 19 日 コメントはありません

引き続き第二章へ突入。

本文

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

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

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

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

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

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

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

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

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

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

カテゴリー: SICP タグ:

SICP を読んでみる #27 第一章(完) p.44

2015 年 2 月 19 日 コメントはありません

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)))

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

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

カテゴリー: SICP タグ:

SICP を読んでみる #26 第一章 pp.31-44

2015 年 2 月 18 日 コメントはありません

昨日も一応問題に手をつけたものの、差し込み作業が入ってしまってほとんど進まなかったので今日も第一章の最後の問題二つ。
内容を見る感じ、第一章の総まとめになる内容なので、キッチリと片をつけたいものです。

1.3 おさらい

全体的に流れが把握できていない感じがしたので、1.3 のおさらいから始めました。

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

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


(define (sum-square a b)
  (define (inc x)
    (+ x 1)
  (sum square a inc b))

上のコードは lambda を使えばこのように書ける

(define (sum-square a b)
  (sum square a (lambda (x) (+ x 1)) b))

(define (sum-square a b)
  (sum (lambda (x) (* x x))  a (lambda (x) (+ x 1)) b))

square まで lambda で書いてしまうのはちょっとやりすぎ感がある

区間積分

(define (cube x)
  (* x x x))

(define dx 0.00001)
(define (integral f a b)
  (* (sum f a (lambda (x) (+ x dx) b) dx)))

(integral cube 0 1)

問1.32 accumulate

(define (accumulate combiner null-value term a next b)
  (define (iter v)
    (if (> v b)
        null-value
        (combiner (term v) (iter (next v)))))

  (* (iter (+ a (/ dx 2))) dx))

(define (integral f a b)
  (accumulate + 0 f a (lambda (x) (+ x dx)) b))

(integral cube 0 1)

関数の不動点の探索

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (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))

(fixed-point cos 1.0)

1.3.4 値として返される手続き

平均緩和のコード化

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

平均緩和付き平方根の計算
y → x/y :

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

上記は収束しないので平均緩和を使用する

y → (average-damp (x/y))

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

(sqrt 2.0)

Newton 法

微分

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

Newton 法で実装

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

Newton 法で平方根を求める

sqrt(y) = x
y^2 = x
g(x) = y^2 - x

g(x) = 0 になればよいので、Newton 法に落しこめる。

(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x)) 1.0))

(sqrt 2.0)

抽象と第一手続き

平均緩和法と Newton 法を用いた平方根の計算方法を導き出したが、これを抽象化できる

平均緩和法はこのように書かれていた :

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

Newton 法はこのように書かれていた :

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))
(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x)) 1.0))

fixed-point-of-transform を定義して、それぞれを書きなおす

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

平均緩和法 :

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

Newton 法 :

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x))
                            newton-transform
                            1.0))

問題回答

問1.45

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

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


(define (n-th-root n x k)
  (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
                            (repeated average-damp k)
                            1.0))

(n-th-root 2 2.0 1) ; OK
(n-th-root 3 2.0 1) ; OK
(n-th-root 4 2.0 1) ; NG

条件を追い切れなかったのでカンニング。

;n=2,3       はk=1で出来る. 
;n=4,5,..,7  はk=2で出来る. 
;n=8,9,...,15はn=3で出来る. 
;n=16,...    はn=4でないと出来ないらしい.

らしい。

(define (n-th-root n x)
  (let ((k (floor (/ (log n) (log 2)))))
    (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
                              (repeated average-damp k)
                              1.0)))

(n-th-root 4 2.0) ;OK

全体の流れがもやっとしていたので、1.3 を一通りおさらいしつつ問題に取り組んでみました。
おかげで前よりも理解が進んだ気がします。

これで第一章は残るところ 問1.46 の一つのみです。

カテゴリー: SICP, 未分類 タグ:

SICP を読んでみる #25 第一章 pp.43-44

2015 年 2 月 16 日 コメントはありません

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

問題解答

問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))

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

カテゴリー: SICP タグ:

SICP を読んでみる #24 第一章 p.43

2015 年 2 月 13 日 コメントはありません

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

問題解答

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

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

カテゴリー: SICP タグ:

SICP を読んでみる #23 第一章 pp.41-43

2015 年 2 月 12 日 コメントはありません

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

本文

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 回しか呼ばれないはずなのになぜ?
→解答を見ながら手で展開してみるも、挫折。明日再チャレンジしてみる。

カテゴリー: SICP タグ: