Andrew Coppin wrote:
PS. There is a technical distinction between the terms "lazy" and
"non-strict", and also the opposite terms "eger" and "strict". I
couldn't tell you what that is.
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). 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.
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".
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.
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".
Paul.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
