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@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
_______________________________________________
bitc-dev mailing list
bitc-dev@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
