normal order evaluation -vs- applicative order evaluation

Question

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]

on page 17 paragraph 1.

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?

Answer 1

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.}

Answer 2

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.