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

[Jan-Willem Maessen]

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

> Bulat Ziganshin <bulat.ziganshin at gmail.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20060831/46106eb3/smime.bin