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.pdf
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: [EMAIL PROTECTED]
url: http://www.cs.kuleuven.be/~toms/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
