练习 1.20

题目要求我们模拟应用序和正则序分别去解释 gcd 函数，并统计 remainder 的调用次数：

;;; p32-gcd.scm

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

应用序

先来看应用序对 gcd 的解释过程：

(gcd 206 40)
(gcd 40 6)      ; (gcd 40 (remainder 206 40)
(gcd 6 4)       ; (gcd 6 (remainder 40 6))
(gcd 4 2)       ; (gcd 4 (remainder 6 4))
(gcd 2 0)       ; (gcd 2 (remainder 2 2))
2

可以看到，对于应用序求值来说， (gcd 206 40) 共使用 5 次 remainder 调用。

正则序

现在，再来看看正则序对 (gcd 206 40) 的解释过程：

(gcd 206 40)

(gcd 40 (remainder 206 40)) ; a = 40, b = 6, t1 = (remainder 206 40)

(if (= t1 0) ...)   ; #f

(gcd t1 (remainder 40 t1))  ; a = 6, b = 4, t2 = (remainder 40 t1)

(if (= t2 0) ...)   ; #f

(gcd t2 (remainder t1 t2))  ; a = 4, b = 2, t3 = (remainder t1 t2)

(if (= t3 0) ...)   ; #f

(gcd t3 (remainder t2 t3))  ; a = 2, b = 0, t4 = (remainder t2 t3)

(if (= t4 0) ...)   ; #t

t3

(remainder t1 t2)

(remainder t1
           (remainder 40 t1))   ; t2

(remainder t1
           (remainder 40
                      (remainder 206 40)))    ; t1

(remainder t1
           (remainder 40 6))

(remainder t1 4)

(remainder (remainder 206 40)   ; t1
           4)

(remainder 6 4)

2

因为直接的展开式太长，所以展开过程中使用了变量表示一部分展开式。

即使不计算 remainder 的准确调用次数也可以看出，在正则序模式下的 gcd 调用 remainder 的次数比起应用序模式要多得多。

讨论

blog comments powered by Disqus