[bitc-dev] FWD: Re: FWD: Resolving type class instances

[wren ng thornton]

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:

     http://hackage.haskell.org/trac/ghc/wiki/MailingListsAndIRC

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
>>> named
>>> instances is that one loses subsumption, and I'm still working through
>>> the
>>> 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 
somewhere else.


>> 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.

-- 
Live well,
~wren