up vote 10 down vote favorite
2

Full laziness has been repeatedly demonstrated to cause space leaks.

Why is full laziness on from -O onwards? I find myself unconvinced by the reasoning in SPJ's The Implementation of Functional Programming Languages. The claim is that in

f = \y -> y + sqrt 4

sqrt 4 is unnecessarily repeated each time f is entered so we should float it outside the lambda. I agree in the small, but since we've seen what problems this transformation causes in the large I don't believe it is worth it. It seems to me that the benefits of this transformation are obtainable unilaterally** with only local code changes and programmers who want it should implement it by hand.

Can you convince me otherwise? Is full-laziness actually really useful? I will be especially convinced if you can provide examples which to implement by hand require multilateral cooperation or non-local transformations.

** unlike optimizations like inlining and stream fusion which to implement by hand would require multilateral cooperation between modules and non-local code changes

share|improve this question
1  
The full-laziness transformantion doesn't actually have anything to do with evaluation order. – Tom Ellis Feb 4 '16 at 21:39
up vote 7 down vote

There's at least one common case where full laziness is "safe" and an optimization.

g :: Int -> Int
g z = f (z+1)
  where f 0 = 0
        f y = 1 + f (y-1)

This really means g = \z -> let {f = ...} in f (z+1) and, compiled that way, will allocate a closure for f before calling it. Obviously that's silly, and the compiler should transform the program into

g_f 0 = 0
g_f y = 1 + g_f (y-1)
g z = g_f (z+1)

where no allocation is needed to call g_f. Happily the full laziness transformation does exactly that.

Obviously programmers could refrain from making these local definitions that do not depend on the arguments of the top-level function, but such definitions are generally considered good style...

Another example:

h :: [Int] -> [Int]
h xs = map (+1) xs

In this case you can just eta reduce, but normally you can't eta reduce. And naming the function (+1) is quite ugly.

share|improve this answer
    
Thanks for the example. The same would apply if f were an Int, especially if calculating it is expensive. However, I was thinking of a less violent transformation: g = let {f = ...} in \z -> f (z+1). This would still be considered good style I think, even if it doesn't fit syntactically as nicely with Haskell's where. – Tom Ellis Jan 31 '16 at 20:24
    
Your second example, h, is more convincing because giving a name to (+1) is indeed quite ugly. I would assess it as being equivalent to SPJ's example with sqrt 4. I guess my conclusion is then that full-laziness saves you from death by a thousand cuts. One could in principle produce optimized versions by hand but it would be inefficient to do so everywhere. – Tom Ellis Feb 1 '16 at 19:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.