More Haste, Less Speed The Complexity of Lazy Evaluation
Richard Bird,
Geraint Jones and
Oege de Moor
We have shown,
we believe for the first time,
that lazy evaluation of functional programming languages
is strictly more powerful than eager evaluation, as measured by the
asymptotic complexity of evaluating certain programs.
One of the attractions of functional programming languages
 ones that do not use assignments 
is that programs consist in essence of mathematical equations,
and can be reasoned about by everyday mathematical techniques such as
the substitution of an expression for any other which is equal to it.
However,
the most straightforward way of implementing a set of equations as a program
 eager evaluation as it is called 
evaluates the arguments of functions first,
and only then applies those functions.
It turns out to be relatively straightforward to estimate the execution
time of functional programs under an eager evaluation strategy,
but it is hard to reason about the value produced:
applying a constant function to a nonterminating expression
leads to a nonterminating program, rather than returning the constant.
This interferes with equational reasoning:
you cannot always substitute for each other
the value of the constant
and an application of a constant function.
Soundness of equational reasoning comes from
normal order evaluation,
in which functions are applied to unevaluated arguments,
although if many copies are made of an unevaluated argument
it might have to be evaluated many times, at great cost in execution time.
Languages such as Haskell
use lazy evaluation,
which applies functions to arguments whose evaluation is postponed until
the first (but only the first) time their values are needed.
This ensures that equational reasoning about the values of programs is sound,
at the expense of making it extremely hard to reason about when expressions
are evaluated, and to estimate how much work is involved in doing so.
We are interested in exploiting the elegance and power of lazy evaluation,
but also in developing techniques to measure the cost of doing so.
Nicholas Pippenger
showed
that under certain simple restrictions,
problems that can be solved in linear time
in a language with assignments
must take longer (by a logarithmic factor)
in an eagerly evaluated purely functional language.
Our paper (Journal of Functional Programming, 7(5):541547, September 1997)
shows that a lazy functional program solves Pippenger's problem in linear time.
This demonstrates that lazy evaluation is strictly more efficient
 in asymptotic terms 
than eager evaluation,
and that there is no general complexitypreserving translation of lazy programs
into an eager functional language.
