SICPを読む_(11)1章_手続きによる抽象の構築(p37-44)

ということで1ヶ月と少しぶりです。SICPの続きです。

前回までで何処までやったかすっかり忘れていますが、37ページ付近まで書いたみたいなので頑張って1章終了まで持っていきます。

1.3.3一般的方法としての手続き(p37~40)

この節で、関数の零点と不動点を探す一般的方法を例にとって、手続きとして直接表現する方法を学ぶ。
(この先、零点だの不動点だの出てきますが、あやぴーは数学パワー低いので数学的な部分に関してはあまり触れないと思いますが、ご了承願いたい)

区間二分法による方程式の零点の探索

区間二分法は方程式f(x)=0の音を探す単純かつ強力な方法
二点a,bがf(a)<0
必要なステップ数はθ(log(L/T))

ということで、例をそのまま書いてみる。

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
	midpoint
	(let ((test-value (f midpoint)))
	  (cond ((positive? test-value)
		 (search f neg-point midpoint))
		((negative? test-value)
		 (search f midpoint pos-point))
		(else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
	(b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
	   (search f a b))
	  ((and (negative? b-value) (positive? a-value))
	   (search f b a))
	  (else
	   (error "Values are not of opposite sign" a b)))))

close-enough?で許容誤差範囲内か確認していますね。
half-interval-methodは関数fと数値a,bを取りa,bが0を挟む場合のみ、searchにかけています。
searchの内容は難しくないので大丈夫ですね！

関数の不動点の探索

xがf(x)=xを満たすときにxを関数fの不動点という。らしいです。
ある関数fについて、最初の予測値からはじめ、fを値があまり変わらなくなるまで繰り返し作用させることで、不動点を見つけることができる

これも書いてあるのは簡単。

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

問題1.35

黄金比Φ^2=Φ+1からx|→1+1/xらしい??ので

(fixed-point (lambda (x) (+ 1 (/ 1 x)))
	     1.0)

問題1.36

fixed-pointを書きなおしてこう

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

問題1.37、1.38、1.39

ごめんなさい。意味がよく分からないのでパス…＞＜

1.3.4値として返される手続き(p41~44)

手続きを返すっていうお話。

本文中にあるように

(define (average-damp f)
  (lambda (x) (average x (f x))))

((average-damp square) 10.0)

これは手続きfを受け取った結果として

(lambda (x) (average x (f x)))

という手続きを返す仕組みになっている。

というのを押さえて(?)Newton法の話

Newton法

gが関数でdxが微小なら、gの微分Dgはxにおけるその値が
Dg(x) = (g(x + dx) - g(x)) / dx
で表すことができるので、Schemeで書きなおして、こう

(define dx 0.00001)

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

で、Newton法がこう
f(x) = x - g(x) / Dg(x)
なので、deriv手続きを使ってこう書ける

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

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

らしいです。

抽象と第一級手続き

合成手続きは計算の一般的方法がプログラム言語の確かな要素として表せるが故に、極めて重要な抽象機構となっている。
また高階手続きがあると、更なる抽象を作り出すためにこれらの一般的方法が操作出来るようになる。
Lispには手続きに完全な第一級身分を与えたため、表現力が高くなった。

他の通常の言語(CとかJavaとか)と違って、手続きを受け取ったり渡したりというのがシンプルに記述できる表現力は、とても魅力的ですよね。

問題1.40、1.44、1.45、1.46

分かる気がしなかったので、とりあえず飛ばしました。。。

問題1.41、1.42、1.43

GitHubに回答上げてるのでそちらで＞＜ => ayato0211/SICP

ということで、駆け足ですけど第一章終了ってことで。
次からは第2章のデータによる抽象の構築です。数学的に難しい、というか今までタッチしたことないようなところは理解し難いので、後でゆっくり読みなおした時に解けたらいいなと思います。

ここまでの感想

手続きによる抽象化が僕の触ってきていたJavaとは比較できないくらい簡単に書けるのが嬉しい
手続きを渡したり、受け取ったりできるので、重複したコードが少なくなる(この部分だけしか違いないんだけどなーが簡単に表現できる)

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ