Sign in to follow this  

Best language for solving diamond problem & is this a good idea for multiple inheritance?

This topic is 815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

This is my first time in these vast forums, and I've come today to ask you if you know of a programming language that has a good solution for the diamond problem unlike C++'s workarounds of virtual inheritance, using :: to specify which super-class to get the implementation from etc.

I also wanted to share my (probably naive and) basic solution for multiple occurrences from multiple super-classes of the same method named implementation in a class, which is to call both implementations in alphabetical order of the super-classes' names. I have a very strong feeling that there could be many problems linked to this form of behavior for classes, yet I fail to see them. I seek criticism on this solution, and if no faults apply to this behavior please do approve.

Kind Regards,
Kreative

Share this post


Link to post
Share on other sites

I suspect most people here will suggest trying composition instead of using inheritance at all. It's easier to get what you want, and you don't have to fight with the language.

QFE.

Most cases where people encounter the diamond problem, in my experience, are cases where composition was more likely to be the appropriate choice. Edited by Washu

Share this post


Link to post
Share on other sites
It sounds like you aim for a language-theoretic discussion. A gamedev forum is probably not the optimal place for that. You may also want to try a forum or mailing list about programming language theory.

Having said that, people here are likely to have a very different view on the problem here, which is what you may be after. Personally, I know you can do multiple inheritance, but I rarely need it. I know the diamond thingie exists, but I have yet to run into one, and I have been programming OOP for about 20 years. In my experience, you write class hierarchies specifically for a goal, and you don't randomly merge it with other class hierarchies ever. Obviously, ymmv, it highly depends in what kind of systems you normally work, probably. If I ever run into one, my first reaction would be to think real hard whether this form of multiple inheritance is really good, and if so, rename a variable or use a pointer to resolve the issue.

I have probably read the C++ solution at some point, but have forgotten all about it. This may be the whole story. From a language theoretic point of view, diamond thingies are highly interesting no doubt, but they are so rare in practice, that basically any solution will do where you can express explicitly how it should be solved, no matter how ugly (ie you want to have an escape if it happens, diamond thingies are ugly already, an ugly work-around doesn't make much difference).

Using alphabetical order, or any other fixed order that cannot be changed easily is probably evil. Your solution may run into trouble when a class gets renamed, in particular a class that is not under your control, but eg from some library.
I would expect in the general case that you need several solutions, maybe two classes need to share the data, but a 3rd class needs its own copy.

Share this post


Link to post
Share on other sites

A gamedev forum is probably not the optimal place for that.


I know what you mean, this website showed up in my google search of "programming forums," and I was hesitant to post this thread until I saw the sub-forum, general programming which stated in the description, programming NOT related to games, so I had a go. I tried coding forums but my registration, account activation or something is a bit buggy and I don't have permission to do anything. So this is where I decided to go for general programming discussion and the only reason I've ever done programming in my life is for game creation, so even this is personally related to game design.
 

 


most people here will suggest trying composition instead of using inheritance at all

 


cases where composition was more likely to be the appropriate choice.


I know composition is usually much easier, however I am killing myself over repetition in programming languages, which in my (probably naive) understanding is the primary purpose of any form of complexity in programming. You can express almost everything in programming in a very long form without using lists, classes, etc, but it will contain millions time more repetition and likely other problems.

Composition can probably eliminate the need for almost any form of inheritance, however using inheritance mostly makes code shorter and less repetitive, imagine an insanely rare case of a triple occurrence of the diamond problem with multiple inheritance, using composition would usually lead to you having to do things like instanceOfClassA.instanceOfClassB.instanceofClassC.instanceOfClassD for every function or variable you're going to use. Although I should expect this never to happen in my lifetime, repetition, how ever little, in my opinion, should always be eliminated.

Note:
I've decided that instead of putting, (probably naive) everywhere I make assumptions or state opinions, I'll just say I'm very naive in programming practice and theory, I hope people read this note so they won't assume that I think that I am right and that I state facts, where they know something I said is an extremely huge assumption or obviously false.

Kind Regards,
Kreative

Edited by Kreative

Share this post


Link to post
Share on other sites

I'm not really sure what language selection has to do with it. While I've only seen it as an occasional problem in C++, I've only seen it exist in C++ and Python.  

 

Wikipedia lists a few other languages beyond C++ and Python that support multiple inheritance, but none are really game related (Lisp, Curl, Dylan, Eiffel, Logtalk, Object REXX, Scala, OCaml, Perl, POP-11, and TCL).  So if you aren't using any of those languages, problem solved. Yay.

 

 

 

In C++ it isn't normally a problem. It is extremely rare to create a situation with a diamond, the normal inheritance case leaves you with two different grandparents. This normal case if you derive from multiple bases you need to specify which to use by implementing the behavior and doing it yourself, specifying which parent's parent to use. And since C++ doesn't have a built-in system that calls base::method() or super() method, there isn't a problem for a default base.  A diamond is only created if you explicitly specify virtual inheritance. The only way to have the problem is to intentionally create it, and it is only intentionally created when it is intentionally needed. So it isn't normally a problem here.

 

Python also potentially has the problem, but again, it isn't normally encountered in games.  The way it is handled is explicitly specified in the language design, it is handled by the order of inheritance. Python DOES support a super() functionality, but the handling is well defined by the ordering.  And like C++, if you need to specify which path to take that is different from the default, you can use that parent's function explicitly. You can use super().method() for automatic use, or you can specifically call base.method() to be clear about it.

Share this post


Link to post
Share on other sites

The diamond problem? The diamond of death? Every language with class inheritance has that issue. Really, it's just up to the programmer to catch what he's doing. And... I have never heard of anyone actually encountering said issue... unless he gets a diamond in his spaghetti soup object structure.

 

And... I wouldn't say avoid inheritance in general. It's actually really the only way you can get things done pretty efficiently, elegantly, and with less code. For 

Share this post


Link to post
Share on other sites

I know the diamond thingie exists, but I have yet to run into one, and I have been programming OOP for about 20 years. In my experience, you write class hierarchies specifically for a goal, and you don't randomly merge it with other class hierarchies ever.
This. I think C++ deals with it sufficiently by not dealing with it at all. It's something you practically never encounter (I can't name a single case that I've encountered, ever).

 

But you could give Java a try, it tackles the problem by only allowing single inheritance. No multiple inheritance, no diamond possible (though I haven't touched Java for about 10 years, and I was told that in the meanwhile they do allow a kind-of-multiple inheritance through the backdoor).

Share this post


Link to post
Share on other sites

I know composition is usually much easier, however I am killing myself over repetition in programming languages, which in my (probably naive) understanding is the primary purpose of any form of complexity in programming. You can express almost everything in programming in a very long form without using lists, classes, etc, but it will contain millions time more repetition and likely other problems.

Composition can probably eliminate the need for almost any form of inheritance, however using inheritance mostly makes code shorter and less repetitive, imagine an insanely rare case of a triple occurrence of the diamond problem with multiple inheritance, using composition would usually lead to you having to do things like instanceOfClassA.instanceOfClassB.instanceofClassC.instanceOfClassD for every function or variable you're going to use. Although I should expect this never to happen in my lifetime, repetition, how ever little, in my opinion, should always be eliminated.

Note:
I've decided that instead of putting, (probably naive) everywhere I make assumptions or state opinions, I'll just say I'm very naive in programming practice and theory, I hope people read this note so they won't assume that I think that I am right and that I state facts, where they know something I said is an extremely huge assumption or obviously false.

Kind Regards,
Kreative

 

 

You can avoid complexity and repetition in other ways without inheritance/member functions etc by using techniques found in the functional world, such as high order functions and the like. The more I play in the functional space the more I find myself move away from OO techniques in favour of these other techniques, I find them more concise, I use far less code and get more code reuse.

 

Now C++ has lambda and closures use can employ many of these techniques in that language as well although its lambda syntax is ugly as imho

 

I recommend you have a play with F# or one of the lisps (scala is popular way to ease you way in) or if you want to really turn your thinking on its head look at haskell, the most hardcore functional language there is. It has a purity and simplicity that is beautiful. You will start to encounter monads and other computational building blocks that ease coding and remove much of the noise in your code that does not actually describe the problem but just controls flow etc.

 

Even if you do not do much with this languages it they will give you mindsets that you find permeate throughout your code no matter the space you work in and give you a whole new bag of tricks and ways to solve problems no matter the language you work in. Functions and data merge and become pretty much the same thing :)

 

The following are a couple of validators from a roguelike I have been playing with in C# but using immutability and functional code. They hook validation monads into the Linq computational engine and if any of the validation fails the code short circuits and the rest does not execute, the result is either the item selected at the end or the error message describing the failure. Notice the lack of control flow or even if statements. All the functions are statics and extensions, no member functions at all, all the branching and control provided by my validation monad and hidden away by Linq.

        public static IValidation<Level> CanSpawnActor(
            this Level level, long actorId, Vector location)
        {
            return
                from isNew in level.IsNewActor(actorId)
                from targetTile in level.IsValidMove(location)
                select level;
        }

        public static IValidation<Level> CanMoveActor(
            this Level level, long actorId, Vector newLocation)
        {
            return
                from actorState in level.ActorStateExists(actorId)
                from actorTile in level.IsValidLocation(actorState.Location)
                from actor in actorTile.HasActor(actorId)
                from withinRange in actorState.IsWithinMoveRange(newLocation)
                from validMove in level.IsValidMove(newLocation)
                select level;
        }

I believe the diamond inheritance shape should be the last solution you look at :)

Share this post


Link to post
Share on other sites

Composition can probably eliminate the need for almost any form of inheritance, however using inheritance mostly makes code shorter and less repetitive, imagine an insanely rare case of a triple occurrence of the diamond problem with multiple inheritance, using composition would usually lead to you having to do things like instanceOfClassA.instanceOfClassB.instanceofClassC.instanceOfClassD for every function or variable you're going to use. Although I should expect this never to happen in my lifetime, repetition, how ever little, in my opinion, should always be eliminated.

Both the composition and inheritance exist for a reason. Overusing one over the other is not a good idea either. Beside of those there are also other patterns and principles that makes developer's life easier, especially "single responsibility" and KISS (keep it simple stupid).

If you run into situation in your code that you need to use something like instanceOfClassA.instanceOfClassB.instanceofClassC.instanceOfClassD, it is clear sign you are doing too much in one class. And the same goes for multiple inheritance.

 

There is reason that many modern languages do not allow for multiple inheritance. It is not because it is hard to implement in compiler (and I believe it is hard ;)), but because it is confusing for developers thus error prone.

Edited by Deflinek

Share this post


Link to post
Share on other sites

There is reason that many modern languages do not allow for multiple inheritance. It is not because it is hard to implement in compiler (and I believe it is hard ;)), but because it is confusing for developers thus error prone.

I think the reason is interfaces, which go a long way towards eliminating the need for multiple inheritance.
The problem that gets solved in both cases is the idea that you can see a single object in multiple ways (ie talk to it in different ways to the same object).

C++ uses inheritance to define how you can talk to an object.
Java (and C# too, it seems) uses interfaces. I don't know C#, but Java has single inheritance, and you add as many interfaces as you like to define how you can talk to an object.

Interfaces are a bit more flexible, in the sense that you're not stuck to the inheritance hierarchy.
On the other hand, interfaces (of Java at least) are less powerful by not allow adding data or implementations. (Iirc work is being done (or has been done) to allow a very simple form of implementations though.) This means you cannot add a base implementation through an interface in Java.

Share this post


Link to post
Share on other sites

I think the reason is interfaces, which go a long way towards eliminating the need for multiple inheritance.
The problem that gets solved in both cases is the idea that you can see a single object in multiple ways (ie talk to it in different ways to the same object).


The last diamond pattern I remember seeing in my work was due to interfaces, and in my experience interfaces encourage multiple inheritance. I feel like I should lay out the situation, because many people are commenting that they've never seen one. I believe this is a very simple case:

This was in a shooting game. The game had base objects that could be in the scene: We'll call the class for those "Actor". Some things to shoot were explicitly targets, so we'll call that class "Target". A target was just a specialized form of actor, so it inherited from Actor. So far, we just have two classes:

Actor
|
Target

These game objects all lived in one component. Other components referenced them through interfaces, which were pretty much one-to-one. So, there was an IActor and ITarget, with the same inheritance to not repeat all the shared functions:

IActor
|
ITarget

Naturally, Actor inherits IActor and Target inherits ITarget, so this is what you get:

          IActor
        /            \
  Actor         ITarget
          \        /
        Target

There you go, a C++ diamond encountered in real life. I'm not saying this is an unsolvable problem, but it was a situation that was left alone because there wasn't any consensus on what would be better.

Share this post


Link to post
Share on other sites

 

I think the reason is interfaces, which go a long way towards eliminating the need for multiple inheritance.
The problem that gets solved in both cases is the idea that you can see a single object in multiple ways (ie talk to it in different ways to the same object).


The last diamond pattern I remember seeing in my work was due to interfaces, and in my experience interfaces encourage multiple inheritance. I feel like I should lay out the situation, because many people are commenting that they've never seen one. I believe this is a very simple case:

This was in a shooting game. The game had base objects that could be in the scene: We'll call the class for those "Actor". Some things to shoot were explicitly targets, so we'll call that class "Target". A target was just a specialized form of actor, so it inherited from Actor. So far, we just have two classes:

Actor
|
Target

These game objects all lived in one component. Other components referenced them through interfaces, which were pretty much one-to-one. So, there was an IActor and ITarget, with the same inheritance to not repeat all the shared functions:

IActor
|
ITarget

Naturally, Actor inherits IActor and Target inherits ITarget, so this is what you get:

          IActor
        /            \
  Actor         ITarget
          \        /
        Target

There you go, a C++ diamond encountered in real life. I'm not saying this is an unsolvable problem, but it was a situation that was left alone because there wasn't any consensus on what would be better.

 

 

If IActor and Target were pure virtual interfaces, I'm not sure that really counts, since a pure virtual interface will have no implementation. Since the implementation inheritance is solely between Actor and Target, there's no ambiguity as to which class provides the implementation for which functions. Even if at the language level it's technically "multiple inheritance," this scenario isn't what most people refer to when they talk about the diamond problem, because the diamond problem specifically refers to situations where it's ambiguous to the compiler what implementation should be used for a virtual function.

 

In other words, not all diamonds are diamond problems.

Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Naturally, Actor inherits IActor and Target inherits ITarget, so this is what you get:
          IActor
        /            \
  Actor         ITarget
          \        /
        Target
There you go, a C++ diamond encountered in real life. I'm not saying this is an unsolvable problem, but it was a situation that was left alone because there wasn't any consensus on what would be better.


Not in C++.

The only way they form a diamond is if the inheritance is marked as virtual.

Also, virtual inheritance is different from virtual functions or abstract classes. So those are just name confusion.

If you used:

class IActor {...}

class Actor : public IActor {...}

class ITarget : public IActor {...}

class Target: public Actor, ITarget {...}

Then you have something like this:

IActor IActor
| |
Actor ITarget
\ /
Target

If you want to create a diamond in C++, you need to specifically state that the inheritance is virtual.

class Actor : public virtual IActor {...}

class ITarget : public virtual IActor {...}

Because that is a very deliberate step, creating a diamond must be a deliberate design decision. If you accidentally share a parent, it will make the parent separate. If you want to createa diamond you must specifically do so, intentionally, on purpose. It doesn't happen in c++ on accident.

Share this post


Link to post
Share on other sites

"Interfaces" in C++ should use public virtual inheritance.

 

 


I've come today to ask you if you know of a programming language that has a good solution for the diamond problem unlike C++'s workarounds of virtual inheritance, using :: to specify which super-class to get the implementation from etc.

Java uses the same exact solution, except they embedded it as a language feature/rule, as opposed to C++'s flexible "do what you want, but please don't be stupid" system.

In C++ an "interface" is just a convention -- if you make an "abstract base class" (something with only unimplemented virtual functions), we call it an interface, and we use virtual inheritance (with multiple virtual inheritance being acceptable). Any other kind of class we call "concrete" by convention, and we use regular inheritance and restrict ourselves to only ever inheriting from one concrete class. Multiple inheritance of concrete classes is possible, but by convention it's a bad thing(tm) and shouldn't be done.

 

In Java, interface-classes and concrete-classes gained their own keywords, and virtual-inheritance got the implements keyword and concrete-inheritance got the extends keyword. Moreover, the only-ever-inherit-from-one-concrete-class convention became a compiler-enforced rule.

Java just took C++'s conventional solution and locked it down to prevent bad and creative use of it.

 

C++ also supports implementation-inheritance, without interface-inheritance via the private keyword. AFAIK most other language lack this feature, which isn't even really present in traditional OO design.

 

As mentioned above though, inheritance is extremely rare in good OOP code (someone tell Java practitioners please!). It's a rule of OOP to use composition where you can and inheritance only where you must (and that inheritance must obey LSP).

Edited by Hodgman

Share this post


Link to post
Share on other sites

I think the most important thing about the diamond problem is to understand the implications, and to understand that there is no diamond problem at all (in fact, the diamond is the solution to the problem).

If you have base class A and classes B and C which derive from it, and class D which derives (non-virtually) from both B and C, then you have a class D with two ancestors which each have a base class (which happens, by sheer coincidence, to be the same).
Both ancestors inherit a virtual function from their respective base class which happens to be the same. By convention, that function should be pure virtual (so both B and C need to define it) but it needs not be. It's perfectly allowable to provide an implementation in A as well.

So, in one word, you have two, possibly three versions of the same function[1], and when you call that function on a D object, it's impossible to tell which one you want to call. You must either say d.A::f(), d.B::f(), or d.C::f(), or you must take the objects address and do a static cast.

This is, however, not a diamond. It's a tree with "a twist and a knot" in its leaves. Or something. But it's not a diamond.

Now what virtual inheritance does is, it turns that knotty tree into a diamond. You now no longer have two base classes which are accidentially on top of each other and from which the two ancestors inherit and possibly override differently a (accidentially identical) virtual function. You now have exactly one base class, and exactly one final overrider in your most derived class (which might call one of the ancestors' implementations, or do something completely different). Problem solved. Thus, the diamond is the cure, not the illness.
 
Of course, virtual inheritance makes the assumption that you actually want that. This is usually, but not always, the case. You might want something different, too (but then you must tell the compiler what you want every time to make the call unambiguous).
 
 
 
[1] Indeed, they could just as well be entirely differrent, unrelated functions which only accidentially have the same name and function arguments. You cannot know.
 
 
Note that extra vtables may be needed for the compiler to transparently do the "magic" so object size and raw pointer addresses are not always "immediately intuitive" (they can indeed be different for the "same" object, but you should not care about raw pointer addresses anyway), and the whole thing doesn't just work with functions, but with data types as well.

Try and figure the output of the following snippet:

#include <stdio.h>

struct A  { int x[100]; };
struct B1 : virtual public A { };
struct C1 : virtual public A { };
struct B2 :         public A { };
struct C2 :         public A { };

struct D :          public B1, public C1 {};
struct E :          public B2, public C2 {};
struct F :  virtual public B2, virtual C2 {};

int main()
{
    printf("sizeof(D) = %llu\n", sizeof(D));
    printf("sizeof(E) = %llu\n", sizeof(E));
    printf("sizeof(F) = %llu\n", sizeof(F));

    return 0;
}

On my machine, output is
 

sizeof(D) = 416
sizeof(E) = 800
sizeof(F) = 808

 

The first obviously has 100 elements (and two vtables), the next one has 200 elements (and no vtable), and the last has 200 elements and a vtable.

Edited by samoth

Share this post


Link to post
Share on other sites

This topic is 815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this