Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book?
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) &amp;\longrightarrow B[x \leftarrow A] &amp;&amp; (\beta) \\
  ((\lambda x_1 x_2. B) \: A_1 \: A_2) &amp;\longrightarrow B[x_1 \leftarrow A_1, x_2 \leftarrow A_2] &amp;&amp; (\beta_2) \\
  (* \: i \: j) &amp;\longrightarrow [\![ i \times j ]\!] &amp;&amp; (\delta_*) \\
  (\texttt{tracing} \: x) &amp;\xrightarrow{\;x\;} x &amp;&amp; (\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))
  &amp;\longrightarrow (* \: (\texttt{tracing} \: 2) \: (\texttt{tracing} \: 2)) &amp;&amp; \text{by \((\beta)\)} \\
  &amp;\xrightarrow{\;2\;} (* \: 2 \: (\texttt{tracing} \: 2)) &amp;&amp; \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_1\)} \\
  &amp;\xrightarrow{\;2\;} (* \: 2 \: 2) &amp;&amp; \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^2_2\)} \\
  &amp;\longrightarrow 4 &amp;&amp; \text{by \((\delta_*)\)}
\end{align} $$
In applicative order:
$$ \begin{align}
  ((\lambda x. (* \: x \: x))\:  (\texttt{tracing} \: 2))
  &amp;\xrightarrow{\;2\;} ((\lambda x. (* \: x \: x)) \: 2) &amp;&amp; \text{by \((\delta_{\texttt{tracing}})\) and \(\text{App}^1_1\)} \\
  &amp;\longrightarrow (* \: 2 \: 2) &amp;&amp; \text{by \((\beta)\)} \\
  &amp;\longrightarrow 4 &amp;&amp; \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.