Lazy evaluation


Lazy evaluation

In computer programming, lazy evaluation (or delayed evaluation) is the technique of delaying a computation until such time as the result of the computation is known to be needed.

The actions 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 actions 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 actions is eager evaluation, also known as "strict evaluation". Eager evaluation is the evaluation behavior used in most programming languages.

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; (i.e. the assignment of the result of an expression to a variable) clearly calls for the expression to be evaluated and the result placed in x, but what actually is in x is irrelevant until there is a need 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" and OCaml's "lazy" and "Lazy.force") or, more generally, by wrapping the expression in a thunk. The object representing such an explicitly delayed evaluation is called a future or promise.

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 only the first n members of the list.

For example, in Haskell, the list of all Fibonacci numbers can be written as

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

Control structures

Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. This is because if one wished to write an if-then-else construct: if' a b c
a = b
otherwise = c
then in an eagerly evaluated language, both b and c would be evaluated fully; as these might be infinite or have side effects or any number of things, a good if-then-else construct could not be defined. If the function is lazily evaluated, then a would be evaluated and then only b or c, but not both — which is the desired behavior. As most programming languages are Turing-complete, it is of course possible to have lazy control structures in eager languages, either as built-ins like C's ternary operator ?: or by other techniques such as clever use of lambdas, or macros.

Other uses

In computer windowing systems, 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 computation of unnecessary display content.

Another example of laziness in modern computer systems is copy-on-write page allocation or demand paging, where memory is allocated only when a value stored in that memory is changed.

Laziness can be useful for high performance scenarios. An example is the Unix mmap functionality. mmap provides "demand driven" loading of pages from disk, so thatonly those pages actually touched are loaded into memory, and unnecessary memory is not allocated.

ee also

*Combinatory logic
*Currying
*Dataflow
*Eager evaluation
*Functional programming
*Graph reduction
*Lambda calculus
*Lazy initialization
*Lookahead
*Minimal evaluation
*Non-strict programming language
*Normal order evaluation

External links

* [http://gnosis.cx/publish/programming/charming_python_b13.html Functional programming in Python becomes lazy]
* [http://www.digitalmars.com/d/lazy-evaluation.html Lazy function argument evaluation] in the D programming language
* [http://nemerle.org/Lazy_evaluation Lazy evaluation macros] in Nemerle
* [http://www-128.ibm.com/developerworks/linux/library/l-lazyprog.html Lazy programming and lazy evaluation] in Scheme
* [http://www.iolanguage.com/docs/talks/2005-10-OOPSLA/p003-dekorte.pdf Lazy argument evaluation] in Io programming language
* [http://groups.google.com/group/comp.lang.c/browse_thread/thread/22211d03c3e0b5c9/f11f83cdbde4eee8 Lazy evaluation list/set processing] in C programming language


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Lazy Evaluation — ist eine Technologie in der Informatik, bei der das Ergebnis eines Ausdrucks nur so weit berechnet wird, wie es gerade benötigt wird. Ein Vorteil einer solchen Auswertungsstrategie ist Zeitersparnis, da Funktionsaufrufe ganz vermieden oder… …   Deutsch Wikipedia

  • lazy evaluation — atidėtasis vykdymas statusas T sritis informatika apibrėžtis ↑Reiškinio skaičiavimo, funkcijos arba procedūros vykdymo sulaikymas iki tol, kol bus reikalingas jų vykdymo rezultatas. Programoje užrašytas veiksmas įsimenamas, bet nevykdomas –… …   Enciklopedinis kompiuterijos žodynas

  • lazy evaluation — noun Any of a variety of computing techniques that delays the computation of expressions until (and unless) the results are needed. Ant: strict evaluation, eager evaluation …   Wiktionary

  • Evaluation strategy — Evaluation strategies Strict evaluation Applicative order Call by value Call by reference Call by sharing Call by copy restore Non strict evaluation Normal order Call by name Call by need/Lazy evaluation …   Wikipedia

  • Lazy systematic unit testing — Lazy Systematic Unit TestingA J H Simons, JWalk: Lazy systematic unit testing of Java classes by design introspection and user interaction, Automated Software Engineering, 14 (4), December , ed. B. Nuseibeh, (Boston: Springer, 2007), 369 418.] is …   Wikipedia

  • Lazy loading — is a design pattern commonly used in computer programming to defer initialization of an object until the point at which it is needed. It can contribute to efficiency in the program s operation if properly and appropriately used. The opposite of… …   Wikipedia

  • Lazy — can refer to: * Laziness, the lack of desire to expend effort * Łazy, a town in Poland (and other places in Poland with the same name) * Lazy (Orlová), a former village now part of the town of Orlová in the Czech Republic * Lazy (song), by Suede… …   Wikipedia

  • Evaluation (disambiguation) — Evaluation is the process of characterizing and appraising something of interest or of determining the value of an expression (mathematics). Computer science * determining the value of an expression (programming) * Eager evaluation or strict… …   Wikipedia

  • Lazy ML — (LML) is a functional programming language developed in the early 1980s by Lennart Augustsson and Thomas Johnsson at Chalmers University of Technology, prior to Miranda and Haskell. LML is a strongly typed, statically scoped language with lazy… …   Wikipedia

  • Lazy initialization — In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. This is typically accomplished by maintaining a flag… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.