icsu8209@caesar.cs.montana.edu (Lou Glassy) (02/14/90)
What does 'lazy evaluation' mean? Is it the same thing as 'short-circuit evaluation?
An example of the latter:
x=0;
if ( (x==1) && ((1/x) == 2) )
{
...
}
If short-circuit evaluation is in effect, the expression '1/x' will never be
evaluated, since the && will return a false directly from 'x==1'.
Is -this- the same thing as 'lazy evaluation' in functional languages? I suspect there's a difference...but what? A matter of degree?
My confusion arises from a kindred (opposite) idea, that of 'eager evaluation'.
If the example above were evaluated eagerly, '1/x' would yield a division-by-zero error. And...I thought 'eager' was the opposite of 'lazy', in terms of evaluation methods.
Can someone clarify 'eager' vs. 'strict' vs. 'lazy' vs. 'short-circuit'
evaluation for me? Or tell me of a good reference (book/article/etc) on
these things?
Thanks in advance.
Lou Glassy
icsu8209@caesar.cs.montana.edufirth@sei.cmu.edu (Robert Firth) (02/14/90)
In article <3109@caesar.cs.montana.edu> icsu8209@caesar.cs.montana.edu (Glassy) writes: >What does 'lazy evaluation' mean? Is it the same thing as 'short-circuit evaluation? I'll have a shot at an answer. (a) 'short-circuit' versus 'full' evaluation is usually considered a compile time issue, ie the compiler generates one of two code sequences. Example: if x>=0 and then sqrt(x)<=y ... this is short circuit evaluation, something like test x branch negative L call sqrt(x) compare y branch greater-than L ... L: so if the first test is enough to decide the condition, the second is not performed. By contrast, full evaluation always evaluates everything. (b) 'lazy' versus 'greedy' evaluation is usually considered an issue in implementing language interpreters, eg for lambda calculus. Greedy evaluation evaluates an expression as soon as it can; lazy evaluation as late as it can. Example: munge(1/x) greedy evaluation will evaluate 1/x and then call munge(). lazy evaluation will call munge(), and evaluate 1/x only when the body of munge referenced its formal parameter. As the example shows, lazy evaluation "works" in cases where greedy evaluation does not - in this case, if x=0 but munge doesn't reference its parameter. Hope that helps.
djones@megatest.UUCP (Dave Jones) (02/14/90)
From article <3109@caesar.cs.montana.edu>, by icsu8209@caesar.cs.montana.edu (Lou Glassy): > What does 'lazy evaluation' mean? Is it the same thing as 'short-circuit evaluation? > Not the same, but quite similar. The term 'lazy evaluation' is borrowed from the lambda calculus. Very loosely it means that evaluations of all expressions other than the final one are defered until such time as the values are needed in another calculation. If it turns out that the value of a subexpression is never needed, ( e.g. because it is the unselected alternative of an if-else-expression), it is never calculated. This has a couple of effects. One is that you get more expressions to evaluate to something, rather than going into infinite evaluation loops, or 'crashing' from divide-by-zero or whatever. In fact, you get exactly the theoretically largest algebra possible, the one the theorists seem to use exclusively. Another effect is that you can write programs in such a way that the progress of the evaluation of two separate expressions can be controlled by the evaluation of a third. In this way one can control the realtime sequencing of the evaluations. Evaluation of the first expression causes the subexpressions of the other two to be done in a particular order by 'needing' them in that order. In the parlance of sequential programming languages, you then have three 'processes': one 'monitor', and two 'child-processes'. Of course, this can be extended to any number of processes and any kind of connectivity. At least some lazy evaluation is necessary in any system. Only the most trivial programs would ever terminate otherwise. (As noted, the unselected alternative of an if-else-expression is seldom calculated.) Systems which use lazy evaluation exclusively are rare. In LISP, it's mainly the evaluation of the CONS record that makes the next big difference. If that evaluation is defered, you can use lists as event-queues.
gudeman@cs.arizona.edu (David Gudeman) (02/14/90)
In article <3109@caesar.cs.montana.edu> icsu8209@caesar.cs.montana.edu (Lou Glassy) writes: >What does 'lazy evaluation' mean? Is it the same thing as 'short-circuit evaluation? No, but they are related. Short-circuit evaluation, as you said, involves avoiding some computations. The most common example is boolean operations such as you showed, however there are other examples such as x := y * f(x); where f(x) does not have to be called if y = 0 (ignoring the issue of side-effects). Lazy evaluation is usually associated with parameter passing. For example, in the function function f(x,y) = if x > 1 then x else y + y given the call f(h(z),g(z)) it is not necessary to ever call g(z) if h(z) > 1. This is like call-by-name in some respects, in that call-by-name also does not evaluate arguments that are never needed, but with lazy evaluation (call-by-need) the expression g(z) is evaluated at most once. The evaluation sequence goes something like this: 1 call f(h(z),g(z)) where the arguments are passed unevaluated 2 try to evaluate (x > 1) 3 the value of x is needed, so call h(z) and assign the result to x 4 evaluate (x > 1) to get the result 5 (assume the result is TRUE) return the value stored at x In call-by-name, the steps are 1 call f(h(z),g(z)) where the arguments are passed unevaluated 2 evaluate (x > 1) as (h(x) > 1) 3 (assume the result is TRUE) return the value of x as h(x) In the call-by-name version, h(x) is called twice. There are other forms of lazy evaluation as well, the term generally means, "when you encounter an expression, don't evaluate the expression until you actually need for it the first time, then store the result in case you need it again." -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
grover@brahmand.Sun.COM (Vinod Grover) (02/16/90)
In article <6081@bd.sei.cmu.edu> firth@sei.cmu.edu (Robert Firth) writes: > >Example: > > munge(1/x) > >greedy evaluation will evaluate 1/x and then call munge(). lazy >evaluation will call munge(), and evaluate 1/x only when the body >of munge referenced its formal parameter. > >As the example shows, lazy evaluation "works" in cases where greedy >evaluation does not - in this case, if x=0 but munge doesn't reference >its parameter. Lazy Evaluation differs fromn call-by-name in that the expression is evaluated at-most-once. If there are multiple refrences to 1/x, in the above example, only one of them will be evaluated if needed.
schaut@cat19.cs.wisc.edu (Rick Schaut) (02/19/90)
In article <3109@caesar.cs.montana.edu> icsu8209@caesar.cs.montana.edu (Glassy) writes: | What does 'lazy evaluation' mean? Is it the same thing as 'short-circuit evaluation? Lazy evaluation is not the same as short-circuit evaluation. Lazy evaluation is where expressions are not evaluated until they are needed. For example, if you had the following function definition: Func Foo(x,y: integer): integer; var z integer; begin z := y + 5; return (z + x / 5); end; and call: a = Foo((3+4),7); the expression, (3 + 4) doesn't get evaluated until the formal parameter, x, is referenced in the return expression. This may seem inocuous, but consider the following: program var a: integer; Func Foo(x,y: integer): integer; begin a = 2; return( x * y + a); end; begin a = 3; Write(Foo((a + 4),7)); end. With normal evaluation, the output is 7 * 7 + 2, or 51. With lazy evaluation, however, the expression (a + 4) isn't evaluated until the return is executed in Foo. The output is 6 * 7 + 2, or 44. If you're interested in why someone might want lazy evaluation, see: Vuillemin, J. [1974]. Correct and optimal implimentation of recursion in a simple programming language. _J. Computer and System Sciences 9:3, 332-354 and Wadsworth, C [1971]. Semantics and Pragmatics of the Lambda Calculus. Ph. D. Thesis, Oxford Univ. [References from Sethi, R., _Programming Languages: Concepts and Constructs_, Addison-Wesley, 1989] -- Rick (schaut@garfield.cs.wisc.edu) Peace and Prejudice Don't Mix! (unknown add copy)