|
Lazy evaluation
In programming language theory, lazy evaluation, or call-by-need,[1] is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (by the use of sharing).[2][3] The benefits of lazy evaluation include:
Lazy evaluation is often combined with memoization, as described in Jon Bentley's Writing Efficient Programs.[4] After a function's value is computed for that 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 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] programming languages. HistoryLazy evaluation was introduced for lambda calculus by Christopher Wadsworth.[5] For programming languages, it was independently introduced by Peter Henderson and James H. Morris[6] and by Daniel P. Friedman and David S. Wise.[7][8] ApplicationsDelayed 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 Control structures
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:[10][11] ifThenElse True b c = b
ifThenElse False b c = c
-- or
True || b = True
False || b = b
-- and
True && b = b
False && b = False
These have the usual semantics, i.e., Conversely, in an eager language the above definition for Working with infinite data structuresDelayed 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) of Fibonacci numbers. 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.[12][13] 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.) 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 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:[13] fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
In Haskell syntax, " List-of-successes pattern
Other usesIn 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.[14] 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.[14] 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.[15] PerformanceThe 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.[16][17] And with certain programs the number of steps may be much smaller, for example a specific family of lambda terms using Church 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).[18] Lazy evaluation can also lead to reduction in memory footprint, since values are created when needed.[19] 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.[18] Lazy evaluation can also introduce memory leaks due to unevaluated expressions.[20][21] ImplementationSome programming languages delay evaluation of expressions by default, and some others provide functions or special syntax to delay evaluation. In 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's " Laziness and eagernessControlling eagerness in lazy languagesIn 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 Also, pattern matching in Haskell 98 is strict by default, so the Simulating laziness in eager languagesJavaIn 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:[23][24] interface Lazy<T> {
T eval();
}
The Each class that implements the 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());
In the above, the variable a initially refers to a lazy integer object created by the lambda expression 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 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 We can build a Java class that memoizes a lazy object as follows:[23][24] 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;
}
}
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 = 0; i < 10; i++) {
Lazy<Integer> b = a;
a = new Memo<Integer>(() -> b.eval() + b.eval());
}
System.out.println("a = " + a.eval());
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,[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. JavaScriptIn JavaScript, lazy evaluation can be simulated by using a generator. For example, the stream of all Fibonacci numbers can be written, using memoization, as: /**
* 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]
PythonIn Python 2.x the >>> r = range(10)
>>> print r
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print r[3]
3
In Python 3.x the >>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3
In Python 2.x is possible to use a function called >>> 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
.NETIn the .NET framework, it is possible to do lazy evaluation using the class 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 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 = true;
if (execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}
Another way is to use the // 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;
}
}
See also
Notes
References
Sources
External links
|
![[icon]](File:Wiki_letter_w_cropped.svg){kind=small}