1.1 プログラムの要素 - 道ばたに仰ぐ

手続きとデータがそれほど違わないというのは，P164の脚注に書いてある。手続きをデータのように見ることも，データを手続きのように見ることもできるというわけだ。

1.1.1 式

1.1.2 名前と環境

名前とオブジェクトの対が環境。

1.1.3 組み合わせの評価

1.1.4 合成手続き

1.1.5 手続き作用の置き換えモデル

ふつける *1によると、簡約とは、関数の適用を定義で置き換えること。
正規順序(normal-order)の評価は、完全に定義を展開して簡約することで、引数の評価は展開後に行われる。正規順序の評価は最外簡約ともいうらしい。
作用的順序の評価は、引数を先に評価してから作用させる。C,Java,Schemeなどほとんどの言語はこっちの順序で行う。これは最内簡約ともいうらしい。

1.1.6 条件式と述語

問題1.1

Schemeプログラムの構文がどのような意味を持つかの確認。

10 => 10
(+ 5 3 4) => 12

(- 9 1) => 8

(/ 6 2) => 3

(+ (* 2 4) (- 4 6)) => 6

(define a 3) => a  (これは処理系により変わりそう)

(define b (+ a 1)) => b

(+ a b (* a b)) => 19

(= a b) => #f

(if (and (> b a) (< b (+ a b)))
  b
  a) => 4

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25)) => 16

(+ 2 (if (> b a) b a)) => 6

(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1)) => 16

問題1.2

S式に慣れましょうという問題だ。

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))
=> -37/150

問題1.3

手続きを定義する練習。

; ver1
(define (f x y z)
  (cond
   ((and (>= x z) (>= y z)) (+ (* x x) (* y y)))
   ((and (>= y x) (>= z x)) (+ (* y y) (* z z)))
   (else (+ (* z z) (* x x)))))
; ver2
(define (sum-of-sqr x y) (+ (* x x) (* y y)))
(define (f x y z)
  (if (> x y)
      (sum-of-sqr x (if (> y z) y z))
      (sum-of-sqr y (if (> x z) x z))))

問題1.4

bが0より大きい場合は(+ a b)が返り値となる.そうでない場合は、(- a b)が返り値となる。これは、(+ a (abs b))の結果と等しい.

問題1.5

(define (p) (p))は無限ループになっており、この間数が評価されると応答が帰らなくなる。正規順序の評価を使う解釈系では、(test 0 (p))は即座に0が返される.なぜなら、正規順序では引数の式は値が必要となるまで評価されないからである。この場合は、(= x 0)が真となるので、y、つまり(p)は評価されない。作用的順序の評価を使う解釈系では、引数は関数適用の前に評価されるので(p)が評価され、無限ループに陥る.

正規順序では

(test 0 (p))
==> (if (= 0 0) 0 (p))
==> (if #t 0 (p))
==> 0

作用的順序では

(test 0 (p))
==> 0 と (p) が評価される
==> 無限ループ

1.1.7 例: Newton法による平方根

平方根を求めるにはNewton法を通常使うらしい。Newton法はあとでまたでてくるのでここでは深く考えない。

xの平方根を求めるNewton法アルゴリズムは

予測値aを決める
aが終了条件を満たしていればaを結果として終了
x/aとaの平均を次の予測値として2へ

問題1.6

good-enough?が#tを返しても、常にsqrt-iterが評価されるので無限ループになる。

問題1.7

非常に小さい数の場合、xが0.001未満の場合終了条件は
$guess < \sqrt{x + 0.0001}$
になる。guessは常に0以上だ。xが非常に小さくなっても、guessが
$0 \leq guess < \sqrt{0.0001} \approx 0.031622$
になると終了してしまう。たとえば、x=0の時には、guess = 0.03125で終了し、理論値の0からの相対誤差が大きくなる。

非常に大きい数の場合、浮動小数点計算の有効桁が減ってしまいimproveでの変化が終了条件(x ± 0.001)を満たさなくなることがある.倍精度浮動小数点数の仮数部は52ビットであって、
$\frac{2^{42}}{2^{52}} = 0.000965$
$\frac{2^{43}}{2^{52}} = 0.0019$
となり、(sqrt $2^{43}$ )は無限ループになる. ちなみに、 $2^{44}$ は終了条件を満たすので無限ループにならない。

終了テストの改良
前回の予測値と次の予測値の変化が0.001未満であったならば終了する。これで、xが非常に小さい、非常に大きい場合もうまく動作するようになった。

(define (sqrt x)
  (define (good-enougth? pre guess)
    (< (abs (- guess pre)) 0.001))
  (define (improve guess)
    (/ (+ guess (/ x guess)) 2))
  (define (sqrt-iter pre guess)
    (if (good-enougth? pre guess)
        guess
        (sqrt-iter guess (improve guess))))
  (sqrt-iter 1.0 (improve 1.0)))
;; sqrt-iterの初期値は xでもOK。なぜならば、
;; 初期値はx=1.0以外においてgood-enough?が#fを返せば良い.
;; xならばx=1.0のときに、即座に終了するのでいいだろう.

問題1.8

(define (cubert x)
  (define (good-enough? pre-guess guess)
    (< (abs (- guess pre-guess)) 0.001))
  (define (improve guess)
    (/ (+ (/ x (* guess guess)) (* 2 guess))
       3))
  (define (cubert-iter pre-guess guess)
    (if (good-enough? pre-guess guess)
        guess
        (cubert-iter guess (improve guess))))
  (cubert-iter 1.0 x))

1.1.8 ブラックボックス抽象としての手続き

*1:asin:4797336021