The point is that Mark proposes a *pessimistic* ambiguity check whereas Tom (as well as GHC) favors an *optimistic* ambiguity check. By pessimistic I mean that we immediately reject a program/type if there's a potential unambiguity. For example, class Foo a b forall a b. Foo a b => b -> b is potentially ambiguous assuming we encounter instance Foo Int Char instance Foo Bool Char But such instances might never arise. See Tom's example below which applies an optimistic ambiguity check. In the extreme case, the optimistic ambiguity check only checks for ambiguity when calling the ground top-level function main. At this point (latest), we must provide (unambiguously) evidence for type classes and type equations. In summary: - The pessimistic ambiguity check is more in line with Haskell's open world view (of type classes and type families/functions being open/extensible). Anything can happen in the future (we might add an new type instances). So let's assume the worst and immediately report any potential ambiguity. - The optimistic ambiguity check takes into account the set of available instance. Depending on the set of instances there may not be any ambiguity after all. Both strategies are backed up by theoretical results. See the Coherence Theorems in Mark's thesis and "A Theory of Overloading" (I'm happy to provide more concrete pointers if necessary). Martin Tom Schrijvers wrote:
Hi Tom,
It seems we are thinking of different things. I was referring to the characterization of a type of the form P => t as being "ambiguous" if there is a type variable in P that is not determined by the variables in t; this condition is used in Haskell to establish coherence (i.e., to show that a program has a well-defined semantics).
[...]
Technically, one could ignore the ambiguous type signature for bar, because the *principal* type of bar (as opposed to the *declared type*) is not ambiguous. However, in practice, there is little reason to allow the definition of a function with an ambiguous type because such functions cannot be used in practice: the ambiguity that is introduced in the type of bar will propagate to any other function that calls it, either directly or indirectly. For this reason, it makes sense to report the ambiguity at the point where bar is defined, instead of deferring that error to places where it is used, like the definition of bar'. (The latter is what I mean by "delayed" ambiguity checking.)
Thanks for explaining the ambiguity issue, Mark. I wasn't thinking about that. We have thought about ambiguity. See Section 7.3 in our paper
http://www.cs.kuleuven.be/~toms/Research/papers/draft_type_functions_2008.pd...
Note that neither Definition 3 nor Definition 4 demands that all unification variables are substituted with ground types during type checking. So we do allow for a form of ambiguity: when any type is valid (this has no impact on the semantics). Consider the initial program
type family F a
foo :: F a -> F a foo = id
You propose to reject function Foo because it cannot be used unambiguously. We propose to accept foo, because the program could be extended with
type instance F x = Int
and, for instance, this would be valid:
foo2 :: F Char -> F Bool foo2 = foo
If you look at the level of the equality constraints:
(F Char -> F Bool) ~ (F alpha -> F alpha)
we normalise first wrt the instance F x = Int, and get
(Int -> Int) ~ (Int -> Int)
which is trivially true. In this process we do not substitute alpha. So alpha is ambiguous, but any solution will do and not have an impact on program execution. GHC already did this before type functions, for this kind of ambiguity, it substitutes alpha for an arbitrary type. That's not unreasonable, is it?
Cheers,
Tom
-- Tom Schrijvers
Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium
tel: +32 16 327544 e-mail: tom.schrijvers@cs.kuleuven.be url: http://www.cs.kuleuven.be/~toms/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe