In this video we're going to continue and
complete our discussion of cool
operational semantics. We'll be taking a
look with the two most complex operations
in cool, the allocation of the new object
and dynamic dispatch. We'll begin by
giving an informal discussion of what
happens when a new object is allocated in
Kuhl. So, the first thing that has to
happen, if we have to allocate space for
the object and essentially, that means
having enough space for the object
attributes. We're going to have to
allocate a location for every attribute of
the object of class t if what we're doing
is allocating a new t object. Then we're
going to set the attributes of, of that
object to their default values and well in
a few minutes, we'll see what the default
values are and why we need to set the, set
the attributes to defaults. And then we
evaluate the initializers so every
attribute in the class declaration can
have an initializing expression. We're
going to evaluate those and set the
resulting attribute values And then we
return the newly allocated objects. So
these are the steps that are involved in
setting a new object and as you can see
it's actually more than just allocating a
little bit of memory. It's actually quite
a bit of computation going on in
allocating new objects in cool. Every
class has a default value associated with
that class. So for integers, the default
value is zero. For Boolean, the default
value is a Boolean false and for strings,
the default value is the empty string And
then for any other class, that isn't one
of these three basic classes or any other
class, the default value is void. In the
operational rules, we're going to need a
way to repair to the attributes of a
class. So we're going to define a function
called class that takes a class name and
returns the list of attributes of, of that
class. So here we have all the attributes
of class a, let's say that a1 through and
in addition, this functions also going to
tell us for each attribute declared type
of the attribute and the expression that
initiali zes the attribute. And one other
important feature of this list, is that it
includes all the attributes of class a
including the inherited ones. And there's
another detail which is in what order
these attributes appear and these are
actually become important when we define
the semantics of how attributes are
initialized and the rule is the attributes
are listed in greatest ancestor first
order And what do I mean by that? Let's
say that we have three classes a, b, and c
and a, I'm sorry, b inherits from a. And c
inherits. From b. Okay, let's say, that a
defines two attributes, a1 and a2 and b
defines two attributes b1, b2 and c
defines two attributes c1 and c2. Then
class of c. We'll list the attributes in
the following order. First we'll come a1
and then a2 Because a is the greatest
ancestor, okay, it's the, the closest to
the root of the object hierarchy and the
attribute was in class a or within any
class, it's always listed in the order
that it textually appear. So, first comes
a1 and a2 and of course the type in the
initializer are also, let's see here, most
of these attributes but we're just
concentrating here in the order in which
the information appears. So, the next
would come class b. So, the attributes of
class b will be next and of course,
there'll be the type and initialize for
those attributes and then finally the
attributes of class c Again, in the order
in which they are listed in the class
definition, okay? So, that defines the
order of the attributes for any class.
It's always in the order of the greatest
ancestor down the inheritance chain to the
class itself which is the argument of the
class functions. At this point we're ready
to actually define the formal semantics of
new t and let switch colors here. So we're
going to be allocating a new object of
type and is going to be in a context with
self object as zero environment e and
store s. The first thing we have to do
we're going to figure out what kind of
object it is that we're actually going to
allocate and the only question is whether
t is se lf type or not because remember
self type is not the name of an actual
class. If t is not self type then the
class that we're going to allocate is
actually a t. T is actually a class name
and with that, that's the kind of object
that we're going to allocate. If t is self
type then the kind of object we're going
to be allocating. Is whatever the class is
of the self objects? So we're going to
look at the dynamic type here of the self
object called that x and that will be the
class that we create. That will be the
kind of objects that we created, all
right? So there's two possibilities,
Either object, object, allocating an
object of type t if t is actually a class
name. Otherwise it's an object of the same
dynamic type as the self object Alright?
So, now we're going to look up t0 is,
alright. And we get out the list of the
attribute types and initializers for t0.
So, this tells that what we have to do to
construct an object of this type. Alright
and the next thing we do is we allocate
locations for each of the attributes. So,
because they were in attributes, we're
going to allocate n locations. One for
each attribute, all right. And then we're
going to create an object with the class
tag t0 and the attributes are going to be
bound to these new locations. So, the i
attribute will be abound to the i new
location that we just allocated and that
were going to update the store. Okay. So,
we're going to take our initial store and
know this is the same with the store we
started with. We take s and we are going
to update it so that at these new
locations, those new locations hold the
default values of, for the type of each of
the attribute. Okay, and that gives us the
store s1 and now we have to evaluate the
initializer. The two actually, initialize
the attributes. And we have to think about
what the environment is in which those
attributes are initialized and remember
the rule is that within initializer I
mean, attribute, all the attributes of the
class are in scope. Alright, so the
environment in this case for the
initializers will ju st consist of the
initializer or the attributes, excuse me,
themselves. Okay, so these are the
attribute names and the i attributes is
bound to the i's new memory location
holding the value, the default value
initially of that attribute. Alright, and
then finally, to evaluate initializers, we
just evaluate them as a block in the order
which they appear in the class function.
This is why it was important to specify
the order in the class function. So
remember that these attributes include all
the inherited attribute so we'll start by
evaluating initializing attributes with
the greatest ancestor and working our way
down to the attributes declared within the
class itself. Notice that the environment
here. Which has all of the attributes in
scope is an interesting point, this
environment has nothing to do with the
environment in which new t is actually
evaluation. You know, these environments e
and e prime are completely separate, okay?
So new, so e prime has in scope the names
of the attributes the class e is a, you
know, is, is some other environment.
There's some functions somewhere that's
calling new t and the variables are in
scope there are just completely different,
okay? But anyway, evaluating this block Of
initializers will yield some value. And
the new store the value isn't used for
anything, okay? But the new store is the
final store. That's the store that we get
out as a result of allocating the object
and then what is the result of new t, well
it is the new object itself, v. To
summarize the semantics of New that was
the first three steps allocate the object
[inaudible] actually allocate the memory
for the object and then the remaining
steps initialize the objects by evaluating
a sequence of assignments and the most
important thing probably to understand
about initialization and one of the most
important things is the context in which
or the stage in which the initializers are
evaluated. So know that only the attribute
are in scope while we emphasize that and
it's the same rule as of typing. So when
you 're type checking a class declaration
only the attributes are in scope of the
you know, for the initializers of the
class and then as the same, naturally the
same thing that we use when we actually
evaluate the initializers at runtime. And
the initial values of the attributes are
the default values and then, then we need
the defaults because, precisely because
the attributes are in-sculpt inside their
own initializers. So, it could be for
example, it's perfectly reasonable like
Kuhls to have an initializer, let's say,
like this. And I'm just going to, I may
leave all the types here just to save time
but I can assign and attribute a the value
of a and this is perfectly okay because
the right hand side of the intializer has
all the attributes and scope and for this
to make sense a has to have some kind of
default value. It has to have some initial
value so because I might read it, before I
might read an attribute before I have
actually finished computing its
initializer All right? And the last point
here, is that notice that in the
initialization or in the yeah, in the
initialization of an object self is the
object itself is the self object. And what
do I mean by that? I forgot to mention
this on the previous slide just flipping
back to that slide for a moment, notice
here. That in the evaluation of the
initializers, what is the context the self
object is v, the self object is v, this is
the new object that we have just
constructed. And so, it's perfectly fine
for e1 or en, the initialization
expressions over here and refers to
stealth and what they were referred to if
they use self is the object that is being
initialized. Alright Returning to this, to
our summary you know it might be a little
bit of a surprise how complicated the.
Semantics of new is, in cool and it's not
just cool that has that property. In fact
every object oriented language, language
has a fairly complex semantics for the
initialization of new objects and it's a
combination of features like inheritance
and the ability of initializers to refer
to the attributes that leads to this kind
of complexity. Now let's talk about the
semantics of dynamic dispatch and we'll
follow the same plan that we did the
semantics of new for us giving for us have
an informal discussion and high level
description of how the evaluation of
dynamic dispatch works and then we'll look
at the formal operational rule. So the
first thing it happens in evaluating a
dispatch is that we'll evaluate the
arguments e1 through en and next we'll
evaluate the target object e0 so that
expression to get the actual object to
which we're dispatching. Next, we're going
to look at the dynamic type of the target
object. So, after we evaluate the zero,
we're going to look at its class peg is
And then, we're going to use that type to
figure out which function which function f
we're supposed to use. So, we're going to
go and look in the method table for the
class x and see what method it has for f.
There we're going to create new locations
and environment [inaudible]. Alright, and
we're going to set up a new locations for
the actual parameters. We're going to
initialize the, those locations with the
actual arguments. Where s itself to be the
target object and then we're going to
evaluate the body of f. Now in order to do
the look up of a method in a class, we're
going to need some representation of what
methods exist and which class is in our
operational rules. So we're going to find
a function eval stands for implementation
and the implementation in a class a of a
method f is, is going to be first of all,
the list of formal parameters. So it's
going to tell us what the formal
parameters are of f and then the body of f
Whatever the, the function body of f is.
Now we're ready to actually discuss the
details of the formal operational
semantics of method dispatch in Kuhl. I'm
going to switch colors here again just for
contrast. So as we said, the first thing
we do is we evaluate the n arguments. So
this first in lines, take care of that ad
notice that each arguments that's
evaluated may have side effects. So, it
starts in some store but it may produce a
different store. So after we've done all
of this we'll have the n arguments
evaluated and some store s (N). The next
thing that happens is we evaluate zero.
This is the expression to which we are
dispatching and that would give us an
object v0 and some updated store s (n) +
one. Okay And now we have to inspect v0.
We want to know what's inside of v0, what
v0 is made of and in particular we're
interested in the classed tag of v0 and
we'll also be interested in the contents
of its attributes. The locations
associated with its attributes but first
let's focus on the class tag. Alright,
because we're going to use that class,
remember, this is the dynamic type of the
zeros and what kind of objects the zeros
actually is when the program is running.
And we're going to use that class to look
up the definition of f that we should run.
So, we look for the method f in class x.
We want to know its implementation and in
particular we get the names of the former
parameters. Okay x1 through xn and we get
the body of the function or method.
Alright So, the next thing we have to do
is we have to allocate space in the memory
or in the store for the actual parameters
of the method call. So, we allocate new
locations. Okay, one for each actual
argument and that we're ready to build an
environment in which we can evaluate the
method, alright? So, what is this
environment going to consist of? So, we
have to think about what names or
in-scoped inside of a method. Well, all
the attributes of the class are in-scope.
Okay. So, this is a class x with
attributes a1 through an so the
environment will have those names to find
a1 through an. And now what are the
attributes or locations of those
attributes. Well those are the locations
of. The zero, that's the object that we're
dispatching to that were going to be the
self object and the attribute names will
refer to the attributes of, of self,
alright. So, those locations here are the
locations of, of the attributes in the
object v0. Now in addition the formal
paramete rs are also in scope inside of
the method body. So we add to this
environment with just the attributes all
of the formal parameters okay and they are
at the new locations l(x1) up to l(xn).
Okay? And notice one slight subtlety about
the way this is defined we're taking an
initial environment which I'll show here
with, I'll, I'll color these braces in
blue. So we're defining and initial
environment of the attributes and then
we're doing updates to that, okay? So
we're, instead of just defining x1 to map
two l sub x1, we're saying we're replacing
The definition of x1 in this environment
in the blue braces with one and maps x1
and l(x1). Why do we do it that way? Well,
the thing is that a method may have a
formal parameter that is the same as an
attribute name so for example I could have
a class a that has an attribute little a
in it And it also has a method f that
takes a formal parameter named a. Okay And
if I do that, and of course, I'm leaving
out types and lots of other things here.
So, here I have an attribute name
[inaudible] that's declared. And then I
have a method that takes the argument
called a. And then the question is when I
refer to a. Inside of the body of the
method what a do I get? Is this a, is this
a bind to the formal parameters, is it
bind to the attribute? And the answer, we
have to get one answer or the other, the
answer in Kuhl, is that it binds to the
formal parameter that hides the, the outer
name. Okay, and that's, and that's
enforced here in the rule by these
updates. So, if a formal parameter has the
same name as one of the attributes, it
will replace the definition of the
attribute in the environment. Okay. Once
we get the environment set up, we need to
set up our store what, what are the
changes to the store? What we just have to
store the actual value of each argument at
the location for that argument. And
finally, we are ready to evaluate the
functioning body and the interesting part
here is the context in which that's done.
So, notice here that the that the self
object in, in the context of running the
method f is the object to which are
dispatching. Okay? And then the
environment is e prime, the new
environment we just set up and once again
notice that this is a complete change of
context that e prime, the environment e
prime has nothing to do with the
environment e. E prime is built completely
from scratch using only information about
the method for calling, it doesn't borrow
anything from the, from the environment
where the method originated, where the
method was called from. And finally all of
this is done in the store that has,
reflects all the side effects performed by
evaluating the arguments, by evaluating e0
and by extending the store with the
locations for the actual parameters. So to
evaluate the body of the method we get
back a value and another updated store and
that value in store are the results of the
entire execution of the dynamic dispatch.
To summarize our discussion of dynamic
dispatch, the body of the method is
invoked with, within environment e. That
has definitions for the formal arguments
and the attributes of the self object and
a store that's just like color store
except that it also has the actual
arguments bound to the locations allocated
for the formal parameters. Notice in the
rules that the notion of a frame or
activation records is implicit. We don't
actually build a data structure. That
contains you know, all of the values all
of the arguments and the, the return
address and all that stuff together. That
information is not gathered together in
one place, it's a little more abstract. We
don't actually have to say you know,
whether things are allocated on the stack
or on the heat and that's a good feature.
That allows us to have, potentially have a
range of implementations like all
implement the semantics correctly. Now, we
didn't do the semantics on the semantics
dispatch but it's extremely similar. The
only difference is in how the class that
we are going to be dispatching to is
looked up so in the stack dispatch you
might be able to you know, you can nam e
the class that you want to dispatch to
this one extra line to the side where the
class is being dispatched to in the formal
rule and you can look in the manual to see
how that works. So it's worth pointing out
that while the operation of rules are very
detailed, they intentionally omit some
cases that you might think they should
cover so let's take a look at our dispatch
example again. So here notice that we look
up the class of v0. So v0 is an object and
we checked what is class tag is and then
we look up in that class, the name of the
method that we're dispatching to and we
get out a definition of the method or not
the definition of the method that we can
write the rest of the rule. Now what would
happen If there was no such method f in
the class x, I mean this, this rule just
assumes that method is in fact to define
the class x, And the rule doesn't say
anything about what to do if it turns out
that this class x doesn't have any method
f? Well, that actually can't happen. So,
type-checking has already guaranteed That
when we go to look up method as in class x
it will exist. That was one of the points
with the type checking rules was that no
dynamic dispatch could ever dispatch to a
method that wasn't defined. And so the
fact that the time checking is already
been done, it will allows us to meet some
cases. So there's some checks that we
don't have to do because we know that,
that system has already effectively done
that And the rules would only be more
complicated if we didn't have type
checking and we needed to actually say
what would happen you know, all of the
cases where type checking will work where
things were not typed correct. Now there
are some run time errors that the type
checker doesn't prevent however and in
cool there are four. One is to dispatch
the void. Divisions by zero you can have a
sub-screen in that excess out of range or
you could run out of memory. You could try
allocating new objects that do not have
enough space for that. And in such cases,
the execution has to aboard gracefully an
d that means with an error message and not
just with a segmentation fault or some
other kind of hard crash and in the manual
there some guidelines as to what a correct
co-implementation should do in this four
situations. To summarize the material in
the last couple of videos the operational
semantic rules are really very precised
and detail. If you understand them then
you really understand how to implement a
correct cool compiler. So the rules are
complete enough and give you enough detail
that it really can't go wrong if you just
implement what the rules tell you to do.
So you need to read the rules very
carefully And I'll emphasize that because
there's actually quite a lot going on in
the rules. They're written in a certain
way and you know, to, to achieve a certain
effect and I pointed out a couple of
subtle things in the rules and so you
know, you really have to actually study
the rules in order to internalize what
they mean and be able to. Implement them
correctly. It's also a great way
understanding these rules and details was
actually a great way to learn quite a bit
of the, the kind of formal thinking that
goes in to the design of programming
languages and what it means for a
programming language to have a semantics
and for implementation of something to be
correct. Now having settled that, I should
say that most languages do not have a well
specified operational semantics. There are
some there are some substantial languages
and fairly realistic languages that do
have a formal semantics but most of the
language is that you're familiar with do
not. Finally just a comment you know
[inaudible] is important when you really
want software that you write behave the
exactly the same in different environments
so you know if I take the same program and
I move it to a different machine or a
different operating system and I still
want to kind of guarantee that this offer
will behave as it as it you know the same
on both machine or the old environment and
the new environment then I really need
some independent defin ition of what it
means what the behavior of these programs
should be. And that's where a formal
semantics becomes a really critical.