Lazy evaluation: Encyclopedia II - Lazy evaluation - Delayed evaluation

Lazy evaluation - 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.

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 the Haskell programming language, the list of all Fibonacci numbers can be written as

  fibs = 1 : 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.

Adapted from the Wikipedia article "Delayed evaluation", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki