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/