Exercise 1.20. The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?
当运行 (gcd 206 40) 的时候，如果解释器是 normal-order，也就是不求值，直接代换的话，我们可以得到下面一系列过程。
(if (= 40 0)
206
(if (remainder 206 40)
40
(if (remainder 40 (remainder 206 40))
(remainder 206 40)
(if (remainder (remainder 206 40)
(remainder 40 (remainder 206 40)))
(remainder 40 (remainder 206 40))
(if ...)))))
normal-order 会等待递归的不断深入直到所有涉及到的运算都只是 primitive 操作的时候开始进行运算。所以 normal-order 会使得递归的操作进入死循环。
而对于 applicative-order，remainder 的执行步骤是 4 步。
1 ]=> (trace remainder1)
;Unspecified return value
1 ]=> (gcd 206 40)
[Entering #[compound-procedure 3 remainder1]
Args: 206
40]
[6
<== #[compound-procedure 3 remainder1]
Args: 206
40]
[Entering #[compound-procedure 3 remainder1]
Args: 40
6]
[4
<== #[compound-procedure 3 remainder1]
Args: 40
6]
[Entering #[compound-procedure 3 remainder1]
Args: 6
4]
[2
<== #[compound-procedure 3 remainder1]
Args: 6
4]
[Entering #[compound-procedure 3 remainder1]
Args: 4
2]
[0
<== #[compound-procedure 3 remainder1]
Args: 4
2]
;Value: 2