SYB with class: Bug in Derive.hs module

newer
Research Position, Leeds: Parallel...

Roman Cheplyaka

3 Sep 2012 3 Sep '12

6 a.m.

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/

Show replies by date

Andrea Vezzosi

3 Sep 3 Sep

6:50 a.m.

On Mon, Sep 3, 2012 at 12:00 PM, Roman Cheplyaka 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

Roman Cheplyaka

8:53 a.m.

* Andrea Vezzosi [2012-09-03 12:50:03+0200]

...

On Mon, Sep 3, 2012 at 12:00 PM, Roman Cheplyaka 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/

Andrea Vezzosi

3:17 p.m.

On Mon, Sep 3, 2012 at 2:53 PM, Roman Cheplyaka wrote:

...

* Andrea Vezzosi [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

Andrea Vezzosi

4 Sep 4 Sep

9:13 p.m.

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

Roman Cheplyaka

5 Sep 5 Sep

4:27 a.m.

* Andrea Vezzosi [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/

4641

Age (days ago)

4643

Last active (days ago)

List overview

Download

5 comments

2 participants

participants (2)

Andrea Vezzosi
Roman Cheplyaka