Sunday, June 7, 2009

Perfect strictness analysis (Part 1)

Previously, I talked about how strict-by-default results in less modular code. Now, I want to talk about problems with lazy-by-default languages, and how these problems could be addressed by better strictness analysis. This will be in multiple parts. (Part 2)

Let's look at a simple example where laziness causes problems. Here's a definition for a left fold in Haskell:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f s [] = s
foldl f s (h:t) = foldl f (f s h) t
If you try evaluating foldl (+) 0 [1..1000000], you'll get a stack overflow. The stack overflow occurs because foldl is 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, f is strict in its arguments, then the seed could also be made strict without any change in semantics. Strictness analysis has failed us: since foldl is 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 foldl automatically 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?)

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

No comments: