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

[Andrea Vezzosi]

On Mon, Dec 7, 2009 at 3:38 PM, David Fox <ddssff at gmail.com> wrote:
> 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
>

While trying to make the test case on the ghc trac self-contained I've
found a workaround which involves changing the Default [a] instance in
happstack-data. I've attached the patch.

I don't know why it works with certainity, so it'd be nice if you
could test it in a large codebase at least.

The problem is that one should work out how all these dictionaries get
constructed, and that means staring at a lot of Core.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: workaround-for-default-wrt-http___hackage_haskell_org_trac_ghc_ticket_3731.dpatch
Type: application/octet-stream
Size: 2026 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100124/aea97d8f/workaround-for-default-wrt-http___hackage_haskell_org_trac_ghc_ticket_3731.obj