The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative
gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in 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?Let's play at being an interpreter again... Just to recap, the definition of
gcd is:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Using normal order evaluation we don't evaluate any of the operands until their values are required. Instead, as it says in section 1.1.5, we "fully expand and then reduce", so here's a full (and somewhat long) expansion and reduction of (gcd 206 40). I've highlighted each occurrence of remainder that gets evaluated on the next line:
(gcd 206 40)
= (if (= 40 0)
206
(gcd 40
(remainder 206 40)))
= (if #f
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)
40
(gcd (remainder 206 40)
(remainder 40
(remainder 206 40))))
= (if #f
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)))))
= (if (= (remainder 40 6) 0)
(remainder 206 40)
(gcd (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))
= (if (= 4 0)
(remainder 206 40)
(gcd (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))
= (if #f
(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))))))
= (if (= (remainder 6
(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))))))
= (if (= (remainder 6
(remainder 40 6))
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))))))
= (if (= (remainder 6 4) 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))))))
= (if (= 2 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))))))
= (if #f
(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)))))))
= (if (= (remainder (remainder 40 6)
(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)))))))
= (if (= (remainder 4
(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)))))))
= (if (= (remainder 4
(remainder 6
(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)))))))
= (if (= (remainder 4
(remainder 6
(remainder 40 6)))
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)))))))
= (if (= (remainder 4
(remainder 6 4))
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)))))))
= (if (= (remainder 4 2) 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)))))))
= (if (= 0 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)))))))
= (if #t
(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)))
= (remainder 6
(remainder 40
(remainder 206 40)))
= (remainder 6
(remainder 40 6))
= (remainder 6 4)
= 2
Phew! Counting up all the highlighted occurrences of remainder tells us that this required a total of 18 applications of remainder.Thankfully, using applicative-order evaluation is much simpler, as we evaluate each of the operands to an operator before we apply the operator. So, once again, here's the evaluation of
(gcd 206 40), but this time using applicative-order evaluation:
(gcd 206 40) = (if (= 40 0) 206 (gcd 40 (remainder 206 40))) = (if #f 206 (gcd 40 (remainder 206 40))) = (gcd 40 (remainder 206 40)) = (gcd 40 6) = (if (= 6 0) 40 (gcd 6 (remainder 40 6))) = (if #f 40 (gcd 6 (remainder 40 6))) = (gcd 6 (remainder 40 6)) = (gcd 6 4) = (if (= 4 0) 6 (gcd 4 (remainder 6 4))) = (if #f 6 (gcd 4 (remainder 6 4))) = (gcd 4 (remainder 6 4)) = (gcd 4 2) = (if (= 2 0) 4 (gcd 2 (remainder 4 2))) = (if #f 4 (gcd 2 (remainder 4 2))) = (gcd 2 (remainder 4 2)) = (gcd 2 0) = (if (= 0 0) 2 (gcd 0 (remainder 2 0))) = (if #t 2 (gcd 0 (remainder 2 0))) = 2Without even counting we can see from the brevity of the evaluation (both in terms of number of lines and length of lines) that the applicative-order evaluation requires much less state to be maintained, and fewer steps. There are a total of 4 applications of
remainder required here.Of course it's worth noting that a system that did implement normal-order evaluation may well cache the results of evaluations (or even evaluate a procedure once and then substitute its result in all places where it can be used), so in actuality the difference between the two may be less pronounced as this.
No comments:
Post a Comment