Modeling multiple inheritance

[oleg at pobox.com]

Brandon Michael Moore wrote regarding the first solution: chain of
super-classes:

> I'm worried about large class hierarchies. If it works on the
> java.* classes I should be fine. Have you used this approach before? I'm
> worried about compile time, runtime costs from the casts (hopefully they
> compile out), and maybe exceeding maximum stack depth in context
> reduction.

I didn't use the approach for anything as complex as all java.*
classes. The only run-time costs are evaluating the chain of fst . snd
. fst . .... The length and the composition of the chain is statically
known. Perhaps the compiler can do something smart here. The maximum
length of the chain is the maximum depth of the inheritance tree. It
shouldn't be too big. A cast from a subclass to a superclass has to be
executed anyway (if not by your code then by JVM). If the maximum
stack depth is exceeded, we can repeat the compilation with a compiler
flag to allocate a bigger stack. In my experience the only time I've
seen the derivation stack depth exceeded is when the derivation truly
diverges.

> What type heap? It sounds like you are talking about information from an
> OO runtime, or are you talking about the collection of instances.

The other solution I talked so confusingly before is that of generic
functions. For that, we need a way to obtain a value representation of a
type. Several such representations exists: e.g., Typable,
representation as an integer, etc. All our objects must be members of
the class Typable. A method (generic function foo) would have the
following signature:
	foo:: (Typable object) => object -> Int ->Int

For example, if foo is defined for ClassA object only, we can write

	foo obj arg = 
	    if inherit_from (typeof obj) (typeof (undefined::ClassA))
	    then particular_instance_foo (coerce obj) arg
	    else error "miscast"

If bar is defined for classB and redefined in classC, we can write

	bar obj arg = 
	    if inherit_from (typeof obj) (typeof (undefined::ClassC))
	    then particular_instance1_bar (coerce obj) arg
	    else if inherit_from (typeof obj) (typeof (undefined::ClassB))
	    then particular_instance2_bar (coerce obj) arg
	    else error "miscast"
			
The functions inherit_from and coerce avail themselves of a table that
records the relationship between types using their value
representations.

The disadvantage of this approach is that the cast errors become
run-time errors. OTH, because type representations and the whole
inheritance graph are values, we can do much more. We can check for
proper and improper diamond inheritance, we can do a rather
sophisticated dispatch.

Types heap and several ways of doing safe casts are discussed in

http://www.haskell.org/pipermail/haskell/2003-August/012372.html
http://www.haskell.org/pipermail/haskell/2003-August/012355.html

See also:
	http://citeseer.nj.nec.com/cheney02lightweight.html
	http://citeseer.nj.nec.com/context/1670116/0
	The Sketch of a Polymorphic Symphony
	http://homepages.cwi.nl/~ralf/polymorphic-symphony/