hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

#1 手続きを用いた抽象化の構築

この本で紹介されるコードは全てLispの方言であるSchemeで記述されています。なぜこんなマイナーな言語を使うのか？

これらの特性の中でも最も意義深いものは、プロセスのLispによる記述(これは手続き(procedure)と呼ばれます)が、それ自身Lispのデータとして表され、操作できるということです。

つまり、Lispには「手続き」と「データ」との間の区別がないという特性があり、これが高い柔軟性を生んでいる。乱暴に言うと、何らかのデータを計算して生成するプログラムが作れるんだから、プログラムを生成するプログラムだって作れる。

#1.1.5 手続き適用の置換モデル

1.1.5.0.scm

(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))

と、定義されていたとして・・・

以下のように展開されるのが、適用順序評価。

1.1.5.1.scm

(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10)
(+ 36 100)
136

以下のように展開されるのは、正規順序評価。

1.1.5.2.scm

(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

以下の式に対するインタプリタの応答は？
自明だけどさぼらずやろう。

ex1.1.scm

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

ex1.2.scm

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

####練習問題1.3

３つの引数をうけとり、そのうち大きい２つの２乗の和を返す手続き。

ex1.3.scm

(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

演算子が複合式であるような以下の例。そのふるまいを説明せよ。

ex1.4.scm

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

正規順序評価での展開例を示す。
引数bが正数ならば

ex1.4.answer1.scm

(a-plus-abs-b 5 2)
((if (> 2 0) + -) 5 2)
(+ 5 2)
7

負数ならば

ex1.4.answer2.scm

(a-plus-abs-b 5 -2)
((if (> -2 0) + -) 5 -2)
(- 5 -2)
7

引数bが正数なら+、負数なら+と、呼ばれる演算子が動的に決定される。

##練習問題1.5

以下のコードは、適用順序評価と正規順序評価とで、異なる結果になるのだとか。

ex1.5.scm

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

(test 0 (p))

それぞれ展開してみよう。まずは適用順序評価。

ex1.5.answer1.scm

(test 0 (p))
(test 0 (p))
(test 0 (p))
...

(p)を評価すると(p)なので無限ループに。実際、Gaucheで実行すると固まる。

正規順序評価ならば。

ex1.5.answer2.scm

(test 0 (p))
(if (= 0 0) 0 (p))
0

ifは特殊形式なので、条件句が真ならば(p)は評価されない。