SICP 問題1.20

2017/08/24

#sicp

手続きが生成するプロセスはもちろん解釈系が使う規則に依存する.
例えば上で述べた反復的gcd手続きを考え, 1.1.5節で論じた正規順序評価を使って解釈したとする.
(ifの正規順序評価規則は問題1.5に書いてある.)
(正規順序の)置換え法を使い, (gcd 206 40)の評価で生成されるプロセスを図示し, 実際に実行されるremainder演算を指示せよ.
(gcd 206 40)の正規順序評価で, remainder演算は実際に何回実行されるか. 作用的順序ではどうか.

まずは正規順序評価と作用的順序評価のおさらい。

1.1.5 手続き作用の置換えモデル - 計算機プログラムの構造と解釈第二版

「完全に展開し, 簡約する」評価方法は正規順序の評価 (normal-order evaluation)という.
それに対し解釈系が実際に使っている「引数を評価し, 作用させる」方法を作用的順序の評価(applicative-order evaluation)という.

言葉だけだとイマイチピンとこないので、1.1.5で出ている例をそれぞれの順序で評価したものもおさらいする。

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

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

; 正規順序評価の場合
(f 5)n
(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

; 作用的順序評価の場合
(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

なるほど。
正規順序評価の場合は引数は評価せずに渡されて、作用的順序評価の場合は引数を評価してから渡される。

おさらい終わり。
じゃあ今回の問題を考えてみる。問題のgcd関数は下記になっている。

(define (gcd a b)
  (if (= b 0) a
      (gcd b (remainder a b))))

正規順序評価でどう展開されるのかを図示してみる。
ちなみに問題文にも書いてあるifの正規順序評価規則は、if式の述語で使う際に評価するみたい。

(gcd 206 40)
↓
(if (= 40 0) 206
  (gcd 40 (remainder 206 40)))
↓
(gcd 40 (remainder 206 40))
↓
(if (= (remainder 206 40) 0) 40
  (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
↓ ; bを評価 x 3
(if (= 6 0) 40
  (gcd 6 (remainder 40 6))
↓
(gcd 6 (remainder 40 6)
↓
(if (= (remainder 40 6) 0) 6
  (gcd (remainder 40 6) (remainder 6 (remainder 40 6))))
↓ ; bを評価 x 3
(if (= 4 0) 6
  (gcd 4 (remainder 6 4)))
↓
(gcd 4 (remainder 6 4))
↓
(if (= (remainder 6 4) 0) 4
  (gcd (remainder 6 4) (remainder 4 (remainder 6 4))))
↓ ; bを評価 x 3
(if (= 2 0) 4
  (gcd 2 (remainder 4 2)))
↓
(gcd 2 (remainder 4 2))
↓
(if (= (remainder 4 2) 0) 2
  (gcd (remainder 4 2) (remainder 2 (remainder 4 2))))
↓ ; bを評価 x 3
(if (= 0 0) 2
  (gcd 0 (remainder 2 0)))
↓
2

合計12回？かな？

作用的順序評価の場合はこちら。

(gcd 206 40)
↓
(if (= 40 0) 206
  (gcd 40 (remainder 206 40)))
↓
(gcd 40 (remainder 206 40))
↓ ; +1
(gcd 40 6)
↓
(if (= 6 0) 40
  (gcd 6 (remainder 40 6)))
↓
(gcd 6 (remainder 40 6))
↓ ; +1
(gcd 6 4)
↓
(if (= 4 0) 6
  (gcd 4 (remainder 6 4)))
↓
(gcd 4 (remainder 6 4))
↓ ; +1
(gcd 4 2)
↓
(if (= 2 0) 4
  (gcd 2 (remainder 4 2)))
↓
(gcd 2 (remainder 4 2))
↓ ; +1
(gcd 2 0)
↓
(if (= 0 0) 2
  (gcd 0 (remainder 2 0)))
↓
2

なので、4回かな？

答えみたら正規順序評価の部分が違った。
僕はifの述語でbを評価する際に、同じbは同時に評価されるのかと思ってたけど、ifの述語のbだけしか評価されないみたい。そうだったのかー
なので、もっと増えるっぽい。