Runtime environments

The compiler asks the operating system for a block of memory in which the target program runs. It is divided into areas with different lifetimes. Code and static data have a size fixed at compile time. The stack and the heap change size at run time; by common convention they sit at opposite ends of the free space and grow towards each other, the stack usually growing towards lower addresses.

Every execution of a procedure is an activation. The activation tree records the calls of a run: one node per activation, the root is the activation of the main program, and a node's children are the activations it calls, left to right in the order of the calls. Calls are properly nested: a procedure returns only after every procedure it called has returned. So at any moment the live activations are exactly the nodes on the path from the root to the current node, and the stack holds their records in that order.

The information for one activation is kept in an activation record (frame). The usual fields, in one common layout from the caller's end to the callee's end (the exact order varies between compilers), are:

A calling sequence is the code that sets up an activation; a return sequence undoes it. The work is split between caller and callee. Below is a typical division of the work; real conventions differ in detail.

Variable-length data (for example an array whose size is decided on entry) can still be placed on the stack, after the fixed-size part of the record, and is reached through a pointer stored in the fixed part. Because the record is popped on return, nothing in it may be used after the call ends.

Static allocation binds every name to a fixed address at compile time. Stack allocation gives each activation its own record on the run-time stack. Heap allocation hands out and takes back memory in any order, at the program's request or by the language's automatic management.

Stack allocation is valid when a procedure's locals are not needed after it returns and no activation outlives the one that created it. If a procedure may return a pointer to a local, or if data must be created by one call and used after it ends, those data must live in the heap or in static storage. The heap manager keeps a list of free blocks and picks one by a policy such as first fit (first block large enough) or best fit (smallest block large enough). Freed blocks next to each other can be merged (coalescing); free memory split into small unusable pieces is external fragmentation.

Under static (lexical) scoping, a use of a name refers to the declaration found by searching the enclosing blocks in the program text, innermost first. Under dynamic scoping, it refers to the most recent binding made by a still-active call, found by searching the calling chain.

Example of the difference:

int x = 10;
void g() { printf("%d", x); }
void f() { int x = 20; g(); }
int main() { f(); return 0; }

With static scoping g sees the global x and prints 10. Read as if the language used dynamic scoping (C itself uses static scoping), g sees the x of its caller f and prints 20.

Convention for nesting depth. The outermost (main) program has depth 1, a procedure declared directly inside it has depth 2, and so on. A variable's depth is the depth of the procedure that declares it. The formulas below use only differences of depths, so they give the same counts if the outermost level is called depth 0 instead.

A display is an array $d[\mathrm{1..}k]$ with one entry per nesting depth. $d[i]$ points to the most recent live activation record of a procedure at depth $i$. A name declared at depth $j$ is reached in one step through $d[j]$, so the cost of a non-local access does not grow with the depth difference. On entry to a procedure at depth $i$, the old value of $d[i]$ is saved in the new record and $d[i]$ is set to the new record; on return the saved value is restored. A display trades a little work at each call for faster non-local access.

Implementing dynamic scoping. Deep access: to find a name, search the records along the control-link chain, starting from the current one, for the first record that declares it; the search can be long. Shallow access: keep one central storage slot per name holding its current value; a procedure that declares the name saves the old value on entry and restores it on exit, so every access takes one step.

In call by reference, the address of the actual is computed once, at the call. In call by name, the expression is evaluated afresh each time the formal is used, using the current values of the variables in it. The two can differ whenever a variable used in the actual changes during the call, for example an array index that the callee assigns, or a global that the callee changes.

Heap data that the program can no longer reach is garbage. In a language with manual freeing, unreachable data that is never freed is a memory leak; freeing data that is still in use leaves a dangling pointer. A garbage collector reclaims unreachable heap data automatically. An object is reachable if it can be got to from a root (static data, stack variables, registers) by following pointers.