In this video, we're going to being our
discussions of run time structures with
the notion of procedure activations.
Before we begin the discussion of
activations, it's worth being explicit
that we have two overall goals in code
generation. One needs to be correct to
generate code that actually faithfully
implements the programmer's program And
the second is to be efficient that, that
code should made good use of resources and
in particular we often care that it run
quickly And is very easy to solve These
problems in isolation. If all we care
about is correctness, it's not a hard
problem to generate Code that is very
simple but also very slow and correctly
implements the program. If all we care
about is speed, we don't care about
getting the right answer, the problem is
even easier. I can generate extremely fast
programs that generate the wrong answer
for any problem that you carry to me And
so really all the complications in code
generation arise from trying to solve
These two problems simultaneously And,
what has grown up over time is fairly
elaborate framework for how a code
generator and the run, and the
corresponding run time structures should
be done to achieve both of these goals,
okay? And the first step in talking about
that is to talk about activations. We're
going to make two assumptions about the
kinds of programming languages for which
we're generating code. The first
assumption is that execution is
sequential. Given that we execute the
statement, the next statement that will be
executed is easy to predict. In fact, it's
just a function of the statement that we
just executed. So, controls is going to
move from one point in a program to
another in some well defined order. The
second assumption is the one that
procedure is called controllable always
return to the point immediately after the
call. That is if I execute a procedure f,
once f is done executing, control will
always return to the statement that
followed Point where f was call And there
are certainly programming languages and
programming lan guage features that
violate this assumption. So the most
important class of programming language is
it violate assumption one are ones that
have concurrency. So the concurring
program just because I execute one
statement there is no easy way to predict
what the next statement is to execute it
because it might be in a completely
different thread. And for assumption too
Advanced control constructs things like
exceptions And Calls [cough]. If you
happen another call [inaudible], it's not
important if you don't. These kinds of
constructs that affect the flow of control
in fairly dramatic ways can violate
assumption to. So in particular, if you're
familiar with catch and throw style
exceptions in Java and C++, when we throw
an exception that exception might escape
from multiple procedures before it is
caught and so there's no guarantee when
you call a procedure if that procedure can
throw an exception that, that it control
whatever return to the point immediately
after the procedure call. Now, we're gonna
keep these assumptions for the rest of the
class. We may later on in future videos
briefly discuss how we would accommodate
some of these more advanced features if
the, the material that we're going to
cover. Is basic to all implementation and
even languages have concurrency and
exception build upon the ideas that we're
going to discuss here. So first the
definition When we invoke the procedure p.
We're going to say that is an activation
of the procedure p and the life time of an
activation of p is gonna be all the steps
are involved executing the procedure p and
including all the steps in the procedures
that p calls so it's going to be all the
steps in the procedures that p calls. So
it's going to be all the statements that
are executed between the moment that p is
called and the moment that p returns
including all the functions and procedures
that p itself calls. We could define in a
[inaudible] notion of the lifetime of a
variable. So the lifetime of a variable x
is gonna be the portion of the execution
in which x is defined, That means that
it's all the step of execution from the
time that x is first created until the
time when x is destroyed or deal located
and just note here that life time is a
dynamic concept so this is that implies to
the executing program. We're talking about
the time when the variable first comes
into existence until the moment in time
when it goes out of existence And scope on
the other hand is a static concept that go
prefers to that portion of the program
text in which the variable is visible.
Okay, so this is a very different idea
from the life time of the variable and
again. It's very important to keep these
two times, what happens at runtime and
what happens in compiler time or what is
associated with the static properties of
the program distinct in your mind. From
the assumptions that we gave a couple of
slides ago we can make a simple
observation and that is when a procedure P
calls the procedure Q. Then Q is going to
return before P returns. And what that
means is that the lifetime of procedures
are going to be properly nested and
furthermore, that means that we can
illustrate or represent activation
lifetimes as a tree. Let's illustrate
activation with a simple example. So
here's a little cool program and as usual,
it will begin running by executing the
main method in the main class. So the
first activation and the root for our
activation tree for this program is the
method main. And. Main is going to call
the method g and so g's lifetime, the set
of instructions were g exist where a
period of time of the execution where g
existed is gonna be properly contain
within the execution of this call to main.
And so we can illustrate that by making g
a child of main. So this indicates that
effect of g is a direct child of main
indicates that main calls g and also the
g's lifetime is properly contained within
the lifetime of main. After g returns main
will call f and so f will also. The, a
child of, of main And then F as itself is
going to call G again And so, it's gonna
have another activation of G And so G Will
also be a child of f. And this tree that
is actually the complete tree for this
particular example illustrates the number
of things. First of all as we already said
it shows the containment of life time. So
again for example g's life time is
contained with a name but it also shows
some other interesting lifetime
relationships. For example, the life time
of this activation of g and the life time
of that activation of f are completely
distinct because their siblings in the
tree, their lifetimes do no overlap at
all. And another thing to notice here is
that there can be multiple occurrences of
the same method in the activation tree. So
every time the method is called that is a
separate activation so in this particular
activation tree there are two activations
of g. So, here's a somewhat more
complicated example the involves a
recursive function. Let's begin here at
the, at the first call. So The call to
main And all main does is call F with the
argument three. So, there is an activation
of F from Main. And then what does f do,
well f asks if it's argument is zero, and
if it is that calls g, while the initial
argument is three so that's not going to
be true on the first call to f. In
otherwise, it calls f with the argument
minus one. So, I was making note over here
on the side about what the argument is
because we need to keep track of that. So
f is called with three clearly that is not
zero, and so then f is going to be called
again with the argument two, that will
results in f being called yet another time
with the argument one and finally, f will
be called. With the argument zero, Which
will then result in a call to G, And so
this is the activation tree for this
particular program, And again notice that
there is gonna be multiple activation of
the procedure on the same run of the
program. It just indicates that the same
procedure can be called multiple times and
also note that the recursive procedure
will result in nesting of activations of
the same function within itself, And so
when f calls i tself and so the life time
say of the second call to f is properly
contained within the life time with the
fist call to f. To sum up our discussion
of activations it's obvious I think that
the activation tree depends on the runtime
behavior of the program. So it depends on
the runtime value who's exactly which
procedures are called and what the
activation tree turns out to be. Now, this
was not illustrated in our examples but it
should be obvious that the activation tree
can be different for different inputs. And
so the programs I showed you didn't take
input and so we didn't have, every time
you run those programs we'll get the same
activation tree, playing general if
program takes input, it will execute
differently and may call different
procedures and different orders. And
finally here's perhaps the most important
point for an implementation point of view.
Since activations are properly nested, we
can use a stack to implement of detract
the currently active activations. So,
let's see how we can use a stack to track
activations. We'll use these examples that
we looked at before. And what I'm going to
do is I'm going to show the activation
tree over here on the left and I'm going
to show the stack of currently executing
activations on the right. So the stack is
not gonna keep track of the entire
activation tree. It's only going to keep
track of the activations that are
currently running so at each step of the
program, the stack should contain all of
the currently active or currently running
activations. So, the tree we already saw
have the build and we begin by executing
main so that will be the root of the tree
And since the stack is supposed to have
all of the currently running activations,
the stack will have to have main on it. So
it will begin with just the procedure main
And now main calls g And so g becomes a
child of main And over here on the stack,
we would push g on to the stack And then G
returns and what that means is that, that
G is no longer running and so G will get
popped off the stack and then, the, the
main procedure calls F and so F will get
pushed on to the stack And you can see
here that after G finishes we can pop it
off and we can push on that and we
maintain the environment that we have a
stack of the currently running
activations. All right, then F is going to
call G. I forgot to complete my tree here,
So main calls f and then f calls g. All
right, So now the stack at this point is
main f and g. And once g finishes running,
it will be Popped off of the stack because
it is no longer executing. And then f will
finish, and f will also get popped off the
stack and finally main will finish and
main will also be popped off the stack.
And so that's the idea. So that is how we
can use the stack. So essentially when a
procedure is called we'll push an
activation for that procedure on to the
stack. And when the procedure returns, we
will pop that activation off the stack.
And because activation lifetimes are
properly nested this will work out. So, to
conclude our discussion of activations,
let's return to the runtime organization
As you may recall. We have a block of
memory that is allocated to the program
and the first portion of that block is
occupied by the code for the program
itself. And now in the rest of that memory
that is allocated to the program, we are
going to have to restore the data that the
program needs to execute and one of the
important structures that goes there is
the stack of activations. So typically,
this will start after the code area. And
the stack would grow towards the other end
of the memory space of the program and the
stack will grow when procedures are called
and it will shrink when procedures return.
And as we'll see, there are other things
that go in this data area that we are
going to be discussing in the upcoming