Editing Lazy evaluation

{{Short description|Software optimization technique}}
{{Evaluation strategy}}
In [[programming language theory]], '''lazy evaluation''', or '''call-by-need''',<ref>{{harvnb|Hudak|1989|p=384}}</ref> is an [[evaluation strategy]] which delays the evaluation of an [[Expression (computer science)|expression]] until its value is needed ([[non-strict evaluation]]) and which avoids repeated evaluations (by the use of [[Sharing (computer science)|sharing]]).<ref name="WattFindlay2004">{{cite book|author1=David Anthony Watt|author2=William Findlay|title=Programming language design concepts|url=https://books.google.com/books?id=vogP3P2L4tgC&pg=PA367|access-date=30 December 2010|year=2004|publisher=John Wiley and Sons|isbn=978-0-470-85320-7|pages=367–368}}</ref><ref>{{harvnb|Reynolds|1998|p=307}}</ref>

The benefits of lazy evaluation include: 
* The ability to define [[control flow]] (structures) as abstractions instead of [[Language primitive|primitives]].
* The ability to define [[actual infinity|potentially infinite]] [[data structure]]s. This allows for more straightforward implementation of some [[algorithm]]s.
* The ability to define partly-defined data structures where some elements are errors. This allows for rapid prototyping.

Lazy evaluation is often combined with [[memoization]], as described in [[Jon Bentley (computer scientist)|Jon Bentley]]'s ''Writing Efficient Programs''.<ref>Bentley, Jon Louis. Writing Efficient Programs. Prentice-Hall, 1985. {{ISBN|978-0139702440}}</ref> After a function's value is computed for that [[Parameter (computer programming)|parameter]] or set of parameters, the result is stored in a [[lookup table]] that is indexed by the values of those parameters; the next time the function is called, the table is consulted to determine whether the result for that combination of parameter values is already available. If so, the stored result is simply returned. If not, the function is evaluated, and another entry is added to the lookup table for reuse.

Lazy evaluation is difficult to combine with [[Imperative programming|imperative]] features such as [[exception handling]] and [[input/output]], because the [[order of operations]] becomes indeterminate.

The opposite of lazy evaluation is [[eager evaluation]], sometimes known as strict evaluation. Eager evaluation is the evaluation strategy employed in most{{quantify|date=July 2020}} [[programming language]]s.

== History ==
Lazy evaluation was introduced for [[lambda calculus]] by Christopher Wadsworth.<ref>{{harvnb|Wadsworth|1971}}</ref> For programming languages, it was independently introduced by Peter Henderson and [[James H. Morris]]<ref>{{harvnb|Henderson|Morris|1976}}</ref> and by [[Daniel P. Friedman]] and David S. Wise.<ref>{{harvnb|Friedman|Wise|1976}}</ref><ref>{{harvnb|Reynolds|1998|p=312}}</ref>

== Applications ==
Delayed evaluation is used particularly in [[functional programming]] 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 <code>x = expression;</code> (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 <code>x</code>, but what actually is in <code>x</code> is irrelevant until there is a need for its value via a reference to <code>x</code> in some later expression whose evaluation could itself be deferred, though eventually the rapidly growing tree of dependencies would be pruned to produce some symbol rather than another for the outside world to see.<ref name="Wadler2006">{{cite conference |last1=Casas |first1=A. |last2=Cabeza |first2=D. |last3=Hermenegildo |first3=M.V. |title=A Syntactic Approach to Combining Functional Notation, Lazy Evaluation, and Higher-Order in LP Systems |editor-last=Hagiya |editor-first=M. |editor2-first=P. |editor2-last=Wadler |book-title=Functional and logic programming, FLOPS 2006 |url=https://books.google.com/books?id=gZzLFFZfc1sC&pg=PA149|access-date=14 January 2011 |year=2006 |publisher=Springer |isbn=978-3-540-33438-5 |page=149 |doi=10.1007/11737414_11 |series=Lecture Notes in Computer Science |volume=3945|url-access=subscription }}</ref>

===Control structures===
{{More citations needed section|date=March 2011}}
Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. For example, one can define [[if-then-else]] and [[short-circuit evaluation]] operators:<ref>{{cite web |title=utility-ht: Data.Bool.HT.Private |url=https://hackage.haskell.org/package/utility-ht-0.0.16/docs/src/Data.Bool.HT.Private.html#if%27 |website=hackage.haskell.org |access-date=8 January 2022}}</ref><ref>{{cite web |title=The Haskell 98 Report: Standard Prelude |url=https://www.haskell.org/onlinereport/standard-prelude.html |website=www.haskell.org |access-date=8 January 2022 |location=Boolean functions}}</ref>

<syntaxhighlight lang="haskell">
ifThenElse True b c = b
ifThenElse False b c = c

-- or
True || b = True
False || b = b

-- and
True && b = b
False && b = False
</syntaxhighlight>

These have the usual semantics, i.e., {{code|ifThenElse a b c|lang=Haskell}} evaluates (a), then if and only if (a) evaluates to true does it evaluate (b), otherwise it evaluates (c). That is, exactly one of (b) or (c) will be evaluated. Similarly, for {{code|EasilyComputed <nowiki>||</nowiki> LotsOfWork|lang=Haskell}}, if the easy part gives '''True''' the lots of work expression could be avoided. Finally, when evaluating {{code|SafeToTry && Expression|lang=haskell}}, if ''SafeToTry'' is '''false''' there will be no attempt at evaluating the ''Expression''.

Conversely, in an eager language the above definition for {{code|ifThenElse a b c|lang=Haskell}} would evaluate (a), (b), and (c) regardless of the value of (a). This is not the desired behavior, as (b) or (c) may have [[Side effect (computer science)|side effects]], take a long time to compute, or throw errors. It is usually possible to introduce user-defined lazy control structures in eager languages as functions, though they may depart from the language's syntax for eager evaluation: Often the involved code bodies need to be wrapped in a function value, so that they are executed only when called.

=== Working with infinite data structures ===
Delayed evaluation has the advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation. The actual values are only computed when needed. For example, one could create a function that creates an infinite list (often called a ''[[Stream (computing)|stream]]'') of [[Fibonacci number]]s. 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.<ref name="Métayer2002">{{cite conference |last1=Wells |first1=J.B. |last2=Haack |first2=C. |title=Branching Types|editor-first=Daniel |editor-last=Le Métayer |book-title=Programming languages and systems, ESOP 2002 |year=2002 |series=Lecture Notes in Computer Science |volume=2305 |doi=10.1007/3-540-45927-8_9 |publisher=Springer |isbn=978-3-540-43363-7 |pages=129–132|doi-access=free }}</ref><ref name="MachineryLanguages2002">{{cite conference |first=Jan-Willem |last=Maessen |title=Eager Haskell: resource-bounded execution yields efficient iteration |book-title=Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell '02): Pittsburgh, Pennsylvania, USA; October 3, 2002 |date=2002|publisher=Association for Computing Machinery|isbn=978-1-58113-605-0|pages=38–50 See p. 40 |doi=10.1145/581690.581694}}</ref>

Take for example this trivial program in [[Haskell]]:

<syntaxhighlight lang="haskell">
numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4
</syntaxhighlight>

In the function {{mono|numberFromInfiniteList}}, the value of {{mono|infinity}} is an infinite range, but until an actual value (or more specifically, a specific value at a certain index) is needed, the list is not evaluated, and even then, it is only evaluated as needed (that is, until the desired index.) Provided the programmer is careful, the program completes normally. 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 (higher-order function)|fold operation]] would result in the program either failing to terminate or running [[out of memory]].

As another example, the list of all Fibonacci numbers can be written in the programming language [[Haskell]] as:<ref name="MachineryLanguages2002"/>

<syntaxhighlight lang="haskell">
 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
</syntaxhighlight>

In Haskell syntax, "<code>:</code>" prepends an element to a list, <code>tail</code> returns a list without its first element, and <code>zipWith</code> uses a specified function (in this case addition) to combine corresponding elements of two lists to produce a third.<ref name="Métayer2002"/>

=== List-of-successes pattern ===
{{expand section|date=March 2011}}

===Other uses===
In computer [[windowing system]]s, 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, windowing systems avoid computing unnecessary display content updates.<ref name="Lampson">[http://research.microsoft.com/en-us/um/people/blampson/slides/lazyandspeculative.ppt Lazy and Speculative Execution] [[Butler Lampson]] [[Microsoft Research]] OPODIS, Bordeaux, France 12 December 2006</ref>

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.<ref name="Lampson"/>

Laziness can be useful for high performance scenarios. An example is the Unix [[mmap]] function, which provides ''demand driven'' loading of pages from disk, so that only those pages actually touched are loaded into memory, and unneeded memory is not allocated.

[[MATLAB]] implements ''[[copy on write|copy on edit]]'', where arrays which are copied have their actual memory storage replicated only when their content is changed, possibly leading to an ''out of memory'' error when updating an element afterwards instead of during the copy operation.<ref>{{cite web|url=http://www.mathworks.co.uk/matlabcentral/answers/46551-out-of-memory-when-assigning-values-to-existing-arrays|title=Out of memory when assigning values to existing arrays? |work=MATLAB Answers |publisher=MATLAB Central}}</ref>

==Performance==
The number of beta reductions to reduce a lambda term with call-by-need is no larger than the number needed by call-by-value or [[call-by-name]] reduction.<ref>{{cite book |last1=Niehren |first1=Joachim |title=Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 |chapter=Functional computation as concurrent computation |date=1996 |pages=333–343 |doi=10.1145/237721.237801 |isbn=0897917693 |s2cid=7332050 |url=https://hal.inria.fr/inria-00536819/file/POPL96.pdf |chapter-url=https://publikationen.sulb.uni-saarland.de/bitstream/20.500.11880/25024/1/RR_95_14.pdf}}</ref><ref>{{cite journal |last1=Niehren |first1=Joachim |title=Uniform confluence in concurrent computation |journal=Journal of Functional Programming |date=September 2000 |volume=10 |issue=5 |pages=453–499 |doi=10.1017/S0956796800003762 |s2cid=66013 |url=https://hal.inria.fr/inria-00536801/document |access-date=7 January 2022}}</ref> And with certain programs the number of steps may be much smaller, for example a specific family of lambda terms using [[Church numeral]]s take an infinite amount of steps with call-by-value (i.e. never complete), an exponential number of steps with call-by-name, but only a polynomial number with call-by-need. Call-by-need embodies two optimizations - never repeat work (similar to call-by-value), and never perform unnecessary work (similar to call-by-name).<ref name=Stelle>{{cite thesis |last1=Stelle |first1=George Widgery |title=Shared-Environment Call-by-Need |date=July 2019 |url=https://digitalrepository.unm.edu/cgi/viewcontent.cgi?article=1099&context=cs_etds#page=23 |access-date=8 January 2022|publisher=University of New Mexico|type=PhD|pages=11–12}}</ref> 
Lazy evaluation can also lead to reduction in [[memory footprint]], since values are created when needed.<ref name="Smith2009">{{cite book|author=Chris Smith|title=Programming F#|url=https://books.google.com/books?id=gzVdyw2WoXMC&pg=PA79|access-date=31 December 2010|date=22 October 2009|publisher=O'Reilly Media, Inc.|isbn=978-0-596-15364-9|page=79}}</ref>

In practice, lazy evaluation may cause significant performance issues compared to eager evaluation. For example, on modern computer architectures, delaying a computation and performing it later is slower than performing it immediately. This can be alleviated through [[strictness analysis]].<ref name=Stelle/> Lazy evaluation can also introduce [[memory leak]]s due to unevaluated expressions.{{sfn|Launchbury|1993}}<ref>Edward Z. Yang. [http://blog.ezyang.com/2011/05/space-leak-zoo/ "Space leak zoo"].</ref>

==Implementation==
Some programming languages delay evaluation of expressions by default, and some others provide [[subroutine|functions]] or special [[syntax of programming languages|syntax]] to delay evaluation. In [[KRC (programming language)|KRC]], [[Miranda (programming language)|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 (programming language)|Scheme's]] "<code>delay</code>" and "<code>force</code>" and [[OCaml]]'s "<code>lazy</code>" and "<code>Lazy.force</code>") or, more generally, by wrapping the expression in a [[thunk (delayed computation)|thunk]]. The object representing such an explicitly delayed evaluation is called a ''[[lazy future]].'' [[Raku (programming language)|Raku]] uses lazy evaluation of lists, so one can assign infinite lists to variables and use them as arguments to functions, but unlike Haskell and Miranda, Raku does not use lazy evaluation of arithmetic operators and functions by default.<ref name="Wadler2006"/>

== Laziness and eagerness ==
===Controlling eagerness in lazy languages===
In lazy programming languages such as Haskell, although the default is to evaluate expressions only when they are demanded, it is possible in some cases to make code more eager—or conversely, to make it more lazy again after it has been made more eager. This can be done by explicitly coding something which forces evaluation (which may make the code more eager) or avoiding such code (which may make the code more lazy). ''Strict'' evaluation usually implies eagerness, but they are technically different concepts.

However, there is an optimisation implemented in some compilers called [[strictness analysis]], which, in some cases, allows the compiler to infer that a value will always be used. In such cases, this may render the programmer's choice of whether to force that particular value or not, irrelevant, because strictness analysis will force [[strict evaluation]].

In Haskell, marking [[Constructor (object-oriented programming)|constructor]] fields strict means that their values will always be demanded immediately. The <code>seq</code> function can also be used to demand a value immediately and then pass it on, which is useful if a constructor field should generally be lazy. However, neither of these techniques implements ''recursive'' strictness—for that, a function called <code>deepSeq</code> was invented.

Also, [[pattern matching]] in Haskell 98 is strict by default, so the <code>[[Tilde#Computer_languages|~]]</code> qualifier has to be used to make it lazy.<ref>{{cite web|url=http://www.haskell.org/haskellwiki/Lazy_pattern_match|title=Lazy pattern match - HaskellWiki}}</ref>

=== Simulating laziness in eager languages ===
====Java====
In [[Java (programming language)|Java]], lazy evaluation can be done by using objects that have a method to evaluate them when the value is needed. The body of this method must contain the code required to perform this evaluation. Since the introduction of [[Anonymous function|lambda expressions]] in Java SE8, Java has supported a compact notation for this. The following example [[Generic classes in Java|generic]] interface provides a framework for lazy evaluation:<ref name="Piwowarek2018">Grzegorz Piwowarek, [https://4comprehension.com/leveraging-lambda-expressions-for-lazy-evaluation-in-java/ Leveraging Lambda Expressions for Lazy Evaluation in Java], [https://4comprehension.com/ 4Comprehension], July 25, 2018.</ref><ref name="Jones2020">Douglas W. Jones, [https://homepage.divms.uiowa.edu/~jones/object/fall20/notes/25.shtml CS:2820 Notes, Fall 2020, Lecture 25], retrieved Jan. 2021.</ref>
<syntaxhighlight lang="java">
interface Lazy<T> {
    T eval();
}
</syntaxhighlight>

The <code>Lazy</code> interface with its <code>eval()</code> method is equivalent to the <code>Supplier</code> interface with its <code>get()</code> method in the <code>java.util.function</code> library.<ref>[https://docs.oracle.com/javase/8/docs/api/java/util/function/Supplier.html Interface Suppier<T>], retrieved Oct. 2020.</ref><ref name=Bloch>{{cite book | title= "Effective Java: Programming Language Guide" |last=Bloch| first=Joshua| publisher=Addison-Wesley | edition=third | isbn=978-0134685991| year=2018}}</ref>{{rp|200}}

Each class that implements the <code>Lazy</code> interface must provide an <code>eval</code> method, and instances of the class may carry whatever values the method needs to accomplish lazy evaluation. For example, consider the following code to lazily compute and print 2<sup>10</sup>:
<syntaxhighlight lang="java">
Lazy<Integer> a = () -> 1;
for (int i = 0; i < 10; i++) {
    Lazy<Integer> b = a;
    a = () -> b.eval() + b.eval();
}
System.out.println("a = " + a.eval());
</syntaxhighlight>

In the above, the variable {{mono|a}} initially refers to a lazy integer object created by the lambda expression <code>() -> 1</code>. Evaluating this lambda expression is similar{{efn|name=Java Lambda|Java lambda expressions are not exactly equivalent to anonymous classes, see [[Anonymous function#Differences compared to Anonymous Classes]]}} to constructing a new instance of an [[anonymous class]] that implements <code>Lazy<Integer></code> with an {{mono|eval}} method returning {{mono|1}}.

Each iteration of the loop links {{mono|a}} to a new object created by evaluating the lambda expression inside the loop. Each of these objects holds a reference to another lazy object, {{mono|b}}, and has an {{mono|eval}} method that calls <code>b.eval()</code> twice and returns the sum. The variable {{mono|b}} is needed here to meet Java's requirement that variables referenced from within a lambda expression be effectively final.

This is an inefficient program because this implementation of lazy integers does not [[memoize]] the result of previous calls to {{mono|eval}}. It also involves considerable [[Autoboxing|autoboxing and unboxing]]. What may not be obvious is that, at the end of the loop, the program has constructed a [[linked list]] of 11 objects and that all of the actual additions involved in computing the result are done in response to the call to <code>a.eval()</code> on the final line of code. This call [[Recursion (computer science)|recursively]] traverses the list to perform the necessary additions.

We can build a Java class that memoizes a lazy object as follows:<ref name="Piwowarek2018" /><ref name="Jones2020" />
<syntaxhighlight lang="java">
class Memo<T> implements Lazy<T> {
    private Lazy<T> lazy;  // a lazy expression, eval sets it to null
    private T memo; // the memorandum of the previous value

    public Memo(Lazy<T> lazy) {
        this.lazy = lazy;
    }

    public T eval() {
        if (lazy != null) {
            memo = lazy.eval();
            lazy = null;
        }
        return memo;
    }
}
</syntaxhighlight>

This allows the previous example to be rewritten to be far more efficient. Where the original ran in time exponential in the number of iterations, the memoized version runs in [[linear time]]:
<syntaxhighlight lang="java">
Lazy<Integer> a = () -> 1;
for (int i = 0; i < 10; i++) {
    Lazy<Integer> b = a;
    a = new Memo<Integer>(() -> b.eval() + b.eval());
}
System.out.println("a = " + a.eval());
</syntaxhighlight>

Java's lambda expressions are just [[syntactic sugar]]. Anything that can be written with a lambda expression can be rewritten as a call to construct an instance of an anonymous [[inner class]] implementing the interface,{{efn|name=Java Lambda}} and any use of an anonymous inner class can be rewritten using a named inner class, and any named inner class can be moved to the outermost nesting level.

====JavaScript====
In [[JavaScript]], lazy evaluation can be simulated by using a [[Generator (computer programming)|generator]]. For example, the [[Stream (computing)|stream]] of all [[Fibonacci numbers]] can be written, using [[memoization]], as:
<syntaxhighlight lang="js">
/**
 * Generator functions return generator objects, which reify lazy evaluation.
 * @return {!Generator<bigint>} A non-null generator of integers.
 */
function* fibonacciNumbers() {
    let memo = [1n, -1n]; // create the initial state (e.g. a vector of "negafibonacci" numbers)
    while (true) { // repeat indefinitely
        memo = [memo[0] + memo[1], memo[0]]; // update the state on each evaluation
        yield memo[0]; // yield the next value and suspend execution until resumed
    }
}

let stream = fibonacciNumbers(); // create a lazy evaluated stream of numbers
let first10 = Array.from(new Array(10), () => stream.next().value); // evaluate only the first 10 numbers
console.log(first10); // the output is [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n]
</syntaxhighlight>

====Python====
In [[Python (programming language)|Python]] 2.x the <code>range()</code> function<ref>{{cite web|url=https://docs.python.org/library/functions.html#range|title=2. Built-in Functions — Python 2.7.11 documentation}}</ref> computes a list of integers. The entire list is stored in memory when the first assignment statement is evaluated, so this is an example of eager or immediate evaluation:
<syntaxhighlight lang="pycon">
>>> r = range(10)
>>> print r
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print r[3]
3
</syntaxhighlight>

In Python 3.x the <code>range()</code> function<ref>{{cite web|url=https://docs.python.org/py3k/library/functions.html#range|title=2. Built-in Functions — Python 3.5.1 documentation}}</ref> returns a [[Generator (computer programming)|generator]] which computes elements of the list on demand. Elements are only generated when they are needed (e.g., when <code>print(r[3])</code> is evaluated in the following example), so this is an example of lazy or deferred evaluation:

<syntaxhighlight lang="pycon">
>>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3
</syntaxhighlight>
:This change to lazy evaluation saves execution time for large ranges which may never be fully referenced and memory usage for large ranges where only one or a few elements are needed at any time.

In Python 2.x is possible to use a function called <code>xrange()</code> which returns an object that generates the numbers in the range on demand. The advantage of <code>xrange</code> is that generated object will always take the same amount of memory.

<syntaxhighlight lang="pycon">
>>> r = xrange(10)
>>> print(r)
xrange(10)
>>> lst = [x for x in r]
>>> print(lst)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
</syntaxhighlight>

From version 2.2 forward, Python manifests lazy evaluation by implementing iterators (lazy sequences) unlike tuple or list sequences. For instance (Python 2):
<syntaxhighlight lang="pycon">
>>> numbers = range(10)
>>> iterator = iter(numbers)
>>> print numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print iterator
<listiterator object at 0xf7e8dd4c>
>>> print iterator.next()
0
</syntaxhighlight>
:The above example shows that lists are evaluated when called, but in case of iterator, the first element '0' is printed when need arises.

====.NET ====
In the [[.NET]] framework, it is possible to do lazy evaluation using the class <syntaxhighlight inline lang="csharp">System.Lazy<T></syntaxhighlight>.<ref>{{cite web|url=http://msdn.microsoft.com/de-de/library/vstudio/dd642331.aspx|title=Lazy(T) Class (System)|publisher=Microsoft}}</ref> The class can be easily exploited in [[F Sharp (programming language)|F#]] using the <syntaxhighlight inline lang="fsharp">lazy</syntaxhighlight> keyword, while the <syntaxhighlight inline lang="fsharp">force</syntaxhighlight> method will force the evaluation. There are also specialized collections like <syntaxhighlight inline lang="csharp">Microsoft.FSharp.Collections.Seq</syntaxhighlight> that provide built-in support for lazy evaluation. 
<syntaxhighlight lang="fsharp">
let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000
</syntaxhighlight>
In C# and VB.NET, the class <syntaxhighlight inline lang="csharp">System.Lazy<T></syntaxhighlight> is directly used. 
<syntaxhighlight lang="csharp">
public int Sum()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => a + b);
    a = 3;
    b = 5;
    return x.Value; // returns 8
}
</syntaxhighlight>
Or with a more practical example: 
<syntaxhighlight lang="csharp">
// recursive calculation of the n'th fibonacci number
public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Which Fibonacci number do you want to calculate?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n)); // function is prepared, but not executed
    bool execute; 
    if (n > 100)
    {
        Console.WriteLine("This can take some time. Do you really want to calculate this large number? [y/n]");
        execute = (Console.ReadLine() == "y"); 
    }
    else execute = true;
    
    if (execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}
</syntaxhighlight>
Another way is to use the <syntaxhighlight inline lang="csharp">yield</syntaxhighlight> keyword: 
<syntaxhighlight lang="csharp">
// eager evaluation 
public IEnumerable<int> Fibonacci(int x)
{
    IList<int> fibs = new List<int>();

    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}

// lazy evaluation 
public IEnumerable<int> LazyFibonacci(int x)
{
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}
</syntaxhighlight>

{{Main|Thunk}}
{{Expand section|date=May 2011}}

==See also==
* [[Combinatory logic]]
* [[Currying]]
* [[Dataflow]]
* [[Eager evaluation]]
* [[Functional programming]]
* [[Futures and promises]]
* [[Generator (computer programming)]]
* [[Graph reduction]]
* [[Incremental computing]] – a related concept whereby computations are only repeated if their inputs change. May be combined with lazy evaluation.
* [[Lambda calculus]]
* [[Lazy initialization]]
* [[Look-ahead (backtracking)|Look-ahead]]
* [[Non-strict programming language]]
* [[Normal order evaluation]]
* [[Short-circuit evaluation]] (minimal)

== Notes ==
{{Notelist}}

== References ==
{{Reflist}}

==Sources==
* {{cite journal
| title = Cons should not evaluate its arguments
| url = http://www.cs.indiana.edu/pub/techreports/TR44.pdf
| first1 = D. P.
| last1 = Friedman
| author-link1 = Daniel P. Friedman
| first2 = David S.
| last2 = Wise
| author-link2 = David S. Wise
| journal = Automata Languages and Programming Third International Colloquium
 |editor=S. Michaelson |editor2=R. Milner |editor2-link=Robin Milner | publisher = Edinburgh University Press
| year = 1976
}}
* {{cite book |doi=10.1145/800168.811543 |chapter=A lazy evaluator |title=Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages - POPL '76 |year=1976 |last1=Henderson |first1=Peter |last2=Morris |first2=James H. |pages=95–103 |s2cid=1228296 }}
* {{cite journal
| title = Conception, Evolution, and Application of Functional Programming Languages
| first = Paul
| last = Hudak
| author-link = Paul Hudak
| journal = ACM Computing Surveys
| volume = 21
| issue = 3
| date = September 1989
| pages = 383&ndash;385
| doi=10.1145/72551.72554
| s2cid = 207637854
}}
* {{cite book |doi=10.1145/158511.158618 |chapter=A natural semantics for lazy evaluation |title=Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93 |year=1993 |last1=Launchbury |first1=John |pages=144–154 |isbn=0897915607 |s2cid=14945994 }}
* {{cite book |first=John C. |last=Reynolds |author-link=John C. Reynolds |title=Theories of programming languages |url=https://books.google.com/books?id=HkI01IHJMcQC&pg=PA307 |year=1998 |publisher=[[Cambridge University Press]] |isbn=9780521594141 |access-date=2016-02-23}}
* {{cite thesis
| last = Wadsworth
| first = Christopher P.
| year = 1971
| title = Semantics and Pragmatics of the Lambda Calculus
| degree = PhD
| institution = University of Oxford
}}

==External links==
* [https://web.archive.org/web/20061110034450/http://nemerle.org/Lazy_evaluation Lazy evaluation macros] in [[Nemerle]]
* [http://spirit.sourceforge.net/dl_docs/phoenix-2/libs/spirit/phoenix/doc/html/phoenix/introduction.html Lambda calculus in Boost Libraries] in [[C++]] language
* [https://www.researchgate.net/publication/301552309_Lazy_Streams_Code Lazy Evaluation ] in ANSI [[C++]] by writing code in a style which uses classes to implement function [[Closure (computer programming)|closures]].

[[Category:Evaluation strategy]]
[[Category:Compiler optimizations]]
[[Category:Implementation of functional programming languages]]
[[Category:Articles with example Haskell code]]