lazy evaluation

[′lā·zē i‚val·yə′wā·shən]

(computer science)

lazy evaluation

(reduction)

An evaluation strategy combining normal order evaluation with updating. Under normal order evaluation (outermost or call-by-name evaluation) an expression is evaluated only when its value is needed in order for the program to return (the next part of) its result. Updating means that if an expression's value is needed more than once (i.e. it is shared), the result of the first evaluation is remembered and subsequent requests for it will return the remembered value immediately without further evaluation. This is often implemented by graph reduction. An unevaluated expression is represented as a closure - a data structure containing all the information required to evaluate the expression.

Lazy evaluation is one evaluation strategy used to implement non-strict functions. Function arguments may be infinite data structures (especially lists) of values, the components of which are evaluated as needed.

According to Phil Wadler the term was invented by Jim Morris.

Opposite: eager evaluation.

A partial kind of lazy evaluation implements lazy data structures or especially lazy lists where function arguments are passed evaluated but the arguments of data constructors are not evaluated.

Full laziness is a program transformation which aims to optimise lazy evaluation by ensuring that all subexpressions in a function body which do not depend on the function's arguments are only evaluated once.

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

Mentioned in

References in periodicals archive

The bizarre, surreal management mess at NUFC even appears to be metamorphosing into an easy, lazy evaluation of Newcastle's ability to manage itself in the eyes of a few tunnel-visioned businesspeople I spoke to.

Cyclists are true sport champions; in association with RBS

The language also supports recursive functions and datatypes, as well as lazy evaluation. Unique concepts include monads, and type classes.

Haskell programming language

"How much?" -s a lazy evaluation. We believe intuitively, that a $2 search piece is twice as expensive as a $1 search piece.

How effective is your marketing? Here's how to make sure you're evaluating marketing effectiveness intelligently

The aim of lazy evaluation [Friedman and Wise 1976; Henderson and Morris 1976], which underlies lazy functional languages (e.g., see Plasmeijer and van Eekelen [1993]) and equational programming [Hoffmann and O'Donnell 1982b], is to combine an efficient implementation with good termination properties.

the performance of eager implementations" and that "interpreters for strict languages (Caml Light, Epic) do seem on the whole to be faster than interpreters for non-strict languages (NHC, Gofer, RUFLI, Miranda)." A bottleneck for the performance of lazy evaluation, compared to eager evaluation, is that it requires a considerable amount of bookkeeping.

We investigate how an eager implementation can be adapted to do some lazy evaluation. We propose the notion of a laziness annotation, which assigns to each argument of a function symbol either the label "eager" or the label "lazy." Only redexes that are not the subterm of a lazy argument (the so-called "active" redexes) are reduced whenever possible, according to the innermost rewriting strategy.

A standard application of lazy evaluation, where compared to eager evaluation it improves both termination behavior and performance, is the if-then-else construct:

In order to solve this inefficiency, lazy evaluation is usually performed by graph rewriting [Staples 1980] instead of term rewriting.

Lazy Rewriting on Eager Machinery

Two implementations are possible: a full evaluation scheme computes the entire set of answers at once, while a lazy evaluation scheme computes only the result, and nodes from inner operands of the query syntax tree are obtained only if they are necessary to compute the final result.

Experimental results (as demonstrated later) show that lazy evaluation is normally better.

For lazy evaluation, instead, we keep a pointer to a node in the disk, and ask it to do the following (3) given a node, retrieve all of its top-level descendants of the same type and (4) given a node, retrieve all of its children.

Observe that this index is not well suited for lazy evaluation, since it cannot efficiently implement (3).

Proximal nodes: a model to query document databases by content and structure