c++ diamond inheritance java multiple oo oop poo problem programming python term vm weekend_reading

My tags:

From Wikipedia, the free encyclopedia

In object-oriented programming languages with multiple inheritance and knowledge organization, the diamond problem is an ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If a method in D calls a method defined in A (and does not override the method), and B and C have overridden that method differently, then from which class does it inherit: B, or C?

For example, in the context of GUI software development, a class Button may inherit from both classes Rectangle (for appearance) and Mouse (for mouse events), and classes Rectangle and Mouse both inherit from the Object class. Now if the equals method is called for a Button object and there is no such method in the Button class but there is an over-ridden equals method in both Rectangle and Mouse, which method should be eventually called?

It is called the "diamond problem" because of the shape of the class inheritance diagram in this situation. Class A is at the top, both B and C separately beneath it, and D joins the two together at the bottom to form a diamond shape.

[edit] Approaches

Different programming languages have addressed this problem in different ways:

• C++ by default follows each inheritance path separately, so a D object would actually contain two separate A objects, and uses of A's members have to be properly qualified. If the inheritance from A to B and the inheritance from A to C are both marked "virtual" (for example, "class B : virtual public A"), C++ takes special care to only create one A object, and uses of A's members work correctly. If virtual inheritance and nonvirtual inheritance are mixed, there is a single virtual A and a nonvirtual A for each nonvirtual inheritance path to A.
• Common Lisp attempts to provide both reasonable default behavior and the ability to override it. By default, the method with the most specific argument classes is chosen; then in the order in which parent classes are named in the subclass definition. However, the programmer can override this, by giving a specific method resolution order or stating a rule for combining methods.
• Eiffel handles this situation by select and rename directives, where the ancestors' methods to use in a descendant are explicitly specified. This allows the methods of the base class to be shared between its descendants or to even give each of them a separate copy of the base class.
• Perl and Io handle this by specifying the inheritance classes as an ordered list. In the above ambiguity, class B and its ancestors would be checked before class C and its ancestors, so the method in A would be inherited through B.
• Python had to deal with this upon the introduction of new-style classes, all of which have a common ancestor, object. Python creates a list of the classes that would be searched in left-first depth-first order (D, B, A, C, A) and then removes all but the last occurrence of any repeated classes. Thus, the method resolution order is: D, B, C, A.
• Ruby resolves method names using a reverse-inclusion-order depth-first search of included modules, before eliminating all but the last occurrence of each module in the resulting list. So, the resolution order is: [D, C, A, B, A], which reduces down to [D, C, B, A]
• Component Pascal does not allow multiple inheritance. This can be circumvented easily by the use of so-called twin classes.
• Java does not allow multiple inheritance.
• C# does not allow multiple inheritance.
• Scala resolves method names using a right-first depth-first search of extended 'traits', before eliminating all but the last occurrence of each module in the resulting list. So, the resolution order is: [D, C, A, B, A], which reduces down to [D, C, B, A]

[edit] Other examples

Languages that only allow single inheritance (such as Ada, Objective-C, PHP, C#, Delphi/Free Pascal and Java) allow the multiple inheritance of interfaces (called protocols in Objective-C). Interfaces are essentially abstract base classes with all abstract methods and no data members. The problem is therefore avoided since there is always only one implementation of a specific method or property and no ambiguity arises.

The diamond problem is not limited to inheritance. It also arises when header files A, B, C, and D #include one another in a diamond as above and separate precompiled headers are created from B and C. If these two precompiled headers are combined, declarations in A are duplicated and the #ifndef convention is ineffective. It also is found when composing middleware stacks; for example, if A is a database and B and C are caches, D may ask both B and C to commit a transaction, resulting in duplicate commit calls to A.

[edit] References

• Eddy Truyen; Wouter Joosen, Bo Jørgensen, Petrus Verbaeten (2004). "A Generalization and Solution to the Common Ancestor Dilemma Problem in Delegation-Based Object Systems". Proceedings of the 2004 Dynamic Aspects Workshop (103-119).