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

From Drewiki
Jump to: navigation, search

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

Personal tools