Re: [Haskell-cafe] SYB <<looping>> very, very mysteriously

On Sat, Dec 5, 2009 at 2:38 AM, Andrea Vezzosi wrote:

On Fri, Dec 4, 2009 at 8:51 PM, Jeremy Shaw wrote:

...

I have stripped things down to the bare minimum, and test under GHC 6.10, GHC 6.12, Linux, and Mac OS X. Results are consistent.

In the following code,

 1. if you load the code into ghci and evaluate e it will hang, but (defaultValueD dict) :: Expression returns fine  2. if you change the gunfold instance for Proposition to, error "gunfold" it stops hanging -- even though this code is never called.  3. if you change, ( Data ctx [Expression], Sat (ctx Expression) => Data ctx Expression, to (Data ctx Expression, ....) => ... it stops hanging.

If someone could explain why each of these cases perform as they do, that would be awesome! Right now it is a big mystery to me.. e calls dict .. and there is only one instance of dict available, which should call error right away. I can't see how something could get in the way there...

It's less of a mystery if you think about the actual dictionaries ghc uses to implement typeclasses. The instance for Data ctx [a] depends on Data ctx a, so by requiring Data ctx [Expression] in the Data ctx Expression instance you're indeed making a loop there, though typeclasses do allow this, and the implementation has to be lazy enough to permit it. Strange that with a direct Data ctx Expression => Data ctx Expression loop we don't get the same problem. The reason the implementation of Proposition's gunfold matters is probably that k gets passed the dictionary for Data DefaultD Expression at the site of its call and some optimization is making it stricter than necessary.

Looks like we need a ghc dev here to fully unravel the mystery, in the meantime i'll try to reduce the test case even further.

I have posted a ghc bug for this: http://hackage.haskell.org/trac/ghc/ticket/3731 and an syb-with-class bug, in case it is not a ghc bug (perhaps due to undecidable instances?):http://code.google.com/p/syb-with-class/issues/detail?id=3