Activation trees and records

An activation tree is a tree structure that represents function calls made by a program during execution. When a function is called a new activation record is pushed to the stack and popped from the stack when the function returns.

Table of contents.

1. Introduction.
2. Activation trees.
3. Activation records.
4. Summary.
5. References.

Introduction.

Language compilers that use procedures, methods, or functions as units of user-defined actions manage their run-time memory or at least part of it on the stack.
When a procedure is called, space is allocated(pushed) for it on the stack and when it terminates the space is popped off the stack.

We will come to see that this arrangement not only allows the sharing of space by procedure calls but also allows for the compilation of procedure code such that the relative addresses of its non-local variables are similar regardless of the procedure calls.

An activation is the execution of a procedure. A procedure has a beginning and an ending delimiter and everything in between is the body of the procedure.
An activation record stores all information that is required to call a procedure.
Assuming the flow of control in a program is sequential when a procedure is called, control is sent to the called procedure and when the procedure is executed, it returns control to the caller.
This flow of control allows us to represent it in a series of activations which form a tree referred to as an activation tree.

Activation trees.

Coming back to stack allocation, it would not be possible if activations did not nest in time.

An example:
We have the program below. It reads nine integers into an array a then uses quicksort algorithm to sort them.

int a[9];

void readArray(){
    // read 9 integers into array a[]
}

int partition(int m, int n){
    // returns partition
}

void quickSort(int m, int n){
    int i;
    if(n > m){
        i = partition(m, n);
        quickSort(m, i-1);
        quickSort(i+1, n);
    }
}

int main(){
    readArray();
    a[0] = -9999;
    a[10] = 9999
    quickSort(1, 9);
}

Looking at the main function, we see it has three tasks, the first is to call readArray, then set the sentinels, and finally call quicksort.

The image below shows a sequence of calls that may result from the execution of the program.
[image 1]

From the above, the call to partition(1, 9) returns 4 therefore a[1] to a[3] store elements that are less than its chosen separator value v, while the larger elements are in a[5] to a[9].

From this example and in general, procedure activations are nested in time. If an activation of procedure p calls procedure q, the activation of q ends before the activation of p.

Three common cases present themselves:

1. q's activation terminates normally, then control resumes after the point p at which the call to q was made.
2. The activation of q or a procedure q is called either directly or indirectly aborts, in this case, execution can't proceed therefore p ends simultaneously together with q.
3. The activation of q terminates because of an exception that it cannot handle. If procedure p handles the exception, the activation of q terminates while that of p proceed although not necessarily to the point at which the call to q was made. If p cannot handle it, the activation of p terminates the same time the activation of q does, presumably this exception is handled by another open activation of a procedure.

We present the activation of procedure in a tree-like structure we call an activation tree. Each node in this tree corresponds to a single activation, the root represents the activation of the main procedure that starts the program.
At the node for activation for procedure p, the children correspond to activations of the procedures called by this activation.

These activations are called from left to right and one child must finish before the right activation begins.

An example:
A possible activation tree that completes the call sequence and returns as can be seen from image 1 is shown in image 2(below). The first letters represent the first letters of functions.
The above tree is only a single possibility, this is because the arguments of subsequent calls and the number of calls along any branch are influenced by the values returned by the partition.

The relationship between the activation tree and the program behavior necessitates the use of a run-time stack.

1. Firstly, the sequence of procedure calls corresponds to a preorder traversal of the activation tree.
2. This sequence of returns corresponds to a post-order traversal of the tree.
3. Assuming control lies within an activation of a procedure that corresponds to a node N of the tree, then the activations that are currently live will be those corresponding to N and its ancestors. The order in which these activations are called is the same order in which they will appear along the path to N, that is, starting from the root, they also return in reverse in a similar order.

Activation records.

The control stack is a run-time stack that manages procedure calls and returns. Each live activation has an activation record on this control stack with the root of the tree at the bottom of the stack and the rest of the sequence corresponding to the path in the tree.

We have the following activation tree that represents calls during the execution of quicksort.

The activation tree that represents calls during quicksort execution.
[image 2]

An example:
Assuming control is at q(2, 3), then the activation record for q(2, 3) will be placed at the top of the control stack.
Below the activation record q(1, 9) and at the bottom is the activation record for m which is the root of the tree and also the main function.

We show the control stack with the bottom of the stack higher than the top and therefore elements in an activation record that are the lowest are closer to the top of the stack.

As can be seen from the image 3, the contents of activation records differ with the language currently being implemented.

The above image shows the kind of data that might be stored in an activation record, below we explain each;

1. Temporary values, for example, those arising from the evaluation of expressions in situations where those temporaries cannot be held in registers.
2. Local data that belongs to the procedure whose activation record it is.
3. The saved machine status gives information regarding the state of the machine before the call to the procedure. Such information involves return addresses, register contents, etc.
4. An access link locates data needed by the called procedure.
5. A control link points to the activation record of the caller.
6. The function represents the space for the return value. Keep in mind not all procedures return a value and it does, we place it in a register for efficiency.
7. The actual parameters are used by the calling procedure, such values are not placed in the activation record rather they are placed in registers for greater efficiency.

Summary.

Storage for local variables is allocated on the run-time stack for languages allowing or that require variables to become inaccessible when their procedure terminate.

For these languages, every live activation has an activation record on the run-time stack also known as the control stack whereby, the root of the tree is located at the bottom of the stack while the entire sequence of activation records on the stack correspond to the path in the activation tree to the activation where control resides.

And at the top of the stack, we have the activation record of the latter.