Lecture 11 - 480/580 (compiler construction)

The Run Time Environment

Up to todays lecture we have always been considering compile time,
the time when we examine a program once and generate code.
This is different from run time, the time when the program is actually
executed.  From this point onwards we are going to discuss code generation,
which takes place at complile time but describes what will happen at run
time, and thus requires a good understanding of both environments.
But before we do so we need to have a good understanding of the environment
the program will execute in when it is running.  This is the topic of
todays lecture.

The traditional conceptual model for conventional, von Neumann style
program execution starts by dividing the objects being considered into two
groups, namely code and data, and then considering various aspects of each
of these parts individually.  (By the way, while this model is widely used,
and is the one most programming languages use, it is not the only possible
model.  Time, unfortunately, does not permit us to talk about other models
of computation).

For our purposes right at the moment the only important aspect of code is
control flow, and the only important aspects of control flow are the
following:
* execution is sequential, that is statements are execute one after another
unless interrupted by explicit branching
* a procedure or function call executes by suspending the calling
procedure, initiating the called procedure, executing the called procedure
until it is finished (during which time other functions or procedures may
have been invoked) and then returning to the caller *following the point*
where the call was made.
* variables local to a procedure exist only as long as the procedure is
executing.

We will derive some implications of these observations in a moment.
Now let us consider data.

Let us consider what the run time environment requires by looking at
various features in programming languages and considering how they
might be supported.  We will start with very simple features, and work
up until we have something approaching modern conventional languages.

Let us first consider and language with the following features:
* no recursion
* no nested procedures (only local and global data)
* call by value parameters
* fixed sized variables with no dynamic allocation
* information associated with local variables is only accessible when we
are executing the procedure in which the local variable appears.

The most important feature of this language is that we can determine, AT
COMPILE TIME, exactly how much data will be used during execution.
We could, in fact, set aside exactly this amount of storage, allocating
blocks for each procedure.  (draw picture)

What needs to be in these blocks? (ask class for ideas)
* local variables (easy one)
* parameters (do we know how big?  What gets stored there)
* link information (how to get back to the caller).

How does one do a procedure call?
CALLER:
	evaluate arguments and place into callee's paramenter area
	place current PC (program counter) into callee's return linkage area
	transfer control to callee
CALLEE:
	execute function or procedure
	return to caller, using the address given in the return linkage
	area.

How does one get to local variables?
How does one get to global variables?

Suppose we changed call by value to call by reference.  What does this mean?
How can it be supported?

Now, there are various ways we could relax our restrictions, the two most
important being we could allow recursion and we could allow dynamically
allocated and/or sized objects.
The major implication of either of these changes is that we now no longer
know, at compile time, how much memory we will need during run time.
Let us treat the problem of recursion first.

The problem with recursion is that every time we start a recursive
execution, we want to have a fresh new data area.  Thus we may have lots of
data areas corresponding to the same function or procedure (draw lots of
data areas corresponding to the same function or procedure).  But remember
our assumption about control flow?  This means that these data areas come
into existance and become unimportant in a strict stack-like fashion.
That is, before we start executing a procedure and after we finish
executing a procedure the data is inaccessible, and hence we have no need
to allocate storage for it.

This area of stack is called an activation record (sometimes, particularly
in older references, a stack frame or activation frame).  
The same set of information needs to appear, namely
* local variables
* control linkage (how to get back)
* parameters
A pointer to this area is called the activation frame pointer.

Now, remember the steps we described for calling a procedure in the
nonrecursive case.  Will these work?  Consider the first step.  We don't
have a fixed area for the parameters; where will we put them?  The only
thing we have is the stack - so we do something like the following:

CALLER:
	Evaluate the arguments and put them on the stack (this is often
	done in reverse order, so that the first argument is topmost on the
	stack).
	Push the current PC and the current activation frame pointer on the
	stack.
	transfer control to the callee

CALLEE:
	Set the current activation frame pointer to the top of stack.
	Bump stack a sufficient amount for local variables.
	Execute code
	Restore PC and activation frame pointer

(we assume here that function results are returned in registers; 
this is usually the case, although sometimes functional results are
returned on the top of the stack).

We can ask the same questions as before, namely:
* how is local data obtained?
* how is global data obtained?
* how are parameters accessed?  (call by value, call by reference)

Now let us relax restrictions even further.  Assume we had nested
procedures, as in Pascal.

[ draw an example Pascal program and show the problem of up level
addressing in terms of activation records].

We can number static scope levels level 1, level 2, etc.

There are basically two solutions: static chains and displays.

A static chain is a pointer to the AR of the next higher (in terms of
static scoping) procedure; notice this need not be the same as the calling 
procedure.  To get a nonlocal variable, you at run time walk back the steps
of the static chain (notice the number of steps you need to go back can be
determined at compile time).  [ give example ]
Notice the static chain must be maintained by the caller, not the callee
(who doesn't know how it is being used).

A display is a small fixed size array that maintains the current AR
pointers for AR's of each of the various static scope levels.
Now it is the callee's turn to do work, part of which is before execution
* save the display value at level n, where n is our current static scope
  level
* put our AR pointer into display at level n

and, after execution:
* restore the display at level n
Now, to get a nonlocal variable, it is simply a matter of getting the
display pointer plus some offset.

The advantage of the static chain is that it is easy.  The advantage of the
display is that it is faster in access time.  Questions to ponder, however:
* how often do people use non-local and non-global data?
* is the expense of supporting static chains or displays worth it?
The designers of C decided the answer was no, which is why C does not have
nested procedures (also why your programming assignment does not have
these, as well).

[ depending upon time, could stop here ----------------------- ]

Now let us consider dynamically sized and/or allocated data.
The latter of these you are used to, as in Pascal new() or C malloc().
Let us ponder what we need to support this -
ask could it be placed on the stack?  what problems would you run into?

requires another data area, traditionally called the heap.  The heap is a
randomly accessed data area, where data comes and goes in no orderly fashion.
Won't get into different ways of managing the heap.

How about dynamically sized areas, such as a local variable declared
array [ 1 .. n ] of integer.  Now this could be put on the stack, right?
(because it lives the same way that local variables live).  Show how this
could be done using indirection and dope-vectors.

[ talk about funargs if you have time ----------------------- ]

We are used to thinking about data as being information.  But data can also
be functions and/or procedures in many languages (even in Pascal!).
Consider the following program:

var y : integer;

procedure f();
var x: integer;
begin
writeln x + y;
end;

procedure g(h: function);
var y: integer;
begin
	h();
end;

begin
  g(f);
end;

To what does y refer to in f?  Draw picture in turns of activation records.
Notice to get this behavior we must pass more than merely the name of the
procedure f, we must pass the AR for f (well, it depends a bit upon whether
we use displays or static chains - at the very least, we must know at what
lexical scope level f is).  This is called the downward funarg problem,
the bane of those who would make functions into truely first class objects.

The downward funarg problem is just the beginning.  Consider the following
even more difficult problem that we encounter if we allow procedures to be
returned as results of functions:

function f : function;
 var y: integer;
   procedure g();
    var x;
   begin
     write x + y;
   end;
begin
  return g;
end;

begin
  h := f;
  h();
end;

Now, when we execute h, what is the value of x? of y?
Notice that neither of these are in activation records that would normally
exist at this time.  Thus activation records do not come into existence
and die in a strict stack-like fashion.  This is called the upward funarg
problem.  

Pascal allows functions to be used as arguments, but not stored as data or
returned as functional values.  This is because the designers of Pascal did
not feel that solving the upward funarg problem was worth the effort,
although they did think the downward funarg problem should be handled.