Difference between revisions of "Lazy vs. non-strict"
m (Research_papers/Runtime_systems: turn HTTP link into Wiki link)
(Minimal change to reference the existing page on WHNF)
|Line 47:||Line 47:|
== WHNF ==
== WHNF ==
describe WHNF ...
WHNF is an abbreviation for [[weak head normal form]].
Revision as of 17:16, 3 January 2012
Direction of evaluation
Non-strictness means that reduction (the mathematical term for evaluation)
proceeds from the outside in,
so if you have
(a+(b*c)) then first you reduce the
then you reduce the inner
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
error 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 propagate 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 correspondence 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.
You can prepend a
~ in order to make pattern matches lazy).
The strictness analyzer 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
- Paul Johnson in Haskell Cafe What is the role of $! ?
WHNF is an abbreviation for weak head normal form.
Laziness is simply a common implementation technique for non-strict languages, but it is not the only possible technique. One major drawback with lazy implementations is that they are not generally amenable to parallelisation. This paper states that experiments indicate that little parallelism can be extracted from lazy programs:
"The Impact of Laziness on Parallelism and the Limits of Strictness Analysis" (G. Tremblay G. R. Gao) http://citeseer.ist.psu.edu/tremblay95impact.html
Lenient, or optimistic, evaluation is an implementation approach that lies somewhere between lazy and strict, and combines eager evaluation with non-strict semantics. This seems to be considered more promising for parallelisation.
This paper implies (section 2.2.1) that lenient evaluation can handle circular data structures and recursive definitions, but cannot express infinite structures without explicit use of delays:
"How Much Non-strictness do Lenient Programs Require?" (Klaus E. Schauser, Seth C. Goldstein) http://citeseer.ist.psu.edu/schauser95how.html
Some experiments with non-lazy Haskell compilers have been attempted: Research_papers/Runtime_systems#Optimistic_Evaluation