Liberalising IncoherentInstances

[Simon Peyton-Jones]

Friends

I've realised that GHC's -XIncoherentInstances flag is, I think, over-conservative.  I propose to liberalise it a bit. This email describes the issue.  Please yell if you think this is a bad idea.

Simon

Suppose we have

	class C a where { op :: a -> String }
	instance C [a] where ...
	instance C [Char] where ...

	f :: [b] -> String
	f xs = "Result:" ++ op xs

With -XOverlappingInstances, but without -XIncoherentInstances, f won't compile.  Reason: if we call 'f' at Char (e.g.  f "foo") then you might think we should use instance C [Char].  For example, if we inlined 'f' at the call site, to get ("Result:" ++ op "foo"), we certainly then would use the C [Char] instance, giving perhaps different results.  If we accept the program as-is, we'll permanently commit 'f' to using the C [a] instance.  

The -XIncoherentInstances flag says "Go ahead and use an instance, even if another instance might become relevant if you were to specialise or inline the enclosing function."  The GHC user manual gives a more precise spec [1].

Now consider this
	class D a b where { opD :: a -> b -> String }
	instance D Int b where ...
	instance D a Int where ...

	g (x::Int) = opD x x

Here 'g' gives rise to a constraint (D Int Int), and that matches two instance declarations.   So this is rejected regardless of flags.  We can fix it up by adding 
	instance D Int Int where ...
but this is pretty tiresome in cases where it really doesn't matter which instance you choose.  (And I have a use-case where it's more than tiresome [2].)

The underlying issue is similar to the previous example.  Before, there was *potentially* more than one way to generate evidence for (C [b]); here there is *actually* more than one instance.  In both cases the dynamic semantics of the language are potentially affected by the choice -- but -XIncoherentInstnaces says "I don't care".


So the change I propose to make IncoherentInstances to pick arbitrarily among instances that match.  More precisely, when trying to find an instance matching a target constraint (C tys),

a) Find all instances matching (C tys); these are the candidates

b) Eliminate any candidate X for which another candidate Y is
  strictly more specific (ie Y is a substitution instance of X),
  if either X or Y was complied with -XOverlappingInstances

c) Check that any non-candidate instances that *unify* with (C tys)
   were compiled with -XIncoherentInstances

d) If only one candidate remains, pick it.
    Otherwise if all remaining candidates were compiled with
    -XInccoherentInstances, pick an arbitrary candidate

All of this is precisely as now, except for the "Otherwise" part of (d).  One could imagine different flags for the test in (c) and (d) but I really don't think it's worth it.


Incidentally, I think it'd be an improvement to localise the Overlapping/Incoherent flags to particular instance declarations, via pragmas, something like
	instance C [a] where
	  {-# ALLOW_OVERLAP #-}
	  op x = ....

Similarly {-# ALLOW_INCOHERENT #-}.   Having -XOverlappingInstances for the whole module is a bit crude., and might be missed when looking at an instance.   How valuable would this be?

[1] http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap
[2] http://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers