オンラインSICP読書女子会 #9

[オンラインSICP読書女子会 #9 (1.3.2〜1.3.3)](http://ladiespp.connpass.com/event/29523/)

前回(#8)は読みなおし回でまとめは省略.
前々回: [オンラインSICP読書女子会 #7](http://ladiespp.connpass.com/event/29144/) (1.3.1 ~ 1.3.2), [自分のまとめ](http://qiita.com/hio-harp/items/2f6ddd6de3ebf172af67)

# 1.3.2 ~ 1.3.3 (練習問題1.34~1.36) 

`lambda` と `let` ようやくつかえる！ヾ(＞ω＜*)ノ"の回

## 1.3.2 `lambda` を使って手続きを構築する

`let` の束縛の右辺値が, 同じ `let` 文で先に束縛した変数使うことはなくて, 常にその `let` 文の外側のスコープにある変数を参照するのちょっと不思議な感じ・ω・`

```scm
; [sec-1.3.2]
(define (sec-1.3.2)
	(let ((expr '(* 8 (pi-sum 1 1000))))
		(print expr " = " (eval expr (interaction-environment))))
	(let ((expr '(integral cube 0 1 0.001)))
		(print expr " = " (eval expr (interaction-environment))))
	(let ((expr '((lambda (x y z) (+ x y (square z))) 1 2 3)))
		(print expr " = " (eval expr (interaction-environment))))

	(let ((x 2))
		(let
			((x 3) (y (+ x 2)))
			(print (* x y))))
	#t
	)


(define (pi-sum a b)
	(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
		a
		(lambda (x) (+ x 4))
		b))


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


; []
(define (cube x) (* x x x))

; [ex-1.30]
(define (sum term a next b)
	(define (iter a result)
		(if (> a b)
			result
			(iter (next a) (+ result (term a)))))
	(iter a 0))
```

```scm
gosh> (sec-1.3.2)
(* 8 (pi-sum 1 1000)) = 3.139592655589782
(integral cube 0 1 0.001) = 0.24999987500000073
; lambda 式をそのまま演算子に使う例.
((lambda (x y z) (+ x y (square z))) 1 2 3) = 12
; 変数名の解決スコープの例.
12
#t
```

## ex-1.34. `(f f)` の実行結果

予想:

```scm
(f f)
==> ; (define (f g) (g 2))
==> (f 2)
==> ; (define (f g) (g 2))
==> (2 2)
==> 数値は演算子になれないのでエラー
```

実際:

```scm
gosh> (ex-1.34)
*** ERROR: invalid application: (2 2)
```


## 1.3.3 汎用手法としての手続き

## 区間二分法によって方程式の根を求める

> 脚注56: これは、ひとつの引数を取り、それをエラーメッセージとして表示する error を使って達成できます。

といいつつ `(error "Values are not of opposite sign" a b)` って引数3つとってる…?

> (原文) This is can be accomplished using `error`, which takes as arguments a number of items that are printed as error messages.

「エラーメッセージとして表示されるいくつかの値を引数として受け取る `error` を使って達成できます。」の誤訳ぽい.

```scm
; [sec-1.3.3-a]

(define (sec-1.3.3-a)
	(let ((expr '(half-interval-method sin 2.0 4.0)))
		(print expr " = " (eval expr (interaction-environment))))

	(let ((expr '(half-interval-method
			(lambda (x) (- (* x x x) (* 2 x) 3))
			1.0 2.0)))
		(print expr " = " (eval expr (interaction-environment))))

	#t)

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


(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 (average a b) (/ (+ a b) 2))
```

```scm
gosh> (sec-1.3.3-a)
(half-interval-method sin 2.0 4.0) = 3.14111328125
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0) = 1.89306640625
#t
```

## 関数の不動点を求める

> tolerance - 3. 許容範囲、許容差、許容誤差、公差、許容値
> http://eow.alc.co.jp/search?q=tolerance

ふむふむ・ω・*

```scm
; [sec-1.3.3-b]

(load "./sec-1.3.3-a")


(define (sec-1.3.3-b)
	(let ((expr '(fixed-point cos 1.0)))
		(print expr " = " (eval expr (interaction-environment))))

	(print "; y = sin y + cos y")
	(let ((expr '(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0)))
		(print expr " = " (eval expr (interaction-environment))))

	(print "; sqrt by fixed-point")
	(let ((expr '(sqrt-by-fixed-point 5.0)))
		(print expr " = " (eval expr (interaction-environment))))

	#t
	)

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


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

```scm
gosh> (sec-1.3.3-b)
(fixed-point cos 1.0) = 0.7390822985224024
; y = sin y + cos y
(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0) = 1.2587315962971173
; sqrt by fixed-point
(sqrt-by-fixed-point 5.0) = 2.236067977499978
#t
```

## ex-1.35. 黄金比 $\phi$ の値

> $\phi$ は黄金比 (golden ratio) で、次の等式を満たします。
> $\phi^2 = \phi + 1$.
> (1.2.2 木の再帰 より)

$\phi \ne 0$ であると仮定すると, 両辺を $\phi$ で割ると $\phi = 1 + \frac{1}{\phi}$ を得る.
けれどなんで不動点…？＝ｘ＝；

```scm
; [ex-1.35]

(load "./sec-1.3.3-b")


(define (ex-1.35)
	(let ((expr '(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)))
		(print expr " = " (eval expr (interaction-environment))))

	#t
	)
```

```scm
gosh> (ex-1.35)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) = 1.6180327868852458
#t
```

## ex-1.36. `fixed-point` 関数の処理のトレース

```scm
; [ex-1.36]

(load "./sec-1.3.3-b")


(define (ex-1.36)
	(define (calc-next-simple f guess)
		(f guess))
	(define (calc-next-avg-damping f guess)
		(average guess (f guess)))

	(define (run calc-next)
		(let ((result (trace-fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0 calc-next)))
			(display "result = ")
			(display result)
			(newline)))

	(display "; with calc-next-simple")
	(newline)
	(run calc-next-simple)
	(display "; with calc-next-avg-damping")
	(newline)
	(run calc-next-avg-damping)
	#t
	)


; (from sec-1.3.3-b)
(define (trace-fixed-point f first-guess calc-next)
	(define (close-enough? v1 v2)
		(<
			(abs (- v1 v2))
			tolerance))
	(define (try guess)
		(display "guess = ")
		(display guess)
		(newline)
		(let ((next (calc-next f guess)))
			(if (close-enough? guess next)
				next
				(try next))))
	(try first-guess))
```

```scm
gosh> (ex-1.36)
; with calc-next-simple
guess = 2.0
guess = 9.965784284662087
guess = 3.004472209841214
guess = 6.279195757507157
guess = 3.759850702401539
guess = 5.215843784925895
guess = 4.182207192401397
guess = 4.8277650983445906
guess = 4.387593384662677
guess = 4.671250085763899
guess = 4.481403616895052
guess = 4.6053657460929
guess = 4.5230849678718865
guess = 4.577114682047341
guess = 4.541382480151454
guess = 4.564903245230833
guess = 4.549372679303342
guess = 4.559606491913287
guess = 4.552853875788271
guess = 4.557305529748263
guess = 4.554369064436181
guess = 4.556305311532999
guess = 4.555028263573554
guess = 4.555870396702851
guess = 4.555315001192079
guess = 4.5556812635433275
guess = 4.555439715736846
guess = 4.555599009998291
guess = 4.555493957531389
guess = 4.555563237292884
guess = 4.555517548417651
guess = 4.555547679306398
guess = 4.555527808516254
guess = 4.555540912917957
result = 4.555532270803653
; with calc-next-avg-damping
guess = 2.0
guess = 5.9828921423310435
guess = 4.922168721308343
guess = 4.628224318195455
guess = 4.568346513136242
guess = 4.5577305909237005
guess = 4.555909809045131
guess = 4.555599411610624
guess = 4.5555465521473675
result = 4.555537551999825
#t
```

だいぶ少なくなってる！
最初のだと前後に揺れながら収束していくけれど, 平均緩和法を使っている方は最初の1回目以降は単調に収束していってる感じ。

```py
>>> 4.555532270803653 ** 4.555532270803653
999.99135793123617
>>> 4.555537551999825 ** 4.555537551999825
1000.0046472054871
```

$-0.0086\dots$ から $+0.0046\dots$ になってるので誤差も減ってそうな感じ. (これはたまたまかも)