In the next couple of videos, we're going
to be looking at the details of the Kuhl
operational semantics going over the
semantics of each individual kind of
expression. We'll start with easy ones and
work our way up to the more complicated
ones. So the easiest rules are the rules
for the constants in Kuhl. So the value
true, the expression true I should say,
evaluates to a Boolean with the value true
And it doesn't modify the store so the
store is unchanged because it doesn't do
any updates obviously And there's a
corresponding rule for false And integers
are very, very similar so if a integer
expression, integer literal i will
evaluate to, and integer object with the
value i and again the store is not
modified by such evaluation. And finally,
strings if a, if s is a string literal of
length n, then it will be evaluated by the
string object of which the properties n
and the string constant s. The evaluation
of identifiers is very straightforward,
given that we have both in environment in
the store. So to evaluate an identifier
and this would be a variable lane y x or y
or for What do we do? Well first we look
up in the environment where that
identifier is stored so now we give us
back a memory location l. So by in this
case And then we look up in the store what
the value is at that memory locations, So,
we use the same memory location here as an
argument to the store to get back the
value that, that, that variable currently
has And notice I just have a reference,
this is a read of memories so this is
loading, I think it was loading the value
of the variable. This does not affect the
store so the store is the same before and
after. This is just looking at the value
of the variable not updating the variable.
The expression self just evaluates to the
self object. So, this is a place where we
just make use of the fact that the self
object is part of the environment so let's
just copy them over here as the result of
expression and that was again that the
store is unaffected by evaluation of self.
Now let's see of a more slightly more
complicated evaluation is evaluated, in
particular the assignment expression. So
an assignment consists of two parts, an
identifier that is being updated and an
expression that is going to give us the
new value. So for example, just to remind
you we might have something like x gets
one + one so one + one here would be the
expression e and x would be the identifier
All right? And so in order to evaluate the
assignment, the first thing we have to do
is we have to know what value we're going
to be writing into the identifier. So what
is the, what is the update we're going to
perform? So the first thing to do is to
evaluate e, okay? And notice here that e
is evaluated in the same environment so it
has the same three components here, and
here, all right? So it just says the first
thing we do is we run e. Okay. That will
give us back a new value. We're going to
get back on value b excuse and possibly an
updated score so you can arbitrate a piece
of code. You could yourself have
assignment statements in it so the story
that we get out might be different.
Alright, so e produces the value of e and
an update store s1 And now it's actually
due to assignment, what do we do? Well we
have to know what memory location was
supposed to update so we look up the
memory location for id and that would give
us some location else of id. And then we
modify the store with the new, we modify
the store at that point with the new value
so we replace the location l, i, d or we
update the value of l, i, d to be the
value of e, the value b and we do that in
store s1 which gives us a new store s2.
And I've noticed. That s2 is the store
that results from the evaluation of e,
okay? So after we do the assignment, the
assignment returns the value b which is of
course the value of a, of running e. And,
it returns the updated store s2. Next,
let's talk about the operational rule for
addition. So, to evaluate e1+e2, what we
are going to do? So, first we evaluate e1
And notice that is done in the same
context as the context of the entire e
xpression, okay? So the components the
context here for evaluating one are
exactly the same as the components for the
overall expression e1 + e2. So when we
evaluate e1 it's going to give us a value
of e1 and it's also going to give us an
updated store s1 And then we're going to
evaluate e2 and notice here And I think
context is different. The soft objects in
the environment are the same; same but now
we're running e2 in the new store s1. And
what does its saying is that if e2 has,
has assignments or variable references in
it those assignments and variable
references have to be done on the store
that resulted from running e1, okay? So,
it's very important that we get that any
side effects would happen in running e1
are visible or that are seen by the
expression e2. So we run e2 in this
environment, we're going to get the value
of e2 and the updated store s2 And then
the result of the entire expression is
going to be b1 + b2 and the results it
store will be the store s2. And notice
here how the stores tell you the order in
which you have to evaluate the
expressions. So because e1 is evaluated in
the same store as the overall expression
that tells you that e1 has to be evaluated
first. And then because e2 is evaluated in
the store that's produced by e1, that
tells you that e1, e2 excuse me, has to be
evaluated after you've evaluated e1 and
then the fact that. S2 is the result of
the whole thing. It tells you [inaudible]
is also the last thing that you evaluate
during the execution of this particular
expression. Okay, let's take a look at the
statement block and just a variety here on
the change my colors. How are we going to
evaluate the, a statement block of
statements e1 through en, okay, so, while
this is semantics, this is that we should
run, I mean order beginning of e1 and the
results of the entire execution will be
the, let's say the value of the entire
block with the value of the last
expression. And this, this rule just says
that. So, first, we evaluate e1 and also
it's done on the same store as the overall
expressio n as it tells you it has to come
first and that produces a new store s1 and
the value b1. Okay And then e2 is
evaluated in the store s1 and it produces
the store s2 and so on And then expression
en is evaluated in the store sn - one and
it produces a value of bn and an updated
store s (N). Okay? And then the result of
the whole thing is the value of vn and
also the updated store s (N) and this
tells you, this would really tell you the
order which had to evaluate the sub
expressions. The dependencies here on the
store of course you do evaluate e1 and
then e2 and then e3 and so on so you have
to do them to net order to get the side
effects to get. You know the side effects
in the correct order for all of these
expressions And furthermore, it also tells
you the only value that you're going to
keep is the value vn. Notice that none of
the other values that are produced here
are used for anything. They don't appear
anywhere else in the rules. Let's think
what we've learned so far and do a small
example. So we want to know what happens
when we evaluate the block. X gets assigns
seven + five, that's the first statement
and the second and the last statement in
the block, is just the expression four.
And the first thing we have to do is to
say what the context did and which we are
going to evaluate this and the context
consists of three parts. There'll be a
self object and in this case it doesn't
really matter what's in the self object
because self is not referred to in the
program and so it won't play any role in
the evaluation. But we, we still need it
so there still be, there'll be some self
object out there just won't get used and
Now, in the new environment which tells us
the locations where all the free variables
in the programs. So, we'll just need a
place for x is going to be stored and so s
will be stored in some location l And then
we know our memory content is, where our
store is and let's just say that at l we
have initially the value zero, okay? So
now we can use our rules to run this
program or to evaluate thi s program. I'm
going to make this line here much longer
And recall that, that evaluation of block
consist of the evaluation of the, all the
statements within the block. Okay, so the
first one is going to be s gets seven+5
and that will be evaluated in the same
environment as the overall expression. So,
we have up here. So the same context
excuse me and I should say I often slip
and I realize and say environment for the
entire left hand side of one of these
judgments. I'll try to be consistent. And
just use environment for the, for the
second components of the context often in
the literature people call the entire
thing on the left hand side of the
environment that's why they make this
mistake but you know for this instead of
notes I'm trying to be consistent the
entire, all the components on left hand
side together are called the context and
the environment is just the second
component. The mapping from variables to
their locations Anyway coming back to the
example, The first statement in the block
is s gets seven+5 alright. And then we're
going to have the second statement as
well. And we know that the self object and
the environment won't change but we don't
know what the store will be. The store
might be different so I'll leave the store
empty for now and we'll figure that out
later and we're going to be evaluating the
expression four. Okay, so this is the
structure of the evaluation now in
progress. We should look at, at this first
statement trying to make some forward
progress on that one. So, to evaluate the
assignment, what do we have to do? Well,
the very first thing we have to do is we
have to evaluate the right hand side so
we're going to have the context for that
is going to be the same And the context
we've been looking at all on because it's
the first thing that's actually going to
happen is to evaluate Seven + five, okay?
And now, I'm leaving a little space down
here for the rest of the assignment role
which we're not going to fill in just yet.
Now to evaluate the plus expression we
have to evaluate the first express ion and
the second expression, okay? And so, how
do we do that? Well, we know, finally, I
think how to do that because we're finally
down and we're going to have a single
integer there and that. We already have a
rule for it, okay and so [inaudible] the
literal evaluates to institute your
object, okay And inside that object is
just about the value, okay. And the store
is unmodified All right? And then
similarly for the other argument here,
Okay. So the five will also evaluate to an
integer object with the value of five and
the store will be unmodified okay so
that's the two sum expressions of this
edition and so now we can fill in the
results here so to take the contents of
the two integers we'll add them. That will
also be integer object so we're going to
have the integer object twelve. And the
store has not been changed, okay? So the,
the store that we get out of here happens
to be the same as the store that went in
just because this expression had no
assignments in it, okay? And now we're
ready to do the assignment. Okay. So how
do we do that? Well, we have to form a new
store. Alright, so we're going to have a
new store which will the L gets zero with
the value of l. Number which way, my
notation went here, I think it's the
number comes first and we're going to put
twelve in the location l and of course,
that's store was just equal to the store
where l has the value twelve, okay And so
now, what happens down here and we do the
assignment and we get out The new value.
Okay so, the value of the right hand side
is twelve and we have a new store where
the location l has twelve, all right? So
now we're going to evaluate the second
statement in the block and that will be
done in the store where l has the location
twelve and of course this is just an
integer And so that will evaluate to the
integer constant of four, the integer
value excuse me, 4or integer object
containing, the integer object with the
value four and our store. And it's just
going to fit not quite, all right? And
that's then the result of the entire
evaluation . So, this block will produce
the value four, an integer object with the
value four and an updated store where
location l has the value twelve. So, the
next expression I would like to take a
look at is the if, then, else expression
and to evaluate if, then, else what do we
do? Actually there should be if, then,
else. See of course, so evaluating if,
then, else as well. First we have to
evaluate the, the predicate and it's done
in the same store, the same context as the
overall expression and if the result is
true If the, if the Boolean predicate
returns the value true. Then we want to
evaluate just the true branch and not the
false branch so that's why you only see
here, evaluation of e2 and e3 isn't
mentioned anywhere and just know here that
the predicate may have side effects and so
e2 is evaluated in whatever store that e1
produces And then the results of the
entire expression is the value of e2.
Okay, that's v and also just the final
store is produced by running the then
branch. And there is a symmetric rule for
what happens if the predicate evaluates
the false. In that case, you would
evaluate e3 and not e2. Next we'll take a
look with what happens with while loops
and cool. So there are two cases. First if
the predicate of the while loop evaluates
the false, okay. Well, in this case the
loop body is not going to execute, alright
so the first thing we do is we evaluate
the predicate and that's done in the same
context as the evaluation of the overall
expression and if the predicate is false
then we exit the loop and so the results
of the loop is void. The value void and
just whatever store resulting from
evaluating the predicate. The other
possibility is that the predicate
evaluates the true. So here we evaluate
the predicate again in the same context as
the overall loop. And if the predicate
evaluates the true then we're going to run
the loop audio once. Okay. So we'll
evaluate the loop audio and also that's
done in this, in whatever store results
from evaluating the predicate. Evaluating
the loop audio is g onna give us a value
of v and a new store s2 and then what we
need to do is we need to go back around
and execute the loop again and how can we
do that? Well, we're really just running
the whole loop in the new context. So, the
next thing we do is we evaluate the entire
loop. Right in the new store So, after I
execute the loop by, loop body one time,
then we go around and just evaluate the
loop again And when this may run for zero
or more iterations, alright. And when I
finally terminate, if it terminates, it
will produce it will produce a new store
s3 evaluated while because always produced
the value of a void. And then what we'll
produce for the entire loops, for the
entire expression is the value void and
the update and store s3. The next
interesting expression to take a look at
is the let expression. So recall how, what
this looks like so let and cool has a
variable thing declared and it's type and
an initializer which is optional so this
is the value that the identifier will be
initialized to and then the expression in
which that new variable is available. And
so how do we evaluate this? Well first,
we're going to evaluate the initial value
of the, of the new variables. So we
evaluate e1 and as usual that's done in
the initial store it produces possibly
modified store. And now the question is,
what are going to, what's going to be the
context here for the evaluation of e2 for
the body of the latter? And so it seems
clear that it's going to involve s1
because it has all the updates from e2 but
it also has to have this new identifier in
it. And so how are we going to do that?
So, what we want is to have a new
environment e but with new binding of ID
to refresh location. So, we're introducing
a new variable. Remember that the
environment has tracked all the free
variables so this is one situation where
you should going to extend the environment
e with the new binding, alright. And that
location, the location for the new
variable has to be a fresh location. We
don't want to conflict with any other
memory locations we are already using.
Okay And so, we're going to allocate a new
memory location for the variable And then
the store, the new store will also will be
like as one as we said we have to include
all the, the values for s1 But also, we
can have these new location for the
variable and that's going to have the
initial value of the variable e1. To
express that we need a new location, we're
going to introduce a new operation on the
store which gives us a new fresh location.
So new lo applied to a store it's just
going to give us some location that isn't
being used by the store. So, the store has
a domain where it's a mapping from
locations to values and we'll just pick
some new location that isn't in the
current list of locations within the store
and that will be the one returned or that
will be one, that will be the one returned
by new lo. Okay, so new lo if you can
think of As modeling the memory allocation
function in the runtime system. So, then,
here we can write out the rule. So, this
is the most complicated rule we seen so
far. So, I'll just take a moment to walk
through it All right? So, the first thing
we do is we evaluate e1, the initializer
for the new variable, okay? So just like
before, this is done in the same context
as the overall expression and this is
going to give us a value for e1 and an
updated store, all right? Then in the
updated store, using the updated store
here we find an unused location, l new.
Okay And then we're going to create a
store where that new location has, has the
value of e1. So we're going to store the
value of e1 at that new location. We're
going to update the store s1 to reflect
that and further more we're going to
extend our environment with the new
identifier which will be stored at this
new location and this is the context then.
Okay, with this updated environment in
store in which we evaluate the body of the
lab which will produce the value b2 and
possible update in store s2 and those are
the results of the overall expression.