SICP exercise 1.20

From Drewiki

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:

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:

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

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

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

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

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

And now it evaluates the consequent:

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:

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

Evaluate (r 40 6) to get:

Evaluate (r 6 4) to get:

Evaluate (r 4 2) to get:

which is 2.

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