Lazy evaluation

Evaluation strategies
Strict evaluation Applicative order Call by value Call by reference Call by sharing Call by copy-restore Non-strict evaluation Normal order Call by name Call by need/Lazy evaluation Call by macro expansion Nondeterministic strategies Full β-reduction Call by future Optimistic evaluation Other Partial evaluation Remote evaluation Short-circuit evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required (non-strict evaluation) and which also avoids repeated evaluations (sharing). The sharing can reduce the running time of certain functions by an exponential factor over other non-strict evaluation strategies, such as call-by-name.^{[citation needed]}

The benefits of lazy evaluation include:

• Performance increases due to avoiding unnecessary calculations and avoiding error conditions in the evaluation of compound expressions.
• The capability of constructing potentially infinite data structures
• The capability of defining control structures as abstractions instead of as primitives.

Lazy evaluation can lead to reduction in memory footprint, since values are created when needed. However, with lazy evaluation, it is difficult to combine with imperative features such as exception handling and input/output, because the order of operations becomes indeterminate. Lazy evaluation can introduce space leaks. Also, debugging is difficult.

The opposite of lazy actions is eager evaluation, sometimes known as strict evaluation. Eager evaluation is the evaluation behavior used in most programming languages.^{[citation needed]}

History

Lazy evaluation was introduced for the lambda calculus by (Wadsworth 1971) and for programming languages independently by (Henderson & Morris 1976) and (Friedman & Wise 1976).

Applications

Delayed evaluation is used particularly in functional languages. When using delayed evaluation, an expression is not evaluated as soon as it gets bound to a variable, but when the evaluator is forced to produce the expression's value. That is, a statement such as x:=expression; (i.e. the assignment of the result of an expression to a variable) clearly calls for the expression to be evaluated and the result placed in x, but what actually is in x is irrelevant until there is a need for its value via a reference to x in some later expression whose evaluation could itself be deferred, though eventually the rapidly-growing tree of dependencies would be pruned in order to produce some symbol rather than another for the outside world to see.

Some programming languages delay evaluation of expressions by default, and some others provide functions or special syntax to delay evaluation. In Miranda and Haskell, evaluation of function arguments is delayed by default. In many other languages, evaluation can be delayed by explicitly suspending the computation using special syntax (as with Scheme's "delay" and "force" and OCaml's "lazy" and "Lazy.force") or, more generally, by wrapping the expression in a thunk (delayed computation). The object representing such an explicitly delayed evaluation is called a future or promise. Perl 6 uses lazy evaluation of lists, so one can assign infinite lists to variables and use them as arguments to functions, but unlike Haskell and Miranda, Perl 6 doesn't use lazy evaluation of arithmetic operators and functions by default.

Delayed evaluation has the advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation. For example, one could create a function that creates an infinite list (often called a stream) of Fibonacci numbers. The calculation of the n-th Fibonacci number would be merely the extraction of that element from the infinite list, forcing the evaluation of only the first n members of the list.

For example, in Haskell, the list of all Fibonacci numbers can be written as:

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

In Haskell syntax, ":" prepends an element to a list, tail returns a list without its first element, and zipWith uses a specified function (in this case addition) to combine corresponding elements of two lists to produce a third.

Provided the programmer is careful, only the values that are required to produce a particular result are evaluated. However, certain calculations may result in the program attempting to evaluate an infinite number of elements; for example, requesting the length of the list or trying to sum the elements of the list with a fold operation would result in the program either failing to terminate or running out of memory.

Control structures

Even in most eager languages if statements evaluate in a lazy fashion.

if a then b else c

evaluates (a), then if and only if (a) evaluates to true does it evaluate (b), otherwise it evaluates (c). That is, either (b) or (c) will not be evaluated. Conversely, in an eager language the expected behavior is that

define f(x,y) = 2*x
set k = f(e,5)

will still evaluate (e) and (f) when computing (k). However, user-defined control structures depend on exact syntax, so for example

define g(a,b,c) = if a then b else c
l = g(h,i,j)

(i) and (j) would both be evaluated in an eager language. While in

l' = if h then i else j

(i) or (j) would be evaluated, but never both.

Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. If (i) or (j) have side effects or introduce run time errors, the subtle differences between (l) and (l') can be complex. As most programming languages are Turing-complete, it is possible to introduce user-defined lazy control structures in eager languages as functions, though they may depart from the language's syntax for eager evaluation: Often the involved code bodies (like (i) and (j)) need to be wrapped in a function value, so that they are executed only when called.

Short-circuit evaluation of Boolean control structures is sometimes called "lazy".

Other uses

In computer windowing systems, the painting of information to the screen is driven by "expose events" which drive the display code at the last possible moment. By doing this, they avoid the computation of unnecessary display content.

Another example of laziness in modern computer systems is copy-on-write page allocation or demand paging, where memory is allocated only when a value stored in that memory is changed.

Laziness can be useful for high performance scenarios. An example is the Unix mmap functionality. mmap provides "demand driven" loading of pages from disk, so that only those pages actually touched are loaded into memory, and unnecessary memory is not allocated.

Laziness in eager languages

Python:

In Python 2.x the range() function computes a list of integers (eager or immediate evaluation):

>>> r = range(10)

>>> print r

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> print r[3]

3

In Python 3.x the range() function returns an iterator which computes elements of the list on demand (lazy or deferred evaluation):

>>> r = range(10)

>>> print(r)

range(0, 10)

>>> print(r[3])

3

This change to lazy evaluation saves execution time for large ranges which may never be fully referenced and memory usage for large ranges where only one or a few elements are needed at any time.

Main article: Thunk (delayed computation)

Controlling eagerness in lazy languages

In lazy programming languages such as Haskell, although the default is to evaluate expressions only when they are demanded, it is possible in some cases to make code more eager—or conversely, to make it more lazy again after it has been made more eager. This can be done by explicitly coding something which forces evaluation (which may make the code more eager) or avoiding such code (which may make the code more lazy). Strict evaluation usually implies eagerness, but they are technically different concepts.

However, there is an optimisation implemented in some compilers called strictness analysis, which, in some cases, allows the compiler to infer that a value will always be used. In such cases, this may render the programmer's choice of whether to force that particular value or not, irrelevant, because strictness analysis will force strict evaluation.

In Haskell, marking constructor fields strict means that their values will always be demanded immediately. The seq function can also be used to demand a value immediately and then pass it on, which is useful if a constructor field should generally be lazy. However, neither of these techniques implements recursive strictness—for that, a function called deepSeq was invented.

Also, pattern matching in Haskell 98 is strict by default, so the ~ qualifier has to be used to make it lazy.

See also

• Combinatory logic
• Currying
• Dataflow
• Eager evaluation
• Functional programming
• Futures and promises
• Graph reduction
• Incremental computing – a related concept whereby computations are only repeated if their inputs change. May be combined with lazy evaluation.
• Lambda calculus
• Lazy initialization
• Lookahead
• Short-circuit (minimal) evaluation
• Non-strict programming language
• Normal order evaluation

References

• Hudak, Paul (September 1989). "Conception, Evolution, and Application of Functional Programming Languages". ACM Computing Surveys 21 (3): 383–385. http://portal.acm.org/citation.cfm?id=72554. 
• Reynolds, John C. (1998). Theories of programming languages. Cambridge University Press. ISBN 978052159414. http://books.google.com/books?id=HkI01IHJMcQC&pg=PA307. 

Further reading

• Wadsworth, Christopher P. (1971). Semantics and Pragmatics of the Lambda Calculus.  PhD thesis, Oxford University
• Henderson, Peter; Morris, James H. (January 1976). "A Lazy Evaluator". Conference Record of the Third ACM symposium on Principles of Programming Languages. http://portal.acm.org/citation.cfm?id=811543. 
• Friedman, D. P.; Wise, David S. (1976). S. Michaelson and R. Milner. ed. "Cons should not evaluate its arguments". Automata Languages and Programming Third International Colloquium (Edinburgh University Press). http://www.cs.indiana.edu/pub/techreports/TR44.pdf. 
• Launchbury, John (1993). A Natural Semantics for Lazy Evaluation. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.2016. 

Design patterns

• John Hughes. "Why functional programming matters". The Computer Journal - Special issue on lazy functional programming. Volume 32 Issue 2, April 1989.
• Philip Wadler. "How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages". Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, 1985, Volume 201/1985, 113-128.

Lazyness in strict languages

• Philip Wadler, Walid Taha, and David MacQueen. "How to add laziness to a strict language, without even being odd". Workshop on Standard ML, Baltimore, September 1998.

Blog posts by computer scientists

• Robert Harper. "The Point of Laziness"
• Lennart Augustsson. "More points for lazy evaluation"

External links

• Lazy Evaluation at the Portland Pattern Repository
• Lazy evaluation at Haskell Wiki
• Functional programming in Python becomes lazy
• Lazy function argument evaluation in the D programming language
• Lazy evaluation macros in Nemerle
• Lazy programming and lazy evaluation in Scheme
• Lambda calculus in Boost Libraries in C++ programming language
• Lazy Evaluation in Perl