Welcome to the Modern Embedded Systems Programming course. My name is
Miro Samek and in this lesson I continue the subject of Object-
Oriented Programming. Today you will learn about the concept of 
*polymorphism* and you will see how it works in C++ and how to 
emulate it in C.

Unlike the previously discussed notions of encapsulation and 
inheritance, polymorphism is a uniquely object-oriented concept that 
has no direct analog in a traditional procedural language like C.
Therefore the plan for today is reversed compared to previous two 
lessons in that you will first see what poloymorphism is and how it 
works in C++, and only with this knowledge you will see how to 
emulate it in C.

So, let’s get started today by making a copy of the previous lesson 
30-understcore-cpp directory and renaming it to lesson 31-underscore-
cpp.

Get inside this new directory and double-click on the uVision project
"lesson" to open it.

To remind you quickly what happened so far, in the last lesson you 
learned about the concept of class inheritance and you’ve created a 
Rectangle class that inherited all attributes and operations from the
Shape base class.

But Rectangle also added its own attributes and operations, such as 
the draw() operation to draw the Rectangle on an LCD screen and the 
area() operation to calculate and return the surface area of the 
Rectangle.

However, both added operations actually make sense for the Shape base
class as well, because any Shape could be drawn on the screen and has
a surface area.

The only problem is that the Shape class is so generic that you don’t
really know *how* to implement the draw() and area() operations at 
this high level.

But by now you probably have noticed that object-oriented programming
is all about separating the *interface* – the “What can be done” from
the implementation – the “How it is done”. So in this spirit, the 
Shape class could at least provide an *interface* to the draw() and 
area() operations and worry about the implementation later.

So, let’s have a look at how it could work.

Let’s at first simply copy the area() and draw() signatures from the 
Rectangle subclass to the Shape superclass.

Let’s also copy the implementation of these operations from Rectangle
and adapt it to Shape. 

Of course at the high level of the generic Shape class, you cannot 
provide real implementations because you don’t yet know if you are 
dealing with Rectangles, Circles, Triangles or Lines. So you provide 
only some dummy code.

But now, when it comes to testing this new Shape interface, in the 
last lesson you learned about *upcasting*, which is casting a derived
class to the base class. This is always safe and object-oriented 
languages like C++ perform such upcasting automatically without 
complaining. 

This opens an interesting option of upcasting a pointer to a 
Rectangle object “r1” to a pointer to Shape “ps” and then calling the
draw() and area() operations on such an upcast pointer.

As you can see, this compiles error and warning-free, so let’s check
in the debugger which operations are called in this case.
And as I step into the call, you can see that... the Shape’s 
implementation is called, which is rather unremarkable, because the 
compiler evidently chose the function corresponding to the type of 
the pointer, not the type of the object.

But, let’s go back to the code and modify the declaration of the 
Shape class by adding the *virtual* keyword in front of the draw() 
and area() operations.

With this change, the compiler raises some warnings, but let’s ignore
them for now and just open the debugger.

This time around, as you step into the draw() operation... the 
Rectangle’s implementation is called.

The same happens for the area() operation call as well.

This means that all of the sudden, the calls select implementations 
based on the type of the object, which is Rectangle, not the type of 
the pointer, which remains Shape.
This is *polymorphism* in action.

The term “polymorphism” itself comes from the Greek roots “poly” 
meaning many and “morphe” meaning form. So polymorphism means 
multiple forms.

And indeed this what’s happening here. The same operation, such as 
draw() or area(), can take multiple forms, depending on the type of 
the object that the pointer happens to be pointing to.
This is all good and perhaps interesting, but what is polymorphism 
good for in practice?

Well, among other things, polymorphism allows you to write generic 
code at a higher level of abstraction than you could without it.

For example, suppose that you want to draw a graph consisting of 
multiple Shapes on your LCD screen. For simplicity, suppose that a 
graph is an array of pointers to various Shape objects. 

Note that the Shape pointers in a graph might actually point to 
different types, but because all of them inherit the Shape base 
class, all can be safely upcast to the Shape type.

Now, you can declare a generic function drawGraph() at the Shape 
class level.

And implement it in shape-dot-cpp. 

The darwGraph() function simply loops over the Shape pointers in the 
graph array until it encounters a zero pointer.

The pivotal point of the implementation is the graph[i]->draw() call 
that employs polymorphism to correctly select the draw() 
implementation depending on the type of the object, not the type of 
the pointer, which is evidently Shape.

Now, it’s time to address the compilation warnings that the draw() 
and area() declarations in the Rectangle class implicitly inherit 
virtual.

The warnings appeared after adding the “virtual” keywords in the 
Shape base class and as you saw in the debugger, this has turned on 
polymorphism with respect to the draw() and area() operations.

But, polymorphim means that the draw() and area() operations in 
Rectangle are not completely new operations added in that subclass. 
Instead, they are merely different forms (or different *methods*) of 
the draw() and area() operations specified already in the Shape base 
class and inherited from it.

So, to introduce some object-oriented terminology here: *methods* 
describe the different forms of the same operation and the different 
methods in the subclasses are said to *override* the original method 
inherited from the base class.

But going back to the code, the compiler noticed that the draw() and 
area() operations in Rectangle are just different methods of the 
operations already declared in the Shape base class. As different 
methods of the same operation they are automatically virtual, meaning
polymprphic, so the compiler strongly suggests to make these methods 
explicitly virtual.

And indeed, adding the keyword virtual to the draw() and area() 
declarations in the Rectangle subclass gets rid of the warnings.
OK, so with this out of the way, I’m sure you are interested how your
high-level drawGraph() function will perform, so let’s quickly test 
in main-dot-cpp.

First, declare an array of Shape pointers, which could be const,
and initialize it with, say:
pointer to the Rectangle r1 and
the pointer to dynamically allocated Shape ps3.
You need to terminate the array with a zero pointer.

Now, you can simply call the drawGraph() function on this graph 
array.

The project builds cleanly, so let’s move the breakpoint to the 
drawGraph() function and open the debugger.

When you step into the drawGraph() implementation, you can see that 
the first graph-of-i-draw() operation invokes the Rectangle::draw() 
method for r1 as the “this” pointer.

The next graph-of-i-draw() operation invokes the Shape::draw() method
for ps3 as the “this” pointer.

Then the loop finds the zero-pointer and terminates.

So, as you can see, the drawGraph() function does exactly what it was
supposed to do in a very simple and intuitive way.

But, to let you fully appreciate the extensibility of the design 
based on polymorphism, let’s create another subclass of Shape, such 
as Circle.

The Circle subclass is similar to Rectangle, so let’s just copy 
rectangle.h and rectangle.cpp and rename to circle.h and circle.cpp, 
respectively.

Quickly add the new circle files to the project and adapt them.
In the header file, simply rename the inclusion guards and the class 
name.

The change in attributes is to replace with and height with radius of
a circle.

The Circle constructor takes r0 as the initial value of the radius.

The Circle class also needs to provide its own specialized methods 
for the draw() and area() operations inherited from Shape, so the 
virtual declarations stay the same.

Now, in the implementation, you include “circle.h” and again replace 
the class name.

The constructor takes the r0 parameter and uses it to initialize the 
radius attribute.

The Circle’s method for the draw() operation will call the primitive 
drawEllipse() function.

Finally, the Circle’s method for the area() operation will calculate 
the area of the circle as pi times radius squared. For simplicity 
here, I will use only integer math and I’ll approximate the pi to 
three.

With the Circle class complete, the last step is to test it in main-
dot-cpp.

You include circle-dot-h header file and instantiate a Circle object 
c1 with the given values for x, y, and the radius..
Then you add pointer to c1 to the graph array so that the Circle c1 
becomes part of the graph subsequently drawn by the drawGraph() 
function.

When you build the project, please note that only circle-dot-cpp and 
main-dot-cpp have been re-compiled. But specifically, shape-dot-cpp 
with the drawGraph() algorithm has NOT been recompiled. This means 
that the final image in this case uses the drawGraph() implementation
compiled before introducing the Circle class.

When you run the program now and step into the drawGraph() function, 
you can see that it calls…

the correct Circle::draw() method for your c1 object as the “this” 
pointer.

The other graph-of-i-draw virtual calls invoke the correct methods 
for the Rectangle r1 and Shape ps3. 

So, as you can see, all this still works as expected. But wait a 
minute, the drawGraph() function has been written and compiled before
the Circle class even existed. Yet, the algorithm automatically 
adapted and recognized the newly added class.

I hope this shows you the power and *extensibility* of polymorphism, 
but also that the virtual call mechanism must be quite different than
the regular function call.

So, let’s now see how virtual call really works. 
For this, let’s add a regular function call right before the virtual 
call to compare the two.

Please note that an operation invoked on a full object, like the 
Rectangle r1, is always a regular, non-virtual function call, even 
though the operation itself might be declared virtual. This is 
because the exact type of the object is know at compile time. 
Incidentally, the connection between the function call and function 
body is called “call binding”. 

The connection established at compile and link time is called “early 
binding”. This is the only call binding used in the procedural 
languages like C.

But in C++, a virtual operation invoked on a pointer, like ps here, 
establishes a different call binding, because the exact type of the 
object is not known at compile time since the pointer might be 
actually upcast from a derived class. This type of binding is called 
“late binding”, “dynamic binding”, or “real-time binding”.

All right, so let’s build the project and move the breakpoint to the 
early binding call to finally see how it compares and differs from 
the “late binding”.

When you launch the debugger and continue to your breakpoint, in the 
disassembly view you can see that the early binding call consist of 
moving the value of the “this” pointer into R0 and then using the 

Branch with Link, BL-instruction, to call the Rectangle::draw() 
function hardcoded in the BL instruction itself.

And indeed, when you step into the BL instruction, you end up in 
Rectangle::draw() function body. While you are at it, notice the 
address of this function in ROM, which is hex-250C.

Now, when you return back to main-dot-cpp, you can see that the late-
binding machine code is significantly different than the early 
binding right before it.

It all starts with loading a 32-bit word from R6, which is later used
as the “this” pointer in R0, so this 32-bit word must be coming from 
the “this” object.

This word is subsequently used as the base address, so the word from 
the “this” object is a pointer itself.

But wait a minute, *you* certainly didn’t add any pointer attributes 
to the Shape or Rectangle classes.

So, let’s take a closer look at the “this” pointer in RAM.

And indeed, you can recognize the 16-bit attributes x, and y, 
inherited from Shape as well as width and height added in Rectangle. 
But now all this is preceded by a pointer which apparently was added 
by the C++ compiler when you introduced virtual functions in the 
Shape base class. So the overall size of the Rectangle object is now 
enlarged by a poiner.

Now, regarding the added pointer inside the Rectangle object, it 
looks like an address in ROM, so let’s see this ROM address in the 
memory view.

When you change the memory view to 32-bit quantities, I hope you can 
recognize that the first word at the ROM address is suspiciously 
similar to the hex-250C, which was the address of the 
Rectangle::draw() function. In fact, it is this exact address plus 
one.

As I explained many times in the earlier lessons of this video 
course, the program addresses in Cortex-M are stored as odd numbers, 
because the least-significant bit is not used for addressing but 
rather is always set to one to represent the Thumb state of the CPU.

So, in short, the first word at the ROM address is the 
Rectangle::draw() function address.

But what about the second word at the ROM address?
Well, lets’ t look for it in the disassembly window, remembering to 
subtract one from the address, which means that you are looking 
for... hex-0002502.

And indeed, this is the address of the Rectange::area() method, which
is the second virtual function of the Rectangle class.

All this reverse-engineering can be summarized as follows:
The compiler has added a pointer at the beginning of the class 
attributes, which points to a table in ROM that contains addresses of
all virtual functions. 

In the literature, the table of virtual functions is called the 
VTABLE and the pointer to it stored in the object is called the VPTR.

But, continuing with the debugging, you can see that the address of 
the Rectangle::draw() function is loaded from the VTABLE into R1 and 
finally the “this” pointer is setup in R0.

The actual function call is performed by the Branch with Link and 
Exchange, BLX-R1 instruction, which jumps to the address provided in 
R1.

And indeed, when you step into the BLX instruction you end up in the 
Rectangle::draw() method.
Here, when you examine the “this” pointer, you can actually see that 
the first attribute of the object slice inherited from Shape is the 
vptr.

So, in summary, compared to early binding, the overhead of late 
binding is the additional VPTR in every object in RAM, one VTABLE per
class in ROM and two more instructions per function call.

This is not a large overhead for what you are getting, but still it 
is non-negligible and therefore C++ applies this mechanism only to 
functions specified explicitly as “virtual”. This is to prevent the 
overhead for functions that don’t need late binding. Other object-
oriented languages, such as Java for example, treat polymorphism as 
such a fundamental feature that all functions are virtual by default.

Also, please note that this VPTR-VTABLE double indirection is just 
one possible implementation of late binding and the C++ standard 
leaves it completely open to the compiler designers. Having said 
that, essentially all existing C++ implementations for wide range of 
CPUs use the VPTR-VTABLE implementation that you just saw.

So, the last remaining question for today is: Who sets the VPTR?

I mean, the constant VTABLE per class in ROM can be easily added just
like the code itself, but the VPTR needs to be set in each and every 
instance of a class, which often are allocated at runtime, for 
example as automatic objects in functions.

I hope that at this point you can guess that the ideal place where 
the VPTR can be established is the class constructor.
But of course, *you* didn’t do anything about VPTR in your C++ code, 
which means that the C++ compiler must have secretly synthesized some
code to do this for you.

As an embedded engineer, I’m sure you must be especially curios abut 
any such secret code,

so let’s set a breakpoint in the Rectangle constructor, for example, 
and start the debugger.

The breakpoint is hit right away, because there is a statically 
allocated instance of Rectangle, which is initialized even before 
main.

When you expand the “this” pointer, you can see that the vptr is 
still not initialized.

So step in, and you end up in the Shape’s constructor, which is 
invoked from the Rectangle’s constructor initializer list.
The “this” pointer now changes type to Shape, but the vptr is still 
not initialized.

Now, looking at the disassembly, you can see two lines of machine 
code that apparently set the VPTR.

But wait a minute, which VTABLE is it pointing to?

Well, you can inspect the VTABLE in the memory view.

Take for example the second entry in the table and locate it in the 
disassembly. 

As explained before, you need to subtract one from the address in 
VTABLE, so you are looking for hex-000024EA. 
And, you end up in Shape::area() method, which means that the VTABLE 
belongs to the Shape class.

So, at this stage of initialization the Rectangle instance is still 
treated as its Shape base class.

But let’s continue stepping through the initialization of the Shape’s
attributes and return back to the Rectangle’s constructor. 

Here, in disassembly, you encounter similar instructions that 
apparently re-initialize the VPTR to a different value.

So again, let’s find out from the memory view which VTABLE this is by
inspecting its second entry.

Now, you are looking for the address hex-00002502.
...and, you end up in Rectangle::area() method, which means that the 

VTABLE now belongs to the Rectangle class.
So, as you see, the VPTR is initialized and re-initialized in every 
constructor to point to the VTABLE of that class. But the order of 
constructor calls is such that the superclasses are always 
initialized before subclasses, so the VPTR ends up pointing to the 
last derived class, which is correct.

This concludes this quick look at polymorphism in C++. In the next 
lesson, you will put your understanding of virtual functions to the 
test by implementing late binding in C. 

If you like this channel, please give this video a like and subscribe
to stay tuned. You can also visit state-machine.com/quickstart for 
the class notes and project file downloads.