Lazy evaluation
From Wikipedia, the free encyclopedia
| Programming evaluation |
|---|
- The term lazy evaluation can also refer to minimal evaluation, also called short-circuit evaluation.
In computer programming, lazy evaluation, also called delayed evaluation, is the technique of delaying a computation until such time as the result of the computation is known to be needed.
The benefits 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 evaluation 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 evaluation 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; 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 demand 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.
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 the first n members of the list only.
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] Other uses
In computer window managers, 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 accessed.
[edit] See also
- Combinatory logic
- Currying
- Dataflow
- Functional programming
- Graph reduction
- Lambda calculus
- Lazy initialization
- Lookahead
- Minimal evaluation
- Non-strict programming language
- Normal order evaluation
