Lambda the Ultimate

I agree that the is rather weak on related work. Another thing which they totally miss to talk about is zip-like functions, function which takes several arguments and which can be fused in all of these arguments. This is an example where many other fusion methods fail. It's extra surprising that they don't talk about this since I believe that their algorithm actually handles this case, although I have yet to work out an example in detail.

I'm also not that convinced that their fusion method will actually do any good in practice. In the paper they only demonstrate that it doesn't degrade the performance which is an incredibly weak demonstration. The identity transformation doesn't degrade performance either!

Another reason for why I'm skeptic about the performance improvements that can be achieved with this method is the following. For short cut fusion as it is used in Haskell, the biggest win is not in removing the intermediate data structures, it's about the optimizations that are enabled after fusion is performed. Now, the problem is that Lightweight fusion doesn't enable nearly as much optimizations as short cut fusion does. An example will help illustrate my point. The important this here is that we're dealing with higher order functions such as map and foldr. I'm going to pretend that lightweight fusion can handle several applications of the same functions so I'm going to use

map f o map g

as my example. Lightweight fusion will (if it could handle this example) yield the following code:

let map_map a b [] = []
    map_map a b (x::xs) = a (b x) :: map_map a b xs
in map_map f g 

Note how the two functions f and g never get "in contact". There is no easy way for the optimizer to see that they are applied in sequence to the same elements all the time.
Now short cut fusion would yield something isomorphic to

map (f o g)

. Now this is a much nicer thing for the optimizer. Suppose (switching to Haskell syntax) that

f = (+2)

and

g = (+4)

then it's now an easy matter for the optimizer to generate the result

map (+6)

. OK, addition is a silly example but it extends directly to more complicated functions. It's clear that lightweight fusion is inferior to short cut fusion in this respect.

I'm also not that convinced that their fusion method will actually do any good in practice. In the paper they only demonstrate that it doesn't degrade the performance which is an incredibly weak demonstration. The identity transformation doesn't degrade performance either!

To be fair, the authors were working with SML#, which is rather handicapped in this regard. Any functions defined in separate modules, such as standard library functions like map and fold, are opaque to SML#'s optimizer, so it can't fuse those definitions properly. They describe these problems towards the end of section 7.

So despite their promising fusion results in section 5 (50% reduction in allocations, and 33% reduction in execution time), actual programs compiled with SML# don't benefit much due to these problems. They also discuss possible solutions.

[Edit: does anyone know if this fusion technique has been used in a compiler that doesn't suffer from SML#'s limitations?]