In the previous post
I teased a little about vtables, how they work, and whether people were familiar with them. Before I go into detail into that I'd like to rehash the notion of polymorphism first. It may be obvious already to OOP programmers or at least those who have been educated about OOP even without using it deeply. Then I go into how vtables work, why they're there, and what good vtables allow programmers to do in C++. Even if you already know all these things, I'd be interested to find out what you think about the content of this post -- comments and discussion would be most appreciated!
First things first. Let's deal with the object-oriented notion of Polymorphism. Polymorphism is achieved in OOP by treating multiple (related) types as if they were the same. Polymorphism is almost literally translated to "many forms". Here's a simple example of the OOP implementation of Polymorphism in C++11 using inheritance and virtual methods:
This is very simple, elementary OOP. We have classes Book and Door and they inherit from and override virtual methods in Object. We treat Book and Door like they were normal Objects. We have a function called "print" that lives alone and can print a reference to an Object.
This is what is called the "substitutability" principle, where we can substitute any type that's derived from Object and treat it as we would an Object. There's more nuances with pure abstract types and even final types (for which no other type can be substituted) but you get the idea.
There are a few questions that arise in this design though. Let's explore some of these questions:
- Can I treat instances of Object and instances of types derived from Object as I would an int? (Regular Types)
- Can I put objects of types derived from Object in a container of Object's? (Value Semantics)
- If I have a type that "looks" like an Object, can I also treat it as an Object? If I can't how can I work around that? (Concepts)
For OOP, these questions get really hard to answer.
Is there a different way?
The other kind of polymorphism is Conceptual polymorphism. This is you might be familiar with if you've done anything with templates and concepts. The idea is to define requirements supported by types instead of looking at relationships between types, to determine whether an algorithm/function can be applied to instances of a given type. That's a lot of words, but code works best.
We take the Book and Door types and we define the concept of an Object. This definition goes like this:
A type is an Object if it can be default constructed, can be copied, and accepts the no-argument print message (has a member function named print that doesn't take arguments).
Now let's see how we can implement this in C++11:
So, not much changed -- but if you squint you'll see a few things. First, the inheritance is gone! We just turned the print function into a template. We see that this works quite well for unrelated types, and we've now got a "generic" print function. Let's then try answering the questions we raised before in the OOP section above:
- Can we treat instances of Object (or O in this case) as we do int's? Yes, as long as O is a regular type.
- We have types that "look" like an Object (or more directly, types that model the Object concept), can I treat each one as I would an Object? Yes!
- Can we put objects of types that model the Object concept in the same container? No (at least not yet).
Oh darn -- we're missing that part of putting things of the same concept in the same container. This is a little embarrassing, but then is there a way to do this? Let's look at our options.
First option is we can use "type erasure" to do the trick. However this still almost requires some sort of inheritance-based polymorphism. This doesn't sound so value-semantic and polymorphic (we'll look at this again later).
Second option is we can stick with the inheritance-based polymorphism and use std::unique_ptr in the container. In C++11 this is a completely valid option but it doesn't allow you to treat the objects referred to as values -- you're now relying on reference semantics to maintain identity. In most situations and in purely OOP design, you can stop here and just take the hit.
Is there a third option? Can we mix the two ideas together and achieve what we want in the end, which is objects of different types being stored in the same container?
Effectively we're going to have to be a little more creative. We can actually use both approaches to achieve what we want in the end: dealing with values, supporting polymorphism, removing the explicit inheritance, and then getting to the juice.
Before we go there, we make a little detour into vtables.
In essence, the way dynamic polymorphism (polymorphism via inheritance) works is through virtual functions, and under the hood they're represented as a table of function pointers. Each instance of a type that has virtual functions in its bases and its declaration will typically have a part of the object's storage in memory dedicated to a pointer to a table of function pointers mapping a function's signature to a function pointer. Compiler vendors may implement virtual tables differently and the C++ standard doesn't define the layout of virtual tables.
You can find out more about virtual tables (or vtables in short) if you reach for your favorite search engine and look up [vtable]. There are a lot of good articles on the web about it, but the gist is that's how virtual function calls determine which actual function to invoke at runtime via inheritance-based polymorphism.
Contrast this to how templates work and how the polymorphism is really happening at compile-time. There's no type erasure going on and there's no dynamic lookup at runtime of which function to actually call, because the compiler knows at compile time exactly which function it needs to execute at the point where the function is invoked. There's no need for a vtable in the concepts-based world.
Or is there?
Let's explore the possibility of putting instances of Object, Book, and Door in the same container by combining type erasure (inheritance-based polymorphism) and static dispatch (concept-based polymorphism). We're also going to be creative with how we define the container holding the values all together and get creative with how we implement some auxiliary "helper" functions for each type.
Intermission: this borrows a lot from Sean Parent's talk at C++Now, where he goes about it in greater detail. If you haven't yet, watch his talk on YouTube
We change the previous listing and remove the template function "print" and instead we add the following:
Now we've gotten two things working together: type erasure (we see object_concept_t, embodied as an abstract type, and an opaque object_t type that can hold different kinds of objects that can be printed) and static dispatch -- the compiler knows exactly which "print" to call at the top level. Let's re-examine our earlier questions here:
- Can we treat instances of object_t as we do int's? Yes!
- We have types that model the Object concept, can I treat each one as I would an Object? Yes!
- Can we put objects of types that model the Object concept in the same container? Yes!
The good part about this approach is that when you have a new type that has a "print" function, you can suddenly add instances of the same type (so long as it's copy+move constructible+assignable) to the container above. This is powerful because now you're dealing with values exclusively -- instances of object_t have value semantics.
If you look closely though we're still relying on the compiler's vtable implementation because we still have virtual functions in object_concept_t. Can we get rid of those?
That's the subject of the next post. Hopefully you've gotten enough in this post to chew on and discuss going forward. I invite you to consider thinking about whether this can be useful in your codebase so that you can better leverage value semantics and get the benefits of type erasure as well as concept-based design. Do you think it would be nice if you never had to do inheritance-based polymorphism when you're designing your classes? How much easier would it be to extend your programs using this approach?
I've love to know what you think in the comments.
Thanks for reading!
Read the complete post at http://feedproxy.google.com/~r/CppSoup/~3/ZnaO0dumMpI/different-forms-of-polymorphism.html
11-09-2012 8:54 AM