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

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?

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 $\

StackExchange Computer Science Q#54000, answer score: 8