In the last several videos, we have
discussed code generation for a various
simple programming language. In this
video, we are going to take a look at code
generation for more advanced feature
objects. Fortunately, this dated code
generation strategy for objects is really
just an extension of what we've already
learned. So, everything that you learn
before we're going to be using and then
there's going to be some additional things
that we do specifically for objects And,
the important thing to know about objects
is slogan that you hear. When people
talked about object oriented programming
is this one. So if b is a subclass of a
then an object of class b can be used
wherever an object of class a as expected.
So there's a substitutability property. If
I have a piece of code that can work on
a's then it could also work on b's and any
other subclass of a. What this means for
the, for the case of code generation is
that the code that we generate for class
a. So, the code that we produced for
method in class a, has to work unmodified
for an object to class b And to see this,
keep in mind that when we compile a, when
we compile class a, I, we may not even
know all the subclasses of a. So, those
maybe not even have been defined yet. So,
in the future some programs may come
along. To find a subclass of a then our
compiled version of a will have to work
with that new subclass. So, there really
only two questions that we have to answer
to give a complete description of how to
generate code for objects. The first one
is how our object represented in memory.
So, we need to decide a layout and
representation for objects And the second
one is how is dynamic dispatch implemented
so that's the characteristic feature of
using objects just so we can dispatch in
the method of an object and we need an
implementation of that. So, to be
concrete, we're going to use this little
example throughout this video and I'll
just take a moment here to, to point out
some features of it. So, we have three
classes, classes am b, and c And notice
that a, is a base class and b and c both
inherit from a, And all three classes
define some attributes, some fields and
also some methods. Now, a couple of
important features here is that notice
that because b inherits from a, and c
inherits from a, they all, they both
inherit, both of those classes inherit the
attributes a, and d from class a. So these
two attributes that are defined in class a
are available in class b and in class c So
even though there's no mention Of a, and d
in the definition say of class b. The
methods in class b can still refer to
those attributes. They are part of the
attributes of class b. They are just
copied over or inherited from a. Another
feature of this example that I like to
point out is that all of the methods refer
to the attribute a so actually referred
into this method and this one referred
twice in this method and also in this
method. And the significance of this is
just what we discussed a couple of slides
ago. For all of these methods to work
attribute a, is going to have to live in
some place and some place where all of
them can find it they generate a code run.
Some particular less considered the method
f. So the method f exists in all three
classes. All three classes when it runs,
it will refer to attribute a, and even
though the objects would be different. In
one case it might be running on an object
and in another case on a c object. It
would need to be able to find the
attribute a, and so therefore the
attribute a, has to be in the same place
in each object And so, how do we
accomplish that? Well, the first principle
is the objects are laid out to in
contiguous memory. So, an object is just a
block of memory. Okay with no gaps and all
the data for the object is stored in the
words of that lock of memory. And each
attribute is stored at a fixed off set in
the objects. So for example, there may be
a place in this object for attribute a On
this case it's at in the middle of the
object is in the, in the fourth position
And, no matter what kind of object it is,
whether it's an a. B or c objects and are
example as with a we always live with that
position so that any piece of code that
refers to a, any method that refers a can
find can find the a attribute. Now the
other thing that's important to understand
and this is you know slight digression
from what we're talking about but it's a
key aspect of code generation for object
is that when a method is invoked, the
object itself is the self parameter. So
the self parameter is the entire object so
self. When a function is involved, it will
refer to the entire object so you think
itself is going to be appointed to the
entire object. Remember that self is like
that this variable or this name in Java.
And then the fields we refer to particular
or the attributes of the object will refer
to particular position within the objects.
So, for example, the attributes, we
decided to leave it there. So here is the
particular object layout used in Kuhl. So
the first three words of a Kuhl object
contain header information and every Kuhl
object always has these three entries. The
first position is a class tag and also at
zero then the next word it also four is
the size of the object and then something
called the dispatch pointer and then all
of the attributes. Now the class tag is an
integer which just identifies the class of
the object. So the compiler will number
all of the classes. So in our example we
have three classes a, b, and c and the
compiler for example might assign them the
numbers one, two, and three. It doesn't
matter what these numbers are As long as
they are different from each other. So, it
doesn't have these numbers consecutively
or anything like that The important thing
is of the class tag is a unique identifier
for a class, each class has its own unique
bit pattern that tells you what kind of
class the object is And the other fields
here the object size is also an integer
which is just a size of the object in
words and the dispatch pointer. Is a
pointer to a table of methods so the
methods are stored off to the side and the
dispatch pointer is a pointer to that
table and we'll talk about this more later
and then all the attributes are laid out
in the sub-sequence slots in some order
that [inaudible] the compiler so the
compiler will fix and order for the
attributes in the class and then all the
objects of that class will have the
attributes of that class in the same
order. And again all of this is laid out
in the continuous chunk of memory. Now,
I'm ready to talk about how inheritance
works. So, the basic ideas like given a
layout for class a, a layout for a
subclass b, so this is a subclass of a can
be defined by extending the layout of a.
So, we don't need to move any of the
attribute of a, we can just add more
fields onto the end of a's layout. And so,
that's going to leave the layout of a
unchanged which is a great property
because this is how the position of an
attribute in the a object will always be
the same for all the subclasses. So
essentially, we will never, once we decide
where an attribute lives in a class it
will never change for any of the
subclasses of that object. So b is just
going to be an extension of the layout of
a. So, let's take a look at our example
here and see how that, that works. Let me
just write down here a little bit about
these classes because we don't have the
example on the screen. So we have a class
a, and class a, had two attributes, a, and
d, okay? And it doesn't matter what their
types are or what the methods were here.
We're just looking at the class names and
the names of the attributes that are
defined in the class. And then we have b.
Which inherits from a and b added a
attribute b and then we had c which also
inherits from a but has no relationship to
b. And class c define an attribute little
c. Alright. So, that's the structure of
our example is relevant to the layout of
the objects. Okay. So Let's talk about the
layout of class a. So, in position zero at
all sub zero, there'll be a tag for a that
will be some small integer at the compiler
picks. There'll be a size of a, we'll come
back to that in just a se cond. There will
be a dispatch pointer again, which we're
going to talk about later. And then come
the attributes of a, and it just laid out
the compiler, the way it's done in the,
the Kuhl c implementations is that they
are laid out in the order in which they
appear textually in the class. So, in this
case, first the attribute a, And then the
attribute d all sets twelve and sixteen
And now since the object, there are two
attributes and three header words that
means the size of the object is five words
and so it's a five that goes in the size
field for a objects. Now, let's take a
look at b. Okay? So b is going to have a
different tag, b objects will have a
different tag so they to distinguish them
from a objects. There's going to be extra
fields so the size will be one bigger But
now the layout preserves the layout of a.
So the attributes of a appears in the same
position. So you can think of there being
an a object Actually embedded inside of
the b object. If I were to strip off the
end here that were just you know cover up
this last bit here b I would say that this
object here has the same size and the same
attributes as an a object so any piece of
code that could work on an a object will
also make sense running on a b object. Now
Of course, the tag is different because it
actually is a subclass and you know, and
there is an extra field so the, the size
is different but the point is that any
code that it refer is just to the fields
here will still work just fine. So any a
method that was compiled that refer to the
methods of an a object will still find
those attributes in the same place at the
b object and afterwards, there is also one
more field here. Which is the new
attribute b It just gets laid out after
all of a's fields. So after all of a's
fields come all of b's fields in the same
order which they appear textually in the
class because there's just only one,
there's just one new field there. And now
looking with class c or the story with
class c is very similar so c has its own
distinct tag and also has one more
attribute than a so it has size six. And
now again the a attributes were on the
same position and now the c attribute just
comes after the a attribute. And so notice
here that a methods again will work just
fine on c objects because the attributes
are on the same places and so the methods
will find the attributes where they expect
to. You cannot however call a method of
class b on an object to class c. Okay
because they have different attributes in
the third position. We may have completely
different types. It may not make sense to
invoke a b method on c object but that's
just fine because if we look in our
[inaudible] over here we'll see that b and
c are actually unrelated. They are both
subclasses of a but they have no
relationship to each other. B is not a
subclass of c and c is not a subclass of b
and so anything beyond their shared
ancestry with a can be completely
different in the layout. So, more
generally, if we have a chain of
inheritance relationship, so let's say, we
have a base class a1 and a1 inherits some
a1 and a3 inherits some a2 and so on with
some class a and inheriting at the bottom
of this of this chain after some long
sequence of, of other intermediate. Some
classes, you know, what is the layout of
all these classes going to look like.
Well, there's going to be a header. Okay,
the three word header and that will be
followed by a1's attributes. And then
followed by a2's attributes followed by
a3's attributes and so on all the way down
to an's attributes down here. Okay. And if
you look again so what we talked about
before each prefix. Of this header is
essentially a valid object a valid one of
these objects. If I look at the first set
of attributes, everything up to the end of
a1 and attributes, that forms a valid
layout for one object is I stop with the
a2 attributes. I have a, I have a, I have
a valid layout for a2 object going all the
way from the header down to you know,
including the a1 and a2 objects. And then
a3 includes all a1, a2 and a3's attributes
and so on. Okay? So, each prefix Of, of
this object, Of this a and object has a
correct layout for some for some super
class of a. Not that we dealt with the
layout of an object's attributes, we can
switch gears and talk about how we layout
its methods and how we implement dynamic
dispatch. So, let's consider a dispatch
called e.g where e here, let's say, is a
class b. Okay? So what do we wanted to
have happen? Well, we want to invoke the g
method here in class b, okay? So that
seems pretty straight forward. So now
let's consider a slightly more complicated
example. What if we are invoking e.f of if
we're calling the f method? Well, if we
have a b object. Then we are going to want
to evoke this method, this f method, okay,
which is the f method to find in b. But if
we have an a object, we want to be sure
that we invoke this method, okay, this
version of f. Alright, and so, this f down
here is said to be overridden. Okay. So,
we have redefined. Method f in class b and
this definition replaces the method
definition that b would otherwise have
inherited from a so in particular in class
c, class c also have an f method okay and
if we invoke the f method, if it turns out
that e here is a type c then which method
should get involved? Well it would be this
one. It would be the one defining class a
so all three of these classes has an f
method. If the, if we do a dynamic
dispatch on either a c or a object or
execute the one defining class a. If we do
the dispatch on the b object, we will
execute the method defined in class b. Now
every class has a fixed set of methods
including the inherited methods. So if
you, if you look, if I tell you the name
of a class, then you know exactly which
methods it has. Those methods never change
at runtime. Okay? So don't be confused
here because overriding is something
that's done at compile time is basically a
static property. South compiler can figure
out even though you can redefine methods
in subclasses the compiler can figure out
a compile time all the methods of a
particular class. Methods never change
while the prog ram is executing. Alright
So, a dispatch tape of there's a table of
some sort is used to index these methods
and this is just in the ray of method
entry point. So, essentially for every
method of the class there's an entry in
the ray for that method. And just like
with attributes, the method f is going to
live at the fixed offset. In the dispatch
table for a class and all of its
subclasses so once we determine the
position that a method lives in. It lives
in the dispatch table; it will stay there
for any subclasses of that class. So let's
take a look at our example again and just
a reminder the structure of the example we
have class a and now we only really care
about the method so class a define an f
method and then we have class b which
inherits from a. And that define the g
method. And then there was the class which
also inherits from a which defines an h
method. Alright so those three classes and
these methods, Okay? And so the dispatch
table for class a only has one method in
it so it's also at zero. We store a
pointer to the code for the f method
define an a, okay? So this is actually
literally just a pointer to the first
instruction of the code that will run
method a. So this is a pointer to the
caller side or the calling sequence or the
label labeled instruction as the entry
point for the method. Now, what about
let's take a look next actually at class
c. Okay? So class inherits from a. So
what's going to happen with all the
methods of a and they're going to be at
the same off sets. So in particular, the f
method will appear at offset zero in class
and this points to the same method as the
one in a And so this inherits that method
from a and then class c defines its own
method h and so in the next position of
the table goes the pointer to the code for
h. And, you know, there have been more
methods defined in this classes than they
would have appeared you know, laid out in
textual order just like for the
attributes. So, if there have been, say,
two methods defined in a, then there will
be two entries here fo r the first method
and the second method define an a and then
c define a three method then there will be
three more entries in the table and so on.
Okay. Now the interesting case is what
happens in class b. So in class b the f
method is redefined and I forgot to
indicate that so let me just indicate that
up here so the f method, we have a new
definition of the f method in class b.
Okay so the important thing to see here is
that the pointer to the code for the f
method lives in the same position. It's
still the first entry in the table, okay
so the position of the f method in the
dispatch table for class b is exactly the
same that never changes. What's difference
is just the contents of that location. The
first entry in the table here points to a
different function. It points to the
method that was defined in b instead of
the one that was defined in a. And then
since b defines some additional methods or
one additional method that gets laid out
after the methods for a. You may recall a
while ago that we talked about the object
header and we mentioned this thing called
the dispatch pointer so this would remind
ourselves what goes in the object header.
There is the tag and then there is the
size and then there was a dispatch pointer
so And then following dispatch pointer
where all the, all the attributes of the
class And now this dispatch pointer is
just a pointer to the table of methods for
that class, okay? So this would be a
pointer to the table. That contains all
the entries for the methods, all the entry
points of the methods for that class. And
the reason for using this level of in
direction and so, why do we have this
pointer to a separate table and so, why
are the methods laid out like that when
all the attributes are just embedded
directly in the class And we could, if we
wanted to just embed all the functions
directly inside the object and, ad, you
know, out this whole table inside t object
and, and not have this extra pointer that
we have to, we have to maintain and follow
And in the reason for this is th at the
attributes are, can be updated. Okay, So,
the attributes for a and object can be
unique object. Every object and have its
own set of attributes so alright But the
functions, the methods for an object never
change. And so the same object table can
be shared Between all the objects of a
given class. So if I have 100 a objects
well then I might have 100 different
version of the attributes and so each a
objects has its own copy of the
attributes. But all those 100 a objects
will have the same methods and I can save
a lot of space by having them share a
common table of the methods And again
every method of the class or every class
is a sign and offset and we'll call that
Os of f. In the dispatch table compiled
times. So the job of the compiler to
figure out all the methods of the class
and then assign each of those methods, a
fixed position, a fixed offset in that
dispatch table, So to wrap up, how do we
implement dynamic dispatch? So let's say
we have a dispatch to an expression e and
we're calling the f method. So, here's
the, a slightly simplified version of the
sequence of steps. So first, we evaluate
the expression e and that's going to give
us back an object x. Okay, and then we are
going to get the dispatch table for x,
where that does come from. Well, it's in
the header of x so we can just take the
object x itself and we know that in every
object at the, in the third word there is
a dispatch pointer for the, that's
appropriate to the class of x. So, we take
that table and then we look up the entry
point of f at the offset For f in that
dispatch table And then we'll jump to that
to that address, okay? That's the entry
point of the function and, and when we do
that, we're buying self to x. So the, the
self parameter inside of the f method will
be the x object.