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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
