[bitc-dev] Why Type Classes?

[Jonathan S. Shapiro]

Recently rys asked over on the Lambda The Ultimate blog:

I understand objects and v-tables, which sound like C++, but I don't
understand typeclasses and polyinstantiation, which sound like the sort of
algebraic approach to languages I always ignore. Are they as abstract as
they sound? Or are details as concrete as v-tables? Can typeclasses be made
a space efficient as v-tables?

This note is an attempt to answer that question. If you've been tracking the
list, you may find it repetitive.

C++ objects end up tying three things together inseparably:

   1. Data structure layout. Derived classes necessarily inherit the members
   of their parents
   2. Interfaces. The virtual function mechanism is basically the only way
   to state a common interface in C++.
   3. Subtyping.

The first two ideas are important. The last may or may not be. The key point
is that there is no reason to tie interfaces and structure extension
together. A common interface means, simply, that two objects implement the
same protocol. It does not require v-tables at all.

The Java "Interface" notion is often closer to what you want. It states a
collection of methods, and *any* object that implements all of those methods
can be referenced via that interface. This is exactly what type classes do.

While type classes are most commonly implemented using "dictionaries", which
are similar to v-tables, the details of assembling dictionaries are a good
bit more complex than the details for v-tables. Where v-tables only need to
consider a single object, dictionaries sometimes need to consider
interactions between multiple types, and this can create a requirement to
fabricate dictionaries dynamically (something that BitC wanted to avoid).
What we have chosen to do in BitC instead is to move all of the resolution
of dictionaries into the polyinstantiator, which basically acts like
template instantiation in C++.

But in contrast to template instantiation, we know quite a lot about the
types being instantiated, and there are a number of ways to avoid doing
stupidly redundant instantiations.

Either the dictionary approach or the instantiation approach is correct, and
either can implement the BitC semantics. At most, BitC will require that an
implementation must specify which technique it uses. The issue is that in
some applications, dynamic allocation of dictionaries would introduce a
requirement for garbage collection that we wish very much to avoid.

BitC "objects" are doing something completely different from C++ objects,
which is why we will probably rename them "capsules". Capsules exist to do
type hiding, and that is about it.

I'm not sure if this response adds to or reduces rys' confusion. Hopefully
he'll come out of lurker mode and tell us.


shap
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20081113/8198db78/attachment.html