SICP Exercise 1.20: GCD

From SICP section 1.2.5 Greatest Common Divisors

Exercise 1.20 asks us to consider the following iterative procedure that uses Euclid's Algorithm to comput the GCD:

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

We're asked to illustrate the process generated by this procedure when using normal-order and applicative-order evaluation rules to evaluate (gcd 206 40). How many remainder operations are actually performed using each evaluation model?

We learned the rules for both applicative-order and normal-order evaluation back in SICP section 1.1.5 The Substitution Model for Procedure Application. We learned that under normal-order evaluation rules, the interpreter fully expands a procedure before reducing it. Operand expressions are substituted for parameters until an expression involving only primitive operators is reached. Under applicative-order rules, arguments are evaluated before operators are applied. This can often avoid multiple unnecessary evaluations of the same expression, which is one of the reasons why Lisp uses applicative-order evaluation.

In section 1.1.6 Conditional Expressions and Predicates (see exercise 1.5) we're told to assume that the evaluation rule for the special form if is the same whether we use normal or applicative order evaluation. "The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression." We'll continue using this assumption until we're told otherwise.

Now let's put all of this together to illustrate both processes for (gcd 206 40).


Normal-order evaluation - fully expand and then reduce.

(gcd 206 40)

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

(gcd 40 (remainder 206 40))

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

(if (= 6 0) ;; 1 remainder evaluated
    40
    (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))

(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))

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

At this point both of the nested remainder operations that were substituted in for b in the (= b 0) procedure need to be evaluated. I'll combine these and show them as one step.

(if (= 4 0) ;; 2 remainders evaluated
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))))

(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40)
                (remainder 40 (remainder 206 40))))

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

Here again, multiple nested remainder operations that were substituted in for b in the (= b 0) procedure need to be evaluated. I'll combine all four and show them as one step.

(if (= 2 0) ;; 4 remainders evaluated
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

(gcd (remainder (remainder 206 40)
                (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
                           (remainder 40 (remainder 206 40)))))

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

There are seven nested remainder operations to evaluate at this point.

(if (= 0 0) ;; 7 remainders evaluated
    (remainder (remainder 206 40)
               (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206
                                                                40)))))))

(remainder (remainder 206 40)
           (remainder 40 (remainder 206 40)))

Finally, we can evaluate these four remainder operations to come up with the answer (GCD) and the total.

2 ;; 18 total remainders evaluated

Applicative-order evaluation - evaluate arguments and then apply operands. This one is a little bit easier to follow. With each substitution, we just evaluate the operands that we need before applying the operators at each step.

(gcd 206 40)

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

(gcd 40 (remainder 206 40))

(gcd 40 6) ;; 1st remainder evaluated

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

(gcd 6 (remainder 40 6))

(gcd 6 4) ;; 2nd remainder evaluated

(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))

(gcd 4 (remainder 6 4))

(gcd 4 2) ;; 3rd remainder evaluated

(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))

(gcd 2 (remainder 4 2))

(gcd 2 0) ;; 4th remainder evaluated

(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

2

As you can see, using applicative-order evaluation, remainder was only evaluated four times, compared to 18 times using normal-order evaluation.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.