Subprograms II: activation records, static and dynamic chains

Last week we talked about what subprograms do; this week how the compiler implements them. At the center there is a single structure: the activation record (ARI). Each time a subprogram is called, an ARI is placed on the run-time stack, and removed when it returns. Exam questions: the contents of an ARI, the picture of the stack for a given call sequence, where the static/dynamic links point, and (chain_offset, local_offset) pairs.

Golden rules:

1. The dynamic link points to the caller, the static link to the static parent.
2. The static parent is read from the text, not from the call order.
3. chain_offset = depth of the place of reference − depth of the place of declaration.
4. Every call is a new ARI: in recursion several ARIs of the same function are on the stack.

Call and return semantics

What must be done in a call (call semantics):

1. Save the caller’s execution state.
2. Allocate space for the local variables (if stack-dynamic).
3. Pass the parameters (copy if value, address if reference).
4. Save the return address.
5. Set up the link needed for nonlocal access (static link).
6. Transfer control to the callee.

At the return (return semantics): copy back the values of out and inout parameters, put the return value of a function where the caller can access it, restore the stack, and go to the return address.

Activation record

The form of the local data a subprogram needs while running is called an activation record, and its concrete instance belonging to a particular call is called an activation record instance (ARI).

            ┌──────────────────┐  ← top of the stack
            │ local variables   │
            │ parameters        │
            │ dynamic link      │  → the caller's ARI
            │ static link       │  → the static parent's ARI
            │ return address    │
            └──────────────────┘  ← base of the ARI

The simple case: no recursion, no nesting

In early Fortran all locals were static. Each subprogram had a single ARI, placed in a fixed location at compile time. Fast, but recursion is impossible: a second activation overwrites the variables of the first.

Stack-dynamic locals: the run-time stack

In languages like C and Java, each call puts a new ARI on the stack. The environment pointer (EP) points to the base of the ARI of the currently running unit; locals are accessed with EP + a fixed offset. The dynamic link points to the caller’s ARI; on return EP is restored to this value. The chain formed by dynamic links is called the dynamic chain (call chain).

static int f(int n) {
    System.out.print("in" + n + " ");
    int r = (n <= 1) ? 1 : n * f(n - 1);
    System.out.print("out" + n + " ");
    return r;
}
// main: int v = f(3); System.out.println(); System.out.println(v);

in3 in2 in1 out1 out2 out3 
6

While f(1) is running the stack is: main, f(3), f(2), f(1). Each ARI has its own n and r. If fact(4) is called from main, there are at most 5 ARIs on the stack.

Nested subprograms: the static chain

In languages like Ada, JavaScript and Python, a function can be defined inside another function. In static scope a nonlocal variable is in the ARI of one of the static ancestors. The problem: where is that ARI on the stack? The solution: a static link pointing to the static parent’s ARI is added to each ARI. The chain of static links is called the static chain.

• Static depth: how many levels inside the outermost a unit is. Main is 0.
• chain_offset (nesting depth): the static depth of the unit where the reference is made − the static depth of the unit where the variable is declared.
• local_offset: the position of the variable inside its own ARI.

Nonlocal access: follow chain_offset static links, and go to local_offset in the ARI reached. Both numbers are known at compile time.

Worked example

Main     declares p, q, r          static depth 0
  Sub1   declares q, s             static depth 1   (inside Main)
    Sub2 declares t, p             static depth 2   (inside Sub1)
  Sub3   declares r, s             static depth 1   (inside Main)

Call sequence: Main → Sub3 → Sub1 → Sub2
ARI layout: 0 return address, 1 static link, 2 dynamic link, locals from 3 onward

The stack while Sub2 is running (bottom to top):

#  ARI    static link →   dynamic link →
3  Sub2   Sub1             Sub1
2  Sub1   Main             Sub3      ← note: static parent Main, caller Sub3
1  Sub3   Main             Main
0  Main   -                -

References inside Sub2:

Inside Sub3, q is in Main: (1, 4). Sub3’s own r: (0, 3).

PITFALL · the static link does not go to the caller. Sub3 called Sub1, but Sub1’s static link points to Main. The static link follows the nesting in the text. The point most often lost on exams is this: drawing the arrow to the ARI right below on the stack.

How is the static link set up?

At call time, the most recent active ARI of the callee’s static parent must be found. The compiler does this with offsets too: the static link is followed as many times as the difference between the static depth of the caller and the depth of the callee’s static parent. Sub3 (depth 1) calls Sub1 (parent Main, depth 0): follow 1 link from Sub3 → Main.

Criticism: access to a deep nonlocal requires following many links and the access time varies with depth; this makes prediction hard in time-sensitive code. The alternative display method keeps a pointer for each depth in an array. In practice, since nesting rarely exceeds 3, the static chain is sufficient.

Blocks

Blocks like { int c, d; ... } can be implemented in two ways:

1. Like subprograms called without parameters, always from the same place: an ARI at every entry.
2. More efficient: the block’s variables are placed statically in the ARI of the enclosing subprogram. Sibling blocks cannot be active at the same time and share the same cells.

void f() {
    int a, b;
    { int c, d; ... }
    { int e, f, g; ... }
}
local cells needed: 2 + max(2, 3) = 5

Implementing dynamic scope

Deep access: a nonlocal name is searched for in the dynamic chain from top to bottom. The ARIs must also hold variable names (which variable is in which ARI is not known at compile time). The chain length is uncertain, access is slow.

If the program above had dynamic scope, r in Sub2: not in Sub2, not in Sub1, found in Sub3 → Sub3.r. In static scope it is Main.r. s, however, is Sub1.s under both rules (Sub1 is both the static parent and the caller).

Shallow access: a separate stack (or a central table) is kept for each variable name; the topmost one is the active one. Access is fast, but calls and returns are expensive (push/pop for each local).

Common mistakes

Main     declares p, q, r
  Sub1   (nested in Main) declares q, s
    Sub2 (nested in Sub1) declares t, p
  Sub3   (nested in Main) declares r, s

static int f(int n) {
    System.out.print("in" + n + " ");
    int r = (n <= 1) ? 1 : n * f(n - 1);
    System.out.print("out" + n + " ");
    return r;
}
// main: System.out.println(f(3));