## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.20

## Problem

The process that a procedure generates is of course dependent on the rules use by the interpreter. As an example, consider the iterative `gcd` procedure given in section 1.2.5 of the text:

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

Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5 of the text. (The normal-order-evaluation rule for `if` is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated by 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?

## Solution

Let's use this definition to keep things slightly more readable:

(define r remainder)

Using the substitution method for a normal-order interpreter and the normal-order rule for evaluating the `if` special form:

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

The `if` special form evaluates `(r 206 40)`, which is 6:

(if (= 6 0) 40 (gcd (r 206 40) (r 40 (r 206 40)))) (gcd (r 206 40) (r 40 (r 206 40))) (if (= (r 40 (r 206 40)) 0) (r 206 40) (gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))))

The `if` special form evaluates `(r 40 (r 206 40))`, which is 4:

(if (= 4 0) (r 206 40) (gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40))))) (gcd (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))) (if (= (r (r 206 40) (r 40 (r 206 40)))) (r 40 (r 206 40)) (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))))))

The `if` special form evaluates `(r (r 206 40) (r 40 (r 206 40)))`, which is 2:

(if (= 2 0) (r 40 (r 206 40)) (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)))))) (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))))) (if (= (r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))) 0) (r (r 206 40) (r 40 (r 206 40))) (gcd (r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))) (r (r (r 206 40) (r 40 (r 206 40))) (r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40)))))))

The `if` special form evaluates `(r (r 40 (r 206 40)) (r (r 206 40) (r 40 (r 206 40))))`, which is 0 (finally!):

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

And now it evaluates the consequent:

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

which is 2, the correct answer.

Procedure `remainder` is called 18 times during the normal-order evaluation of `(gcd 206 40)`.

Now let's examine the applicative-order evaluation:

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

Evaluating this combination evaluates the combination `(r 206 40)`:

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

Evaluate `(r 40 6)` to get:

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

Evaluate `(r 6 4)` to get:

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

Evaluate `(r 4 2)` to get:

(gcd 2 0) (if (= 0 0) 2 (gcd 0 (r 2 0)))

which is 2.

Procedure `remainder` is called 4 times during the applicative-order evaluation of `(gcd 206 40)`.