| Lazy Evaluation |
Article Index for Lazy |
Shopping Evaluation |
Website Links For Lazy |
Information AboutLazy Evaluation |
| CATEGORIES ABOUT LAZY EVALUATION | |
| programming paradigms | |
| programming evaluation | |
| compiler optimizations | |
| articles with example haskell code | |
|
In Computer Programming , lazy evaluation is a technique that attempts to delay computation of expressions until the results of the computation are known to be needed. It has two related, yet different, meanings that could be described as ''delayed evaluation'' and ''minimal evaluation''. The benefits of lazy evaluation include: performance increases due to avoiding unnecessary calculations, avoiding error conditions in the evaluation of compound expressions, the ability to construct infinite Data Structure s, and the ability to define Control Structure s as regular functions rather than built-in primitives. Languages that use lazy evaluation can be further subdivided into those that use a call-by-name Evaluation Strategy and those that use call-by-need. Most realistic lazy languages, such as Haskell , use call-by-need for performance reasons, but theoretical presentations of lazy evaluation often use call-by-name for simplicity. The opposite of lazy evaluation is Eager Evaluation , also known as '' Strict Evaluation ''. Eager evaluation is the evaluation behavior used in most Programming Languages . COMPOUND EXPRESSIONS Suppose a logical expression such as ''(a and b)'' is to be evaluated: should term ''a'' be '''false''', there is no need to evaluate term ''b'' in determining the result of the expression. Likewise, in ''(a '''or''' b)'' if term ''a'' is '''true'''. These terms might be complex expressions so the gain is obvious, and leads to thought as to which terms to present first in an expression based on the expected likelihood of a result '''true''' or '''false''' as well as the cost of evaluation. Thus in an expression such as ''(a '''or''' b '''or''' c)'' one would hope that term ''a'' is both quite likely to have the value '''true''', and be easy to evaluate. To deliver on these possibilities, the compiler would insert tests to jump out of further evaluation, giving rise to the alternative term short-circuit evaluation. These tests, should they fail to jump, will of course increase the time taken to evaluate the full expression (in the cases where that is needed) over that needed for the unconditional full-evaluation approach. A corresponding approach could be taken to the evaluation of arithmetic expressions: there is no point in adding zero to a number, and multiplications by zero or one have special effects. However, introducing code to test for these special values is less beneficial as a number has many values besides these special ones whereas logical variables have but two values. However, the hardware performing the calculation might well attend to special cases, if for no other reason than that zero is not representable as a normalised floating-point value. EVADING ERROR CONDITIONS Suppose you have some expression that in certain situations must not be evaluated lest an error condition be triggered. The expression might be protected via a form such as ''(safettoevaluate and expression)'' for instance in something like ''(N <> 0 and (x mod N = 0))''. Obviously, this could be written as ''if N <> 0 then if x mod N = 0 then ...'' which already is a little clunky. Contrariwise, you may have a case where the test is ''(a or b)'' and if ''a'' is '''true''', not only ought ''b'' not be evaluated but doing so might or would cause trouble. Since you do wish the action taken if either ''a'' or ''b'' is true (that is what the expression means!) the polite form becomes ''if a then action else if b then action;'' which repetition conduces to mistakes. More sensibly, suppose you have a text string with possible trailing spaces and you wish to know the location of the last non-blank character. l:=Length(t); %Pace C-programmers, where this scans the string for the terminating zero character. while l > 0 and t(l) = " " do decrement l; or, in a more flexible language, for l:=Length(t):1:-1 while t(l) = " " do; Clearly, if the string is entirely filled with spaces, ''l'' should become zero, but, there must be no attempt to access character zero of the string. It would be wasted effort at best, and an error at worst. DELAYED EVALUATION Delayed evaluation is used particularly in Functional Language s. 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. Some programming languages delay evaluation of expressions by default, and some others provide Function s 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 "delay" and "force") or, more generally, by wrapping the expression in a Thunk . Delayed evaluation has the advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation. 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 the first n members of the list only. For example, in the Haskell Programming Language , the list of all Fibonacci numbers can be written as fibs = 1 : 1 : zipWith (+) fibs (tail fibs) In Haskell syntax, " :" prepends an element to a list, tail returns a list without its first element, and zipWith uses a specified function (in this case addition) to combine corresponding elements of two lists to produce a third.Provided the programmer is careful, only the values that are required to produce a particular result are evaluated. 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. SEE ALSO
Compare: EXTERNAL LINKS REFERENCES |
|
|