9

Note: I am not sure of the correct terminology for what I am describing, so if you have suggestions for a better title please feel free to edit it.

"Favor composition over inheritance" is generally a good rule to follow, but there are some cases where inheritance is a must, like in the following case:

Node a = ...
Node b = ...
List<Node> path = GraphUtil.shortestPath(a,b);

Here we have a hypothetical graph library that provides some nice functionality for us, but we would like to augment it with some extra properties, like color or something. If we use inheritance, our code can be like this:

MyNode a = ...
MyNode b = ...
List<MyNode> path = (List<MyNode>)GraphUtil.shortestPath(a,b);
// highlight the path:
for (MyNode n : path) { n.color = "green"; }

This is still not totally amazing due to a runtime cast, but it gets the job done.

However, if we were to use composition, this won't work at all. We would need some kind of external map in order to achieve this (in C++ maybe some pointer hackery).

The question is: are there any existing strategies to achieve this behavior via composition that do not involve things like external maps or pointer hackery?

Of course the obvious answer is "just use inheritance", but if the Node class is made by a factory or is otherwise inconvenient to inherit from, what are the alternatives? Obviously a map is one option, but that is very inconvenient and messy, and not to mention slow.

7
  • 3
    Hey, is there anything stopping you from making the graph library generic (so shortestPath<T implements Node>(...)? Like, this is solvable without inheritance if the graph library takes an interface Node` instead of a concrete base class one must inherit from. Sep 15 at 14:57
  • 2
    Why do you need a runtime cast? why can't GraphUtil (by the way, this name indicates that this class has no clear purpose) use generics to return a list of <T extends Node>, where T is the type of A and B?
    – njzk2
    Sep 15 at 20:57
  • 2
    (you can also use a mix of inheritance and composition, with a delegate pattern)
    – njzk2
    Sep 15 at 20:58
  • 2
    @njzk2 well I'm not sure, you will have to ask the creators of GraphUtil about that, maybe they had a good reason. My only question was what to do if they didn't anticipate this use case, or could not accommodate it for whatever reason. Sep 15 at 21:00
  • 1
    A decently designed interface for this feature would include generics. It's not acceptable to return a list that is not "a list of elements of the types of a and b". So if your question is "how do I get around poorly designed interfaces", that's a different problem.
    – njzk2
    Sep 16 at 19:56
14

Composition over inheritance

[A] Composition over inheritance is generally a good rule to follow,
[B] but there are some cases where inheritance is a must

Your conclusion in B implies that you are understanding A to mean "composition should always be used instead of inheritance". This interpretation is not correct.

There are some cases where inheritance is the only reasonable working solution. There are some cases where composition is the only reasonable working solution. Neither of these cases are relevant when considering "composition over inheritance".

There are some cases where composition and inheritance are both reasonable working solutions. "Composition over inheritance" advises that in these specific cases where either would a viable solution, that you should favor composition because it's not as likely for you to end up having painted yourself in a corner later on in the development cycle.

The example you bring to the table is one where inheritance is the only reasonable workable solution, and is therefore irrelevant as to the "composition over inheritance" guideline.
Similarly, the hypothetical you present is one where composition is the only reasonable workable solution, and is therefore equally irrelevant as to the "composition over inheritance" guideline.

The core of the question is irrespective of composition over inheritance. You're essentially asking "how to do A, which only works in situation X, while at the same time doing B, which only works in situation !X". By definition, you can't.

The question is: are there any existing strategies to achieve this behavior via composition that do not involve things like external maps or pointer hackery?

You already pre-empted the response, but in cases where only inheritance makes sense and not composition, just use inheritance.

Using the wrong solution for your scenario means that any difficulties you encounter from doing so are a self-imposed hurdle, and trying to make it work without addressing that hurdle turns into an XY problem really quickly.

Of course the obvious answer is "just use inheritance", but if the Node class is made by a factory or is otherwise inconvenient to inherit from, what are the alternatives? Obviously a map is one option, but that is very inconvenient and messy, and not to mention slow.

If the Node class is maintained by you, then this is another self-imposed hurdle. The obvious solution is to adapt the Node implementation so that it is inheritance-friendly.

If the Node class is maintained by the library developer, the same advice applies as it does for any complaint about the library you're using: either find another library to use, get the library developer to change their library, or deal with it. That last option then also entails letting go of the fact that it's going to require a dirty hack to get it working the way you need it to.

If the library designer chose to make it impossible to derive the Node class, or unknowingly designed their library in a way that makes it impossible, then that's how the library is designed. Any circumvention of that design is therefore by definition a hack.

An informal way to define a hack is that it is an inferior/shoddy solution when a better solution is available. The corollary here is that if there are no better solutions to the problem, then it's not a hack.

6
  • Great post. I would disagree with your informal hack definition. In my world a hack is a shoddy way to do something but without any alternatives. Contructing an example: assume your languages template system doesn't support primitives. I would consider creating your own class and implementing all operators a hack. Doing the same in C++ just bad programming. So a hack would be "To do something you are not supposed".
    – Baumflaum
    Sep 16 at 5:59
  • @Baumflaum: I can definitely think of some hacky examples that don't have a clear better solution, but for this question it seemed relevant to point out that the best way to get something done when it needs to get done, even if hacky, is generally acceptable.
    – Flater
    Sep 16 at 7:09
  • I can't think of anything you can do with inheritance that you absolutely cannot do with composition, or vice versa. Even polymorphic method dispatch could be done, you'd simply have to express all the stuff that's done transparently by the compiler as explicit code. Could you give an example?
    – Peter Wone
    Sep 16 at 12:09
  • @PeterWone: "can be done" != "should be done". "can be done" is a bit broad. There should be a common sense boundary to that statement. With that boundary in place, generic typing (and specifically generic type constraints) can be configured with regards to inheritance (Foo<T> where T : MyBaseClass), but not composition. For OP's library method, this could have enabled him to use the library method and have it return his own custom derived type. Without it, he's stuck having to manually downcast a base type to a more concrete one, which is something you'd rather avoid in OOP.
    – Flater
    Sep 16 at 12:46
  • @PeterWone I have rephrased my answer towards referring to "the only reasonable workable solution" to pull that common sense boundary more into focus.
    – Flater
    Sep 16 at 12:49
5

After I wrote most parts of my answer, you added this question:

are there any existing strategies to achieve this behavior via composition that do not involve things like external maps

Short answer: no, there isn't!.

You want to avoid inheriting from Node, but carry some extra attributes for each nodes around. Assumed you cannot add the attributes to those nodes by inheritance, and assumed there is no other designated extension mechanism in the Node class (as mentioned by @pjc50), it is necessary to store the extra attributes somewhere outside. And to reach the related extension attributes for a given node, some kind of map or Dictionary<Node,Color> is the straightforward, canonical and most simple solution.

Of course, this requires Node objects to be "hashable" a.k.a. suitable as keys for a dictionary or map, or having an Id which can serve as a key to distinguish between them. Here is a short sketch in C#:

Dictionary<Node,Color> nodeColors = ... (init this for all nodes)

Node a = ...
Node b = ...

List<Node> path = GraphUtil.shortestPath(a,b);

for (Node n : path) { nodeColors[n]=Color.Green; }

Nodes in a graph will usually provide some way of identifying them in a unique way (maybe by some Id, maybe by guaranteeing fixed object references), so this should usually work for most real-world cases.

If you want to make use of Composition, you can combine this with the dictionary approach:

class MyNode
{
     Node node;
     Color color;
}

Using a dictionary Dictionary <Node,MyNode> instead of Dictionary <Node,Color> might be useful when you need the extra attributes together with the related Node object for further processing in multiple places.

With this, you can encapsulate the shortestPath function like this:

class MyGraphUtil
{
   // init this during construction of MyGraphUtil for all nodes);
   private Dictionary<Node,MyNode> nodeDict;

   public List<MyNode> path shortestPath(MyNode a,MyNode b)
   {
         return GraphUtil.shortestPath(a.node, b.node)
                         .Select(n => nodeDict[n]).ToList();
   }
}

so the dictionary will only be visible in one place.

(Maybe that was what @candied_orange meant, I am not really sure.)

7
  • You're right, and this does work. But I think it's easy to see how (especially from a design pov) this is not optimal. I was looking for an alternative to a map Sep 15 at 5:51
  • @Asad-ullahKhan: see my edit. If you want to store an extra attribute for a Node somewhere outside of it, and have a search algorithm which returns you a bunch of nodes, it is necessary to associate the nodes with these extra attributes, and the canonical solution for this is an associative array a.k.a map a.k.a. dictionary.
    – Doc Brown
    Sep 15 at 5:57
  • I actually like the encapsulation method at the end, so far the best idea Sep 15 at 13:36
  • 1
    Consider making ShortestPath(...) a generic method over TNode : class, Node or TNode : IHas<Node>, thus allowing for true return-type variance: public IReadOnlyList<TNode> GetShortestPath<TNode>( TNode x, TNode y ) where TNode : IHas<Node> {} with public interface IHas<T> { T Value { get; } }
    – Dai
    Sep 15 at 18:08
  • 2
    @DocBrown In the OP’s head, sure - but it’s for the benefit of others finding this page. I’ve come across far too many libraries in-general that should support return-type variance but don’t.
    – Dai
    Sep 15 at 18:40
3

There is a solution from the pre-OO era that is still commonly used in C when handling things like callbacks, and that is for the library object to provide an "any other data" field. In C, this is usually a pointer to void; in OO languages you would use a reference to the base Object type. Sometimes this is an integer instead of a pointer or reference.

Effectively the Node class should support being composed with any other object type in order to be useful without inheritance.

For example, Microsoft have used this technique to link the items in List controls with the underlying data objects of any type. C# : https://docs.microsoft.com/en-us/dotnet/api/system.windows.controls.itemscontrol?view=net-5.0 or C: https://docs.microsoft.com/en-us/windows/win32/controls/lvm-insertitem

The C implementation uses Windows messages, which are a fantastic example of how to do composition over inheritance in a language that doesn't support inheritance at all!

2
  • It's interesting to me that this is a well known and long standing problem and newer methodologies (at that time) like OOP just...don't address it?? Like how is this super old idea with a void pointer still one of the better solutions (newer languages might use a template). It still sucks as a solution. Sep 15 at 16:45
  • 1
    I feel your remark about WPF's ListControl is incorrect: WPF's data-binding relies on reflection, and not simply passing around arbitrary Object references. WPF is very, very different to the Win32/USER32/CommonControls of yore (for example, in WPF you can nest a button in another button, but in User32 you can't even render one control on-top of another...)
    – Dai
    Sep 16 at 2:06
2

This is really a question about how to implement polymorphic data structures, and we can use the standard Java answer: generics. The Node class could be declared as a generic, with the parameter type used as the “metadata” for each node:

class Node<T> {
    public T metadata;
}

class MyMetadata {
    public Color color;
}

List<Node<MyMetadata>> path = graph.shortestPath(...);
for (Node<MyMetadata> node: path) {
    node.metadata.color = Color.GREEN;
}

Of course, this is up to the library designer. In Java, the annoying bit would be initializing the metadata field for each node polymorphically; you could supply a Callable to do that when constructing the graph as one option. In a language like Rust or Haskell, you could also use traits/type classes to specify that the metadata parameter should be constructible in some way.

11
  • While I agree that this is a solution from a library designer perspective, I wanted to know of solutions that didn't care as much about the library design. After all, isn't the entire point of OOP and code reuse that I can write code that other people can use easily? It seems bizarre that a library designer has to anticipate every possible way their users might extend their objects. I was just certain there had to be a better way Sep 15 at 19:37
  • 3
    @Asad-ullahKhan But generics is exactly the solution to allowing other people to re-use your code without having to predict every possible way the consumer might use it! Your question is premised on a poorly built library that is hostile to its consumers. As Doc Brown pointed out, there is little you can do in that situation. This answer is exactly how you avoid that situation in the first place (in the library design) by favoring composition over inheritance. Sep 15 at 20:39
  • @Asad-ullahKhan The nominal intent behind OOP is to add language features and design patterns that make code reuse easier and more reliable. That doesn’t mean code using those features is inherently easier to reuse; that’s just the intent of the feature. In the general case, trying to have perfectly reusable code is basically equivalent to the halting problem: you can’t predict what a user may want. In this example, the developer didn’t consider that a user may want to associate data with each node. (Inheritance may work, but it may also be brittle.)
    – gntskn
    Sep 15 at 20:52
  • In this case, you can just use Node<Color>. You only need another class if you need to aggregate more metadata.
    – Polygnome
    Sep 15 at 21:50
  • 1
    @Asad-ullahKhan Anticipating use cases and writing extensible and reusable code is exactly what males writing good libraries so damn hard. Node should be an interface, or it should be generic and have a getData<T> method, or maybe even both! Done that way, it is rather flexible.
    – Polygnome
    Sep 15 at 21:51
0

Design decisions are most often made for you when you use an existing library. As @pcj50 notes, some libraries provide support for composition by adding a field to structures whose content can be defined by the user.

But if the author of the graph library did not foresee the need (or preferred inheritance over composition), you're essentially forced to do it their way and implement workarounds where that isn't feasible.

0

To answer that question we need to find out the main reason why the "Favor composition over inheritance" advice is important: it solves the hard coupling between the base class and the child class caused by inheritance. Composition allows us to use an interface to reference one class into another, thus solving the coupling problem.

However, in your case it seems to me that you are trying to inherit only data from the Node class. And data is, by itself, already fully customizable. That is, you can "mock" any data inside a field or property. This is different from a method that can only have its behaviour substituted when it is behind an interface.

So it is totally fine to use inheritance as long as there is no behavior being inherited, in the end you are just reusing some data fields.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.