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

[PR Stanley]

Hi
Thanks for the response.

	JCC: In most languages, if you have some expression E, and when the 
computer attempts to evaluate E it goes in to an infinite loop, then 
when the computer attempts to evaluate the expression f(E), it also
goes into an infinite loop, regardless of what f is.  That's the 
definition of a strict language.

PRS: Does that mean that a strict language is also imperative?

Either e or f(e) could result in an infinite loop.

	JCC: In Haskell, this isn't the case ---we can write functions f 
such that the computation f(E)  terminates,
even when E does not.  (:) is one such function, as are some 
functions built from it, such as (++); xn ++ ys terminates whenever 
xn does, even if ys is an infinite loop.  This is what makes it easy
and convenient to build infinite loops in Haskell; in most strict 
languages, if you said
	let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
the language would insist on evaluating fibs before it actually 
assigned anything to the memory cell for fibs, giving rise to an 
infinite loop.  (For this reason, most strict languages make such 
definitions compile-time errors).

Unfortunately, non-strictness turns out to be a pain in the ass to 
implement, since it means when the code generator sees an expression, 
it can't just generate code to evaluate it --- it has to hide the 
code somewhere else, and then substitute a pointer to that code for 
the value of the expression.

	PRS: Is there a kind of strictness applied when the 
compiler/interpreter sorts the various sub-expressions into little 
memory compartments indexed with pointers for later evaluation? To 
put it another way, does lazy evaluation begin with the outer-most 
expression, the most abstract, and determine what sshould go where in 
relation to the subsequent inner expressions?  For example:
	
		takeWhile (<20) [0..9] ++ [10..]

The compiler determiens at the outset that the result of takeWhile is 
a list followed by the calculation of the length of that list based 
on the predicate (<20), and then calls ++ which is for all intents 
and purposes on its own an infinite loop. Is this what happens?

This is a very simple example, that's to say, I am aware that the 
compiler may be faced with a much more complex job of applying lazy 
evaluation. Nevertheless, I wonder if there are a set of fundamental 
rules to which the compiler must always adhere in lazy evaluation.

	JCC: There are a number of clever optimizations you can use here 
(indeed, most of the history of Haskell compilation techniques is a 
list of clever techniques to get around the limitations of compiling 
non-strict languages), but most of them rely on the compiler knowing 
that, in this case, if a sub- expression is an infinite loop, the 
entire expression is an infinite loop.  This is actually pretty easy 
to figure out (most of the time), but sometimes the compiler needs a 
little help.

That's where $! (usually) comes in.  When the compiler sees (f $ x), 
it has to look at f to see whether, if x is an infinite loop, f $ x 
is one as well.  When the compiler sees (f $! x), it doesn't need to 
look at f --- if x is an infinite loop, (f $! x) always is one as 
well.  So, where in (f $ x) the compiler sometimes needs to put the 
code for x in a separate top-level block, to be called later when 
it's needed, in (f $! x) the compiler can always generate code for x 
inline, like a compiler for a normal language would.  Since most CPU 
architectures are optimized for normal languages that compile f(E) by 
generating code for E inline, this is frequently a big speed-up.

PrS: Your description of $! reminds me of the difference between 
inline functions and "ordinary" functions in C++ with the former 
being faster. Am I on the right track? In either case, (f $ x) and (f 
$! x), lazy evaluation must be applied at a higher level
otherwise either instruction could result in an infinite loop. 
Therefore, is efficiency the only consideration here?

If Haskell is a lazy language and $ merely implies lazy evaluation 
then what's the difference between (f $ x \oplus y) and (f (x \oplus y))?

Thanks, Paul