Lazy evaluation

In computer programming, lazy evaluation is a concept that attempts to minimize the work the computer has to do. It has two related, yet different, meanings that could be described as delayed evaluation and minimal evaluation. Besides performance increases, the most important benefit of lazy evaluation is that it allows one to construct an infinite data structure.

The opposite of lazy evaluation is eager evaluation, also known as strict evaluation. This is the normal evaluation behavior in most programming languages.

Contents

1 Minimal evaluation 2 Delayed evaluation 3 Lazy evaluation as a design pattern 4 See also 5 Tutorials

Minimal evaluation

Minimal evaluation (also known as short circuit evaluation) is an evaluation strategy in which an expression is only evaluated until the point where its final value is known. This means that in some cases it's not necessary to evaluate all the parts of an expression. Consider the following example using the C programming language:

   int a = 0;
   if (a && myfunc(b)) {
       do_something();
   }

In this example minimal evalution guarantees that myfunc(b) is never called. This is because a evaluates to false, and false AND q evaluates to false for any value of q. This feature permits two useful programming constructs. Firstly, if the first sub-expression checks whether an expensive computation is needed and the check evaluates to false, one can eliminate expensive computation in the second argument. Secondly, it permits a construct where the first expression guarantees a condition without which the second expression may cause a runtime error, such as in the following C code where minimal evaluation prevents a null pointer dereference:

   bool is_three_chars_long(const char *p) {
     return p && (strlen(p) == 3);
   }

When using minimal evaluation it is important to know the expression evaluation order. A consistent order is guaranteed in some (but not all) programming languages, for example, C, Java, Perl, Python, and Ruby.

It is worth noting that such expressions are simply a more compact way of saying:

   if (cond_a) {
       if (expensive_or_dangerous_cond_b) {
           ...
       }
   }

Minimal evaluation is also responsible for the common Perl idiom:

 some_condition or die;    # Abort execution if some_condition is false

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 to delay evaluation. In Miranda and Haskell, evaluation is delayed by default. In the Scheme programming language, evaluation can be delayed by saying (define delayed-expression (delay expression)). Then (force delayed-expression) will yield the value of expression.

Delayed evaluation has the added advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation. One could create a function that creates an infinite list 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)

Here, : 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, the entire infinite list is never calculated, but only the values that are required to produce a result. However, certain calculations may result in the program attempting to evaluate the entire list and crashing; for example requesting the length of the list, or trying to sum the elements of the list with a fold operation.

Lazy evaluation as a design pattern

As well as the formal concept of lazy evaluation in programming languages, lazy evaluation is a design pattern often seen in general computer programming.

For example, in modern 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 over-eager computation of unnecessary display content.

Another example of laziness in modern computer systems is copy-on-write page allocation.

See also

• non-strict programming language
• functional programming
• lambda calculus
• combinatory logic
• Currying
• Graph reduction

Compare:

• Lazy initialization

Tutorials

• Lazy Programming in Ocaml (http://www.bagley.org/~doug/ocaml/Notes/lazy.shtml)