excercise-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?

Ans

使用的程序

1
2
3
4

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

应用序

1
2
3
4
5
6

(gcd 206 40)
(gcd 40 6)      
(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

共 5 次

正则序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

(gcd 206 40)

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

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

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

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

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

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

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

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

t3  ; 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

总共: t1 一次, t2 一次, t3 两次, t4 一次

t1 调用 remainder 1 次, t2 调用 remainder 2 次, t3 调用 remainder 4 次, t4 调用 remainder 7 次.

所以总共调用 remainder 的次数为:$1+2+4*2+7=18$次