Let's look at a simple example where laziness causes problems. Here's a definition for a left fold in Haskell:
If you try evaluating
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f s  = s
foldl f s (h:t) = foldl f (f s h) t
foldl (+) 0 [1..1000000], you'll get a stack overflow. The stack overflow occurs because
foldlis lazy in the parameter
s(the 'seed' parameter); each iteration of the fold creates a thunk with one more level of nesting than the current seed. When the result of the fold is finally evaluated it requires stack space proportional to the length of the list folded over. If you want to sum a list in constant space, you can either use a hand-coded loop, or you can use
foldl', which is strict in its seed argument. (Update: there's another way, too, see below.)
But wait a minute - if you look at the definition for
foldl, you can see that if the operator,
fis strict in its arguments, then the seed could also be made strict without any change in semantics. Strictness analysis has failed us: since
foldlis polymorphic, the compiler can't assume anything about the strictness of the operator and must therefore treat the seed parameter as lazy. In principle the compiler could produce specialized versions of
foldlautomatically and apply the usual strictness analysis to the specialized versions. However, I doubt this works as a general solution to the problem as it's possible to construct examples where this strategy leads to an explosion in code size. (Open question: are said examples really that common in practice?)
foldl, as it's written in GHC, will actually do the right thing assuming you compile with strictness analysis turned on. However, the recursive definition I gave above still yields a stack overflow.
Optimizations like strictness analysis that can't be counted on to be applied in all relevant cases are leaky abstractions. And like all leaky abstractions, strictness analysis fails to form a new semantic level upon which we can build new abstractions and modes of thinking; rather, it is an ad hoc piece of machinery that must be explicitly unpacked and considered when writing code. This places additional conceptual burden on the programmer.
Contrast this with laziness itself: laziness is pervasively and predictably applied, not an optimization you hope gets triggered. Laziness lets you program in a different style than you would in a strict language.
What would it look like to have perfect strictness analysis, which worked predictably, correctly handling polymorphic functions like
foldl? I'll detail a possible solution in my next post.
Update: It appears I was overly optimistic about the difficulty of this problem. Read on for the details.