Runtime Environments and Activation Records

The code a compiler generates runs inside a runtime environment: an agreed layout of memory and an agreed protocol for calls and returns. The compiler decides where each name lives (a fixed address, a slot in a stack frame, or a block in the heap), how a procedure finds its parameters and its nonlocal variables, and who saves which registers. These decisions are fixed at compile time, but they describe what happens at run time.

The central data structure is the activation record (stack frame): one per live call. Examination questions ask which fields it holds, how control and access links are set, how many records are on the stack at a given moment, and which storage class suits which kind of data.

A typical run-time image places the target code in the low area, then static data, then the heap, which grows toward higher addresses. The stack starts at the top and grows toward lower addresses. Heap and stack share the free space between them, so neither needs a fixed size limit.

In C terms: global and static variables and string literals are static; ordinary locals and parameters are on the stack; objects from malloc are in the heap, while the pointer that holds their address may be a stack local.

A general activation record holds, from the caller's side to the callee's side:

Variable-length data, such as an array whose size depends on a parameter, is placed beyond the fixed part, and the fixed part holds a pointer to it, so every fixed field keeps a constant offset.

The calling sequence allocates the record and fills it; the return sequence restores state. A common division of work:

Fields that the caller fills go first (nearest the caller), so that the caller can fill them without knowing the callee's local layout. A frame pointer typically points to the end of the fixed-length fields so that locals are at known offsets from it.

For fib(n) = n if $n < 2$, else fib(n-1) + fib(n-2), the activation tree of fib(4) has 9 nodes and 5 leaves. Its preorder (the order of calls) is fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0). The deepest root-to-leaf path is fib(4), fib(3), fib(2), fib(1), so at most 4 activation records of fib are on the stack at once. For fib(5) there are 15 activations and a maximum depth of 5. The number of records alive at once is the maximum node-depth (edge height plus 1), not its size.

Let $h(n) = n$ for $n \le 2$ and $h(n) = h(n-1) + h(\lfloor n/2 \rfloor)$ otherwise, with the left call made first. For $h(6)$:

When the last activation, $h(1)$ called from the second $h(3)$, is running, the stack holds only $h(6), h(3), h(1)$: the whole subtree of $h(5)$ has already returned. A question asking "how many records are on the stack when $h(1)$ runs for the second time" wants this root-to-node path, 3, not the number of calls made so far, 11.

Without nested procedures (C). Every name is either global, at a static address, or local to the current activation, at an offset from the frame pointer. No access link is needed.

With nested procedures (Pascal, ML, nested functions). Consider sort (depth 1) declaring readarray, exchange and quicksort (depth 2), with partition (depth 3) declared inside quicksort. Under lexical scope, partition may use variables of quicksort and sort. The record of the enclosing procedure is reached through the access link, which in the direct, non-escaping nested-procedure model here points to the appropriate active lexical parent. For passed or escaping nested functions, a closure retains the defining lexical environment; it need not be the most recently active parent.

Setting the access link (direct, non-escaping nested calls only). When a procedure $p$ at depth $n_p$ calls $q$ at depth $n_q$:

To use a variable declared at depth $n_a$ from code at depth $n_p$, follow $n_p - n_a$ access links and then use the variable's offset in that record. Both counts are known at compile time.

Example 3: the stack during partition and exchange. Let sort call quicksort(1,9), which calls quicksort(1,3), which calls partition(1,3), which calls exchange(1,3). There are five records and four control links, each pointing to the record just below. The access links are:

The control links reflect who called whom; the access links reflect who encloses whom in the program text. They differ for quicksort(1,3) and exchange(1,3).

Using a nonlocal. If the array a is declared in sort (depth 1), then exchange (depth 2) reaches it by following $2 - 1 = 1$ access link, and partition (depth 3) by following $3 - 1 = 2$ links: first to quicksort(1,3), then to sort. The same counts hold for every activation of those procedures, whatever the call history.

A display is an array $d$ with one pointer per nesting depth: $d[i]$ points to the most recent activation at depth $i$. A procedure at depth $n$ reaches a variable at depth $i \le n$ in one step through $d[i]$, instead of following $n - i$ links. On a call to a procedure at depth $n_q$, its record saves the old $d[n_q]$ and $d[n_q]$ is set to the new record; the return restores the saved value. In Example 3, after the call to exchange, $d[1]$ points to sort and $d[2]$ to exchange, while $d[3]$ still points to partition; exchange uses only $d[1]$ and $d[2]$, which are exactly its static chain.

The memory manager hands out and takes back heap blocks. Strategies such as best fit and first fit trade search time against fragmentation; adjacent free blocks are coalesced. Manual deallocation can leave dangling pointers (use after free) and memory leaks (blocks never freed).

Related material. Automatic garbage collection (reference counting, mark-and-sweep, copying collectors) reclaims unreachable heap blocks; it is treated in Dragon Book Sections 7.5 and 7.6.

Common misconceptions.