Re: Re[2]: [GHC] #876: stack overflow on 'length . filter odd $ [0 .. 999999999]'

On Aug 31, 2006, at 6:29 AM, Malcolm Wallace wrote:

Bulat Ziganshin wrote:

...

...

It makes sense to me that the above behaviour is seen: length is now a good consumer, but it generates 1+(1+(1+(1+... as it is consuming, and this causes a stack overflow. I don't think we can fix this while staying with fold/build fusion, so it looks to me like the patch should be reverted and the whole problem looked at post-6.6.

in general, for any function we can either implement 1) good consumer based on using foldr 2) tail-recursion

are you agree?

I'd like to point out that, if you are prepared to abandon foldr/build fusion in favour of hylo fusion, you can code good consumers using either foldr or foldl. (Length is a foldl, because it uses an accumulator.) Foldl is tail-recursive, but this does not prevent it being a good consumer, provided your framework of fusion laws is sufficiently flexible.

Actually, it's sufficient to do good arity-raising transformations, and use the definition: foldl f z xs = foldr (\x k a -> k (f a x)) id xs z This yields code which looks a bit like this: let loop [] = id loop (x:xs) = let k = loop xs in (\a -> k (f a x)) in loop xs z In the pH compiler we recognized this idiom (and its generalizations to multiple accumulating parameters) and arity-raised loop as follows: let loop [] a = a loop (x:xs) a = loop xs (f a x) in loop xs z So we *can* make foldl into a good consumer---it's not even particularly difficult---but it relies rather heavily on getting some of the knock-on program transformations to be reliable. That means making sure we recognize the above pattern before it gets mangled by other optimizations. A possibility to avoid this problem is just to look for over-saturated applications of "loop" and then attempt arity expansion and see if any under-saturated recursive calls remain. There are alternatives that involve real interprocedural arity analysis, but that's hard enough that I've never tried to do it except on paper. We can actually play some similar games with functions which use an accumulating parameter but exit early, or which can be modeled by little state machines, but the transformations required to get "the code you want" in these cases involve actual arity and closure analysis rather than simple pattern-matching (which suffices for the foldl-using-foldr trick). A look at recent papers by Olin Shivers should give an idea of the kind of tricks required. Hylo fusion is great if you want to deforest non-cleverly written library code or non-lists. Jacob Schwartz (now at Bluespec) did a hylo fusion pass for pH---but the knock-on transformations proved a bit problematic. I speculate that if you do a full-on analysis a la jhc you'd get really great code---but the GRIN argument was that you could just skip all this deforestation nonsense at that point as it happened implicitly during the analysis. -Jan-Willem Maessen

Regards, Malcolm _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users