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

[Jonathan Cast]

On 17 Nov 2007, at 8:04 PM, PR Stanley wrote:

> Hi
> okay, so $! is a bit like $ i.e. the equivalent of putting  
> parentheses around the righthand expression. I'm still not sure of  
> the difference between $ and $!. Maybe it's because I don't  
> understand the meaning of "strict application". While we're on the  
> subject, what's meant by Haskell being a non-strict language?

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.  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.  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.

jcc