SI413: OOP a la languages like C++ and Java

Reading

These notes!

Homework

Do hw.

OOP

Object oriented programming (OOP) has four central ideas: encapsulation, data hiding, inheritance and polymorphism. We are doing to focus on encapsulation, inheritance and polymorphism, and specifically focus on how they are implemented in languages like C++ and Java. Remember that an "object" in OOP is a collection into a single package of related pieces of data and functions operating on that data.

Structs in languages like C++ and Java

First we need to discuss how data gets packaged together in languages like C, C++ and Java. Let's just look at a simple struct/class definition like this:

class Foo	
{
  int i;
  int j;
  double y;
};

In this case we need at least 16 bytes, because each int takes 4 bytes and the double takes 8. The bytes for the fields are typically laid out sequentially, in the order fields appear textually in the class definition. So for Foo, the first four bytes are i, the next four are j, and the last eight are y.

So the compiler/interpreter will keep track of the offset of each field in the struct/class. If you access a field, the compiler will know its type (and thus how many bytes) and its offset within the object, so it can compute exactly which bytes belong to that object. The example below shows how the compiler really transforms field access within structs to nothing more than pointer arithmetic with offsets and some type casting.

class Foo	    Offset     Example code    As the compiler sees it: pointer to f + offset, cast to the proper type
{                              Foo f;          note that "unsigned char*"  means pointer to a raw byte
  int i;            0          f.i = 7;        *(int*)((unsigned char*)&f + 0) = 7;
  int j;            4          f.j = 42;       *(int*)((unsigned char*)&f + 4) = 42;
  double y;         8          f.y = 0.357;    *(double*)((unsigned char*)&f + 8) = 0.357;
};

If you don't believe me, you can try this little experiment. Compile and run the code below, and you will see that the fields are assigned their proper values using the "pointer to f + offset, cast to the proper type" method:

ex1.cpp	running
	$ g++ ex1.cpp $ ./a.out 7 42 0.357

A quick note on the reality of the placement of fields

For efficiency reasons, compilers typically prefer to align N-byte objects to start at memory locations with addresses that are zero mod N. For example, doubles start at addresses that (in hex!) end in either zero or eight, whereas ints start at addresses that (in hex!) end in 0, 4, 8 or C (note that C=12 in hex). This means that the layout of fields in objects might leave gaps of unused memory.

ex1a.cpp	running	discussion
	$ g++ ex1a.cpp $ ./a.out sizeof(f) = 16 0x7ffc208ee160 f 0x7ffc208ee160 f.i 0x7ffc208ee168 f.y	First notice that the size of a Foo object is 16 bytes even though one 4-byte int and one 8-byte double should only take 12 bytes. Second notice that the the address shows that the int i occupies the first four bytes of the Foo object (the address of f and f.i are the same), and the double y occupies the final eight bytes. This leaves a 4-byte gap between them! This gap occurs because the compiler wants to align the 8-byte double on 8-byte boundaries --- i.e. it wants addresses ending in either 0 or 8. That forces a gap.

Of course these issues of alignment are not usually something we think much about, but when you want to be as efficient as possible with memory, you might have to take it into account!

Methods (aka member functions): part 1, the non-polymophic case

In this section we'll examine how methods (aka member functions) are implemented in languages like C++ and Java in the case in which there is no polymorphism. Suppose we have something like this:

class Foo	
{
public:
  int i;
  int j;
  double y;
  int bar() { i++; return j; }
};

... where there is no inheritance and thus no polymorphism to worry about. The method "bar" is different from normal functions because it has access to the fields of the object on which it was called. For example, if we have Foo f and call f.bar(), the "bar" function will access f's i and j fields. We handle this by rewriting methods to add a pointer to the object on which the method was called as the first parameter to the function. In the above example, we would rewrite bar as:

Of course we know that, in reality, int bar() { i++; return j; } would be rewritten like this:

int bar(Foo* this) {	  
  *(int*)((unsigned char*)this + 0)++;
  return *(int*)((unsigned char*)this + 4);
}

Here's a sligthly prettier version of the same thing:

int bar(Foo* this) {	  
  unsigned char* ptr = (unsigned char*)this;
  int* iptr = (int*)(ptr + 0); // offset 0
  int* jptr = (int*)(ptr + 4); // offset 4
  *iptr++;
  return *jptr;
}

int bar(Foo* this) { this->i++; return this->j; }

Additionally, each method call would have to be rewritten as well, so that for example:

f.bar() is rewritten as bar(f)

In this way methods (aka member functions) and method calls are nothing more than syntactic sugar: we can systematically rewrite them as normal function definitions and normal function calls. At least for "final" methods in Java or non-virtual member functions in C++ (i.e. when there is no polymorphism) this is how things work.

If you look at the "prettier" rewritten version of bar to the right, you see that bar picks out the fields of the object based solely on offsets from the "this" pointer. That's important!

Inheritance

The fundamental problem with inheritance is that code that works with objects of the base class should also work with objects of the derived class types. Let's continue with the class Foo from the previous section and derive from it a new class Foov2

class Foov2 : public Foo    //-- in java we'd write: class Foov2 extends Foo
{
public:
  bool tag;
  void rat() { cout << y << tag << endl; }
};

... and let's suppose that we instantiate a Foov2 object and set some of its fields and call some of its methods

Foov2 f2;
f2.i = 42;
f2.j = 23;                   <--- How does any of this work?!?!?
f2.y = 3.5;
f2.tag = true;
cout << f2.bar() << endl;
f2.rat();

Let's do a deep dive and see how this might actually work.

How are the fields in an object of the derived class laid out?
The layout of the derived class is simple: the compiler concatenates the object layout of the base class with the layout for the new fields of the derived class. That means that field "bool tag;" will just be stuck on the end of the i,j,y fields, which are laid out just as they are for class Foo on its own.

Let's see this borne out in code.

ex2.cpp	running
	$ g++ ex2.cpp $ ./a.out sizeof(f2) = 24 0x7ffe4b8062f0 f2 0x7ffe4b8062f0 f2.i offset 0 0x7ffe4b8062f4 f2.i offset 4 0x7ffe4b8062f8 f2.y offset 8 0x7ffe4b806300 f2.tag offset 16

We know that getting/setting fields is really just done by offsets from the "this" pointer, and now we know that those offsets are enchanged for the fields inherited from the base class.

How do calls of methods from the base class work on objects of the derived class?
Let's consider the method bar() from the base class. As we saw, that method definition is actually syntactic sugar. It is rewritten as something like this:
```
int bar(Foo* this) {	  
  unsigned char* ptr = (unsigned char*)this;
  int* iptr = (int*)(ptr + 0); // offset 0
  int* jptr = (int*)(ptr + 4); // offset 4
  *iptr++;
  return *jptr;
}
```
Now if we execute this code with a pointer to a foov2 object as its argument, like "bar(&f2)", what happens? Well: f2->i sits at offset 0 and f2->j sits at offset 4, so ... the function still works perfectly. It is blissfully unaware that at offset 16 from &f2 there is more data that pure Foo objects wouldn't have. It never looks beyond the offsets of fields in Foo objects.
So inherited methods simply work without any extra shennanigans purely as a by-product of the way new fields of the derived class are contatenated onto the field of the base class.
How do new methods in the derived class work?
So how do new methods of the derived class work? Hopefully the preceeding discussion makes it clear. They work just like the methods from the base class work, except that they may reference fields from the derived class (i.e. offsets beyond the area of memory in which the fields of the base class live).

Methods (aka member functions): part 2, polymorphic functions!

So now we get to the last issue: how do polymorphic function calls work? C++ and Java handle polymorphic calls similarly from an implementation perspective. From a programmer's perspective, an important difference is that functions are polymorphic by default in Java (but you can turn it off by marking a method "final"), but in C++ functions are by default not polymorphic (though you can turn it on by marking a method "virtual"). So let's make the function bar() in class Foo polymorphic, and let's override it in class Foov2. We'll set it up so that if there are no command-line arguments, pointer p points to a Foo object, and if there are command-line arguments pointer p points to a Foov2 object. Here's the source code (split into two parts):

ex3part1	ex3part2

So now we'll run this program twice, once with no command-line arguments and once with command-line arguments.

compile

run1

run2

$ g++ ex3.cpp

$ ./a.out 
p->bar() = 23
sizeof(*p) = 24
0x7fffbab96040 p
0x7fffbab96048 p->i   offset 8
0x7fffbab9604c p->i   offset 12
0x7fffbab96050 p->y   offset 16

$ ./a.out dummy
p->bar() = 42
sizeof(*p) = 24
0x7ffe61eea620 p
0x7ffe61eea628 p->i   offset 8
0x7ffe61eea62c p->i   offset 12
0x7ffe61eea630 p->y   offset 16

This is the prototypical polymorphic function call. We have one call site in the code -- p->bar() -- and sometimes that call site results in Foo's bar() function getting called, and other times it results in Foov2's bar() function getting called. That decision, note, is a runtime decision. The compiler doesn't know which version of bar() will be called, and it can change from run to run (or in other examples where we have loops, it can change within a single run of the program).

Important: The secret to how this is implemented hinted at by the other output of this program. Did you notice that the offset of field i, the first field in the Foo object, jumped? It went from offset 0 to offset 8. Why? And what do you think the compiler is doing with those first eight bytes in a Foo object?

Because we have marked bar() as "virtual" in class Foo, the compiler has to handle polymorphic function calls, and the extra eight bytes that have been inserted into the front of Foo objects is integral to how this is done. Those first eight bytes comprise a pointer to a data structure called the "vtable" for the class.

If we were to print the value of the vtable pointer for any instance of Foo, it would always be the same. So the vtable is shared by all instances of the class. The vtable pointer for Foov2 instances are all the same as one another, but different from the Foo vtable pointers. So in some sense, the vtable pointer is what makes Foo instances different from Foov2 instances. The vtable contains function pointers for methods at fixed offsets just as the instance contains values for data fields at fixed offsets. When we make the call p->bar() here's what happens:

the first 8 bytes of the memory pointed to by p is read (this is the vtable pointer)
we read the value of the function pointer for our function call from the vtable pointer plus some fixed offset that is unique to bar
we call the function given by that function pointer

So suppose that the fixed offset associated with bar() is 24 bytes. We will read the function pointer at address vtablepointer + 24. Since vtablepointer is different for Foo's than for Foov2's, we get a different function address for Foo objects than for Foov2 objects.

Here's one last demo which, I hope, will drive home this point.

ex4.cpp	running
	$ g++ ex4.cpp $ ./a.out ptr1->bar() = 23 ptr2->bar() = 42 ptr1->bar() = 42 ptr2->bar() = 23

We have ptr1 that points to Foo A, and ptr2 that points to Foov2 X. We call ptr1->bar() followed by ptr2->bar() and see, as we expect, 23 followed by 42. But then we swap the first eight bytes of Foo A and Foov2 X. Now they point to each other's vtables. When we call ptr1->bar() followed by ptr2->bar() again, we see that Foo A is now calling the Foov2 bar() implementation and Foov2 X is now calling the Foo bar() implementation. So by changing the vtable pointer in the instances, we are changing how those polymorphic calls act. BTW: don't ever do something like this in a real program!