Eager evaluation/applicative order and lazy evalua

Question

As far as I know, eager evaluation/applicative order evaluates all arguments to a function before applying it, on the other hand, lazy evaluation/normal order evaluates the arguments only when needed.

So, what are the differences between the pair of terms eager evaluation and applicative order, and lazy evaluation and normal order?

Thanks.

Answer 1

Lazy evaluation evaluates a term at most once, while normal order would evaluate it as often as it appears. So for example if you have f(x) = x+x and you call it as f(g(42)) then g(42) is called once under lazy evaluation or applicative order, but twice under normal order.

Eager evaluation and applicative order are synonymous, at least when using the definition of applicative order found in Structure and Interpretation of Computer Programs, which seems to match yours. (Wikipedia defines applicative order a bit differently and has it as a special case of eager evaluation).

Answer 2

I'm reading SICP too, and I've been curious by the definition of normal order given by the authors. It seemed rather similar to Lazy evaluation to me, so I went looking for some more information regarding both.

I know this question was asked a long time ago, but I looked at the FAQ and found no mention of answering old questions, so I thought I'd leave what I've found here so other people could use it in the future.

This is what I've found, and I'm inclined to agree with those:

I would argue (as have others) that lazy evaluation and NormalOrderEvaluation are two different things; the difference is alluded to above. In lazy evaluation, evaluation of the argument is deferred until it is needed, at which point the argument is evaluated and its result saved (memoized). Further uses of the argument in the function use the computed value. The C/C++ operators ||, &&, and ? : are both examples of lazy evaluation. (Unless some newbie C/C++ programmer is daft enough to overload && or ||, in which case the overloaded versions are evaluated in strict order; which is why the && and || operators should NEVER be overloaded in C++).

In other words, each argument is evaluated at most once, possibly not at all.

NormalOrderEvaluation, on the other hand, re-evaluates the expression each time it is used. Think of C macros, CallByName in languages which support it, and the semantics of looping control structures, etc. Normal-order evaluation can take much longer than applicative order evaluation, and can cause side effects to happen more than once. (Which is why, of course, statements with side effects generally ought not be given as arguments to macros in C/C++)

If the argument is invariant and has no side effects, the only difference between the two is performance. Indeed, in a purely functional language, lazy eval can be viewed as an optimization of normal-order evaluation. With side effects present, or expressions which can return a different value when re-evaluated, the two have different behavior; normal order eval in particular has a bad reputation in procedural languages due to the difficulty of reasoning about such programs without ReferentialTransparency

Should also be noted that strict-order evaluation (as well as lazy evaluation) can be achieved in a language which supports normal-order evaluation via explicit memoing. The opposite isn't true; it requires passing in thunks, functions, or objects which can be called/messaged in order to defer/repeat the evaluation.

And

Lazy evaluation combines normal-order evaluation and sharing:

• Never evaluate something until you have to (normal-order)

• Never evaluate something more than once (sharing)

http://c2.com/cgi/wiki?LazyEvaluation

http://cs.anu.edu.au/student/comp3610/lectures/Lazy.pdf