Diamond Inheritance

NOTE This page has been resurrected from an archive. I still stand by what I wrote, but some details could be explained better, and it does contain the occasional typo and unfinished section. You have been warned.

On Diamond Inheritance

Abstract

„Diamond Inheritance“ is generally considered complicated, even dangerous. In fact it has given rise to some very subtle bugs.
This article argues that this is due to a misinterpretation of what really goes on during multiple interpretation. It offers a perspective from which diamond inheritance is no more complicated than single inheritance.

The Traditional View

Traditionally, inheritance was seen just as a way to reuse code, with the added side benefit that the resulting classes would usually do what was intended, almost „automagically“.
Of course, this didn’t work in all cases. Name clashes when inheriting from multiple sources would have to be resolved in some way. Some languages chose to automatically resolve the clash using some default rule (such as „first inherited, first served“); others provided some way to specify a precedence, some tried to offer all possibilities.
Some critics observed that even single inheritance didn’t always work as expected. Identifying a routine by its name would result in surprising behaviour if the name was taken to be equivalent to its semantics, simply because names can subtly change semantic assumptions in the programmers‘ minds when read in a different context.
An example where the difference is easy to see is if the superclass defines a routine „close“, and subclasses door and electrical_switch simply have different concepts of „closing“ one of their instances.) Such semantic gaps can become arbitrarily small, to the point that it’s very, very difficult to observe or describe the gap; in project meetings, this can quickly lead to accusations of being overly picky with details, which means that participants who observe the differences will learn to keep such observations for themselves. The fiendish trap is that the less conspicuous the difference is, the more difficult will it become to actually find (and correctly diagnose!) the mistake once it has lead to a bug.

Nailing down the semantics

The kind of problem detailed above led to the formulation of Barbara Liskov’s law: „Any subclass should define object that can stand in wherever an object of the superclass is expected by the code.“ This is widely known as the „Liskov Substitution Principle“ (LSP).
This rather informal principle was formalized by Bertrand Meyer, in the form of „Design by Contract“ (DbC). Basically, DbC comprises the following guidelines:

  • Each routine has a set of preconditions and postconditions. These two sets of assertions form a kind of contract: a routine is obliged to establish the postcondition if it is called with its preconditions established. (Some programming languages, especially Bertrand Meyer’s Eiffel, even offer a formal place in the language definition for this, but that’s not strictly necessary to apply DbC.)
  • If a routine is overridden in a subclass, it must establish at least the „contract“ of the routine is replaces. It may not place more restrictions on its caller, so it must not require stricter preconditions than the routine that is replaces; and it must ensure at least as much as the precursor routine so that the caller will still find the results it expects.

Design by Contract (besides having other virtues) is a powerful tool: it’s a kind of Occam’s Razor to judge the relative merits of subclass concepts. Instead of personal value judgements that a particular subclass „shouldn’t do that“, we can nail down precisely in what respects a subclass succeeds or fails to hold up the contracts upheld in its superclass. This kind of precise judgement is even possible for entire classes of subclass constructions, as will be demonstrated in the next sections.

Canonical Example

Let’s assume we have four classes, A, B, C, and C, inheriting from each other in the following way:

      A
     / \
    B   C
     \ /
      D

Let’s further assume that A defines a routine r that is overridden both in B and C, giving the following situation:

 

Class Status of r
A Original definition
B Inherited and overridden; the overriding routine will be called rB to differentiate it from other variants
C Inherited and overridden; the overriding routine will be called rC to differentiate it from other variants
D Inherited from both B and C

The rest of the article explores the possibilities for a proper semantics of r in D.

Complications

Now let’s explore what semantics r might have in D.

Assuming DbC rules, things seem rather simple: it must not have a precondition that’s stronger than those of its predecessors, rB and rC. In other words, it should be the logical or of it’s predecessors‘ preconditoins.
Similarly, the postcondition must be at least as strong as those of its predecessors, so they should be merged using a logical and.

Unfortunately, this doesn’t cover all cases that occur in practice. Sometimes, rB and rC are so different that merging them into a single routine is neither practical nor desirable. In terms of DbC, it may be that the combined postcondition cannot be fulfilled (will always yield false). Or the routines might achieve the same effects, but operate on different data.

From the perspective of „an instance of a subclass is-an instance of the subclass“, this means that any object that is-a D is-also-an A, but in fundamentally different ways.

Coming up with a concrete example of such a situation might seem difficult at first (it certainly was for the author of these lines), but it’s easy to continue the chain once one has seen the first few.

Examples of Replicated Interface Inheritance

Let’s reconstruct the basic interface of arithmetic, from the grounds up. In the name of simplicity, we restrict ourselves to two operations, addition and multiplication.

Here’s some peudocode for a base class, Monoid. (In mathematics, monoids are things that have an operator, traditionally named o („circle“, „oh“), a set of values to apply the operator to, and a „neutral element“. The full definition is a bit more verbose and precise, but that’s the gist of it.)

An abstract class that defines monoids would look like this (in pseudocode):

class Monoid
operator "o" (other: Monoid): Monoid;
end class

The integers are a group, so let’s stay somewhat abstract and define the Group class:

class Group
inherit Monoid
rename operator "o" as operator "+";
end inherit
inherit Monoid
rename operator "o" as operator "*";
end inherit
end class

In other words, a Group is-a Monoid, but in two very different ways – in isolation, both "+" and "*" are valid redefinitions of the abstract "o" operator, but nobody would confuse the two when it comes to actually apply the two operators!
Of course, languages that enforce a merge at the bottom of the diamond force programmers to do exactly that.

The Monoid example could be expanded. For example, any serious Monoid class would have a neutral_element member. It would be renamed to zero for addition, and one to provide the neutral element for multiplication. This is just the same situation as with the operators: Groups have a neutral element as Monoid mandates, but actually they have two since they a Group is a Monoid in two fundamentally different ways, by definition.
Note that integers aren’t the only groups in existence; other examples include square matrices, some classes of numbers that are interesting in

This is just a bare-bones examples. In practice, the situation often involves several additional routines or member variables, some of them eligible for merging and others that should be kept separate.
For example, a similar example could be constructed for classes like Ticket, Adult_Ticket, Child_Ticket, and a common descendant to adult and child tickets, Family_Ticket.

Most OO languages fail miserably in handling such a situation; that’s why the common advice is to avoid diamond inheritance if at all possible, and if it can’t be avoided, to avoid redefinitions along the way. I hope the above exposition clarifies the causes for the problems, and enables class hierarchy to designer how to manage diamond inheritance when it’s unavoidable.

Solution Sketch

Let me indulge in a common vice and envision how the archetypical „ideal language“ would handle the situation.

To talk about concrete situations, we need four variables named a, b, c, and d, declared to be of types A, B, D, and D, respectively, and initialized as follows:

d := new D Create an object of type D
b := d; c := d Assign it to variables of the intermediate types B and C
a := d Assign it to a variable of the root type, A

The interesting case here is the last one: what should be the semantics of a call to a.r?

In the case of sharing, the answer is clear. a.r must observe the semantics of both rB and rC, i.e. it must not require more than the preconditions of both, and it must ensure at least their postconditions.

In the case of replication, there is no such thing as a single r routine. An object of type D has two interfaces, both conforming to the interface of A but addressing different aspects.
In other words, an assignment like the last one isn’t complete: we cannot simply assign a type-D object to a type-A variable, we have to select which of the two interfaces is is meant.

Applying this principle to the Monoid/Group example, this means that any group consists of two monoids, an „additive monoid“ and a „multiplicative monoid“ (both of whic h share a set of values but have different operators). In fact this corresponds to established mathematical terminology.
When assigning an object of type Group to a variable of type Monoid, we have to select which of the two groups we mean: the additive or the multplicative one.

Of course, to be able to select one of the interfaces, they need a name. Writing down

some_monoid_variable := some_monoid_value.additive

isn’t going to have a useful semantics unless additive isn’t defined somewhere in the Groupclass.

Note that, in our ABCD example, there is no selection required when assigning

b := d; a := b

or

c := d; a := c

For each single assignment, it’s clear which of the two interfaces of d is meant, and no specific identification is required. The problem occurs only if we directly assign

a := d

Of course, in the Group/Monoidexample, there are no intermediate classes that could be used for identifying the interface to select, so the need for identifying inheritance paths is unavoidable even if the vast majority of diamond inheritance could do without.

A Sketch of a Full Solution

Let me further indulge in the sweet vice of language design and present an outline of how the syntax and semantics of a language could look like if it adhered to the above solution.
The proposal probably contains several omissions; I haven’t checked all details. It is intended to be a proof-of-concept, not a full-fledged solution that can be immediately dropped into any existing language.

Not written yet.

Naive Implementation

Not written yet.

Optimization Opportunities

The naive implementation requires two lookups in dispatch tables, plus code that copies updated attributes from one interface record to another.

The dispatch overhead can be mostly eliminated through the usual optimizations that turn dynamic dispatch into static subroutine calls. I have no reason to believe that this will be more difficult or give less optimization opportunities than in traditional OO languages.
This kind of optimization is essential since it’s prerequisite for inlining, which in turn is essential for giving reasonable efficiency in any language, so I’d expect this to be a small problem since all the call-flow analysis techniques required for eliminating the double dispatch are needed anyway.

Variable updates should be done through setter routines. Otherwise, routines that update a member variable might see an inconsistent state when reading back the just-updated value, getting the old or the new value depending on the interface through which they access it.
The performance impact can be considerably softened through the liberal application of inlining optimizations, however.

Personal Statements

This article was published in the hopes that it will help with the design and usage of existing tools. It doesn’t mean that I hold the belief that the current OO-based paradigm is the best of all possible worlds; in fact there is a serious concern that the combination of inheritance and subtyping is generally a bad idea that has led to all sorts of problems.

However, I do believe in improving existing tools even while the next toolset is being developed. The next toolset may be just around the corner, or it may be stalled for another decade; in the latter case, interim improvements serve a useful purpose.
I hope that this article will contribute to this end.

Finally, I wish to thank various people with whom I have discussed the issues. Without their contributions, I wouldn’t have been able to elaborate the above to the point at which it curently is.
In particular, I wish to thank Jocelyn Coulmance, who initially discussed the issue with me in the context of the Eiffel programming language.

Comments, improvements, praise and critique are all equally welcome. Direct them at me via email.

Joachim Durchholz, October 2004, Bad Breisig

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.