| Evaluation strategies |
|---|
Inprogramming language theory,lazy evaluation, orcall-by-need,[1] is anevaluation strategy which delays the evaluation of anexpression until its value is needed (non-strict evaluation) and which avoids repeated evaluations (by the use ofsharing).[2][3]
The benefits of lazy evaluation include:
Lazy evaluation is often combined withmemoization, as described inJon Bentley'sWriting Efficient Programs.[4] After a function's value is computed for thatparameter or set of parameters, the result is stored in alookup 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 withimperative features such asexception handling andinput/output, because theorder of operations becomes indeterminate.
The opposite of lazy evaluation iseager evaluation, sometimes known as strict evaluation. Eager evaluation is the evaluation strategy employed in most[quantify]programming languages.
Lazy evaluation was introduced forlambda calculus by Christopher Wadsworth.[5] For programming languages, it was independently introduced by Peter Henderson andJames H. Morris[6] and byDaniel P. Friedman and David S. Wise.[7][8]
Delayed evaluation is used particularly infunctional 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 asx = 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 is placed inx, but what actually is inx is irrelevant until there is a need for its value via a reference tox 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.[9]
Lazy evaluation is fundamental in big data frameworks such asApache Spark, where computations on distributed datasets are delayed until results are explicitly needed, allowing for execution optimizations and reduction of unnecessary processing.[10]
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(March 2011) (Learn how and when to remove this message) |
Lazy evaluation allows control structures to be defined normally, and not as primitives or compile-time techniques. For example, one can defineif-then-else andshort-circuit evaluation operators:[11][12]
ifThenElseTruebc=bifThenElseFalsebc=c-- orTrue||b=TrueFalse||b=b-- andTrue&&b=bFalse&&b=False
These have the usual semantics, i.e.,ifThenElseabc 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, forEasilyComputed||LotsOfWork, if the easy part givesTrue the lots of work expression could be avoided. Finally, when evaluatingSafeToTry&&Expression, ifSafeToTry isfalse there will be no attempt at evaluating theExpression.
Conversely, in an eager language the above definition forifThenElseabc would evaluate (a), (b), and (c) regardless of the value of (a). This is not the desired behavior, as (b) or (c) may haveside 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'ssyntax for eager evaluation: Often the involved code bodies need to be wrapped in a function value, so that they are executed only when called.
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 astream) ofFibonacci numbers. The calculation of then-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.[13][14]
Take for example this trivial program inHaskell:
numberFromInfiniteList::Int->IntnumberFromInfiniteListn=infinity!!n-1whereinfinity=[1..]main=print$numberFromInfiniteList4
In the functionnumberFromInfiniteList, the value ofinfinity 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 (i.e., only to 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 afold operation would result in the program either failing to terminate or runningout of memory.
As another example, the list of all Fibonacci numbers can be written in the programming languageHaskell as:[14]
fibs=0:1:zipWith(+)fibs(tailfibs)
In Haskell syntax, ":" prepends an element to a list,tail returns a list without its first element, andzipWith uses a specified function (in this case addition) to combine corresponding elements of two lists to produce a third.[13]
![[icon]](/mt/?noimg=&dark=on&url=https%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aWiki_letter_w_cropped.svg) | This sectionneeds expansion. You can help byadding missing information.(March 2011) |
In computerwindowing systems, the painting of information to the screen is driven byexpose events which drive the display code at the last possible moment. By doing this, windowing systems avoid computing unnecessary display content updates.[15]
Another example of laziness in modern computer systems iscopy-on-write page allocation ordemand paging, where memory is allocated only when a value stored in that memory is changed.[15]
Laziness can be useful for high performance scenarios. An example is the Unixmmap function, which providesdemand driven loading of pages from disk, so that only those pages actually touched are loaded into memory, and unneeded memory is not allocated.
MATLAB implementscopy on edit, where arrays which are copied have their actual memory storage replicated only when their content is changed, possibly leading to anout of memory error when updating an element afterwards instead of during the copy operation.[16]
The number of beta reductions to reduce a lambda term with call-by-need is not larger than the number needed by call-by-value orcall-by-name reduction.[17][18] With certain programs the number of steps may be much smaller, for example a specific family of lambda terms usingChurch numerals 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).[19] Lazy evaluation can also lead to reduction inmemory footprint, since values are created when needed.[20]
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[dubious –discuss]. This can be alleviated throughstrictness analysis.[19] Lazy evaluation can also introducememory leaks due to unevaluated expressions.[21][22]
Some programming languages delay evaluation of expressions by default, and some others providefunctions or specialsyntax to delay evaluation. InKRC,Miranda, andHaskell, 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 withScheme's "delay" and "force" andOCaml's "lazy" and "Lazy.force") or, more generally, by wrapping the expression in athunk. The object representing such an explicitly delayed evaluation is called alazy future.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.[9]
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 calledstrictness 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 forcestrict evaluation.
In Haskell, markingconstructor fields strict means that their values will always be demanded immediately. Theseq 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 implementsrecursive strictness—for that, a function calleddeepSeq was invented.
Also,pattern matching in Haskell 98 is strict by default, so the~ qualifier has to be used to make it lazy.[23]
InC++, thestd::ranges library uses lazy range adaptors.[24]
importstd;usingstd::vector;usingstd::ranges::to;usingstd::views::filter;usingstd::views::iota;usingstd::views::transform;vector<int>v=iota(1,1'000'000)// lazily generate ints from 1 to 1,000,000|filter([](intx)->bool{returnx%2==0;})// filter out odd numbers, keeping evens|transform([](intx)->int{returnx*x;})// square each value|to<vector>();// convert the range back to a vector<int>
InJava, 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 oflambda expressions in Java SE8, Java has supported a compact notation for this. The following examplegeneric interface provides a framework for lazy evaluation:[25][26]
interfaceLazy<T>{Teval();}
TheLazy interface with itseval() method is equivalent to theSupplier interface with itsget() method in thejava.util.function library.[27][28]: 200
Each class that implements theLazy interface must provide aneval 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 210:
Lazy<Integer>a=()->1;for(inti=0;i<10;i++){Lazy<Integer>b=a;a=()->b.eval()+b.eval();}System.out.println("a = "+a.eval());
In the above, the variablea initially refers to a lazyinteger object created by the lambda expression() -> 1. Evaluating this lambda expression is similar[a] to constructing a new instance of ananonymous class that implementsLazy<Integer> with aneval method returning1.
Each iteration of the loop linksa 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 aneval method that callsb.eval() twice and returns the sum. The variableb 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 notmemoize the result of previous calls toeval. It also involves considerableautoboxing and unboxing. What may not be obvious is that, at the end of the loop, the program has constructed alinked list of 11 objects and that all of the actual additions involved in computing the result are done in response to the call toa.eval() on the final line of code. This callrecursively traverses the list to perform the necessary additions.
We can build a Java class that memoizes a lazy object as follows:[25][26]
classMemo<T>implementsLazy<T>{privateLazy<T>lazy;// a lazy expression, eval sets it to nullprivateTmemo;// the memorandum of the previous valuepublicMemo(Lazy<T>lazy){this.lazy=lazy;}publicTeval(){if(lazy!=null){memo=lazy.eval();lazy=null;}returnmemo;}}
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 inlinear time:
Lazy<Integer>a=()->1;for(inti=0;i<10;i++){Lazy<Integer>b=a;a=newMemo<Integer>(()->b.eval()+b.eval());}System.out.printf("a = %s%n",a.eval());
Java's lambda expressions are justsyntactic sugar. Anything that can be written with a lambda expression can be rewritten as a call to construct an instance of an anonymousinner class implementing the interface,[a] 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.
InJavaScript, lazy evaluation can be simulated by using agenerator. For example, thestream of allFibonacci numbers can be written, usingmemoization, in the followingTypeScript code:
/** * Generator functions return generator objects, which reify lazy evaluation. * @return {!Generator<bigint>} A non-null generator of integers. */function*fibonacciNumbers():Generator<bigint,never,unknown>{letmemo:[bigint,bigint]=[1n,-1n];// create the initial state (e.g. a vector of "negafibonacci" numbers)while(true){// repeat indefinitelymemo=[memo[0]+memo[1],memo[0]];// update the state on each evaluationyieldmemo[0];// yield the next value and suspend execution until resumed}}conststream:Generator<bigint,never,unknown>=fibonacciNumbers();// create a lazy evaluated stream of numbersconstfirst10:bigint[]=Array.from(newArray(10),()=>stream.next().value);// evaluate only the first 10 numbersconsole.log(first10);// the output is [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n]
InPython 2.x therange() function[29] 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)printr# prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]printr[3]# prints 3
In Python 3.x therange() function[30] returns agenerator which computes elements of the list on demand. Elements are only generated when they are needed (e.g., whenprint(r[3]) is evaluated in the following example), so this is an example of lazy or deferred evaluation:
r:Iterator[int]=range(10)print(r)# prints range(0, 10)print(r[3])# prints 3
In Python 2.x is possible to use a function calledxrange() which returns an object that generates the numbers in the range on demand. The advantage ofxrange is that generated object will always take the same amount of memory.
r=xrange(10)printr# prints xrange(10)lst=[xforxinr]printlst# prints [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:Iterator[int]=range(10)iterator:Iterator[int]=iter(numbers)print(numbers)# prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]print(iterator)# prints <listiterator object at 0xf7e8dd4c>print(iterator.next())# prints 0
In the.NET framework, it is possible to do lazy evaluation using the classSystem.Lazy<T>.[31] The class can be easily exploited inF# using thelazy keyword, while theforce method will force the evaluation. There are also specialized collections likeMicrosoft.FSharp.Collections.Seq that provide built-in support for lazy evaluation.
letfibonacci=Seq.unfold(fun(x,y)->Some(x,(y,x+y)))(0I,1I)fibonacci|>Seq.nth1000
In C# and VB.NET, the classSystem.Lazy<T> is directly used.
publicintSum(){inta=0;intb=0;Lazy<int>x=new(()=>a+b);a=3;b=5;returnx.Value;// returns 8}
Or with a more practical example:
// recursive calculation of the n'th fibonacci numberpublicintFib(intn){return(n==1)?1:(n==2)?1:Fib(n-1)+Fib(n-2);}publicvoidMain(){Console.WriteLine("Which Fibonacci number do you want to calculate?");intn=Int32.Parse(Console.ReadLine());Lazy<int>fib=new(()=>Fib(n));// function is prepared, but not executedboolexecute;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}}
Another way is to use theyield keyword:
// eager evaluationpublicIEnumerable<int>Fibonacci(intx){IList<int>fibs=newList<int>();intprev=-1;intnext=1;for(inti=0;i<x;i++){intsum=prev+next;prev=next;next=sum;fibs.Add(sum);}returnfibs;}// lazy evaluationpublicIEnumerable<int>LazyFibonacci(intx){intprev=-1;intnext=1;for(inti=0;i<x;i++){intsum=prev+next;prev=next;next=sum;yieldreturnsum;}}
InRust, lazy evaluation is included in the RustStandard library, through the typesstd::cell::LazyCell andstd::sync::LazyLock.LazyLock is thethread safe version ofLazyCell. The types are described as"a value which is initialized on the first access",[32] as so:
usestd::cell::LazyCell;letlazy:LazyCell<i32>=LazyCell::new(||{println!("initializing");92});println!("ready");println!("{}",*lazy);println!("{}",*lazy);// Prints:// ready// initializing// 92// 92
The types are defined asLazy<T, F = fn() -> T> whereT is the type of the inner cell, and return type ofF, the function called once upon initialization.
| This sectionneeds expansion. You can help byadding missing information.(May 2011) |