Lazy evaluation

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (December 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.
For another use of this term, see Short-circuit evaluation.
Programming
evaluation

Eager
Lazy
Partial
Remote
Short-circuit
Strategy

In computer programming, lazy evaluation (or delayed evaluation) is the technique of delaying a computation until such time as the result of the computation is known to be needed.

The actions of lazy evaluation include: performance increases due to avoiding unnecessary calculations, avoiding error conditions in the evaluation of compound expressions, the ability to construct infinite data structures, and the ability to define control structures as regular functions rather than built-in primitives.

Languages that use lazy actions can be further subdivided into those that use a call-by-name evaluation strategy and those that use call-by-need. Most realistic lazy languages, such as Haskell, use call-by-need for performance reasons, but theoretical presentations of lazy evaluation often use call-by-name for simplicity.

The opposite of lazy actions is eager evaluation, also known as strict evaluation. Eager evaluation is the evaluation behavior used in most programming languages.

Contents

[edit] Delayed evaluation

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") or, more generally, by wrapping the expression in a thunk. The object representing such an explicitly delayed evaluation is called a future or promise.

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.

[edit] Control structures

Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. This is because if one wished to write an if-then-else construct:

if' a b c 
       | a = b
       | otherwise = c

then in an eagerly evaluated language, both b and c would be evaluated fully; as these might be infinite or have side effects or any number of things, a good if-then-else construct could not be defined. If the function is lazily evaluated, then a would be evaluated and then only b or c, but not both — which is the desired behavior. As most programming languages are Turing-complete, it is of course possible to have lazy control structures in eager languages, either as built-ins like C's ternary operator ?: or by other techniques such as clever use of lambdas, or macros.

[edit] 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 data is not allocated.

[edit] See also

[edit] External links