Subject: Re> Multiple Inheritance

From: [email-masked] (Jeff Prothero)
Date: Mon, 29 Mar 1993 08:13:28 -0800

Kudos on a good post.  In particular the references and pointing out
how shaky is the theoretical ground on which multiple (or even single)
inheritence rests.  I feel this tend to be under-appreciated...

After sleeping on it, however, I think that coldmud's solution may
be more clever than it is wise.

| The two strategies I've seen proposed for dealing with method searches
| (and presumably variable searches) are:
| 
|         * A depth-first search on the parents graph
|         * Disallowing conflicting verb definitions
| 
| The first strategy, without any restrictions, leads to a number of
| problems.  Suppose I have the digraph (on all of my diagrams, all
| edges are directed upwards):
| 
|         Root object
|           /     \
|         a         b
|           \     /
|              c
| 
| If b and the root object both define a verb, then presumably we'd
                                                    ----------
| rather use b's override than the root object's definition; but a
| depth-first search on the parents tree finds the root object's
| definition first.

The entire argument in your post depends on this presumption, which
appears based entirely on an appeal to intuition:

| This enumeration is, in my opinion, the most intuitive.

(At least, I find no further elaboration of the "number of problems"
depth-first search is said to lead to...?)

Intuition, alas, while indispensable, is a weak reed to lean solely
on.  We could, for example, make an arguably equally plausible appeal
to intuition on the grounds that the verb definition in 'Root' is
"presumably" (*grin*) more general than that in 'b', which is likely
specialized to 'b's peculiar properties, and that 'c', by inheriting a
much more general environment by mixing 'a' and 'b', might well in
fact be much better off with a general verb definition than one
perhaps too specialized to function in 'c'.

By and large, it is nice to use intuition to discover ideas, but
analysis to validate them.  What fundamental criteria can we use to
decide what a 'good' multiple inheritance semantics might be?

One rather fundemantal concern of object-oriented design is that of
encapsulation: packaging some code plus data into a class which then
hides the implementation details while exporting an interface to the
rest of the programming system, making it both easier to change the
internals of a class without breaking code throughout the system, and
also exporting an abstraction which we hope is simpler to program with
than the full internal mechanism of the class.

Keeping this in mind, it is reasonably clear that, everything else
being equal, we would like a multiple inheritance mechanism which
allows the user of a class to make use of that class knowing only the
exported interface of that class: when choosing to inherit behavior
from a class, we would prefer not to have to refer to the internal
implementation detail of that class in order to understand the
resulting behavior of the system.

Depthfirst search will achieve precisely this, if we presume parents
are searched in the order specified by the user: the user can know,
without rooting through internals, that if a verb is exported by two
of the parent classes selected, the first listed parent exporting it
will be the one selected.  Further, the behavior of the multiply
parented object ('c' in the example) will not change as long as the
exported behavior of 'a' and 'b' does not change, which simplifies the
semantics of the system both for the user of the class, and for the
maintainer of the class.

Under the coldmud mechanism described, by contrast, someone
constructing a new class cannot predict what 'c' will do based only on
a knowledge of the exported behavior of 'a' and 'b': is is necessary
to poke through the internals of classes 'a' and 'b' to see exactly
how they implement their behavior, specifically from who they inherit
it, if they do, and via how many links.  Since implementation
internals are exported to all users of a class in the coldmud scheme,
much of the benefit of encapsulation is lost.  For example, a
maintainer can no longer assume that it it safe to insert a new
superclass in a given hierarchy (in order perhaps to share some code
with a newly created class -- a common sort of maintainance
programming in an oo system) merely if all pre-existing classes export
the same behavior after the change: the maintainer must verify that
the change in treedepth of each moved method does not break the
behavior of any _user_ of any of the classes by implicitly switching
it to another method.

Having to roam the entire system examining all the users of a class in
order to make a simple change in the internals of a class is precisely
the sort of task which oo encapsulation is intended to avoid.

While "closest-first" inheritance might seem superficially more
intuitive glancing at an inheritance graph, it seems likely that the
resulting behavior of the system will be much harder to understand
intuitively than that of depth-first inheritance.

(Changing updating the parent pointers in an object from an O(1)
operation to, worstcase, an O(N) operation in the size of the db, as
the coldmud approach appears to do, seems also unappealing, especially
in a diskbased system.)

Occam may be old, but his Razor remains sharp: first-fit serenely
keeps outperforming best-fit, intuition or no intuition.  *grin*.

Jeff/CrT