I wrote:
This "CSE-makes-it-worse" property strikes me as "interesting". Has anyone worked on characterizing CSE space leaks (and avoiding CSE in those cases)?
and Simon replied:
You might find chapter 23 "The pragmatics of graph reduction" in my 1987 book worth a look. It gives other examples where CSE can be harmful.
There are some great examples there. Specifically, 23.4.2 "Excessive Sharing" (viewable at http://research.microsoft.com/~simonpj/papers/ slpj-book-1987/PAGES/405.HTM) gives a neat example, the powerList function. In short, it contrasts two definitions. The first uses sharing: powerList [] = [ [] ] powerList (x:xs) = pxs ++ map (x :) pxs where pxs = powerList xs and a space-efficient one (that does more reductions): powerList [] = [ [] ] powerList (x:xs) = (powerList xs) ++ map (x :) (powerList xs) ... when running length(powerList [1..20]). But my original question was whether this problem is considered "interesting", etc. As Simon points out above, its an issue that has existed for at least 20 years, but Simon also wrote for GHC bug #947 (which looked like a related issue):
I don't know any way to solve this problem automatically. But I do think it should be under your control.
To me, problems that Simon doesn't know how to solve are by definition at least a little interesting, but probably likely to be rather hard... :-) Melissa. P.S. GHC bug #947 can be viewed at http://hackage.haskell.org/trac/ ghc/ticket/947 (Simon's bandaid for GHC bug #947 was -fno-cse.)