Tuesday, January 26, 2010

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.

3 comments:

Anonymous said...

Thank you very much for publishing these answers in such a thorough way. It really helps as a learning tool to the book.

Jedd Fenner said...

I just want to add my thanks also, very much appreciated Mr Lizard.

Giorgio Sironi said...

After seeing the first 3 iterations of normal order I thought the pattern was exponential (1-2-4-8-16...). After confronting my solutions with this article I understood instead every step is the sum of the two before plus 1 additional remainder evaluation (contained in the else).
This ties together nicely with Fibonacci's definition, giving a sequence that is (Fib(n) - 1): 1-2-4-7-12-20-...