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?

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

------------------------------------------------------------------------

normal-order evaluation:

(gcd 206 40)

apply gcd:
(if (= 40 0) 206 (gcd 40 (remainder 206 40)))

evaluate special form if:
(gcd 40 (remainder 206 40))

apply gcd (using 'r' for 'remainder'):
(if (= (r 206 40) 0) 40 (gcd (r 206 40) (r 40 (r 206 40))))

evaluating the if performs one remainder operation and gives:
(gcd (rem 206 40) (rem 40 (rem 206 40)))

apply gcd:
(if (= (r 40 (r 206 40)) 0) (r 40 (r 206 40)) (gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))))

there are now two remainder operations in the if condition

(gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40))))

applying gcd again...

(if (= (r (r 206 40) (r 40 (r 206 40))) 0) ... )

now there are four remainders in the condition, which is 
still false, so we get:

(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)))))

In the next if, after 8 remainder operations, the condition 
evaluates to true and returns gcd's 'a' argument:

(r (r 206 40) (r 40 (r 206 40)))

Which after four remainder operations yields the answer 2.

So there are 19 total remainder operations.



applicative-order evaluation:

(gcd 206 40)

(if (= 40 0) 206 (gcd 40 (remainder 206 40)))

Since (= 40 0) is false:
(gcd 40 (remainder 206 40))

(gcd 40 6)

So there is at most one remainder operation per call to gcd, 
in this case a total of four calls.