when making a function call foo(2 + 3, 4 *5), when are 2+3 and 4*5 evaluated?
Applicative order evaluation:
- arguments are evaluated before calling foo
- foo receives the calues of the evaluation of foo(5, 20)
Normal order evaluation:
- foo receives the expressions 2+ 3 and 4* 5 unevaluated
- foo evaluates its arguments if and when it needs to know their values
Applicative order evaluation:
- default in most languages
- easy to implement, efficient.
Normal order is much harder to implement, because you're passing around entire expression trees.
For example, if you needed to use the value of the 39th fib number 10000 times, you would end up calculating it 10000 timse. whereas with applicative you would already have the value.
They also interact poorly with side effects
BUT, there are more programs that are CORRECT under normal order than applicative. Normal order also allows you to defien infinite data structures.
Lazy evaluation mitigates the major downsides of normal evalluation:
- avoids repeated evaluation of expressions
- side effects happen only once (but not necessarily when we expect)
Scheme: ‘delay’ can postpone an expression being evaluated. ‘force’ can then evaluate it.
But every time you call force on a delayed function, it has to evaluate it again. this is essentially normal order evaluation, which passes around unevaluated expressions and evaluates them as it needs them, perhaps several times.
Lazy evaluation is just normal order evaluation, plus cacheing.
Index