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.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
