[bitc-dev] FWD: Re: FWD: Resolving type class instances
wren ng thornton
wren at freegeek.org
Thu Aug 5 11:54:07 PDT 2010
Jonathan S. Shapiro wrote:
> On Mon, Aug 2, 2010 at 11:19 PM, wren ng thornton <wren at freegeek.org> wrote:
>> I'm not sure I see what you're saying. Haskell assumes the linker is
>> smart enough to chase imports and determine when something is the same
>> entity imported through multiple routes (and therefore isn't an
>> identifier clash). Presumably this is implemented as you suggest.
> Interesting. I would not have expected this to be a linker responsibility. I
> would have expected import chasing to be a compiler responsibility and
> duplicate suppression to be a linker responsibility.
Heh, that would make things easier wouldn't it...
I'm familiar with the formal structure of how GHC compiles code and what
the RTS looks like, but I haven't had a chance to get into the guts of
how it handles the non-formal implementation details like linking. For
that, you'd have better luck getting in touch with the GHC devs:
While dynamic linking is a goal they have, it's not forthcoming because
GHC does heavy inlining across module boundaries (which breaks ABI
stability across different versions of a library, and could lead to
segfaults or semantic bugs). They recently added support for dynamically
linking the RTS component, but I don't think they have dynamic linking
for Haskell libraries yet. So, I'd assume almost everything is cached
out before ld.
>>> I think we agree that this is a bad thing. The one problem I see with
>>> instances is that one loses subsumption, and I'm still working through
>>> implications of that.
>> You still have subsumption, it's just no longer decisive. It's a similar
>> situation to when you get collisions in a hash table; you just need a
>> resolution method for when subsumption returns multiple answers.
> I'm not sure this is correct. It's clear enough that you retain
> *type*subsumption, subject to the duplicates problem that you identify
> above. The
> problem I see is that in this case type subsumption is viewed by the
> programmer as a shorthand for semantic subsumption.
This is true. Although, before we had GADTs or type families, there's
little reason to think that structural subsumption is an inadequate
proxy--- because the only structure at the type level is for parametric
polymorphism, and subsumption captures naive subtyping. Once you have
non-parametric indices or real subtyping, then that goes away.
> Consider a perverse example in which I give two instances for Eq a. One
> implements the normal equality/inequality operators. The other reverses
> them. Under these conditions the *meaning* of subsumption has been lost.
I'm not sure we can discuss what that would mean without first settling
other issues about what it means to have named instances. That is, since
this situation is flatly rejected in Haskell, it's not entirely clear to
me that subsumption is where it becomes meaningless, or whether it's
>> The things I've mentioned are some of the reasons why the Haskell Prime
>> committee haven't approved multiparameter typeclasses or fundeps yet as
>> part of official Haskell.
> I'm not aware of any inherent issue in multiparameter type classes, and
> there are truly compelling use cases.
The main problem with MPTCs is that they can introduce excessive
ambiguity, leading to the need for type annotations in order to resolve
types. Moreover, giving the proper annotations can require other
extensions like -XScopedTypeVariables to make type variables bound by a
top-level quantifier available in the body of an expression (instead of
being implicitly quantified in the annotation).
Fundeps were introduced as an alternative mechanism for removing
ambiguity in common use cases for MPTCs. Associated Types can also
capture some of these common use cases. But ultimately, MPTCs requires
some additional mechanism in order to resolve the types enough to locate
an instance. Other than that, MPTCs are perfectly safe so far as I'm aware.
More information about the bitc-dev