Skip to main content
2 of 3
fixed the answer, since the prev. version is based on misreading the question
Anton Trunov
  • 3.5k
  • 1
  • 19
  • 26

Notice that the first quote contains a definition of normal-order evaluation, but the second one treats normal-order languages, i.e. languages that use normal-order evaluation.

The nice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

Anton Trunov
  • 3.5k
  • 1
  • 19
  • 26