Modeling multiple inheritance

[oleg at pobox.com]

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. 

	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.

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