Applicative Order vs. Normal Order Evaluation

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

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

(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

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

Normal Order Evaluation

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