1
00:00:02,120 --> 00:00:07,648
In this video, we're going to being our
discussions of run time structures with

2
00:00:07,648 --> 00:00:14,248
the notion of procedure activations.
Before we begin the discussion of

3
00:00:14,248 --> 00:00:19,296
activations, it's worth being explicit
that we have two overall goals in code

4
00:00:19,296 --> 00:00:24,343
generation. One needs to be correct to
generate code that actually faithfully

5
00:00:24,343 --> 00:00:29,588
implements the programmer's program And
the second is to be efficient that, that

6
00:00:29,588 --> 00:00:35,225
code should made good use of resources and
in particular we often care that it run

7
00:00:35,225 --> 00:00:40,856
quickly And is very easy to solve These
problems in isolation. If all we care

8
00:00:40,856 --> 00:00:45,538
about is correctness, it's not a hard
problem to generate Code that is very

9
00:00:45,538 --> 00:00:50,569
simple but also very slow and correctly
implements the program. If all we care

10
00:00:50,569 --> 00:00:55,228
about is speed, we don't care about
getting the right answer, the problem is

11
00:00:55,228 --> 00:01:00,321
even easier. I can generate extremely fast
programs that generate the wrong answer

12
00:01:00,321 --> 00:01:05,539
for any problem that you carry to me And
so really all the complications in code

13
00:01:05,539 --> 00:01:10,389
generation arise from trying to solve
These two problems simultaneously And,

14
00:01:10,389 --> 00:01:15,104
what has grown up over time is fairly
elaborate framework for how a code

15
00:01:15,104 --> 00:01:19,758
generator and the run, and the
corresponding run time structures should

16
00:01:19,758 --> 00:01:25,392
be done to achieve both of these goals,
okay? And the first step in talking about

17
00:01:25,392 --> 00:01:30,244
that is to talk about activations. We're
going to make two assumptions about the

18
00:01:30,244 --> 00:01:34,408
kinds of programming languages for which
we're generating code. The first

19
00:01:34,408 --> 00:01:38,345
assumption is that execution is
sequential. Given that we execute the

20
00:01:38,345 --> 00:01:43,080
statement, the next statement that will be
executed is easy to predict. In fact, it's

21
00:01:43,080 --> 00:01:47,587
just a function of the statement that we
just executed. So, controls is going to

22
00:01:47,587 --> 00:01:52,037
move from one point in a program to
another in some well defined order. The

23
00:01:52,037 --> 00:01:56,258
second assumption is the one that
procedure is called controllable always

24
00:01:56,258 --> 00:02:01,452
return to the point immediately after the
call. That is if I execute a procedure f,

25
00:02:01,452 --> 00:02:06,763
once f is done executing, control will
always return to the statement that

26
00:02:06,763 --> 00:02:12,457
followed Point where f was call And there
are certainly programming languages and

27
00:02:12,457 --> 00:02:16,855
programming lan guage features that
violate this assumption. So the most

28
00:02:16,855 --> 00:02:21,996
important class of programming language is
it violate assumption one are ones that

29
00:02:21,996 --> 00:02:26,727
have concurrency. So the concurring
program just because I execute one

30
00:02:26,727 --> 00:02:32,487
statement there is no easy way to predict
what the next statement is to execute it

31
00:02:32,487 --> 00:02:37,970
because it might be in a completely
different thread. And for assumption too

32
00:02:38,223 --> 00:02:46,754
Advanced control constructs things like
exceptions And Calls [cough]. If you

33
00:02:46,754 --> 00:02:51,609
happen another call [inaudible], it's not
important if you don't. These kinds of

34
00:02:51,609 --> 00:02:56,641
constructs that affect the flow of control
in fairly dramatic ways can violate

35
00:02:56,641 --> 00:03:01,378
assumption to. So in particular, if you're
familiar with catch and throw style

36
00:03:01,378 --> 00:03:06,292
exceptions in Java and C++, when we throw
an exception that exception might escape

37
00:03:06,292 --> 00:03:10,910
from multiple procedures before it is
caught and so there's no guarantee when

38
00:03:10,910 --> 00:03:16,002
you call a procedure if that procedure can
throw an exception that, that it control

39
00:03:16,002 --> 00:03:21,040
whatever return to the point immediately
after the procedure call. Now, we're gonna

40
00:03:21,040 --> 00:03:27,258
keep these assumptions for the rest of the
class. We may later on in future videos

41
00:03:27,470 --> 00:03:33,829
briefly discuss how we would accommodate
some of these more advanced features if

42
00:03:33,829 --> 00:03:40,211
the, the material that we're going to
cover. Is basic to all implementation and

43
00:03:40,211 --> 00:03:47,191
even languages have concurrency and
exception build upon the ideas that we're

44
00:03:47,191 --> 00:03:54,483
going to discuss here. So first the
definition When we invoke the procedure p.

45
00:03:54,483 --> 00:03:59,589
We're going to say that is an activation
of the procedure p and the life time of an

46
00:03:59,589 --> 00:04:04,756
activation of p is gonna be all the steps
are involved executing the procedure p and

47
00:04:04,756 --> 00:04:09,801
including all the steps in the procedures
that p calls so it's going to be all the

48
00:04:09,801 --> 00:04:14,725
steps in the procedures that p calls. So
it's going to be all the statements that

49
00:04:14,725 --> 00:04:19,527
are executed between the moment that p is
called and the moment that p returns

50
00:04:19,527 --> 00:04:26,395
including all the functions and procedures
that p itself calls. We could define in a

51
00:04:26,395 --> 00:04:31,854
[inaudible] notion of the lifetime of a
variable. So the lifetime of a variable x

52
00:04:31,854 --> 00:04:37,179
is gonna be the portion of the execution
in which x is defined, That means that

53
00:04:37,179 --> 00:04:42,504
it's all the step of execution from the
time that x is first created until the

54
00:04:42,504 --> 00:04:47,648
time when x is destroyed or deal located
and just note here that life time is a

55
00:04:47,648 --> 00:04:52,984
dynamic concept so this is that implies to
the executing program. We're talking about

56
00:04:52,984 --> 00:04:58,006
the time when the variable first comes
into existence until the moment in time

57
00:04:58,006 --> 00:05:03,405
when it goes out of existence And scope on
the other hand is a static concept that go

58
00:05:03,405 --> 00:05:08,239
prefers to that portion of the program
text in which the variable is visible.

59
00:05:08,239 --> 00:05:13,073
Okay, so this is a very different idea
from the life time of the variable and

60
00:05:13,073 --> 00:05:17,904
again. It's very important to keep these
two times, what happens at runtime and

61
00:05:17,904 --> 00:05:22,976
what happens in compiler time or what is
associated with the static properties of

62
00:05:22,976 --> 00:05:29,747
the program distinct in your mind. From
the assumptions that we gave a couple of

63
00:05:29,747 --> 00:05:35,571
slides ago we can make a simple
observation and that is when a procedure P

64
00:05:35,571 --> 00:05:41,252
calls the procedure Q. Then Q is going to
return before P returns. And what that

65
00:05:41,252 --> 00:05:46,788
means is that the lifetime of procedures
are going to be properly nested and

66
00:05:46,788 --> 00:05:51,821
furthermore, that means that we can
illustrate or represent activation

67
00:05:51,821 --> 00:05:58,068
lifetimes as a tree. Let's illustrate
activation with a simple example. So

68
00:05:58,068 --> 00:06:04,101
here's a little cool program and as usual,
it will begin running by executing the

69
00:06:04,101 --> 00:06:09,688
main method in the main class. So the
first activation and the root for our

70
00:06:09,688 --> 00:06:15,351
activation tree for this program is the
method main. And. Main is going to call

71
00:06:15,351 --> 00:06:20,844
the method g and so g's lifetime, the set
of instructions were g exist where a

72
00:06:20,844 --> 00:06:26,066
period of time of the execution where g
existed is gonna be properly contain

73
00:06:26,066 --> 00:06:31,762
within the execution of this call to main.
And so we can illustrate that by making g

74
00:06:31,762 --> 00:06:36,984
a child of main. So this indicates that
effect of g is a direct child of main

75
00:06:36,984 --> 00:06:42,815
indicates that main calls g and also the
g's lifetime is properly contained within

76
00:06:42,815 --> 00:06:51,312
the lifetime of main. After g returns main
will call f and so f will also. The, a

77
00:06:51,312 --> 00:06:59,042
child of, of main And then F as itself is
going to call G again And so, it's gonna

78
00:06:59,042 --> 00:07:05,957
have another activation of G And so G Will
also be a child of f. And this tree that

79
00:07:05,957 --> 00:07:10,723
is actually the complete tree for this
particular example illustrates the number

80
00:07:10,723 --> 00:07:15,606
of things. First of all as we already said
it shows the containment of life time. So

81
00:07:15,606 --> 00:07:20,018
again for example g's life time is
contained with a name but it also shows

82
00:07:20,018 --> 00:07:24,431
some other interesting lifetime
relationships. For example, the life time

83
00:07:24,431 --> 00:07:29,196
of this activation of g and the life time
of that activation of f are completely

84
00:07:29,196 --> 00:07:33,844
distinct because their siblings in the
tree, their lifetimes do no overlap at

85
00:07:33,844 --> 00:07:39,170
all. And another thing to notice here is
that there can be multiple occurrences of

86
00:07:39,170 --> 00:07:44,651
the same method in the activation tree. So
every time the method is called that is a

87
00:07:44,651 --> 00:07:50,133
separate activation so in this particular
activation tree there are two activations

88
00:07:50,133 --> 00:07:55,960
of g. So, here's a somewhat more
complicated example the involves a

89
00:07:55,960 --> 00:08:01,960
recursive function. Let's begin here at
the, at the first call. So The call to

90
00:08:01,960 --> 00:08:09,936
main And all main does is call F with the
argument three. So, there is an activation

91
00:08:09,936 --> 00:08:16,131
of F from Main. And then what does f do,
well f asks if it's argument is zero, and

92
00:08:16,131 --> 00:08:21,741
if it is that calls g, while the initial
argument is three so that's not going to

93
00:08:21,741 --> 00:08:26,797
be true on the first call to f. In
otherwise, it calls f with the argument

94
00:08:26,797 --> 00:08:32,871
minus one. So, I was making note over here
on the side about what the argument is

95
00:08:32,871 --> 00:08:39,064
because we need to keep track of that. So
f is called with three clearly that is not

96
00:08:39,064 --> 00:08:45,109
zero, and so then f is going to be called
again with the argument two, that will

97
00:08:45,109 --> 00:08:51,302
results in f being called yet another time
with the argument one and finally, f will

98
00:08:51,302 --> 00:09:01,340
be called. With the argument zero, Which
will then result in a call to G, And so

99
00:09:01,340 --> 00:09:06,436
this is the activation tree for this
particular program, And again notice that

100
00:09:06,436 --> 00:09:11,533
there is gonna be multiple activation of
the procedure on the same run of the

101
00:09:11,533 --> 00:09:16,755
program. It just indicates that the same
procedure can be called multiple times and

102
00:09:16,755 --> 00:09:21,789
also note that the recursive procedure
will result in nesting of activations of

103
00:09:21,789 --> 00:09:26,822
the same function within itself, And so
when f calls i tself and so the life time

104
00:09:26,822 --> 00:09:31,856
say of the second call to f is properly
contained within the life time with the

105
00:09:31,856 --> 00:09:36,781
fist call to f. To sum up our discussion
of activations it's obvious I think that

106
00:09:36,781 --> 00:09:41,627
the activation tree depends on the runtime
behavior of the program. So it depends on

107
00:09:41,627 --> 00:09:45,839
the runtime value who's exactly which
procedures are called and what the

108
00:09:45,839 --> 00:09:50,686
activation tree turns out to be. Now, this
was not illustrated in our examples but it

109
00:09:50,686 --> 00:09:55,580
should be obvious that the activation tree
can be different for different inputs. And

110
00:09:55,580 --> 00:09:59,986
so the programs I showed you didn't take
input and so we didn't have, every time

111
00:09:59,986 --> 00:10:04,227
you run those programs we'll get the same
activation tree, playing general if

112
00:10:04,227 --> 00:10:08,137
program takes input, it will execute
differently and may call different

113
00:10:08,137 --> 00:10:13,617
procedures and different orders. And
finally here's perhaps the most important

114
00:10:13,617 --> 00:10:20,141
point for an implementation point of view.
Since activations are properly nested, we

115
00:10:20,141 --> 00:10:26,381
can use a stack to implement of detract
the currently active activations. So,

116
00:10:26,381 --> 00:10:32,795
let's see how we can use a stack to track
activations. We'll use these examples that

117
00:10:32,795 --> 00:10:38,158
we looked at before. And what I'm going to
do is I'm going to show the activation

118
00:10:38,158 --> 00:10:43,385
tree over here on the left and I'm going
to show the stack of currently executing

119
00:10:43,385 --> 00:10:48,230
activations on the right. So the stack is
not gonna keep track of the entire

120
00:10:48,230 --> 00:10:53,175
activation tree. It's only going to keep
track of the activations that are

121
00:10:53,175 --> 00:10:58,658
currently running so at each step of the
program, the stack should contain all of

122
00:10:58,658 --> 00:11:04,343
the currently active or currently running
activations. So, the tree we already saw

123
00:11:04,343 --> 00:11:10,164
have the build and we begin by executing
main so that will be the root of the tree

124
00:11:10,164 --> 00:11:15,850
And since the stack is supposed to have
all of the currently running activations,

125
00:11:15,850 --> 00:11:22,010
the stack will have to have main on it. So
it will begin with just the procedure main

126
00:11:22,010 --> 00:11:30,577
And now main calls g And so g becomes a
child of main And over here on the stack,

127
00:11:30,577 --> 00:11:38,746
we would push g on to the stack And then G
returns and what that means is that, that

128
00:11:38,746 --> 00:11:45,106
G is no longer running and so G will get
popped off the stack and then, the, the

129
00:11:45,106 --> 00:11:51,311
main procedure calls F and so F will get
pushed on to the stack And you can see

130
00:11:51,311 --> 00:11:57,439
here that after G finishes we can pop it
off and we can push on that and we

131
00:11:57,439 --> 00:12:02,946
maintain the environment that we have a
stack of the currently running

132
00:12:02,946 --> 00:12:09,572
activations. All right, then F is going to
call G. I forgot to complete my tree here,

133
00:12:09,572 --> 00:12:18,037
So main calls f and then f calls g. All
right, So now the stack at this point is

134
00:12:18,037 --> 00:12:26,452
main f and g. And once g finishes running,
it will be Popped off of the stack because

135
00:12:26,452 --> 00:12:31,550
it is no longer executing. And then f will
finish, and f will also get popped off the

136
00:12:31,550 --> 00:12:36,284
stack and finally main will finish and
main will also be popped off the stack.

137
00:12:36,284 --> 00:12:41,200
And so that's the idea. So that is how we
can use the stack. So essentially when a

138
00:12:41,200 --> 00:12:45,873
procedure is called we'll push an
activation for that procedure on to the

139
00:12:45,873 --> 00:12:50,668
stack. And when the procedure returns, we
will pop that activation off the stack.

140
00:12:50,668 --> 00:12:56,645
And because activation lifetimes are
properly nested this will work out. So, to

141
00:12:56,645 --> 00:13:01,517
conclude our discussion of activations,
let's return to the runtime organization

142
00:13:01,517 --> 00:13:06,206
As you may recall. We have a block of
memory that is allocated to the program

143
00:13:06,206 --> 00:13:11,017
and the first portion of that block is
occupied by the code for the program

144
00:13:11,017 --> 00:13:16,193
itself. And now in the rest of that memory
that is allocated to the program, we are

145
00:13:16,193 --> 00:13:21,247
going to have to restore the data that the
program needs to execute and one of the

146
00:13:21,247 --> 00:13:25,997
important structures that goes there is
the stack of activations. So typically,

147
00:13:25,997 --> 00:13:31,705
this will start after the code area. And
the stack would grow towards the other end

148
00:13:31,705 --> 00:13:37,609
of the memory space of the program and the
stack will grow when procedures are called

149
00:13:37,609 --> 00:13:43,049
and it will shrink when procedures return.
And as we'll see, there are other things

150
00:13:43,248 --> 00:13:48,555
that go in this data area that we are
going to be discussing in the upcoming