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

David Fox ddssff at gmail.com
Mon Dec 7 09:38:51 EST 2009


On Sat, Dec 5, 2009 at 2:38 AM, Andrea Vezzosi <sanzhiyan at gmail.com> wrote:
> On Fri, Dec 4, 2009 at 8:51 PM, Jeremy Shaw <jeremy at n-heptane.com> 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


More information about the Haskell-Cafe mailing list