John Cowan on Multiple Inheritance for Julia

[Jeffrey Sarnoff]

> My recollection is that you knew how to expand the

> existing machinery or modify the algorithmic approach of Julia's support

> for single inheritance of abstract types for multiple inheritance.

John Cowan:

The expensive bit is type testing, but my proposal (partly due to Alex

Shinn, who uses a version of it in Chibi Scheme) is to allocate a array

of C-level pointers in each type that point to *all* its supertypes,

including itself.  Then to ask "Does object o belong to type T?" we

search the elements of the supertype array in o's type object and see

if any of them are T.  If yes, o belongs to T, otherwise not.

So to take the classic silly example, if Woody is an object of type

CowboyToy, which inherits from the abstract types Cowboy (which inherits

from Person) and Toy, and we want to see if Woody belongs to type BadGuy,

we check the 4-word supertype array in CowboyToy, namely [CowboyToy,

Cowboy, Person, Shape], to see if BadGuy is there.  It isn't, so we

return false.  This is both reasonably fast and reasonably space-cheap.

We can do better than linear search if we allocate a little more space.

In particular, if both o's type and T are known to have only a single

path to the root (which is statically determinable and can be stored

in the type objects), then we can look at just the k'th element of o's

supertype array, where k is the lattice depth of T (also statically

determined and stored in T) to see if it is T.  This is what Chibi does.