lazy evaluation

reduction An evaluation strategy combining normal orderevaluation 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.

(1994-12-14)