Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.