Runtime environments and activation records

Why it exists

A procedure can be called many times, even from inside itself, and each call needs its own copies of the parameters and local variables. The storage cannot be fixed at compile time (static allocation fails for recursion), and it is not enough to allocate on call and free on return in an arbitrary order: because calls are properly nested, a stack is the right structure. The compiler must therefore design what is stored for one call (the activation record), how a call and a return manipulate the stack, and how a name used in a procedure is mapped to the right storage (the scope rules).

Prerequisites

You need the picture of recursion and the call stack from recursion and the call stack: a call pushes a frame, a return pops it.

Precise definitions

Activation. One execution of a procedure body, from the call to the return. Different calls of the same procedure are different activations. The lifetime of an activation is the time from the first step of the body to the last (including the time spent in procedures it calls).

Activation tree. A tree with one node per activation: the root is the activation of main, and the children of the node for $P$ are the activations started by $P$, from left to right in the order of the calls. If control returns from $P$ to its caller, the node is complete. The lifetimes of two activations are either disjoint or nested (never partly overlapping), which is what makes a stack possible.

Control stack (run-time stack). The stack of activation records of the activations that are currently live: it holds exactly the path from the root of the activation tree to the activation that is running. A call pushes one record, a return pops one.

Activation record (frame). The block of storage for one activation. The usual fields, from the bottom of the record upwards (the order and the exact content depend on the compiler and the machine):

A frame pointer (or base pointer) points to a fixed place in the current record; the local variables are addressed as constant offsets from it, and a stack pointer points to the top.

Calling sequence and return sequence. On a call: the caller evaluates and stores the actual parameters, saves the return address and calls; the callee saves the old frame pointer and registers, sets the new frame pointer, allocates space for locals and temporaries and starts to execute. On return: the callee puts the return value in place, restores the registers and the frame pointer and releases its record; the caller reads the result. The split of the work between caller and callee is a design choice; what the callee can know (its own frame size) it should do, which keeps the caller's code small.

Scope rules. Which declaration does a name refer to?

• Static (lexical) scoping: a non-local name refers to the declaration in the textually enclosing block or procedure that is nearest outwards. This is determined from the program text; most languages (C, Pascal, Java) use it.
• Dynamic scoping: a non-local name refers to the most recent active binding, found by searching the callers (the control links) from the innermost outwards. It depends on the run-time call chain. (Some Lisps and shell languages.)

The same program may print different values under the two rules (first animation below).

Access to non-local data with nested procedures (static scoping). A procedure declared inside another one can use the outer procedure's variables. Each activation record has an access link to the activation record of the procedure that encloses it in the program text (the most recent one). To find a variable declared $k$ nesting levels out, follow $k$ access links and use the variable's offset. If the nesting depth of a procedure is the number of procedures that enclose it (the outermost program has depth 0), then a procedure at depth $d_c$ calls a procedure $Q$ declared inside a procedure of depth $d_p$: the new record's access link is found by following $d_c - d_p$ access links from the caller (and if $Q$ is declared inside the caller, $d_c = d_p$ and the link just points to the caller). A display is an array indexed by nesting depth that holds a pointer to the most recent record at each depth: non-local access then takes constant time instead of following a chain, at the cost of updating the display on calls and returns.

Access to non-local data with dynamic scoping. Deep access searches the control links at run time (slow but cheap to call); shallow access keeps a stack of values for each name (fast access but each call must save and restore the bindings).

How it works

The same program under both scoping rules. The program has a global x = 10; f prints x; g declares its own x = 20 and calls f. The control link of f points to g (its caller); the access link of f points to main (where f is declared). Under static scoping f follows the access link and prints 10.

1var x = 10;
2proc f() {
3  print x;
4}
5proc g() {
6  var x = 20;
7  f();
8}
9g();

Under dynamic scoping the same call finds the x of the caller g first and prints 20.

1var x = 10;
2proc f() {
3  print x;
4}
5proc g() {
6  var x = 20;
7  f();
8}
9g();

Now nested procedures: inner is declared inside outer, which is declared in main. When inner prints a + b + m, it finds m in its own record, b one access link out (in outer) and a two access links out (in main).

1var a = 1;
2proc outer(n) {
3  var b = 10;
4  proc inner(m) {
5    print (a + b) + m;
6  }
7  inner(n);
8}
9outer(5);

Recursion: one record per activation. fact(3) makes the stack four records deep (the three activations of fact and main); each activation has its own n, while the global r is shared.

1var r = 1;
2proc fact(n) {
3  if (n > 1) {
4    fact(n - 1);
5  }
6  r = r * n;
7}
8fact(3);
9print r;

The activation tree of the recursive Fibonacci function: every call is a node, and the control stack at any moment is the path from the root to the running activation. For fib(4) there are 9 activations and the stack is never more than 4 deep.

Worked examples

var x = 10;
proc f() { print x; }
proc g() { var x = 20; f(); }
g();

Cheat box

Traps and GATE patterns

Connections

The stack picture is the one of recursion and the call stack and, at machine level, of stack frames and calls. How the actual parameters are passed is parameter passing. Where the stack sits among static and heap storage is storage organisation. The symbol table of phases of a compiler supplies the offsets of the variables within the record.

PYQs

Which of the following are true?

I. A programming language which does not permit
global variables of any kind and has no nesting of
procedures/functions, but permits recursion can be
implemented with static storage allocation.

II. Multi-level access link (or display) arrangement is
needed to arrange activation records only if the

programming language being implemented has
nesting of procedures/functions.

III. Recursion in programming languages cannot be
implemented with dynamic storage allocation.

IV. Nesting of procedures/functions and recursion
require a dynamic heap allocation
scheme and cannot be implemented with a stack-
based allocation scheme for activation records.

V. Programming languages which permit a function
to return a function as its result cannot be
implemented with a stack-based storage allocation
scheme for activation records.

Which of the following are true?
(I)
A programming language which does not
permit global variables of any kind and has
no nesting of procedures/functions, but
permits recursion can be implemented with
static storage allocation
(II)
Multi-level
access
link
(or
display)
arrangement is needed to arrange activation
records only if the programming language
being
implemented
has
nesting
of
procedures/functions.
(III) Recursion in programming languages cannot
be implemented with dynamic storage
allocation
(IV) Nesting procedures/functions and recursion
require a dynamic heap allocation scheme
and cannot be implemented with a stack-
based allocation scheme for activation
records
(V)
Programming languages which permit a
function to return a function as its result cannot
be implemented with a stack-based storage
allocation scheme for activation records.

Which of the following statements are Correct?
1. Static allocation of all data areas by a compiler
makes it impossible to implement recursion.
2. Automatic garbage collection is essential to
implement recursion.
3. Dynamic allocation of activation records is
essential to implement recursion.
4. Both heap and stack are essential to implement
recursion.

Consider the program given below, in a block-
structured pseudo-language with lexical scoping
and
nesting of procedures permitted.

Program main;
    Var ...
    Procedure A1;

        Var ...

   Call A2;
    End A1
    Procedure A2;
        Var ...
        Procedure A21;
            Var
            Call A1;
        End A21
        Call A21;
    End A2
    Call A1;
End main.
Consider the calling chain: Main → A1 → A2 →
A21 → A1
The correct set of activation records along with
their access links is given by

Self-check

Revision card

References