# normal order evaluation -vs- applicative order evaluation

I am going through Abelson and Sussman (Structure and Interpretation of Computer Programs) and I am a little confused about when normal order evaluation is used and when applicative order evaluation is used.

This sentence throws me off:

Lisp uses applicative-order evaluation partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions suich 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 modeled by substitution. [emphasis added]

However, in exercise 1.6, the implication is that Lisp uses normal order evaluation for primitives but applicative order evaluation for complex procedures.

Could someone clarify?

-

First: there are multiple implementations of Lisp, each of which may have different evaluation models. I believe SICP mostly uses Scheme.

Exercise 1.6 does not imply that Scheme uses normal order -- it's about a special form (`if`). For special forms, the evaluation can be neither of applicative or normal.

I believe Scheme always uses applicative order except in the case of special forms.

For example:

``````(cond (x 1)
(y 2)
(else 3))
``````

`cond` is a special form. This would evaluate by evaluating `x`, and if it's true, then return 1, otherwise evaluate `y`, returning 2 if it's true, otherwise returning 3.

I'm a little rusty on the Scheme -- hope I didn't forget any parentheses! I'm also aware that there are multiple versions of Scheme, but not sure which one is used by the book.

-

because normal-order evaluation becomes much more complicated to deal with when we leave the realm of procedures that can be modeled by substitution.

To put this differently, consider

``````let x = (print "ha", print "ho") in x
``````

The question is, does this print a) nothing, b) ha c) ho d) haho?

Does it do this only the first time, or every time x is used?

With normal order evaluation, it would depend on how much of the expression was demanded, like:

``````y = fst x
``````

This is one reason why non-strict languages (i.e. using a form of normal order evaluation that can be modeled by substitution) tend to be pure, i.e. side effects in expressions are not allowed.

-