John Cowan on Multiple Inheritance for Julia

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

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.