[Haskell-cafe] What is the role of $!?

[Paul Johnson]

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.