(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 1/100.
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.