[bitc-dev] Are type classes just abstract, generic classes?

[Bruno Oliveira]

Regarding the issue of constraint simplification, I'll copy here what  
I wrote at Lambda the Ultimate:

http://lambda-the-ultimate.org/node/3837#comment-58139

Neither the system proposed in this paper (In reference to: "Objects  
to unify Type Classes and GADTs) nor Scala implicits (credits due to  
Martin Odersky, not me :)) do constraint simplification. This also  
means that we do not lose any late binding ability.

In Scala it doesn't even make sense to talk about constraints, because  
there is no actual notion of a constraints (only implicit parameters).  
This is also true to an extent in our system, because we really  
interpret constraints as implicit parameters. This is related to the  
semantics of constraints: set semantics for Haskell; tuple semantics  
for our system.

The issue that you mention has been debated in essentially all the  
proposals extending or inspired by type classes. Namely "Named  
instances for haskell type classes", "Making implicit parameters  
explicit" and our paper. You can find a summary in Section 5, under  
the paragraph "Named Instances and Explicit Implicit Parameters".

The paper "Named instances for haskell type classes" may be  
interesting to look at if you'd like to see a system where you can  
still perform constraint simplification and yet support explicitly  
passed instances. Of course you cannot get both at the same time :).



Also, I noticed that apparently performance is a big issue, so if you  
are really concerned about this, why not something like Sandro has  
proposed:

specialized class Eq 'a where
  eq :: 'a -> 'a -> bool

specialized notEquals :: Eq 'a => 'a -> 'a -> bool

The specialised keyword would impose certain restrictions (perhaps no  
explicit parametrization is allowed being one of them) to ensure that  
for this particular class no abstraction penalty is paid, or to ensure  
that a particular function is always specialized.

Scala has a related mechanism for user-specified specialisation. See:

Compiling Generics Through User-Directed Type Specialization
by Iulian Dragos and Martin Odersky, EPFL,
Fourth ECOOP Workshop on Implementation, Compilation, Optimization of  
Object-Oriented Languages, Programs and Systems (ICOOOLPS'2009),  
Genova, Italy - 6th July 2009

Bruno

On 26 Mar 2010, at 15:33, Jonathan S. Shapiro wrote:

> In earlier email, I toyed with the idea of type class inheritance  
> and allowing (that is: not rejecting) fields in type class  
> definitions. Sandro and Michal argued that this somehow violates  
> what an interface/class is supposed to be about. In reviewing the  
> paper draft that Bruno is submitting tomorrow, an interesting case  
> emerged that may provide a counter-example.
>
> Because constraints are types in Scala, any function of the form
>
>   Constraint 'a => 'a -> bool
>
> can be rewritten as a function taking an additional argument:
>
>   Constraint 'a -> 'a -> bool
>
> Bruno proposes to add a keyword "implicit" to Scala, with the intent  
> that a parameter marked "implicit" is optional. If omitted, the  
> required value will be taken from the unique, global, implicit value  
> of that type. This is somewhat like default parameters, but is  
> really intended to provide "fill in the blank" behavior for type  
> classes. It lets him write a single procedure:
>
>   sortList : implicit Ord 'a -> ['a] -> ['a]
>
> where the user can explicitly provide an ordering rule or (by  
> omission) use the default ordering rule for the type. So far so good.
>
> But note that Ord 'a is in turn constrained by Eq 'a. So if we start  
> with the original, unsimplified type of sortList:
>
>   sort: Eq 'a, Ord 'a => ['a] -> ['a]
>
> and move the Ord constraint to argument position as an implicit  
> parameter:
>
>   sort Eq 'a => implicit Ord 'a -> ['a] -> ['a]
>
> we have not automatically discharged the Eq 'a constraint, and we  
> cannot erase it! We know that *some* definition for Eq 'a was  
> required in order for Ord 'a to be instantiated, but if some variant  
> Ord 'a is provided as an argument we don't know which variant of Eq  
> 'a was used in that definition of Ord 'a. This leads to the  
> potentially awkward outcome that the ord.<= operation may use a  
> different criteria for equality than the == operation used in the  
> implementation of sort. Worse, there is no way for the sort  
> implementation to know that it is using the *same* sense of  
> equality. If we move the Eq 'a constraint:
>
>   sort: implicit Eq 'a -> implicit Ord 'a -> ['a] -> ['a]
>
> then the caller is free to provide unrelated definitions of Eq 'a  
> and Ord 'a.
>
> Note further that moving the Eq 'a constraint to the instance/object  
> definition doesn't really help any.
>
> In the Scala scheme, the Ord constraint type class could be written  
> in two ways (in quasi-Haskell, since I don't know Scala):
>
>   Eq 'a => class Ord 'a where ...
>   class Ord 'a (eq :: Eq 'a) where ...
>
> the first says that in order to instantiate Ord 'a we must show some  
> satisfaction for Eq 'a. The second says that we must provide a  
> *specific* satisfaction of Eq 'a at the instance object definition  
> as an argument to the constructor for Ord 'a. That is: Ord 'a has a  
> *field* that provides a dictionary pointer.
>
> Why a public field? Why not just a field that becomes part of the  
> internal (existential) type? Because there are situations where the  
> user of a particular Ord 'a needs to know that they are using the  
> same definition of equality that was used by that particular  
> instantiation of Ord 'a...
>
> My first thoughts here are (a) this seems to have great power, but  
> also great potential for confusion, but (b) without the ability to  
> require this field at the type class definition, we have no way to  
> state the requirement that each instantiation must expose the  
> instantiation of Eq 'a that was used for that instance of Ord 'a.
>
> And just for completeness, note that inheritance would not simplify  
> matters here.
>
> I just sent a note off to Bruno about this. I suppose my summary  
> comment for the moment is that this stuff is damned subtle, and  
> adding the flexibility of explicitly named dictionaries/constraints  
> seems to impede the compiler's ability to inline fundamental type  
> classes.
>
>
> Jonathan
> _______________________________________________
> bitc-dev mailing list
> bitc-dev at coyotos.org
> http://www.coyotos.org/mailman/listinfo/bitc-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20100326/6b16b962/attachment.html