Personal tools

Lazy evaluation

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(cyclic list with constant space consumption)
m (added an external reference)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
'''Lazy evaluation''' means [[Non-strict semantics]] and [[Sharing]].
+
'''Lazy evaluation''' 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.
   
Non-strict semantics allows to bypass undefined values (e.g. results of infinite loops)
+
Technically, lazy evaluation means [[Non-strict semantics]] and [[Sharing]]. A kind of opposite is [[eager evaluation]].
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.
+
Non-strict semantics allows one to bypass undefined values (e.g. results of infinite loops)
A Haskell program cannot observe whether <hask>2+2 :: Int</hask> and <hask>4 :: Int</hask> are different objects in the memory.
+
and in this way it also allows one to process formally infinite data.
In many cases it is also not necessary to know it,
+
  +
When it comes to machine level and efficiency issues it is important whether or not equal objects share the same memory.
  +
A Haskell program cannot know whether <hask>2+2 :: Int</hask> and <hask>4 :: Int</hask> are different objects in the memory.
  +
In many cases it is not necessary to know it,
 
but in some cases the difference between shared and separated objects yields different orders of space or time complexity.
 
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>.
 
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>,
+
For 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.
 
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.
 
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.
+
It only consumes constant space.
 
In an imperative language (here [http://www.modula3.org/ Modula-3]) the same would be achieved with the following code:
 
In an imperative language (here [http://www.modula3.org/ Modula-3]) the same would be achieved with the following code:
   
Line 29: Line 29:
 
</code>
 
</code>
   
  +
Thus, lazy evaluation allows us to define cyclic graphs of pointers with warrantedly valid pointers.
  +
In contrast, 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.
  +
  +
  +
== See also ==
  +
  +
* [[Lazy vs. non-strict]]
  +
* [http://alpmestan.com/2013/10/02/oh-my-laziness/ Oh my laziness!], an introduction to laziness and strictness in Haskell
   
 
[[Category:Glossary]]
 
[[Category:Glossary]]

Latest revision as of 13:59, 17 January 2014

Lazy evaluation 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.

Non-strict 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.

When it comes to machine level and efficiency issues it is important whether or not equal objects share the same memory.

A Haskell program cannot know whether
2+2 :: Int
and
4 :: Int
are different objects in the memory.

In many cases it is 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
 let x = 1:x in x
. For non-strict semantics it would be ok to store this as a flat list
 1 : 1 : 1 : 1 : ...
, with memory consumption as big as the number of consumed
1
s.

But with lazy evaluation (i.e. sharing) this becomes a list with a loop, a pointer back to the beginning. It only consumes constant space. In an imperative language (here Modula-3) the same would be achieved with the following code:

TYPE
  List =
    REF RECORD
          next:  List;
          value: INTEGER;
        END;
VAR
  x := NEW(List, value:=1);
BEGIN
  x.next := x;
END;

Thus, lazy evaluation allows us to define cyclic graphs of pointers with warrantedly valid pointers. In contrast, 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.


[edit] See also