Applicative Order vs. Normal Order Evaluation

In Applicative Order Evaluation arguments to functions get evaluated (reduced as much as possible) before being passed to a function. Here’s a trace of what would happen do a function call f defined above with arguments of 3 and (+ 3 1).

In Normal Order Evaluation a full expansion of all the function application happens first and then the arguments are evaluated.

The best case and simplest case I can think of illustrating the difference between the two is the following:
Suppose there is a defined function rand which will return a random integer, (rand 100) returns an random int between 0 and 100.
In this case I pretend that (rand 100) returned 13.
Applicative Evaluation

The chances of running (f (rand 100)) under applicative order again and getting the same answer is 1/100.

Normal Order Evaluation

I want to stop here to note that all 4 calls to (rand 100) should, if the rand function is any good, evaluate to 4 random integers between 0 and 100.
Only if there is a lot of luck involved (the chances of the this Normal Order f being the same its Applicative Order cousin is about 1 in one hundred million) will the rest of this statement evaluate to the same result as the the Applicative Evaluation earlier.

2 thoughts on “Applicative Order vs. Normal Order Evaluation

  1. This was really helpful. Started taking SICP in OCW Courseware, and I was finding the difference of these evaluations tricky… That is until you used rand(100) to explain it. Now it totally makes sense! Thanks!

Leave a Reply