Runtime Environments

The runtime environment is the machinery a compiler generates to manage storage while the program runs. It looks like a collection of unrelated conventions and is really the answer to two questions asked of every name.

Where does this name's storage live, and how long does it last?

A global variable lives in the static area for the whole program. A local lives on the stack for one activation. A dynamically allocated object lives on the heap until something releases it. Those three answers generate the three storage areas, and every mechanism in this chapter exists to manage one of them.

The second organising fact is that the stack works because call nesting is last-in-first-out and the heap needs machinery because allocation lifetimes are not.

A procedure called second returns first, so a stack matches the discipline exactly and needs no bookkeeping beyond a pointer. Heap objects are freed in no predictable order, which is why the heap needs a free list, or a garbage collector, or both.

So the diagnostic question for any storage feature is which lifetime it serves. Recursion needs per-activation storage, hence the stack. Closures outliving their creator need heap storage. Static variables persisting across calls need the static area.

1. Storage Organisation

Four regions divide the address space, and each holds a different lifetime.

The heap and stack grow towards each other from opposite ends of the free space, which lets either expand as far as the other permits without a fixed split.

Static allocation requires that every size be known at compile time and that no recursion occur. Early languages such as FORTRAN 77 used it exclusively, which is precisely why they could not support recursion: a second activation would have nowhere separate to store its locals.

2. Activation Records

An activation record, or frame, holds everything one procedure activation needs. The layout varies between machines but the components are standard.

The control link and the access link are different pointers answering different questions, and confusing them is the commonest error in this topic.

The control link points to the caller — whoever invoked this activation at run time. It is used to restore the stack on return, and the chain of control links is the dynamic call chain.

The access link points to the most recent activation of the lexically enclosing procedure — whoever contains this one in the program text. It is used to find non-local variables, and the chain of access links follows the static nesting structure.

In a language without nested procedures, such as C, no access link is needed at all, because a non-local name is necessarily global and lives in the static area.

Locals are addressed as fixed offsets from a frame pointer, which is exactly the base-plus-displacement addressing mode. That is why the offset is known at compile time even though the frame's address is not.

3. The Call Sequence

Responsibility for building and dismantling a frame is split between caller and callee, and the split is a convention rather than a necessity.

The caller typically evaluates arguments, places them in the new frame, saves any caller-saved registers, and transfers control.

The callee typically saves the return address and callee-saved registers, allocates space for locals, and sets up the frame pointer.

The return sequence reverses both halves: the callee places the return value, restores registers and the stack pointer, and jumps back; the caller then retrieves the value and restores its own saved registers.

Placing shared responsibilities in the callee saves code space, since the callee's sequence appears once while the caller's appears at every call site. This is why register saving is pushed to the callee where possible.

The register-saving split has its own logic. A caller-saved register may be destroyed by a call, so the caller preserves it only if it needs the value afterwards. A callee-saved register must be restored, so the callee preserves it only if it actually uses it. The split minimises total saves because each side skips the work it does not need.

4. Scope Rules

Two rules decide which declaration a non-local name refers to, and they can give different answers for the same program.

Static scope, also called lexical scope, resolves a name using the program text. A name refers to the declaration in the nearest enclosing block, determined at compile time.

Dynamic scope resolves a name using the call chain. A name refers to the most recent still-active declaration, determined at run time.

Consider a procedure that reads a variable it does not declare, called from two places that each declare it differently. Static scope gives the same answer in both cases, namely whatever the text encloses. Dynamic scope gives different answers, depending on which caller is active.

Almost every modern language uses static scope, because it lets a reader determine a name's meaning from the text alone, and lets the compiler resolve it to a fixed location.

Dynamic scope requires a run-time search of the call chain or an association list, which is both slower and harder to reason about.

5. Nested Procedures

When a language allows procedures to be nested, an inner procedure may reference the locals of an enclosing one, and finding them requires machinery.

The access link solves it by pointing to the most recent activation of the immediately enclosing procedure. To reach a variable declared $k$ levels out, follow $k$ access links and then apply the fixed offset.

Setting the access link correctly at a call depends on the relative nesting depths. If the callee is nested directly inside the caller, the caller's own frame is the enclosing activation. If the callee is at the same depth or shallower, the caller follows its own access links the appropriate number of times.

A display replaces the chain walk with an array. Entry $i$ of the display points to the most recent activation at nesting depth $i$, so a variable $k$ levels out is reached by one array lookup rather than $k$ pointer dereferences.

The trade is between access cost and maintenance cost. Access links cost $O(k)$ per access and nothing at a call; a display costs $O(1)$ per access but must be saved and restored around each call.

6. Parameter Passing

Four mechanisms appear, and the differences show up only under aliasing or side effects.

Call by value copies the argument into the parameter. The callee cannot affect the caller's variable at all.

Call by reference passes the address, so the parameter is an alias for the caller's variable and assignments are immediately visible.

Call by value-result, also called copy-restore, copies in on entry and copies back on exit. It resembles reference for simple cases and differs when the same variable is passed twice or modified concurrently.

Call by name substitutes the argument expression textually and re-evaluates it at every use. An array subscript passed by name is recomputed each time, which is what makes Jensen's device possible and what makes the mechanism unpredictable.

The standard discriminating test is passing the same variable twice. Under reference the two parameters alias, so an assignment through one is visible through the other. Under value-result they are independent copies until exit, when the write-back order decides the result — and that order is usually unspecified.

C has only call by value. Passing a pointer gives the appearance of reference, but the pointer itself is copied, so the callee can change what it points at and not which object the caller's variable names.

7. Heap Management

The heap holds objects whose lifetime does not match any activation, and managing it is the hardest part of the runtime.

Explicit management makes the programmer responsible. Two errors follow: a dangling reference when memory is freed while a pointer to it remains, and a memory leak when memory becomes unreachable without being freed.

A dangling reference is the more dangerous, because the memory is reused and the stale pointer silently reads or writes another object's data.

Automatic management, or garbage collection, reclaims unreachable objects.

Reference counting keeps a count per object and frees it when the count reaches zero. It reclaims immediately and spreads its cost evenly, but it cannot collect cycles: two objects referring only to each other keep each other's counts positive forever.

Mark and sweep traverses from the roots, marks everything reachable, then sweeps the heap freeing the unmarked. It collects cycles correctly, because reachability from the roots is the criterion rather than incoming references. The cost is a pause proportional to the heap size and the fragmentation left by sweeping.

A copying collector divides the heap in two and copies live objects to the other half, which compacts as it collects and makes allocation a pointer bump. The cost is half the heap sitting unused.

Generational collection exploits the observation that most objects die young, collecting a small nursery frequently and the older regions rarely.

8. Worked Examples

Example 1. Distinguish the control link from the access link, and state when each is used.

The control link points to the caller's activation record — the frame of whoever invoked this procedure at run time. It exists to restore the stack on return, and following the chain of control links traces the dynamic call sequence.

The access link points to the activation record of the lexically enclosing procedure — whoever contains this one in the program text. It exists to locate non-local variables, and following the chain traces the static nesting.

They differ whenever a procedure is called from somewhere other than its immediate lexical parent.

Suppose procedure $Q$ is nested inside $P$, and $P$ calls $R$, which calls $Q$. Then $Q$'s control link points to $R$'s frame, because $R$ made the call. But $Q$'s access link points to $P$'s frame, because $P$ encloses $Q$ in the text.

Using the control link to find a non-local would reach $R$'s locals, which are not what $Q$'s text refers to.

In a language without nested procedures the access link is unnecessary, because any name a procedure does not declare must be global and lives at a fixed static address. That is why C frames carry a control link and no access link.

Example 2. A procedure passes the same variable as both arguments to a routine that increments the first parameter and doubles the second. With $x=4$ initially, give the result under value, reference and value-result.

Call by value. Both parameters are independent copies holding 4. The routine sets the first copy to 5 and the second to 8, then both are discarded on return. The caller's $x$ is untouched, so $x$ remains 4.

Call by reference. Both parameters alias $x$ itself, so every operation acts on $x$ directly. The first statement makes $x$ equal to 5. The second statement then reads the current value of $x$, which is now 5, and doubles it to 10. So $x$ becomes 10.

Call by value-result. Both parameters are copies on entry, both holding 4. The routine sets the first copy to 5 and the second copy to 8, operating independently exactly as in call by value. On exit both copies are written back to $x$.

The result depends on the write-back order. Left to right gives 5 then 8, ending at 8. Right to left gives 8 then 5, ending at 5.

The three mechanisms give three different answers, and value-result gives two depending on an order most language definitions leave unspecified. This is exactly why aliasing is the standard test for distinguishing them.

Example 3. Explain the difference between static and dynamic scope with a program that distinguishes them.

Consider this structure. A global variable $x$ is set to 10. Procedure $P$ prints $x$ without declaring it. Procedure $Q$ declares a local $x$ set to 20 and then calls $P$. The main program calls $Q$.

Under static scope, $P$ prints 10. The compiler resolves $P$'s reference to $x$ by looking at the program text: the nearest enclosing declaration of $x$ visible from $P$ is the global one. Nothing about who calls $P$ matters, and the resolution is fixed before the program runs.

Under dynamic scope, $P$ prints 20. At run time, $P$ searches the call chain for the most recent still-active declaration of $x$. $Q$ is active and has declared its own $x$ as 20, so that is what $P$ finds.

The difference is that static scope reads the program text and dynamic scope reads the call stack.

Static scope is used by almost every modern language for two reasons. A reader can determine a name's meaning by looking at the enclosing text, without knowing every possible caller. And the compiler can resolve the name to a fixed offset, so access costs nothing at run time, whereas dynamic scope requires a search.

Example 4. Procedure $A$ contains $B$, which contains $C$. If $C$ is executing and needs a variable declared in $A$, how is it reached with access links, and how with a display?

With access links, each frame points to the most recent activation of its immediate lexical parent.

$C$'s access link points to $B$'s frame. $B$'s access link points to $A$'s frame.

$A$ is two levels out from $C$, so the code follows two access links and then applies the compile-time offset of the variable within $A$'s frame.

The cost is two pointer dereferences, and in general $k$ dereferences for a variable $k$ levels out. The compiler knows $k$ at compile time, since it is the difference in nesting depths, so it emits exactly that many.

With a display, an array indexed by nesting depth holds a pointer to the most recent activation at each depth.

$A$ is at depth 1, so the code reads display entry 1 and applies the offset — one array lookup regardless of the depth difference.

The trade is where the cost falls. Access links cost nothing at a call and $O(k)$ at each access. A display costs $O(1)$ at each access but must be updated on entry and restored on exit of every procedure, since a new activation at depth $d$ overwrites display entry $d$ and the old value must be saved in the frame.

For deeply nested code with frequent non-local access, the display wins. For shallow nesting or infrequent access, access links are cheaper overall.

Example 5. Why can reference counting not reclaim a cycle, and how does mark and sweep succeed?

Reference counting stores, with each object, the number of pointers currently referring to it. Creating a reference increments the count; destroying one decrements it; reaching zero frees the object.

Consider two objects each holding a pointer to the other, with no external pointer to either.

Object $X$'s count is 1, because $Y$ points to it. Object $Y$'s count is 1, because $X$ points to it.

Both counts are positive, so neither is ever freed. Yet neither is reachable from any root, so the program can never access either again. The memory is lost permanently.

The failure is structural: reference counting asks "does anything point at this?", and in a cycle the answer is always yes even when nothing outside can reach it.

Mark and sweep asks a different question: "is this reachable from the roots?"

It begins at the roots — global variables, the stack, and registers — and traverses every pointer, marking each object it reaches. Anything left unmarked when the traversal finishes is unreachable.

A cycle with no external reference is never reached during the traversal, so both objects stay unmarked and both are swept. The criterion is reachability rather than incoming references, and that is exactly what fixes the cycle problem.

The costs are different too. Reference counting spreads its work evenly and reclaims immediately but cannot handle cycles and pays on every pointer assignment. Mark and sweep handles cycles and costs nothing during normal execution, but pauses the program for a time proportional to the heap size and leaves the free space fragmented.

Example 6. Why can a language using only static allocation not support recursion?

Static allocation assigns each variable a fixed address at compile time, chosen once and used for the entire execution.

A procedure's locals therefore occupy one fixed set of addresses, and there is exactly one copy of each.

Recursion requires several activations of the same procedure to be simultaneously alive, each with its own values for the locals.

If a procedure calls itself, the inner activation writes its locals to the same fixed addresses the outer activation is using. The outer activation's values are destroyed, and when control returns to it, its variables hold the inner call's values.

The return address suffers the same fate. With one fixed slot per procedure, the inner call overwrites the outer call's return address, so the outer call eventually returns to the wrong place.

A stack fixes both problems because each activation gets its own frame, allocated on entry and released on return. The last-in-first-out discipline of the stack matches the nesting discipline of calls exactly, which is why the two are inseparable.

This is precisely why early FORTRAN, which used static allocation for speed and simplicity, did not permit recursion, and why every language that does permit it uses a stack.

Summary

The runtime environment answers two questions for every name: where its storage lives and how long it lasts. Three answers give three storage areas, plus the code region.

Static allocation fixes addresses at compile time and cannot support recursion, because a second activation would overwrite the first's locals and return address.

An activation record holds the return value, parameters, control and access links, saved state, locals and temporaries. Locals are reached as fixed offsets from a frame pointer.

The control link points to the caller and restores the stack; the access link points to the lexically enclosing activation and locates non-local variables. They differ whenever a procedure is called from outside its lexical parent, and C needs no access link at all.

Placing shared responsibilities in the callee saves code space, since the callee's sequence appears once and the caller's at every call site.

Static scope resolves names from the program text and is used by almost every modern language; dynamic scope resolves from the call chain and requires a run-time search.

Access links cost $O(k)$ per non-local access and nothing at a call; a display costs $O(1)$ per access but must be saved and restored around every call.

Call by value copies, reference aliases, value-result copies in and out, and name re-evaluates the argument at every use. Passing the same variable twice is the standard test that distinguishes them, and value-result's answer depends on an unspecified write-back order.

Explicit heap management risks dangling references and leaks. Reference counting reclaims promptly but cannot collect cycles, because it asks whether anything points at an object rather than whether the object is reachable. Mark and sweep uses reachability and therefore collects cycles, at the cost of a pause and fragmentation.