Chapter 1.1.5 - Applicative vs Normal Order Evaluation

Applicative vs Normal Order Evaluation

Chapter 1.1.5 is about substitution - comparing applicative-order evaluation and normal-order evaluation. It uses the following example, from the previous section:

1(define (f a)
2  (sum-of-squares (+ a 1) (* a 2)))

There are two ways to evaluate this.

Applicative Order Evaluation

Applicative-order evaluation means to evaluate the arguments before applying the procedure (or operator) to those arguments.

The body of the function is:

1(sum-of-squares (+ a 1) (* a 2))

If we were evaluating (f 5) we would substitute the argument 5 into the formal parameter a in the body of the function, giving us:

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

Which would then evaluate to:

1(sum-of-squares 6 10)
2
3(+ (* 6 6) (* 10 10))
4
5(+ 36 100)
6
7136

Something to note here, I’m realizing, is that the term procedure seems interchangeable with operator, and argument interchangeable with operand.

Normal Order Evaluation

To contrast this, normal-order evaluation would expand each procedure (or operator) first until there are only “primitive operators” (or numbers?). Only at that point would it perform the evaluation.

So (sum-of-squares (+ 5 1) (* 5 2)) would expand to (+ (square (+ 5 1)) (square (* 5 2)) ).

Then each square would be expanded to what it actually represents, at which point, all the primitive operators could evaluate the operands.

This section almost seems unnecessary, in the sense that it’s showing you can evaluate functions in two different ways to get the same answer. Part of me thinks: “Who cares what is going on under the hood?”

However, the authors explain their purpose. They will eventually get into talking about interpreters and compilers in the later chapters, which I admittedly know little to nothing about. So building the foundation here seems important.

They write:

Most interpreters use applicative-order evaluation, partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions such as those illustrated with (+ 5 1) and (* 5 2) above and, more significantly, because normal-order evaluation becomes much more complicated to deal with when we leave the realm of procedures that can be modelled by substitution, as we will do in chapter 3.

I don’t know what sort of procedures can’t be modeled by substitution yet, but it will be interesting to find out.

Soundtrack: A Pseudo Steady State by Lusine