1 2 3 |
(define (square x) (* x x)) (define (sum-of-squares x y) (+ (square x) (square y))) (define (f x) (sum-of-squares x (+ x 1))) |

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

1 2 3 4 5 6 7 |
(f 3) (sum-of-squares 3 (+ 3 1)) (sum-of-squares 3 4) (+ (square 3) (square 4)) (+ (* 3 3) (* 4 4)) (+ 9 16) 25 |

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

1 2 3 4 5 6 7 |
(f 3) (sum-of-squares 3 (+ 3 1)) (+ (square 3) (square (+ 3 1)) (+ (* 3 3) (* (+ 3 1) (+ 3 1))) (+ 9 (* 4 4)) (+ 9 16) 25 |

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

1 2 3 4 5 6 7 8 |
(f (rand 100)) (sum-of-squares 13) (sum-of-squares 13 (+ 13 1)) (sum-of-squares 13 14) (+ (square 13) (square 14)) (+ (* 13 13) (* 14 14)) (+ 169 196) 365 |

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

Normal Order Evaluation

1 2 3 4 |
(f (rand 100)) (sum-of-squares (rand 100) (+ (rand 100) 1)) (+ (square (rand 100)) (square (+ (rand 100) 1)) (+ (* (rand 100) (rand 100)) (* (+ (rand 100) 1) (+ (rand 100) 1))) |

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.

Nice explanation!

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!