Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book?

Question

As per this explaination, it defines applicative and normal order evaluation in one form saying:

This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation.

while this explanation defines the other way around

applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed

They seem to contradict each other. Do these definitions mean the same thing?

Answer 1

Those definitions are saying the same thing (at the level of precision of the English description).

An example from the book

Normal-order evaluation goes “fully expand and then reduce”, meaning that function calls are expanded before reducing the arguments, and the reduction only happens when the value is needed. Let's take one of the examples in the book: start from (sum-of-squares (+ 5 1) (* 5 2)). First, we fully expand the definition of sum-of-squares:

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

Since + is a primitive, we can't expand it. It requires integers as arguments, so here we have no choice: we must reduce the arguments. To reduce (square (+ 5 1)) in normal order, we start by expanding:

(square (+ 5 1)) → (* (+ 5 1) (+ 5 1))

Then we have the primitive *, also requiring integers as arguments, so we must reduce the arguments.

(+ 5 1) → 6
(+ 5 1) → 6

and so

(* (+ 5 1) (+ 5 1)) →→ (* 6 6) → 36

and likewise for (square (* 5 2)), so the original expression finally evaluates thus

(+ (square (+ 5 1)) (square (* 5 2))) →→ (+ 36 100) → 136

In contrast, applicative-order evaluates the arguments when the function is applied, before expanding the function call. So to evaluate (sum-of-squares (+ 5 1) (* 5 2)), we first need to evaluate the arguments:

(+ 5 1) → 6
(* 5 2) → 10

and then we can expand the function call:

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

The next step is to evaluate the arguments of +; they're function calls, and in each case the arguments are already fully evaluated so we can perform the function call right away:

(square 6 6) → (* 6 6) → 36
(square 10 10) → (* 10 10) → 100

and finally

(+ (square 6 6) (square 10 10)) →→ (+ 36 100) → 136

An example with side effects

The order of evaluation doesn't make any difference when the expressions have no side effect. (Except with respect to termination, if you don't consider non-termination a side effect: an expression may terminate in some evaluation orders and loop forever in others.) Side effects change the deal. Let's define a function with a

(define (tracing x)
  (write x)
  x)

If we evaluate (square (tracing 2)) in applicative order then the argument is evaluated only once:

(tracing 2) → 2 [write 2]
(square (tracing 2)) → (square 2) [write 2]
                     → (* 2 2)
                     → 4

In normal order, the argument is evaluated twice, so the trace is shown twice.

(square (tracing 2)) → (* (tracing 2) (tracing 2))
(tracing 2) → 2 [write 2]
(tracing 2) → 2 [write 2]
(* (tracing 2) (tracing 2)) →→ (* 2 2) [write 2, write 2]

You can observe this in Scheme. Scheme applies applicative order to function evaluation, but also has a macro facility. Macro calls use normal order.

(define-syntax normal-order-square
  (syntax-rules () ((normal-order-square x) (* x x))))

At a Scheme prompt, you can see that (square (tracing 2)) prints 2 once whereas (normal-order-square (tracing 2)) prints 2 twice.

Towards theory

Let's present the rules of evaluation in a more formal way (with small-step semantics). I'm going to use a notation that's closer to what is commonly used in theory:

• $(\lambda x y. A)$ is (lambda (x y) A), where $A$ is an expression.
• $B[x\leftarrow A]$ means to take the expression $B$ and replace all occurrences of $x$ by $A$.
• $[\![ \ldots ]\!]$ is an integer obtained by some mathematical computation, e.g. $[\![ 2+2 ]\!] = 4$.
• $A \xrightarrow{\;t\;} B$ means that the expression $A$ evaluates to the expression $B$, and in doing so prints the trace $t$.

I'll simplify away everything that's related to variable binding: a variable is considered equivalent to its definition.

Evaluation rules come in two flavors. There are head rules, that explain how to make progress on the evaluation of an expression by looking at the topmost node in the syntax tree.

$$ \begin{align} ((\lambda x. B) \: A) &\longrightarrow B[x \leftarrow A] && (\beta) \\ ((\lambda x_1 x_2. B) \: A_1 \: A_2) &\longrightarrow B[x_1 \leftarrow A_1, x_2 \leftarrow A_2] && (\beta_2) \\ (* \: i \: j) &\longrightarrow [\![ i \times j ]\!] && (\delta_*) \\ (\texttt{tracing} \: x) &\xrightarrow{\;x\;} x && (\delta_{\texttt{tracing}}) \\ \end{align} $$

$(\beta)$ is the rule the application of a user-defined function. I've defined a variant for two arguments (there are other, better ways to treat functions with multiple arguments but that's a topic for another day). The $(\delta)$ rules are for the evaluation of primitives (I'm treating tracing as a primitive because expressing it in terms of progn and write would unnecessarily complicate this presentation).

There are context rules, that explain how to look for things to evaluate deeper inside the evaluation syntax tree. The notation $\dfrac{P}{C}$ means “if there's a way to do the reduction $P$ according to the rules, then $C$ is also a valid reduction”. In other words, assuming that the premise above the line holds, the conclusion below the line holds.

$$ \dfrac{A \xrightarrow{t} A'}{(F \, A \xrightarrow{t} F \, A')} (\texttt{App}^1_1) \qquad \dfrac{A_1 \xrightarrow{t} A_1'}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1' \, A_2)} (\texttt{App}^2_1) \qquad \dfrac{A_2 \xrightarrow{t} A'_2}{(F \, A_1 \, A_2 \xrightarrow{t} F \, A_1 \, A_2')} (\texttt{App}^2_2) $$

For example the rule $(\texttt{App}^1_1)$ means that to evaluate a function call, we can evaluate the argument. In a full treatment, there would be a similar rule for the function part, but we don't need it here.

The arrow $\longrightarrow$ means “evaluates in a single step to”. We can derive the notion of “evaluates to” (in any number of steps): $$ \dfrac{}{A \xrightarrow{} A} \qquad \dfrac{A \xrightarrow{\;t\;}^* B \text{ and } B \xrightarrow{\;t'\;} C}{A \xrightarrow{\;t,t'\;}^* C} $$ The first rule means that an expression evaluates to itself (in zero steps). The second rule allows adding one more step to a sequence of evaluations.

These rules are non-deterministic: there can be more than one applicable rule for a given expression, and thus there are multiple possibilities to evaluate an expression. This is where evaluation strategies come into play. An evaluation strategy defines a priority on the rules.

• In normal order, $(\beta)$ (the application rule) is applied before context rules that would affect the arguments. This is what the first quote means by “fully expand [apply head rules] and then reduce [in context]”, and what the second quote means by “delay the evaluation of procedure arguments until the actual argument values are needed” (don't apply context rules until forced by a $\delta$ rule). (In the first quote, the use of the word “expand” is somewhat jarring — applying $(\beta)$ is a reduction too!)
• In applicative order, the context rules are applied first, and $(\beta)$ is only applied if the arguments can't be evaluated anymore. This is what the first quote means by “evaluate the arguments [in context] and then apply [head rules]”, and what the second quote means by “all the arguments (…) are evaluated when the procedure is applied [before performing the actual application]”.

Let's look at (square (tracing 2)) in this model. In the notation I've presented, that's $((\lambda x. (* \: x \: x)) (\texttt{tracing} \: 2))$. In normal order: $$ \begin{align} ((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2)) &\longrightarrow (* \: (\texttt{tracing} \: 2) \: (\texttt{tracing} \: 2)) && \text{by \((\beta)\)} \\ &\xrightarrow{\;2\;} (* \: 2 \: (\texttt{tracing} \: 2)) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_1\)} \\ &\xrightarrow{\;2\;} (* \: 2 \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_2\)} \\ &\longrightarrow 4 && \text{by \((\delta_*)\)} \end{align} $$ In applicative order: $$ \begin{align} ((\lambda x. (* \: x \: x))\: (\texttt{tracing} \: 2)) &\xrightarrow{\;2\;} ((\lambda x. (* \: x \: x)) \: 2) && \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^1_1\)} \\ &\longrightarrow (* \: 2 \: 2) && \text{by \((\beta)\)} \\ &\longrightarrow 4 && \text{by \((\delta_*)\)} \end{align} $$ (I used left-to-right evaluation for function arguments; specifying this is necessary to get a fully deterministic evaluation order.) This shows how $((\lambda x. (* \: x \: x)) \: (\texttt{tracing} \: 2))$ evaluates to $4$ with the trace $2,2$ under normal order, but to $4$ with the trace $2$ under applicative order.

Answer 2

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.

Answer 3

Yes, it seems to me they are in contradiction.

I think you're reading it correctly, and it's just one of those errors that make it into text books from time to time.

I searched, and found this errata page, but it seems to be more focused on code errata, and not on conceptual errors.

Hope this helps, -john