Exercise 1.20 of SICP

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 Algorithm:

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

Normal Order:

    R1 = (remainder 206 40) ; 6
    (gcd 206 40)
    (if (= 40 0)
      40
      (gcd 40 R1))
    (if (= R1 0)
      40
      (gcd R1 (remainder 40 R1)))
    R2 = (remainder 40 R1) ; 4
    (if (= R2 0)
        R1
        (gcd R2 (remainder R1 R2)))
    R3 = (remainder R1 R2) ; 2
    (if (= R3 0)
        R2
        (gcd R3 (remainder R2 R3)))
    R4 = (remainder R2 R3) ; 0
    (if (= R4 0)
      R3
      (gcd ....)) ; Never called because R4 evaluates to 0

Every time there is an R in an if = statement that R gets evaluated. #{R1}+#{R2}+#{R3}+#{R4}= 1 + 2 + 4 + 7 = 14 times remainder is run in the if = R3 is ran once in order to return the actual remainder.

14+#{R3}=18

Number of Times “remainder” function called 18.

Applicative Order:

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

Number of Times “remainder” function called 4.