Prev: There is some way to stop the "M15" spam?
Next: Pattern for multiple States
From: kj on 4 Jan 2008 13:15


Several times I have come across mentions of the dreaded "diamond
pattern" that can occur with multiple inheritance. I typically
avoid multiple inheritance anyway, so I have not paid too much
attention to the "dreaded diamond" problem, but in a recent design
task the DD has emerged so naturally that I'm amazed I never faced
it before.

Suppose, for example, that I have a class Node representing a simple
tree node, and class Root represents the special case of Node, i.e.
the (unique) root of such a tree. That's straightforward enough.

But now, suppose one wants to "customize" these two classes to
produce a "parallel hierarchy" consisting of classes MyNode and
MyRoot. Inheritance seems like a natural way to do this. MyNode
will be a subclass of Node, no problem... But what about MyRoot?
In the general case it will *have* to inherit both from Root (to
get all the root-specific methods) and from MyNode (to get all the
customizations of Node implemented by MyNode). Boom! Right there
we have the diamond pattern. And yet, the design process leading
to it seems so reasonable and wholesome!

What's a programmer to do?

When I Google for this topic I am flooded with pages devoted to
railing against the evils of multiple inheritance and/or in defense
of languages that do not support it.

But I don't need to be convinced that multiple inheritance is
problematic. What I need is good, practical, specific advice on
how a designer can avoid such a natural pattern.

If someone could point me to such material I'd greatly appreciate
it.

One more specific question: suppose that one's programming language
allows one to specify an order of precedence for the co-parents of
a class whenever more than one parent provides a method of the same
name (I would imagine that any language that supports MI would
offer this functionality, but I don't know). In this case, and
returning to the two co-parents of MyRoot in the example above, I
would give MyNode precedence over Root, so that MyRoot would inherit
the node API from MyNode, and only those root-specific methods from
Root. This looks like it should work. Are there subtle problems
lurking in this solution?

TIA!

kj

--
NOTE: In my address everything before the first period is backwards;
and the last period, and everything after it, should be discarded.
From: Martin Vuille on 4 Jan 2008 13:48
kj <socyl(a)987jk.com.invalid> wrote in
news:fllt4v$its$1(a)reader2.panix.com:

> One more specific question: suppose that one's programming
> language allows one to specify an order of precedence for the
> co-parents of a class whenever more than one parent provides
> a method of the same name (I would imagine that any language
> that supports MI would offer this functionality, but I don't
> know). In this case, and returning to the two co-parents of
> MyRoot in the example above, I would give MyNode precedence
> over Root, so that MyRoot would inherit the node API from
> MyNode, and only those root-specific methods from Root. This
> looks like it should work. Are there subtle problems lurking
> in this solution?

There is another issue besides resolving ambiguities between same-
named methods inherited from several parents: the possibility of
having multiple copies of any data contained in the repeated base
class(es).

In your example, let's say that Node has some data members. Then
Root contains a Node with those data members and so does MyNode.
Unless you do what is required by the language (e.g., use virtual
inheritance in C++), MyRoot will contain two Nodes, one by virtue
of containing a Root, and one by virtue of containing a MyNode.

When a MyRoot method is called that ultimately causes the data in
MyRoot's Root's Node to be updated, that change will not be
reflected in MyRoot's MyNode's Node. That may or may not be what
you want.

MV

--
I do not want replies; please follow-up to the group.
From: Daniel T. on 4 Jan 2008 14:27
kj <socyl(a)987jk.com.invalid> wrote:

> Several times I have come across mentions of the dreaded "diamond
> pattern" that can occur with multiple inheritance. I typically
> avoid multiple inheritance anyway, so I have not paid too much
> attention to the "dreaded diamond" problem, but in a recent design
> task the DD has emerged so naturally that I'm amazed I never faced
> it before.
>
> Suppose, for example, that I have a class Node representing a simple
> tree node, and class Root represents the special case of Node, i.e.
> the (unique) root of such a tree. That's straightforward enough.

Not really. What is a Node that is not a Root called? "It's called a
Node" isn't an acceptable answer because Roots are also called Node, but
they are non-Root Nodes.

> But now, suppose one wants to "customize" these two classes to
> produce a "parallel hierarchy" consisting of classes MyNode and
> MyRoot. Inheritance seems like a natural way to do this. MyNode
> will be a subclass of Node, no problem... But what about MyRoot?
> In the general case it will *have* to inherit both from Root (to
> get all the root-specific methods) and from MyNode (to get all the
> customizations of Node implemented by MyNode). Boom! Right there
> we have the diamond pattern. And yet, the design process leading
> to it seems so reasonable and wholesome!
>
> What's a programmer to do?
>
> When I Google for this topic I am flooded with pages devoted to
> railing against the evils of multiple inheritance and/or in defense
> of languages that do not support it.

Multiple inheritance of fields is problematic.

> But I don't need to be convinced that multiple inheritance is
> problematic. What I need is good, practical, specific advice on
> how a designer can avoid such a natural pattern.

Don't put member-data/fields in classes that are designed to be
inherited from and the pattern can be avoided easily.

> If someone could point me to such material I'd greatly appreciate
> it.

Look up he evils of implementation inheritance.

> One more specific question: suppose that one's programming language
> allows one to specify an order of precedence for the co-parents of
> a class whenever more than one parent provides a method of the same
> name (I would imagine that any language that supports MI would
> offer this functionality, but I don't know).

Python does, C++ requires/allows the new class to specify which
implementation to use on a method-by-method basis.

> In this case, and
> returning to the two co-parents of MyRoot in the example above, I
> would give MyNode precedence over Root, so that MyRoot would inherit
> the node API from MyNode, and only those root-specific methods from
> Root. This looks like it should work. Are there subtle problems
> lurking in this solution?

The problem with the above is that your MyRoot class will actually
contain two sets of data from Node. When the object is used as a Root,
any methods not specialized by MyRoot will use one set of Node data, and
when it is used as a MyNode, it will use a different set of data. In
essence, the diamond isn't really a diamond, but a U-shape:

[Node] [Node]
A A
| |
[MyNode] [Root]
A A
| |
+----+----+
|
[MyRoot]


C++ has a special construct called virtual inheritance to avoid the
above problem, but all classes in the chain have to know about it and
objects have to follow special construction rules.
From: Dmitry A. Kazakov on 4 Jan 2008 15:13
On Fri, 4 Jan 2008 18:15:59 +0000 (UTC), kj wrote:

> Suppose, for example, that I have a class Node representing a simple
> tree node, and class Root represents the special case of Node, i.e.
> the (unique) root of such a tree. That's straightforward enough.
>
> But now, suppose one wants to "customize" these two classes to
> produce a "parallel hierarchy" consisting of classes MyNode and
> MyRoot. Inheritance seems like a natural way to do this. MyNode
> will be a subclass of Node, no problem... But what about MyRoot?
> In the general case it will *have* to inherit both from Root (to
> get all the root-specific methods) and from MyNode (to get all the
> customizations of Node implemented by MyNode). Boom! Right there
> we have the diamond pattern. And yet, the design process leading
> to it seems so reasonable and wholesome!

What you have here is not diamond. Actually you want supertyping, i.e.
injecting a common parent My_Stuff in front of Root and Node. There is
little support for that in contemporary OOPLs. What you can try is mix-in
inheritance or generics in order to emulate this. Parallel types hierarchy
could also do the trick, but it is even less supported. Sometimes I use
storage pools for dealing parallel hierarchies, it works nice for things
like linked lists and trees.

> When I Google for this topic I am flooded with pages devoted to
> railing against the evils of multiple inheritance and/or in defense
> of languages that do not support it.

OK, what is customarily written about MI is mostly rubbish. Issues like
name conflicts exists with and without MI. The ways they are resolved are
standard. Same can be said about semantic differences between aliasing
(virtual base in MI) and overloading (non-virtual base in MI). It is also
well known outside MI as identity (reference) vs. value semantics. Nothing
special.

> But I don't need to be convinced that multiple inheritance is
> problematic.

It is not.

> One more specific question: suppose that one's programming language
> allows one to specify an order of precedence for the co-parents of
> a class whenever more than one parent provides a method of the same
> name (I would imagine that any language that supports MI would
> offer this functionality, but I don't know).

There is IMO a much simpler way to handle conflicts. When the compiler
detects a conflict, it should make the conflicting thing abstract. That
will force the programmer to explicitly override it (if the result type is
itself non-abstract). By overriding he will tell to whom that thing should
be delegated. It is simpler and more flexible than virtual vs. not bases in
C++. Note that components shall be considered as methods (a getter-setter
pair), so it should work for them too.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
From: H. S. Lahman on 4 Jan 2008 18:07
Responding to Kj...

> Several times I have come across mentions of the dreaded "diamond
> pattern" that can occur with multiple inheritance. I typically
> avoid multiple inheritance anyway, so I have not paid too much
> attention to the "dreaded diamond" problem, but in a recent design
> task the DD has emerged so naturally that I'm amazed I never faced
> it before.

In OOA/D class systems are about member identity and set membership. To
avoid ambiguity in set membership there are two important rules that
must be followed in OO generalizations:

(1) The members of sibling subclasses must be disjoint subsets of the
<common> parent superset.

(2) The union of all sibling subsets' members must be a complete set of
the parent superset.

So when one has:

[A]
A
|
+------+-------+
| |
[B] [C]
A A
| |
+------+-------+
|
[D]

one has a problem when one tries to map [D]'s members unambiguously into
the [B] or [C] sets. That is, the disjoint property for [B]/[C] is
indeterminate in [D].

The ambiguity becomes apparent when one tries to identify the properties
that define set membership. [D] necessarily has all of [A]'s properties
since [B] and [C] both inherit those. But since [D] inherits from both
[B] and [C], [D] also has /all/ of the specializations of both [B] and
[C]. But the [B] and [C] set membership is defined by the unique
properties each set provides that are not provided to members of the
other subset. Since all members of [D] are also members of [A], that
presents a conundrum because one cannot subdivide them, as As, into [B]
and [C] sets based on different specialized properties.

As a more specific example consider the following:

[Account]
A
| R1
+----------+----------+
| |
[Checking] [InterestBearing]
A A
| R2 | R3
+-----+--------+ +------------+------+
| | | |
[Regular] [InterestChecking] [Savings]

The [InterestChecking] class is a no-no because of the necessary
disjoint constraint on R1; an Account can be a Checking Account or an
Interest Bearing Account, but not both. That rule is violated when the
Checking and InterestBearing subclasses are composed into
InterestChecking via the subsequebt R2 and R3 generalizations. For any
member of [InterestChecking] it is impossible to allocate it to just one
of the subclasses in the R1 generalization.

[BTW, one problem you may be having is in thinking of multi-level
inheritance trees as monolithic. They are actually composed of multiple
simple superclass/subclass generalizations that are standalone in the
problem space. Thus R1, R2, and R3 are separate generalizations in the
example above. The problem with the diamond is that the individual
generalizations are not combined properly. The rules above are necessary
to ensure that when individual generalizations are combined one does not
shoot oneself in the foot. IOW, if the rules above are consistently
applied throughout the tree, one should not have any ambiguity in
determining what specific properties a leaf subclass member has or which
properties will be accessed via polymorphic dispatch through a parent
superclass.]

So...

>
> Suppose, for example, that I have a class Node representing a simple
> tree node, and class Root represents the special case of Node, i.e.
> the (unique) root of such a tree. That's straightforward enough.
>
> But now, suppose one wants to "customize" these two classes to
> produce a "parallel hierarchy" consisting of classes MyNode and
> MyRoot. Inheritance seems like a natural way to do this. MyNode
> will be a subclass of Node, no problem... But what about MyRoot?
> In the general case it will *have* to inherit both from Root (to
> get all the root-specific methods) and from MyNode (to get all the
> customizations of Node implemented by MyNode). Boom! Right there
> we have the diamond pattern. And yet, the design process leading
> to it seems so reasonable and wholesome!
>
> What's a programmer to do?

Not this. B-)

Alas, without specific properties that distinguish subsets, it is
difficult to say how the situation should be modeled. That is, it all
depends on what properties MyNode and MyRoot have that warrant making
them separate sets from Node and Root.

IOW, tell me why you want MyNode and MyRoot in addition to Node and Root
and I can tell you how to model the generalizations.

> When I Google for this topic I am flooded with pages devoted to
> railing against the evils of multiple inheritance and/or in defense
> of languages that do not support it.

Multiple inheritance is not directly a problem here. It is just a
vehicle that enables incorrect composition. That is, the problem is with
abstracting the generalizations from the problem space, not with the
multiple inheritance mechanism for resolving leaf subclass properties.


--
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl(a)pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info(a)pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH
 |  Next  |  Last
Pages: 1 2
Prev: There is some way to stop the "M15" spam?
Next: Pattern for multiple States