Hi, all! It's been a while since I sent the message below to the GHC list, which I believe is its rightful forum, but I've had no reply so far. So I am giving the haskell list a try. Thanks in advance. Cheers, Jorge. --------------------------- Mensagem Original ---------------------------- Assunto: undecidable & overlapping instances: a bug? De: "Jorge Marques Pelizzoni" <jpeliz@icmc.usp.br> Data: Sab, Outubro 13, 2007 5:59 am Para: "GHC users" <glasgow-haskell-users@haskell.org> -------------------------------------------------------------------------- Hi, all! I am quite intrigued at the behaviour examplified in the attached module. It's true I am a newbie and probably don't quite get the whole consequence spectrum of -fallow-undecidable-instances, but why providing that dummy instance (commented out) get the thing to compile? By the way, I'm using GHC 6.6 on WinXP (actually, latest Visual Haskell with MS Visual Studio 2005) and the error message I get is: FooModule.hs:13:9: Could not deduce (Show a) from the context (Concrete a b) arising from use of `bar' at FooModule.hs:13:9-13 Possible fix: add (Show a) to the class or instance method `foo' In the expression: bar x In the definition of `foo': foo x = bar x In the definition for method `foo' A second question: which kinds of overlapping are covered by -fallow-overlapping-instances? It seems that the following (also in the attached module) is not allowed: instance (Show a, Abstract a b) => Concrete a b where foo x = show x instance (Abstract a b) => Concrete a b which gives me the message: FooModule.hs:17:0: Duplicate instance declarations: instance [overlap ok] (Show a, Abstract a b) => Concrete a b -- Defined at FooModule.hs:17:0 instance [overlap ok] (Abstract a b) => Concrete a b -- Defined at FooModule.hs:30:0 Thanks in advance for any pointers. Cheers, Jorge.
| I am quite intrigued at the behaviour examplified in the attached module. | It's true I am a newbie and probably don't quite get the whole consequence | spectrum of -fallow-undecidable-instances, but why providing that dummy | instance (commented out) get the thing to compile? Sorry I must have missed this. It's a nice example of the trickiness of functional dependencies. Here's what is happening. First a very cut-down version of your example: class Concrete a b | a -> b where bar :: a -> String instance (Show a) => Concrete a b wib :: Concrete a b => a -> String wib x = bar x Now consider type inference for 'wib'. GHC figures out that the call of 'bar' gives rise to the constraint (Concrete p q), where x has type 'p'. Ah, but x must have type 'a', so the constraint is (Concrete a q). Now GHC tries to satisfy (Concrete a q) from (Concrete a b). If it applied improvement right away it'd succeed, but sadly it first looks at instances declarations. Success: we can get (Concrete a q) from (Show a). So it uses the instance decl and now we can't get (Show a) from (Concrete a b). OK, so you found that adding instance Concrete Bool Bool fixed the problem. That's weird isn't it? The reason is this. When GHC looks at the instance decls, it now sees *two* instance decls matching (Concrete a q), and so it declines for now to use either of them (since it's not clear which would be the right one). Once it has finished with instance decls it tries improvement. And, yes, it now sees that q=b, so all is well. You might say that GHC should use improvement more vigorously, and perhaps you'd be right. And indeed the upcoming GHC 6.8 does exactly that. But it's a great example of the delicacy of type inference in the presence of equalities. I'm going to add it to GHC's test suite! Simon
Simon Peyton-Jones wrote:
| I am quite intrigued at the behaviour examplified in the attached module. | It's true I am a newbie and probably don't quite get the whole consequence | spectrum of -fallow-undecidable-instances, but why providing that dummy | instance (commented out) get the thing to compile?
Sorry I must have missed this. It's a nice example of the trickiness of functional dependencies. Here's what is happening. First a very cut-down version of your example:
class Concrete a b | a -> b where bar :: a -> String
instance (Show a) => Concrete a b
wib :: Concrete a b => a -> String wib x = bar x
Now consider type inference for 'wib'. ...
Hold on a second! There's a more serious problem here, before we get to 'wib'. The definition of class Concrete asserts that there is a dependency from a to b. In other words, it promises that, for any a, there must be at most one b such that Concrete a b holds. But then the following instance declaration says that Concrete a b can be instantiated for *any* a and b, the only proviso being that a is an instance of Show. In particular, there is no functional relationship between the parameters. As such, these two declarations are in direct conflict with one another! To quote the error message that Hugs produces, the "Instance is more general than a dependency allows". I thought this must be a typo in your email, but then I discovered that the ghci (6.6.1) installed on my machine accepts this code, at least once the Concrete Bool Bool instance was added. If the instance declarations are not consistent with the functional dependency, then improvement is unsound, and all bets are off! Further experiments suggest that this behavior occurs only when the-fallow-undecidable-instances flag is specified. But the reason you need to check for consistency between instance declarations and dependencies is to ensure soundness, not decidability. I don't know if this was the problem in the original example, but perhaps we should debug this cut down version first :-) All the best, Mark
Hi, Mark is quite right, and there is a bug report that documents the problem: http://hackage.haskell.org/trac/ghc/ticket/1241 The trac ticket is targeting GHC 6.8 but the ticket is still open. I have not had a chance to try out any of the 6.8 release candidates yet, so I am not sure if there have been changes in this area. -Iavor On 10/17/07, Mark P Jones <mpj@cs.pdx.edu> wrote:
Simon Peyton-Jones wrote:
| I am quite intrigued at the behaviour examplified in the attached module. | It's true I am a newbie and probably don't quite get the whole consequence | spectrum of -fallow-undecidable-instances, but why providing that dummy | instance (commented out) get the thing to compile?
Sorry I must have missed this. It's a nice example of the trickiness of functional dependencies. Here's what is happening. First a very cut-down version of your example:
class Concrete a b | a -> b where bar :: a -> String
instance (Show a) => Concrete a b
wib :: Concrete a b => a -> String wib x = bar x
Now consider type inference for 'wib'. ...
Hold on a second! There's a more serious problem here, before we get to 'wib'. The definition of class Concrete asserts that there is a dependency from a to b. In other words, it promises that, for any a, there must be at most one b such that Concrete a b holds. But then the following instance declaration says that Concrete a b can be instantiated for *any* a and b, the only proviso being that a is an instance of Show. In particular, there is no functional relationship between the parameters. As such, these two declarations are in direct conflict with one another! To quote the error message that Hugs produces, the "Instance is more general than a dependency allows".
I thought this must be a typo in your email, but then I discovered that the ghci (6.6.1) installed on my machine accepts this code, at least once the Concrete Bool Bool instance was added. If the instance declarations are not consistent with the functional dependency, then improvement is unsound, and all bets are off!
Further experiments suggest that this behavior occurs only when the-fallow-undecidable-instances flag is specified. But the reason you need to check for consistency between instance declarations and dependencies is to ensure soundness, not decidability.
I don't know if this was the problem in the original example, but perhaps we should debug this cut down version first :-)
All the best, Mark
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Good point Mark! And yes, the bug is still open Iavor. The trouble is that a) the coverage condition ensures that everything is well behaved b) but it's too restrictive for some uses of FDs, notably the MTL library c) there are many possibilities for more generous conditions, but the useful ones all seem complicated Concerning the last point I've dumped the current brand leader for (c) into http://hackage.haskell.org/trac/ghc/ticket/1241#comment:15. Better ideas for (c) would be welcome. Simon | -----Original Message----- | From: Iavor Diatchki [mailto:iavor.diatchki@gmail.com] | Sent: 17 October 2007 19:19 | To: Mark P Jones | Cc: Simon Peyton-Jones; Haskell users; Tom Schrijvers; Martin Sulzmann | Subject: Re: [Haskell] [Fwd: undecidable & overlapping instances: a bug?] | | Hi, | Mark is quite right, and there is a bug report that documents the problem: | http://hackage.haskell.org/trac/ghc/ticket/1241 | The trac ticket is targeting GHC 6.8 but the ticket is still open. I | have not had a chance to try out any of the 6.8 release candidates | yet, so I am not sure if there have been changes in this area. | -Iavor | | On 10/17/07, Mark P Jones <mpj@cs.pdx.edu> wrote: | > Simon Peyton-Jones wrote: | > > | I am quite intrigued at the behaviour examplified in the attached | module. | > > | It's true I am a newbie and probably don't quite get the whole | consequence | > > | spectrum of -fallow-undecidable-instances, but why providing that dummy | > > | instance (commented out) get the thing to compile? | > > | > > Sorry I must have missed this. It's a nice example of the trickiness of | > > functional dependencies. Here's what is happening. First a very cut- | down | > > version of your example: | > > | > > class Concrete a b | a -> b where | > > bar :: a -> String | > > | > > instance (Show a) => Concrete a b | > > | > > wib :: Concrete a b => a -> String | > > wib x = bar x | > > | > > Now consider type inference for 'wib'. ... | > | > Hold on a second! There's a more serious problem here, before we | > get to 'wib'. The definition of class Concrete asserts that there | > is a dependency from a to b. In other words, it promises that, for | > any a, there must be at most one b such that Concrete a b holds. | > But then the following instance declaration says that Concrete a b | > can be instantiated for *any* a and b, the only proviso being that a | > is an instance of Show. In particular, there is no functional | > relationship between the parameters. As such, these two | > declarations are in direct conflict with one another! To quote the | > error message that Hugs produces, the "Instance is more general than | > a dependency allows". | > | > I thought this must be a typo in your email, but then I discovered | > that the ghci (6.6.1) installed on my machine accepts this code, at | > least once the Concrete Bool Bool instance was added. If the | > instance declarations are not consistent with the functional | > dependency, then improvement is unsound, and all bets are off! | > | > Further experiments suggest that this behavior occurs only when | > the-fallow-undecidable-instances flag is specified. But the reason you | > need to check for consistency between instance declarations and | > dependencies is to ensure soundness, not decidability. | > | > I don't know if this was the problem in the original example, but | > perhaps we should debug this cut down version first :-) | > | > All the best, | > Mark | > | > _______________________________________________ | > Haskell mailing list | > Haskell@haskell.org | > http://www.haskell.org/mailman/listinfo/haskell | >
participants (4)
-
Iavor Diatchki -
Jorge Marques Pelizzoni -
Mark P Jones -
Simon Peyton-Jones