SYB with class: Bug in Derive.hs module

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

SYB with class: Bug in Derive.hs module

Roman Cheplyaka-2
There's a bug in syb-with-class reported by Alexey Rodriguez Yakushev in
2008 [1]. I can confirm that the bug is still there (syb-with-class-0.6.1.3,
ghc 7.4.1).

[1]: http://www.haskell.org/pipermail/haskell-cafe/2008-March/041179.html

Here's an even simpler test case:

    {-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses,
        UndecidableInstances, TemplateHaskell, OverlappingInstances,
        DeriveDataTypeable #-}
    import Data.Generics.SYB.WithClass.Basics
    import Data.Generics.SYB.WithClass.Derive

    data Foo = Foo Foo | Bar
      deriving (Typeable, Show)

    deriveData [''Foo]

    f :: (Data NoCtx ast, Typeable ast) => ast -> TypeRep
    f = typeOf

    main = print $ f $ Foo Bar

The cause of this bug is a self-referencing instance created by
deriveData:

    instance (Data ctx Foo, Sat (ctx Foo)) => Data ctx Foo where ...

What's the proper way to fix it?

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: SYB with class: Bug in Derive.hs module

Andrea Vezzosi
On Mon, Sep 3, 2012 at 12:00 PM, Roman Cheplyaka <[hidden email]> wrote:

> There's a bug in syb-with-class reported by Alexey Rodriguez Yakushev in
> 2008 [1]. I can confirm that the bug is still there (syb-with-class-0.6.1.3,
> ghc 7.4.1).
>
> [1]: http://www.haskell.org/pipermail/haskell-cafe/2008-March/041179.html
>
> Here's an even simpler test case:
>
>     {-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses,
>         UndecidableInstances, TemplateHaskell, OverlappingInstances,
>         DeriveDataTypeable #-}
>     import Data.Generics.SYB.WithClass.Basics
>     import Data.Generics.SYB.WithClass.Derive
>
>     data Foo = Foo Foo | Bar
>       deriving (Typeable, Show)
>
>     deriveData [''Foo]
>
>     f :: (Data NoCtx ast, Typeable ast) => ast -> TypeRep
>     f = typeOf
>
>     main = print $ f $ Foo Bar

This is pretty similar to what ended up being a ghc bug, fixed in 7.0 though:
http://hackage.haskell.org/trac/ghc/ticket/3731

> The cause of this bug is a self-referencing instance created by
> deriveData:
>
>     instance (Data ctx Foo, Sat (ctx Foo)) => Data ctx Foo where ...
>
> What's the proper way to fix it?

From a few tests it seems we no longer need the circular context hack
in ghc-7.4.1 to get the instance to typecheck, so we could side-step
the issue entirely by removing it from the generated code.

-- Andrea Vezzosi

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: SYB with class: Bug in Derive.hs module

Roman Cheplyaka-2
* Andrea Vezzosi <[hidden email]> [2012-09-03 12:50:03+0200]

> On Mon, Sep 3, 2012 at 12:00 PM, Roman Cheplyaka <[hidden email]> wrote:
> > There's a bug in syb-with-class reported by Alexey Rodriguez Yakushev in
> > 2008 [1]. I can confirm that the bug is still there (syb-with-class-0.6.1.3,
> > ghc 7.4.1).
> >
> > [1]: http://www.haskell.org/pipermail/haskell-cafe/2008-March/041179.html
> >
> > Here's an even simpler test case:
> >
> >     {-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses,
> >         UndecidableInstances, TemplateHaskell, OverlappingInstances,
> >         DeriveDataTypeable #-}
> >     import Data.Generics.SYB.WithClass.Basics
> >     import Data.Generics.SYB.WithClass.Derive
> >
> >     data Foo = Foo Foo | Bar
> >       deriving (Typeable, Show)
> >
> >     deriveData [''Foo]
> >
> >     f :: (Data NoCtx ast, Typeable ast) => ast -> TypeRep
> >     f = typeOf
> >
> >     main = print $ f $ Foo Bar
>
> This is pretty similar to what ended up being a ghc bug, fixed in 7.0 though:
> http://hackage.haskell.org/trac/ghc/ticket/3731

The difference between my test case and the one attached to the ticket
is that here there's an explicitly circular instance generated by TH.
In the "SYB with class" paper it is specifically said to be broken. So
it looks more like a problem in the TH code rather than in GHC.

> > The cause of this bug is a self-referencing instance created by
> > deriveData:
> >
> >     instance (Data ctx Foo, Sat (ctx Foo)) => Data ctx Foo where ...
> >
> > What's the proper way to fix it?
>
> From a few tests it seems we no longer need the circular context hack
> in ghc-7.4.1 to get the instance to typecheck, so we could side-step
> the issue entirely by removing it from the generated code.

Not sure what hack you're referring to.

As I understand it, the circular context arises as a special case of the
context that includes all the "inner" types of a data type. It's not
possible to get rid of this context entirely — for example, consider

    data X a = X (Y a)

where we really need the "Data ctx (Y a)" context (but perhaps it could
be "Data ctx a" instead?).

So we need some criterion to decide whether a structural part of a data
type should be included into the instance context.

Does this make sense, or am I on the completely wrong track?

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: SYB with class: Bug in Derive.hs module

Andrea Vezzosi
On Mon, Sep 3, 2012 at 2:53 PM, Roman Cheplyaka <[hidden email]> wrote:

> * Andrea Vezzosi <[hidden email]> [2012-09-03 12:50:03+0200]
>> > [...]
>>
>> This is pretty similar to what ended up being a ghc bug, fixed in 7.0 though:
>> http://hackage.haskell.org/trac/ghc/ticket/3731
>
> The difference between my test case and the one attached to the ticket
> is that here there's an explicitly circular instance generated by TH.
> In the "SYB with class" paper it is specifically said to be broken. So
> it looks more like a problem in the TH code rather than in GHC.

Right, it's debatable whether ghc should support these instances,
though in our case they are well-founded, it only has to produce code
that's lazy enough on the dictionaries as far as i can tell.

>> > The cause of this bug is a self-referencing instance created by
>> > deriveData:
>> >
>> >     instance (Data ctx Foo, Sat (ctx Foo)) => Data ctx Foo where ...
>> >
>> > What's the proper way to fix it?
>>
>> From a few tests it seems we no longer need the circular context hack
>> in ghc-7.4.1 to get the instance to typecheck, so we could side-step
>> the issue entirely by removing it from the generated code.
>
> Not sure what hack you're referring to.

I was going from memory and remembering that the additional Data ctx
Foo in the context was necessary to make the instance typecheck, and
calling that an hack.
(Now I think I was remembering some HappS code using syb-wc which had
to do that instead).

> As I understand it, the circular context arises as a special case of the
> context that includes all the "inner" types of a data type. It's not
> possible to get rid of this context entirely — for example, consider
>
>     data X a = X (Y a)
>
> where we really need the "Data ctx (Y a)" context (but perhaps it could
> be "Data ctx a" instead?).

(I don't think I like changing the produced code on the basis of which
instances are in scope, so I'd stick with "Data ctx (Y a)")

> So we need some criterion to decide whether a structural part of a data
> type should be included into the instance context.
>
> Does this make sense, or am I on the completely wrong track?

Yes that's correct, I meant to only filter out Data ctx (X a) in this
case, in general I propose to eliminate all the "Data ctx (X ..)" from
the context, when X is the data constructor for which we are making
the instance, but keep the corresponding "Sat (ctx (X ..))", do you
think this would break any instances that would otherwise work?

It'd be interesting to find out if we can make a sensible instance for
non-regular types like the following though:

data Z a = Z (Z (a,a)) | Leaf a

the instance we produce currently makes instance resolution
non-terminate and the instance we'd  produce under my proposal
wouldn't typecheck.

-- Andrea Vezzosi

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: SYB with class: Bug in Derive.hs module

Andrea Vezzosi
I've pushed the discussed changes to the repo[1], it'd be good if you
(and other users) could test them before they get to hackage.

[1] darcs get http://patch-tag.com/r/Saizan/syb-with-class/

-- Andrea

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: SYB with class: Bug in Derive.hs module

Roman Cheplyaka-2
* Andrea Vezzosi <[hidden email]> [2012-09-05 03:13:56+0200]
> I've pushed the discussed changes to the repo[1], it'd be good if you
> (and other users) could test them before they get to hackage.
>
> [1] darcs get http://patch-tag.com/r/Saizan/syb-with-class/

I confirm that it fixed my problem.

Thank you!

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe