Lazy evaluation

In almost all common "eager" languages, if statements evaluate in a lazy fashion.

if a then b else c

evaluates (a), then if and only if (a) evaluates to true does it evaluate (b), otherwise it evaluates (c). That is, either (b) or (c) will not be evaluated. Conversely, in an eager language the expected behavior is that

define f(x, y) = 2 * x
set k = f(d, e)

will still evaluate (e) when computing the value of f(d, e) even though (e) is unused in function f. However, user-defined control structures depend on exact syntax, so for example

define g(a, b, c) = if a then b else c
l = g(h, i, j)

(i) and (j) would both be evaluated in an eager language. While in a lazy language,

l' = if h then i else j

(i) or (j) would be evaluated, but never both.

Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. If (i) or (j) have side effects or introduce run time errors, the subtle differences between (l) and (l') can be complex. 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 (like (i) and (j)) need to be wrapped in a function value, so that they are executed only when called.

Short-circuit evaluation of Boolean control structures is sometimes called lazy.

Many languages offer the notion of infinite data-structures. These allow definitions of data to be given in terms of infinite ranges, or unending recursion, but the actual values are only computed when needed. Take for example this trivial program in Haskell:

numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4

In the function numberFromInfiniteList, the value of 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.)

A compound expression might be in the form EasilyComputed or LotsOfWork so that if the easy part gives true a lot of work could be avoided. For instance, suppose a large number N is to be checked to determine if it is a prime number and a function IsPrime(N) is available, but alas, it can require a lot of computation to evaluate. Perhaps N=2 or [Mod(N,2)≠0 and IsPrime(N)] will help if there are to be many evaluations with arbitrary values for N.

A compound expression might be in the form SafeToTry and Expression whereby if SafeToTry is false there should be no attempt at evaluating the Expression lest a run-time error be signalled, such as divide-by-zero or index-out-of-bounds, etc. For instance, the following pseudocode locates the last non-zero element of an array:

 L:=Length(A);
 While L>0 and A(L)=0 do L:=L - 1;

Should all elements of the array be zero, the loop will work down to L = 0, and in this case the loop must be terminated without attempting to reference element zero of the array, which does not exist.

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, windowing systems avoid computing unnecessary display content updates.[16]

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.[16]

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 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.[17]

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 fields strict means that their values will always be demanded immediately. The seq 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 deepSeq was invented.

Also, pattern matching in Haskell 98 is strict by default, so the ~ qualifier has to be used to make it lazy.[18]

In 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 lambda expressions in Java SE8, Java has supported a compact notation for this. The following example generic interface provides a framework for lazy evaluation:[19][20]

interface Lazy<T> {
    T eval();
}

The Lazy interface with its eval() method is equivalent to the Supplier interface with its get() method in the java.util.function library.[21]

Each class that implements the Lazy interface must provide an eval 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¹⁰:

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = ()-> b.eval() + b.eval();
}
System.out.println( "a = " + a.eval() );

In the above, the variable a initially refers to a lazy integer object created by the lambda expression ()->1. Evaluating this lambda expression is equivalent to constructing a new instance of an anonymous class that implements Lazy<Integer> with an eval method returning 1.

Each iteration of the loop links 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, b, and has an eval method that calls b.eval() twice and returns the sum. The variable b is needed here to meet Java's requirement that variables referenced from within a lambda expression be final.

This is an inefficient program because this implementation of lazy integers does not memoize the result of previous calls to eval. It also involves considerable 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 a.eval() on the final line of code. This call recursively traverses the list to perform the necessary additions.

We can build a Java class that memoizes a lazy objects as follows:[19][20]

class Memo<T> implements Lazy<T> {
    private Lazy<T> lazy;  // a lazy expression, eval sets it to null
    private T memo = null; // the memorandum of the previous value

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

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

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:

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = new Memo<Integer>( ()-> b.eval() + b.eval() );
}
System.out.println( "a = " + a.eval() );

Note that Java's lambda expressions are just syntactic sugar. Anything you can write with a lambda expression can be rewritten as a call to construct an instance of an anonymous inner class implementing the interface, 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.

In Python 2.x the range() function[22] 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:

>>> r = range(10)
>>> print r
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print r[3]
3

In Python 3.x the range() function[23] returns a special range object which computes elements of the list on demand. Elements of the range object are only generated when they are needed (e.g., when print(r[3]) is evaluated in the following example), so this is an example of lazy or deferred evaluation:

>>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3

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 xrange() which returns an object that generates the numbers in the range on demand. The advantage of xrange is that generated object will always take the same amount of memory.

>>> 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]

From version 2.2 forward, Python manifests lazy evaluation by implementing iterators (lazy sequences) unlike tuple or list sequences. For instance (Python 2):

>>> 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

The above example shows that lists are evaluated when called, but in case of iterator, the first element '0' is printed when need arises.

In the .NET Framework it is possible to do lazy evaluation using the class System.Lazy<T>.[24] The class can be easily exploited in F# using the lazy keyword, while the force method will force the evaluation. There are also specialized collections like Microsoft.FSharp.Collections.Seq that provide built-in support for lazy evaluation.

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000

In C# and VB.NET, the class System.Lazy<T> is directly used.

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
}

Or with a more practical example:

// 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 = false;
    
    if (execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}

Another way is to use the yield keyword:

// 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;
    }
}