Stack overflow in stream-fusion library with GHC 6.10 RC

[dons]

Regression from GHC 6.8.x to GHC 6.10 release candidate,

$ runhaskell Setup.lhs configure 
Configuring stream-fusion-0.1.1...
$ runhaskell Setup.lhs build     
Preprocessing library stream-fusion-0.1.1...
Building stream-fusion-0.1.1...
...
Data/Stream.hs:575:4:
    Warning: Pattern match(es) are non-exhaustive
             In the definition of `next':
                 Patterns not matched: (_ :!: (Just (L _))) :!: S2
[2 of 3] Compiling Data.List.Stream ( Data/List/Stream.hs, dist/build/Data/List/Stream.o )
stack overflow: use +RTS -K<size> to increase it

The stack overflow was not present with GHC 6.8.x

You can get the code here:  http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion

[igloo]

I haven't tracked down exactly what's going on here, but it seems to be going round some sort of loop in functions like simplNonRecE and simplLam, with binders [ds_dC6, ds_dC7] and body

 case ds_dC7 of _ {
   [] -> GHC.Types.[] @ b;
   : x [ALWAYS Once Nothing] xs [ALWAYS Once Nothing] ->
     GHC.Types.:
       @ b (ds_dC6 x) (Data.List.Stream.mapx @ a @ b ds_dC6 xs)

I'll attach a cut-down example.

[igloo]

Compile with:

ghc --make -O -Wall -XBangPatterns -XExistentialQuantification -XMagicHash -XTypeOperators Data.Stream Data.List.Stream -fforce-recomp

[simonpj]

I know more or less what is happening now. Here's the diagnosis. Stream.2.hs contains this:

mapx f (x:xs) = f x : mapx f xs
{-# NOINLINE [1] mapx #-}

{-# RULES
    "mapx -> fusible" [~1] forall f xs.
        mapx f xs = unstream (mapy f (stream xs))
    "mapx -> unfused" [1] forall f xs.
        unstream (mapy f (stream xs)) = mapx f xs
  #-}

(Note that the second of these rules is an orphan.) After applying the fusible rule, at the end of Phase 1 GHC sees

mapx f (x:xs) = f x : unstream (mapy f (stream xs))

Now mapx looks non-recursive; after all, mapy is imported. So when the occurrence analyser runs in Phase 0 mapx is not marked as a loop breaker and can be inlined freely. However the unfused rule fires, and makes mapx recursive after all. Before the occurrence analyser runs again, though, the simplifier processes the next definition:

initsx (x:xs) = [] : mapx (x:) (initsx xs)

Since mapx is not a loop breaker, it's just inlined repeatedly; result infinite loop.

You may say that the occurrence analyser should be run again after finishing each definition. But that is only sticking plaster. Suppose we had

  mapx x = mapy x

(non-recursive, no rules) and imported that into a scope where there was an orphan rule

  RULES "x" mapy = mapx

Then you can see that would make GHC loop. (Inline mapx, run the RULE, and repeat.)

What to do? In general it's very hard to do much about RULES that give rise to loops, esp when they are orphans. When they are defined in the same module as the function they are RULES for, GHC is pretty good; but otherwise it's difficult.

In this case the obvious thing is to add

{-# NOINLINE [~1] mapx #-}

to stop it being inlined after Phase 1. That should cure the loop, but I'm not sure if the optimisations you have in mind would still work. (Curiously the exact inverse annotation is provided in the test case, saying don't inline until Phase 1.)

I'm surprised 6.8.3 works on this example; I suspect it's a fluke. (Should check this.)

Bottom line: I can't see a quick fix. Need to discuss how important this pattern is. At least we know what the problem is.

Simon

[rl]

FWIW, I don't think it is necessary to do anything about this. The library code and the pattern in general are arguably wrong since the fusible rule really shouldn't be applied in the rhs of mapx. It is also easily fixed:

mapx = id mapz
mapz f (x:xs) = f x : mapz f xs
{-# INLINE [1] mapx #-}

{-# RULES
    "mapx -> fusible" [~1] forall f xs.
        mapx f xs = unstream (mapy f (stream xs))
    "mapx -> unfused" [1] forall f xs.
        unstream (mapy f (stream xs)) = mapz f xs
  #-}

or simply

mapx f xs = unstream (mapy f (stream xs))
mapz f (x:xs) = f x : mapz f xs
{-# INLINE mapx #-}

{-# RULES
  "mapx -> unfused" [1] forall f xs.
    unstream (mapy f (stream xs)) = mapz f xs
  #-}

[simonpj]

Excellent. So who is responsible for the library stream-fusion? Can he or she take advantage of Roman's advice?

Meanwhile I'd like to leave this ticket open, to remind someone (ideally not me) to add some Wiki docs to  http://haskell.org/haskellwiki/GHC/Using_rules to explain in a more standalone way what I documented above. Pretty please?

Simon

[dons]

@simonpj

He/she is me, and yes, I'll apply Roman's advice.

[igloo]

Don, are you planning to write something about this on the wiki page?

We should either write it, or admit defeat and close the ticket.

[igloo]

Admitting defeat.