Modeling multiple inheritance

[Brandon Michael Moore]

On Thu, 25 Sep 2003 oleg at pobox.com wrote:
>
> Brandon Michael Moore wrote:
>
> > So I defined a class to model the inheritance relationships
>
> > class SubType super sub | sub -> super where
> >   upCast :: sub -> super
>
> > Now I can define a default instance of HasFooMethod:
> > instance (HasFooMethod super args result,
> >           SubClass super sub) =>
> >          HasFooMethod sub args result where
> >   foo sub args = foo (upCast sub) args
>
> > This will propagate foo methods down the inheritance hierarcy. If a new
> > class C is derived from A, I just need to say
>
> > One problem is that the subclass relationship needs the functional
> > dependency
>
> > Does anyone know of clever solutions that would model multiple inheritance
> > while preserving the functional dependencies (unsafe compiler flags are
> > fine too), or ways to reduce the pain of overloading resolution without
> > the functional dependency?
>
> Yes. The code included. The solution is trivial: in case of a multiple
> inheritance, a class has a _sequence_ of superclasses rather than a
> single superclass. Like
>
> instance SubClass (Object,()) ClassA
> instance SubClass (Object,()) ClassB
>
> -- Multiple inheritance (including the diamond!)
> instance SubClass (ClassA,(ClassB,())) ClassC
> instance SubClass (ClassA,(ClassB,(ClassC,()))) ClassD
>
> And we need some intelligence to traverse the sequence. But even a
> computer can do that.

That should solve my problem. Putting all the superclasses in a tuple
should work. 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. This is a clever solution. I like it. Now, is anyone up to
encoding the Dylan MRO in Haskell type classes? ;)

> 	I would like to propose a different solution: a dual of
> typeclasses in the value domain. Function foo is just a regular
> function
>
> foo:: Object -> Int -> Int
> foo x y = y
>
> We then need a class MApplicable fn args result with a method
> mapply. The trick is that the method should take any object of a type
> castable and cast it to the type of the first argument of fn. The cast
> can be made safe and statically checkable, using the type
> heap. Actually, we can use the type heap to model the dispatch table
> (whose rows are functions and columns are object/classes). Given a
> function and an object, we can search in many way for the applicable
> combination.

What type heap? It sounds like you are talking about information from an
OO runtime, or are you talking about the collection of instances. I tried
a system where method names were also represented by data types, but
without your solution for multiple inheritance I couldn't get the
implementation inheritance I wanted. How would you implement this dispatch
table? What are the advantages of this approach over the type class
encoding? I'm worried that generating bindings would be a problem if the
dispatch table needs to be a monolithic value with a very interesting type
in some file.

Brandon

> And now, the code for the solution that works.
> Compiler flags:
> -fglasgow-exts -fallow-overlapping-instances -fallow-undecidable-instances
>
> data Object = Object
> data ClassA = ClassA
> data ClassB = ClassB
> data ClassC = ClassC
> data ClassD = ClassD
>
> class SubClass super sub | sub -> super where
>   upCast :: sub -> super
>
> instance SubClass (Object,()) ClassA
> instance SubClass (Object,()) ClassB
> -- Multiple inheritance (including the diamond!)
> instance SubClass (ClassA,(ClassB,())) ClassC
> instance SubClass (ClassA,(ClassB,(ClassC,()))) ClassD
>
> class HasFooMethod cls args result where
>   foo ::  cls -> args -> result
>
> instance (SubClass supers sub,
>           HasFooMethod supers args result)
>          => HasFooMethod sub args result where
>   foo obj args = foo (upCast obj) args
>
> instance (HasFooMethod cls args result) => HasFooMethod (cls,()) args result
>   where
>     foo (x,()) = foo x
>
> instance (HasFooMethod cls args result) => HasFooMethod (x,cls) args result
>   where
>     foo (x,y) = foo y
>
> instance HasFooMethod Object Int Int where
>   foo _ x = x
>
> test1::Int = foo Object (1::Int)
> test2::Int = foo ClassA (2::Int)
> test3::Int = foo ClassD (3::Int)
>
> -- Likewise for another method:
>
> class HasBarMethod cls args result where
>   bar ::  cls -> args -> result
>
> instance (SubClass supers sub,
>           HasBarMethod supers args result)
>          => HasBarMethod sub args result where
>   bar obj args = bar (upCast obj) args
>
> instance (HasBarMethod cls args result) => HasBarMethod (cls,()) args result
>   where
>     bar (x,()) = bar x
>
> instance (HasBarMethod cls args result) => HasBarMethod (x,cls) args result
>   where
>     bar (x,y) = bar y
>
> instance HasBarMethod ClassB Bool Bool where
>   bar _ x = x
>
> test4::Bool = bar ClassB True
> test5::Bool = bar ClassC True
> test6::Bool = bar ClassD True
>
>