[mercury-users] Document Giving Help with Typeclasses

[Ralph Becket]

I've been bitten quite hard when trying to use typeclasses and it seems
I'm not alone.  Below is a document I've knocked out that describes most
of the problems I've come up against, explains what the problem is and
provides the solution.  Feedback most welcome, esp. error reports.

Cheers,

Ralph



Typeclasses.txt		Ralph Becket <rbeck at microsoft.com>	2 Nov 2000



Understanding how typeclasses, multi-parameter typeclasses, and existential
types work has been an uphill struggle.  It is obvious from the Mercury 
mailing lists that I'm not the only person who's found them tricky.  This
document is intended to convey what I have learned and hopefully will be of
assistance to other people in getting to grips with typeclasses.

Many thanks to Fergus for all his help in leading me to this point.



EXISTENTIAL TYPES

Q. What's the difference between existential types and polymorphic types?

A. A polymorphic type is decided by the caller, so

:- func make_pair(T) = {T, T}.
make_pair(X) = {X, X}.

has to work for *any* type T that is passed to it by the caller.

Sometimes, however, we want things to work the other way around.  Consider

:- type db(DB) ---> db(DB, map(key(DB), record)).
:- type record.
:- type key(DB).

:- some [DB] func new_db = db(DB).
:-           mode new_db = uo is det.

:- pred add_record(record, key(DB), db(DB), db(DB)).
:- mode add_record(in, out, di, uo) is det.

:- pred lookup_record(key(DB), record, db(DB), db(DB)).
:- mode lookup_record(in, out, di, uo) is det.

Here, new_db/0 generates new database objects on demand.  Each database has
its own, unique type.  When we add records to a database, we obtain keys
also tagged with that type.  This means that the compiler can statically
check that we don't use keys from one database to try to access records in
another database.

This only works because new_db/0 decides the DB type tag, not its callers.


Q. "Existential types + typeclasses = object orientation."  What's that all
about, then?

A. Existential types really come into their own when combined with type
classes.  Say I have the following typeclass:

:- typeclass showable(A) where [
	func show(A) = string
].

and some instances:

:- instance showable(int)    where [ show(X) = string__format("%d", [i(X)])
].
:- instance showable(float)  where [ show(X) = string__format("%f", [f(X)])
].
:- instance showable(string) where [ show(X) = X ].
...

Now, say I want a function that will apply the show/1 method to a list of
showable objects:

:- func show_all1(list(T)) = list(string) <= showable(T).
show_all(Xs) = list__map(show, Xs).

Unfortunately, however, this only works for lists of the same type of
showable object.  For example, the following are all fine:

	X = show_all([1, 2, 3]),
	Y = show_all([1.0, 2.0, 3.0]),
	Z = show_all(["one", "two", "three"])

however, we can't do

	W = show_all([1, 2.0, "three"])

because the list argument is not well typed: all objects in a list have to
have the same type.  We can get around this using existentially quantified
types as follows:

:- type some_showable ---> some [T] some_showable(T) => showable(T).

Now we can write

:- func show_showables(list(some_showable)) = list(string).
show_showables(Xs) = list__map(func(some_showable(X)) = show(X), Xs).

and do

	W = show_showables([
		'new some_showable'(1),
		'new some_showable'(2.0),
		'new some_showable'("three")
	])

Note the use of the 'new ' prefix on the constructors: this is to inform the
compiler that you are indeed constructing a value rather than pattern
matching.

More discussion on OO-style programming using existential types and
typeclasses is presented below in the section on container typeclasses.



MULTI-PARAMETER TYPECLASSES

Q. What's wrong with this?

:- typeclass tc1(A) <= tc2(A, B) where [...].

A. The typeclass constraint tc2(A, B) contains a variable (B) not listed in
the typeclass being defined.  The problem is that the type variables are
universally quantified, so this constraint means that anything that is a
tc1(A), must also be a tc2(A, B) for *all* types B.  This is clearly a
mistake since there are an infinite number of types and one can only write
a finite number of instance declarations.


Q. What's wrong with this?

:- typeclass tc3(A, B) where [
	func f(A, B) = B,
	func g(A) = A
].

A. Every func/pred signature in a typeclass definition must mention *all* of
the type variables in the typeclass.  Why?  Consider the following instance
declarations:

:- instance tc3(t1, t2a) where [..., g(X) = foo(X)].
:- instance tc3(t1, t2b) where [..., g(X) = bar(X)].

Now, if Y is an object of type t1 and we try the method call g(Y), the
compiler has no way of deciding which of the two definitions to use.


Q. So what's the solution?

A. You need to split your typeclass up as follows:

:- typeclass tc3(A, B) <= (tc3a(A), tc3b(A, B)) where [].
:- typeclass tc3a(A) where [
	func g(A) = A
].
:- typeclass tc3b(A, B) where [
	func f(A, B) = B
].


Q. I'm trying to define a container typeclass, but nothing seems to work.

A. At the moment, this is not nearly as straightforward as one would like it
to be and, indeed, some things are just not possible using the current
typeclass system.  These problems will disappear once constructor classes
and functional dependencies are added to the language, but until then,
here's the best one can do.


(a) CONTAINER TYPECLASSES USING EXISTENTIAL TYPES

Let's say we want a stack typeclass holding objects implementing the tc4
typeclass (whatever that happens to be).

:- typeclass tc4_stack(S) where [
	func new_stack = S,
	func push(T, S) = S <= tc4(T),
	some [T] pred pop(S::in, T::out, S::out) is det => tc4(T)
].

Now we want to make lists an instance of tc4_stack/1:

:- instance tc4_stack(list(T)) where [
	new_stack = [],
	push(X, S) = [X | S],
	( pop(S0, X, S) :-
		( S0 = [],	throw("attempt to pop empty stack")
		; S0 = [X | S]
		)
	)
].

But this *doesn't work* because the push method takes *any* type
that happens to implement tc4 and a list, not necessarily of that type, and
attempts to cons the first argument on to the list.

Instead we have to use existential types again:

:- type some_tc4 ---> some [T] some_tc4(T) => tc4(T).

And now we try this:

:- instance tc4_stack(list(some_tc4)) where [
	new_stack = [],
	push(X, S) = ['new some_tc4'(X) | S],
	( pop(S0, X, S) :-
		( S0 = [],	throw("attempt to pop empty stack")
		; S0 = [some_tc4(X) | S]
		)
	)
].

Unfortunately, this won't compile because typeclass instances have to be
types of the form `typename(typevar, ...)' (in order to avoid ambiguity
problems) wheras `list(some_tc4)' is of the form `typename(typename)'.

We can't use equivalence types to solve the problem

:- type tc4_list == list(some_tc4).

:- instance tc4_stack(tc4_list) where [...].

because the compiler will expand out tc4_list in the instance declaration
and bring you to book.

Instead another level of wrapping is required:

:- type tc4_list ---> tc4_list(list(some_tc4)).

:- instance tc4_stack(list(some_tc4)) where [
	new_stack = tc4_list([]),
	push(X, tc4_list(S)) = tc4_list(['new some_tc4'(X) | S]),
	( pop(tc4_list(S0), X, tc4_list(S)) :-
		( S0 = [],	throw("attempt to pop empty stack")
		; S0 = [some_tc4(X) | S]
		)
	)
].

As you can see, successful use of typeclasses is more work than you might
imagine.

Q. Is there a performance cost associated with the use of existential types?

A. Although the compiler will not exact a price for the wrapper types
(so called no-tag types) such as tc4_list, there is a penalty to be paid for
using existential types.  Every existentially typed object must also carry
around with it some way of identifying its actual type at runtime.
Moreover, if a typeclass is associated with that object then it must also
carry around a method dispatch table which the compiler cannot get rid of
through static analysis.  The upshot of this is that existential types are
best used when you genuinely need collections of heterogeneously typed
objects.


(b) CONTAINER TYPECLASSES USING MULTI-PARAMETER TYPECLASSES

Let's try the same thing using multi-parameter typeclasses.

:- typeclass tc4_stack(S, T) <= (tc4_stack_a(S), tc4_stack_b(S, T)) where
[].
:- typeclass tc4_stack_a(S) where [
	func new_stack = S
].
:- typeclass tc4_stack_b(S, T) <= tc4(T) where [
	func push(T, S) = S,
	pred pop(S::in, T::out, S::out) is det
].

Once again, we try making the list type an instance of tc4_stack:

:- instance tc4_stack(list(T), T) where [].
...

But this fails because the second parameter is not of the form
`typename(typevar, ...)'.  So we have to wrap up our tc4 objects:

:- type a_tc4(T) ---> a_tc4(T).

:- instance tc4_stack(list(T), a_tc4(T)) where [].
:- instance tc4_stack_a(list(T)) where [
	func new_stack = []
].
:- instance tc4_stack_b(list(T), a_tc4(T)) <= tc4(T) where [
	push(a_tc4(X), S) = [X | S],
	( pop(S0, a_tc4(X), S) :-
		( S0 = [],	throw("attempt to pop empty stack")
		; S0 = [X | S]
		)
	)
].

Success!  But, unfortunately we have to wrap and unwrap every
tc4 argument to push and pop with the a_tc4 constructor.  This doesn't cost
us anything because a_tc4 is a no-tag type, but it is a little clumsy on the
page.


Q. Is there any advantage to using multi-parameter typeclasses rather than
existential types and typeclasses?

A. Where the multi-parameter typeclass approach is applicable, it should be
noticably more efficient.  In particular, a good compiler should be able to
statically work out which method implementations are being called at each
call site, which means that (i) a method dispatch table is not required and
(ii) the compiler can then inline, deforest and generally do good things to
the resulting code.


Q. Will life always be like this?

A. Hopefully not.  Constructor classes and, in particular, functional type
dependencies will be integrated into the typeclass mechanism and do away
with the need for many of the work-arounds outlined in this document.

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------