题目要求我们模拟应用序和正则序分别去解释 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
的次数比起应用序模式要多得多。