ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

SICP: Exercise 1.20

問題 1.20

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

計算機プログラムの構造と解釈 第二版 1.2.5 最大公約数」より

正規順序評価

もうとにかく面倒くさいので、先に

(define r remainder)

ということにしておきます。。。

(gcd 206 40)
 
(if (= 40 0)
  206
  (gcd 40 (r 206 40)))
 
;;
(gcd 40 (r 206 40))
 
(if (= (r 206 40) 0)
  ;; 1 回
  40
  (gcd (r 206 40) (r 40 (r 206 40))))
 
;;
(gcd (r 206 40) (r 40 (r 206 40)))
 
(if (= (r 40 (r 206 40)) 0)
  ;; 2 回(計 3 回)
  (r 206 40)
  (gcd (r 40 (r 206 40))
       (r (r 206 40)
          (r 40 (r 206 40)))))
 
;;
(gcd (r 40 (r 206 40))
     (r (r 206 40)
        (r 40 (r 206 40))))
 
(if (= (r (r 206 40)
          (r 40 (r 206 40)))
       0)
  ;; 4 回(計 7 回)
  (r 40 (r 206 40))
  (gcd (r (r 206 40)
          (r 40 (r 206 40)))
       (r
         (r 40 (r 206 40))
         (r (r 206 40)
            (r 40 (r 206 40))))))
 
;;
(gcd (r (r 206 40)
        (r 40 (r 206 40)))
     (r
       (r 40 (r 206 40))
       (r (r 206 40)
          (r 40 (r 206 40)))))
 
(if (= (r
         (r 40 (r 206 40))
         (r (r 206 40)
            (r 40 (r 206 40))))
       0)
  ;; 7 回(計 14 回)
  ;; ここでやっと #t になる。
  ;; (r
  ;;   (r 40 6)
  ;;   (r 6
  ;;      (r 40 6)))
  ;; (r 4
  ;;    (r 6 4))
  ;; (r 4 2)
  ;; 0
  (r (r 206 40)
     (r 40 (r 206 40)))
  (gcd (r
         (r 40 (r 206 40))
         (r (r 206 40)
            (r 40 (r 206 40))))
       (r
         (r (r 206 40)
            (r 40 (r 206 40)))
         (r
           (r 40 (r 206 40))
           (r (r 206 40)
              (r 40 (r 206 40)))))))
 
;;
(r (r 206 40)
   (r 40 (r 206 40)))
;; 2 回(計 16 回)
(r 6
   (r 40 6))
;; 1 回(計 17 回)
(r 6 4)
;; 1 回(計 18 回)
2

というわけで remainder 演算は正規順序評価では 18 回行われる。疲れた…

作用的順序評価

正規順序評価と比べると雲泥の差で、さらっといける。

(gcd 206 40)
(gcd 40 (remainder 206 40))
;; 1 回
(gcd 40 6)
(gcd 6 (remainder 40 6))
;; 1 回(計 2 回)
(gcd 6 4)
(gcd 4 (remainder 6 4))
;; 1 回(計 3 回)
(gcd 4 2)
(gcd 2 (remainder 4 2))
;; 1 回(計 4 回)
(gcd 2 0)
2

以上から remainder 演算は作用的順序評価ではたった 4 回。

置換モデルで書き下すととんでもない差になった(その面倒くささで、この記事を書くまでやる気との戦いが長引いてしまった)。