More Haste, Less Speed
The Complexity of Lazy Evaluation

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 non-terminating expression leads to a non-terminating 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):541-547, 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 complexity-preserving translation of lazy programs into an eager functional language.