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

PR Stanley prstanley at ntlworld.com
Wed Nov 28 23:23:11 EST 2007

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

More information about the Haskell-Cafe mailing list