Hi
Thanks for the explanation. I would be grateful for some examples
accompanying the text. I will indicate the right places for real life
(Haskell code) examples in the paragraphs below:
PJ: As I understand it, the distinction is between the mathematical
term "non-strict" and the implementation method of
"lazy". Non-strict" means that "reduction" (the mathematical term
for evaluation) proceeds from the outside in, so if I have (a+(b*c))
then first you reduce the "+", then you reduce the inner (b*c).
PRS: No problems so far..
PJ: Strict languages work the other way around, starting with the
innermost brackets and working outwards.
This matters to the semantics because if you have an expression that
evaluates to "bottom" (i.e. an error, exception or endless loop) then
any language that starts at the inside and works outwards will always
find that bottom value, and hence the bottom will propogate outwards.
PRS: You would also get different results - e.g.
let a = 3, b = 7, c = 2
therefore 20 = strict ( ( (a+(b*c)) )
therefore 17 = non-strict ( (a+(b*c)) )
or am I misunderstanding the concept?
PJ: However if you start from the outside and work in then some of
the sub-expressions are eliminated by the outer reductions, so they
don't get evaluated and you don't get "bottom".
PRS: I'm not sure if I fully understand the bottom idea here. I
thought it related to the base value in a recursive pattern. For example:
f (.) [] = []
f . (x:xs) = x . f xs
What's a sub-expression?
PJ: Lazy evaluation, on the other hand, means only evaluating an
expression when its results are needed (note the shift from
"reduction" to "evaluation"). So when the evaluation engine sees an
expression it builds a "thunk" data structure containing whatever
values are needed to evaluate the expression, plus a pointer to the
expression itself. When the result is actually needed the evaluation
engine calls the expression and then replaces the thunk with the
result for future reference.
PRS: A thunk data structure? Again, a example would be nice.
PJ: Obviously there is a strong correspondance between a thunk and a
partly-evaluated expression. Hence in most cases the terms "lazy"
and "non-strict" are synonyms. But not quite. For instance you
could imagine an evaluation engine on highly parallel hardware that
fires off sub-expression evaluation eagerly, but then throws away
results that are not needed.
In practice Haskell is not a purely lazy language: for instance
pattern matching is usually strict (so trying a pattern match forces
evaluation to happen at least far enough to accept or reject the
match). The optimiser also looks for cases where sub-expressions are
*always* required by the outer expression, and converts those into
eager evaluation. It can do this because the semantics (in terms of
"bottom") don't change. Programmers can also use the "seq" primitive
to force an expression to evaluate regardless of whether the result
will ever be used. "$!" is defined in terms of "seq".
PRS: More examples please.
Thanks, Paul
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
