hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。
1 手続きを用いた抽象化の構築
この本で紹介されるコードは全てLispの方言であるSchemeで記述されています。なぜこんなマイナーな言語を使うのか？
これらの特性の中でも最も意義深いものは、プロセスのLispによる記述(これは手続き(procedure)と呼ばれます)が、それ自身Lispのデータとして表され、操作できるということです。
つまり、Lispには「手続き」と「データ」との間の区別がないという特性があり、これが高い柔軟性を生んでいる。乱暴に言うと、何らかのデータを計算して生成するプログラムが作れるんだから、プログラムを生成するプログラムだって作れる。
1.1.5 手続き適用の置換モデル
(define (square x) (* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
と、定義されていたとして・・・
以下のように展開されるのが、適用順序評価。
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10)
(+ 36 100)
136
以下のように展開されるのは、正規順序評価。
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136
普通は適用順序評価が採用される、よね。
適用順序評価のほうが効率はいい。例えば(+ 5 1)を何度も計算せずにすむ。
しかし実行結果は変わらないはず・・・と思いきや、練習問題1.5を見よ。
練習問題1.1
以下の式に対するインタプリタの応答は？
自明だけどさぼらずやろう。
gosh> 10
10
gosh> (+ 5 3 4)
12
gosh> (- 9 1)
8
gosh> (/ 6 2)
3
gosh> (+ (* 2 4) (- 4 6))
6
gosh> (define a 3)
a
gosh> (define b (+ a 1))
b
gosh> (+ a b (* a b))
19
gosh> (= a b)
#f
gosh> (if (and (> b a) (< b (* a b))) b a)
4
gosh> (cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
16
gosh> (+ 2 (if (> b a) b a))
6
gosh> (* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
16
練習問題1.2
以下の式を前置記法に置き換えよ。
数式を書く練習。
\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}
gosh> (/ (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5))))))
(* 3 (- 6 2) (- 2 7)))
-37/150
練習問題1.3
３つの引数をうけとり、そのうち大きい２つの２乗の和を返す手続き。
(define (ex_1_3 x y z)
(cond ((and (< x y) (< x z)) (sum-of-squares y z))
((and (< y x) (< y z)) (sum-of-squares x z))
(else (sum-of-squares x y))))
練習問題1.4
演算子が複合式であるような以下の例。そのふるまいを説明せよ。
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
正規順序評価での展開例を示す。
引数bが正数ならば
(a-plus-abs-b 5 2)
((if (> 2 0) + -) 5 2)
(+ 5 2)
7
負数ならば
(a-plus-abs-b 5 -2)
((if (> -2 0) + -) 5 -2)
(- 5 -2)
7
引数bが正数なら+、負数なら+と、呼ばれる演算子が動的に決定される。
練習問題1.5
以下のコードは、適用順序評価と正規順序評価とで、異なる結果になるのだとか。
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
(test 0 (p))
それぞれ展開してみよう。まずは適用順序評価。
(test 0 (p))
(test 0 (p))
(test 0 (p))
...
(p)を評価すると(p)なので無限ループに。実際、Gaucheで実行すると固まる。
正規順序評価ならば。
(test 0 (p))
(if (= 0 0) 0 (p))
0
ifは特殊形式なので、条件句が真ならば(p)は評価されない。