Personal tools

Lazy evaluation

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Added simple intro)
m (s/The things is/The thing is/)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
'''Lazy evaluation''' causes that expressions are not evaluated when they are bound to variables, but their evaluation is '''deferred''' until their results are needed by other computations. In consequence, arguments are not evaluated before they are passed to a function, but only when their values are actually used.
+
'''Lazy evaluation''' is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is '''deferred''' until their results are needed by other computations. In consequence, arguments are not evaluated before they are passed to a function, but only when their values are actually used.
  
Technically, lazy evaluation means [[Non-strict semantics]] and [[Sharing]]. A kind of opposite is [[eager evaluation]].
+
Technically, lazy evaluation means [http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name call-by-name] plus [[Sharing]]. A kind of opposite is [[eager evaluation]].
  
Non-strict semantics allows to bypass undefined values (e.g. results of infinite loops)
+
Lazy evaluation is part of operational semantics, i.e. ''how'' a Haskell program is evaluated. The counterpart in denotational semantics, i.e. ''what'' a Haskell program computes, is called [[Non-strict semantics]]. This semantics allows one to bypass undefined values (e.g. results of infinite loops) and in this way it also allows one to process formally infinite data.
and this way it also allows to process formally infinite data.
+
  
When it comes to machine level and efficiency issues then it is important whether equal objects share the same memory.
+
While lazy evaluation has many advantages, its main drawback is that memory usage becomes hard to predict. The thing is that while two expressions, like <hask>2+2 :: Int</hask> and <hask>4 :: Int</hask>, may denote the same value 4, they may have very different sizes and hence use different amounts of memory.
A Haskell program cannot observe whether <hask>2+2 :: Int</hask> and <hask>4 :: Int</hask> are different objects in the memory.
+
In many cases it is also not necessary to know it,
+
but in some cases the difference between shared and separated objects yields different orders of space or time complexity.
+
Consider the infinite list <hask> let x = 1:x in x </hask>.
+
For the non-strict semantics it would be ok to store this as a flat list <hask> 1 : 1 : 1 : 1 : ... </hask>,
+
with memory consumption as big as the number of consumed <hask>1</hask>s.
+
But with lazy evaluation (i.e. sharing) this becomes a list with a loop, a pointer back to the beginning.
+
It does only consume constant space.
+
In an imperative language (here [http://www.modula3.org/ Modula-3]) the same would be achieved with the following code:
+
 
+
<code>
+
TYPE
+
  List =
+
    REF RECORD
+
          next:  List;
+
          value: INTEGER;
+
        END;
+
 
+
VAR
+
  x := NEW(List, value:=1);
+
BEGIN
+
  x.next := x;
+
END;
+
</code>
+
 
+
That is lazy evaluation allows us to define cyclic graphs of pointers with warrantedly valid pointers.
+
In contrast to that C allows cyclic graphs of pointers, but pointers can be uninitialized, which is a nasty security hole.
+
An eagerly evaluating functional language without hacks, would only allow for acyclic graphs of pointers.
+
  
 +
An extreme example would be the infinite list
 +
<hask>1 : 1 : 1 …</hask> and the expression <hask> let x = 1:x in x </hask>. The latter is represented as a cyclic graph, and takes only finite memory, but its denotation is the former infinite list.
  
 
== See also ==
 
== See also ==
  
 
* [[Lazy vs. non-strict]]
 
* [[Lazy vs. non-strict]]
 +
* [https://hackhands.com/guide-lazy-evaluation-haskell/ The Incomplete Guide to Lazy Evaluation] – A series of tutorials on lazy evaluation: How it works, how it makes code more modular, how it relates to non-strict semantics, and other things.
 +
* [http://alpmestan.com/posts/2013-10-02-oh-my-laziness.html Oh my laziness!] – An introduction to laziness and strictness in Haskell.
  
 
[[Category:Glossary]]
 
[[Category:Glossary]]

Latest revision as of 03:52, 3 September 2015

Lazy evaluation is a method to evaluate a Haskell program. It means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations. In consequence, arguments are not evaluated before they are passed to a function, but only when their values are actually used.

Technically, lazy evaluation means call-by-name plus Sharing. A kind of opposite is eager evaluation.

Lazy evaluation is part of operational semantics, i.e. how a Haskell program is evaluated. The counterpart in denotational semantics, i.e. what a Haskell program computes, is called Non-strict semantics. This semantics allows one to bypass undefined values (e.g. results of infinite loops) and in this way it also allows one to process formally infinite data.

While lazy evaluation has many advantages, its main drawback is that memory usage becomes hard to predict. The thing is that while two expressions, like
2+2 :: Int
and
4 :: Int
, may denote the same value 4, they may have very different sizes and hence use different amounts of memory.

An extreme example would be the infinite list

1 : 1 : 1
and the expression
 let x = 1:x in x
. The latter is represented as a cyclic graph, and takes only finite memory, but its denotation is the former infinite list.

[edit] See also