[Haskell-cafe] does the compiler optimize repeated calls?

[Brian Hulley]

John Hughes wrote:
> The trouble is that this isn't always an optimisation. Try these two
> programs:
>
> powerset [] = [[]]
> powerset (x:xs) = powerset xs++map (x:) (powerset xs)
>
> and
>
> powerset [] = [[]]
> powerset (x:xs) = pxs++map (x:) pxs
>  where pxs = powerset xs
>
> Try computing length (powerset [1..n]) with each definition. For small
> n, the second is faster. As n gets larger, the second gets slower and
> slower, but the first keeps chugging along. The problem is that the
> second has exponentially higher peak memory requirements than the
> first. Round about n=25, on my machine, all other programs stop responding
> while the second one runs. You don't really want a compiler to make
> that kind of "pessimisation" to your program, which is why it's a
> deliberate decision to leave most CSE to the programmer. You can
> still write the second version, and suffer the consequences, but at least 
> you know
> it's your own fault!

Thanks for the above example. I found it quite difficult to understand why 
the second is worse than the first for large n, but I think the reason is 
that you're using the second def in conjunction with (length). Therefore it 
is the *combination* of the cse'd (powerset) with (length) that is less 
efficient, because (length) just reads its input as a stream so there is no 
need for the whole of (powerset xs) to exist in memory thus the non cse'd 
version gives a faster (length . powerset).

Ideally it would be great if the compiler could make use of the context in 
which a function is being applied to produce optimized code across function 
boundaries. In the above example of (length . powerset), (length) has no 
interest in the contents of the powerset itself so could the compiler not 
fuse (length . powerset) into the following function:

    lengthPowerset [] = 1
    lengthPowerset (x:xs) = 2 * lengthPowerset xs

The compiler would need to analyse the definition of (++) and (map) to 
discover that

    length (x ++ y) === length x + length y

    length (map f y) === length y

and with that knowledge I imagine the steps could be something like:

    lengthPowerset [] = length (powerset []) = length ([[]]) = 1

    lengthPowerset (x:xs)
        = length (powerset xs ++ map (:x) (powerset xs))
        = length (powerset xs) + length (map (:x) (powerset xs))
        = length (powerset xs) + length (powerset xs)
        = lengthPowerset xs + lengthPowerset xs
        = 2 * lengthPowerset xs

After getting the function (lengthPowerset) as above, I'd also expect the 
compiler to apply a transformation into a tail recursive function:

    lengthPowerset y = lengthPowerset' y 1
        where
            lengthPowerset' [] i = i
            lengthPowerset' (_:xs) i = lengthPowerset' xs $! 2*i

resulting in a tightly coded machine code loop to rival, or greatly 
exceed(!), the best efforts of C.

In the meantime I tend to code in Haskell just expecting these kind of 
optimizations to be done (unless I'm writing a really time-critical piece of 
code that can't wait), knowing of course that they might not be done just at 
the moment but at least some time in the (hopefully not too distant) 
future... ;-)

Regards, Brian.
-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com