Diamond vs triangle inheritance

Question

My question is the same as this old one, but I do not yet understand the answer given: Diamond Problem

In the diamond problem, D inherits from B and C which both inherit from A, and B and C both override a method foo in A.

Suppose instead a triangle: there is no A, D inherits from B and C, which both implement a method foo.

As I understand, without special handling, the following would be ambiguous in either the diamond or triangle because it is not clear which foo to call:

D d = new D;
d.foo();

So I'm still not sure what makes this a diamond problem and not a more general multiple inheritance problem. It seems like you would need to provide some way to disambiguate this even in the "triangle" problem.

I'm not sure I understand the ambiguity in your second example - you'll be calling `B`s `foo` method or an override in `D`. But most descriptions of this type of problem don't assume any further overriding in `D`, so you know exactly which method you're calling. — Damien_The_Unbeliever, Oct 24 '17 at 13:26
My thinking was if the language behaved in a way that called the method based on the runtime type of object, so with the object being of type D it would still be ambiguous whether to call B.foo() or C.foo(). Whether it's handled this way, or the way you describe, it seems like it's something common to diamond and triangle. — allstar, Oct 24 '17 at 14:06
Name lookup happens at compile time in most languages. In the second example, at runtime, you'll be looking for "`B.foo` or an override of `B.foo` in a further derived class". You won't be looking for "any method called `foo`" — Damien_The_Unbeliever, Oct 24 '17 at 14:13
I believe that's not the case in Java due to late binding. Just ran a little test with C inheriting from B. B b = new C(); C c = new C(); ... In both cases b.foo() and c.foo() invoke the method in class C. — allstar, Oct 24 '17 at 14:19
I think the bit you're missing is *how* dynamic dispatch is typically implemented, which I've tried to describe above but you're not getting since your counter-examples are talking at odds with what I'm trying to say. An answer is likely to be too large if you don't understand e.g. what `vtables` are, so do you? — Damien_The_Unbeliever, Oct 24 '17 at 14:31
Ah, I misread what you wrote. You are right, I don't know what vtables are in depth, but I do now understand what your initial comment is. In my example, I was overriding foo in C, which as you point out is not the typical description of the problem. I updated the question to remove this incorrect example. — allstar, Oct 24 '17 at 14:46
@Damien_The_Unbeliever regarding the case that I left in the question, it seems like this is due to multiple inheritance more generally rather than specifically multiple inheritance from two classes with the same superclass (diamond). — allstar, Oct 24 '17 at 20:54

Damien_The_Unbeliever · Accepted Answer · 2017-10-27T06:45:48.743

As I alluded to in the comments, some of the issues relate to how dynamic dispatch is typically implemented.

Assuming a vtable approach, any particular type must be able to produce a vtable that allows it to be treated as itself or any of its supertypes. Under single inheritance, this can be really easily implemented since each type's vtable can start with the same vtable layout as its immediate supertype followed by any new members that it introduces.

E.g. If B has two methods

vtable_B
Slot #       Method
1            B.foo
2            B.bar

And D inherits from B, overrides bar and introduces baz:

vtable_SI_D
Slot #       Method
1            B.foo
2            D.bar
3            D.baz

Since D didn't override foo, it just copies whatever entry it finds in Bs vtable for slot #1.

Then any code working with a D through a B variable will only ever use slots #1 and #2 and everything works fine.

Introduce multiple inheritance, however, and you may not be able to use a single vtable. Assume we now introduce C which also has foo and bar methods. Now we'll need to use different vtables when D is cast to B:

vtable_MI_D_as_B
Slot #       Method
1            B.foo
2            D.bar

or to C:

vtable_MI_D_as_C
Slot #       Method
1            C.foo
2            D.bar

These are unambiguous¹. The issue is trying to fill in the vtable for D when its not cast to anything:

Slot #       Method
1            <what goes here>
2            D.bar
3            D.baz

So, you're correct that the triangle inheritance does raise some issues. But since we're using a different vtable for D as D (as opposed to D as B or C) we could simply omit an entry for Slot #1 and make it illegal to call D.foo (in the simple case that nothing further is stated in Ds definition such as to use Bs foo or overriding foo):

vtable_MI_D
Slot #       Method
2            D.bar
3            D.baz

Let's now introduce A and have it define foo, back to the classic diamond pattern. So As vtable is:

vtable_A
Slot #       Method
1            A.foo

B and C are as described above. We can follow exactly the same approach above for D, except for one additional problem. We have to supply a vtable for D cast as A. We can't just omit slot #1 - code dealing with an A expects to be able to call foo. And we can't just copy the entry from B or C's vtable since they have different values and they're both immediate supertypes.

This, I believe, is the gist of why the diamond pattern is typically used - because we can't just implement a "you can't call foo on a D" rule and be done with it.

¹It's also worth observing here that slots #1 and #2 in the vtable_MI_D_as_B and vtable_MI_D_as_C vtables are completely unrelated. C could have had slot #2 be for its foo method and slot #6 for its bar method. Method with the same names won't necessarily share the "same" slots.

This is in contrast with the later discussion of the diamond inheritance pattern where slot #1 really is the same slot across all types.

This is an awesome explanation, thank you so much. I do have a followup: why vtable_MI_D_as_A would not have a copy of A.foo from vtable_A, similar to the way you described vtable_MI_D_as_B — allstar, Oct 25 '17 at 17:49
@allstar - well, you *could*, but that's not how inheritance usually works. In `vtable_MI_D_as_B`, `B` is an immediate supertype, and so we're inheriting its `foo` implementation if we don't have our own. With single inheritance but using separate vtables for each `as` instance, `vtable_SI_D_as_A` would still use `B`s `foo`. At this point, any suggested modifications are trying to *fix* the diamond inheritance problem - and all of these fixes have various downsides - that's what makes it a much discussed problem in the first place :-) — Damien_The_Unbeliever, Oct 26 '17 at 05:29

Jaloopa · Answer 2 · 2017-10-24T14:10:41.873

D d = new D();
d.foo();

the call would be ambiguous, and there would be a compiler error. You would be forced to specify which version of foo you want

(B)d.foo();
(C)d.foo();

No problem. This applies whether A and B both inherit A or not. The issue is when you have:

A a = new D();
a.foo();

This is also ambiguous, even though A clearly only has one version of foo. If you're given an A and it happens to be a D, you'll get an error even though you're calling a method on an object. If you have to test whether it's a D, then decide whether to cast to a B or C before calling foo, that breaks polymorphism

Edit to respond to the comment:

I have a method

void DoStuff(A a)
{
    a.foo();
}

and I pass in a D. Which version of foo() should be called? If DoStuff is in a library referenced by other code that has defined B, C and D, DoStuff() will have no idea what to do with this, as you can't expect the library maintainer to implement overrides for every possible object that inherits from A

Right, but it seems like the same issue to be handled in the same way: (B)a.foo(); — allstar, Oct 24 '17 at 14:02
That is to say, the issue you describe is certainly true, but since it is adding another layer of inheritance, but the issues is already there with just the multiple inheritance of B and C, it seems strange that the canonical problem is called the diamond problem. I feel like I must be missing something distinctly different. — allstar, Oct 24 '17 at 14:13

Diamond vs triangle inheritance

2 Answers2