CODEWITHSUNDEEP
schemesicp
Leo
Leo

Reputation: 492

The evaluation process in normal order(Scheme)?

I'm studying SICP, and ex1.20 gives the following code:

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

The question asks about the times remainder is called when we run (gcd 206 40) in applicative order and normal order, respectively. I can figure out remainder is called 4 times in applicative order, but I can't understand why it becomes 18 when it comes to normal order. In my view, first (gcd 40 (remainder 206 40))is called, and next we need to calculate (remainder 206 40), which is 6, if we want to know which branch we go to, and then (remainder 40 6), and so on, and it turns out to be 4 times, too. But the answer gives the following process:

     (gcd 206 40) 

     (if (= 40 0) ...) 

     (gcd 40 (remainder 206 40)) 

     (if (= (remainder 206 40) 0) ...) 

     (if (= 6 0) ...) 

     (gcd (remainder 206 40) (remainder 40 (remainder 206 40))) 

     (if (= (remainder 40 (remainder 206 40)) 0) ...) 

     (if (= 4 0) ...) 

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

     (if (= 2 0) ...) 

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

     (if (= 0 0) ...) 
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

So in total it's 18 times. I think the main difference between the two answers is that I think once a remainder is calculated, then it won't need to be calculated any more, but the answer might seem to calculate it every time. Is this a matter of compiler? Isn't this too efficientless?

Upvotes: 2

Views: 309

Answers (1)

Will Ness
Will Ness

Reputation: 71065

edit: actually, what I described as normal order is call-by-name. Lazy is call-by-need and both are indeed normal order.

Your intuition is correct for applicative order, where arguments are evaluated (i.e. their value is found out) before a function call. But in normal order they are only evaluated inside the function call, when their value is needed - and then, this value is forgotten. Normal order which remembers the found values is known as lazy evalution, by the way.

Thus, the reduction sequence for applicative order of evaluation is

> (gcd 206 40)
= (if (= 40 0) 206 (gcd 40 (remainder 206 40)))
= (gcd 40 (remainder 206 40))
> (remainder 206 40) => 6
= (gcd 40 6)
= (if (= 6 0) 40 (gcd 6 (remainder 40 6)))
= (gcd 6 (remainder 40 6))
> (remainder 40 6) => 4
= (gcd 6 4)
....

But for the normal order it'll be 

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

You can see the difference.

Upvotes: 2

Related Questions