[Haskell-cafe] strict, lazy, non-strict, eager

[wren ng thornton]

On 12/28/11 6:47 AM, Thiago Negri wrote:
> I got a glimpse of understanding of what you are talking about after
> reading the wiki [1].
>
> Still difficult to reason about the difference between lazy and
> non-strict without taking a look at the text.

One way to keep them distinct is to recall that "lazy" is quite a bit 
more specific than "non-strict". Let's take the wiki's definition:

     non-strict means evaluation from outside in

(however problematic that may be). Now, just because we've specified 
this directionality of evaluation, that doesn't mean we've said 
everything we need to say about evaluation order. In particular, there 
are two common/obvious implementations of non-strict semantics: 
call-by-name, and call-by-need.

In call-by-name evaluation, we just pass in the argument to functions as 
a literal expression. This is easy to reason about mathematically, 
however it has poor performance because it can cause duplication of 
effort. Namely, if a function uses its argument N times, then 
beta-reduction will create N copies of the argument, each of which will 
be evaluated (or not) separately.

In call-by-need (aka "lazy") evaluation, we don't just pass the 
expression in duplicating it if need be. Instead, we create a thunk and 
replace all references to the argument with references/pointers to the 
thunk. In this way, we can share the evaluation effort since we only 
have to evaluate/mutate the thunk once and the result can be shared 
across all use sites.

In other words, in call-by-name beta-reduction is the familiar:

     (\x. a) $ b
     -----------
     [x |-> b] a

where [_|->_]_ is literal substitution of expressions for variables in 
expressions. Whereas in call-by-need, beta-reduction is something like:

     (\x. a) $ b
     -----------
     let x = b in a

where let_=_in_ is a primitive construct for expressing shared 
substructure. Notably, in call-by-need the locus of evaluation shifts to 
a, so we evaluate under let_=_in_. The locus of evaluation only ever 
moves to b if indeed x is forced within a.

In practice, GHC (and other Haskell compilers) are not lazy. That is, 
they do not exclusively use the call-by-need evaluation order. Instead, 
there is a hybridization of call-by-name, call-by-need, and 
call-by-value, the choice of which being based on the strictness 
analyzer and other optimization passes. The fact that GHC is allowed to 
do this can still call itself "Haskell" stems from the fact that the 
semantics of Haskell are defined merely as being non-strict, rather than 
being more specific.

-- 
Live well,
~wren