Lazy evaluation

In computer programming, lazy evaluation is a technique that attempts to delay computation of expressions until the results of the computation are known to be needed. It has two related, yet different, meanings that could be described as delayed evaluation and minimal evaluation.

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.

Compound Expressions

Suppose a logical expression such as (a and b) is to be evaluated: should term a be false, there is no need to evaluate term b in determining the result of the expression. Likewise, in (a or b) if term a is true. These terms might be complex expressions so the gain is obvious, and leads to thought as to which terms to present first in an expression based on the expected likelihood of a result true or false as well as the cost of evaluation. Thus in an expression such as (a or b or c) one would hope that term a is both quite likely to have the value true, and be easy to evaluate. To deliver on these possibilities, the compiler would insert tests to jump out of further evaluation, giving rise to the alternative term short-circuit evaluation. These tests, should they fail to jump, will of course increase the time taken to evaluate the full expression (in the cases where that is needed) over that needed for the unconditional full-evaluation approach.

A corresponding approach could be taken to the evaluation of arithmetic expressions: there is no point in adding zero to a number, and multiplications by zero or one have special effects. But introducing code to test for these special values is less beneficial as a number has many values besides these special ones whereas logical variables have but two values. However, the hardware performing the calculation might well attend to special cases, if for no other reason than that zero is not representable as a normalised floating-point value.

Evading error conditions

Suppose you have some expression that in certain situations must not be evaluated lest an error condition be triggered. The expression might be protected via a form such as (safetoevaluate and expression) for instance in something like (N <> 0 and (x mod N = 0)) - perhaps to insert a blank line in a report every N lines, or, to not do so at all. Obviously, this could be written as if N <> 0 then if x mod N = 0 then ... which already is a little clunky. Contrariwise, you may have a case where the test is (a or b) and if a is true, not only ought b not be evaluated but doing so might or would cause trouble. Since you do wish the action taken if either a or b is true (that is what the expression means!) the polite form becomes if a then action else if b then action; which repetition conduces to mistakes.

More sensibly, suppose you have a text string with possible trailing spaces and you wish to know the location of the last non-blank character. l:=Length(t); %Pace C-programmers, where this scans the string for the terminating zero character. while l > 0 and t(l) = " " do decrement l; or, in a more flexible language, for l:=Length(t):1:-1 while t(l) = " " do; Clearly, if the string is entirely filled with spaces, l should become zero, but, there must be no attempt to access character zero of the string. It would be wasted effort at best, and an error at worst.

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, however 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 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.

External links

Functional programming in Python becomes lazy

References

Steve Summit's C FAQs

Programming paradigms | Programming evaluation | Compiler_optimizations

Évaluation paresseuse | 느긋한 계산법 | Wartościowanie leniwe | Ленивые вычисления | 惰性计算

Gourt Home::Gourt :: Lazy evaluation

Compound Expressions

Evading error conditions

Delayed evaluation

See also

External links

References