Activation Records

An Activation Record—also called a stack frame—stores the execution state associated with a single procedure call. It is normally created when a routine is called and reclaimed when that routine returns.

Activation records are central to procedure calls, recursion, parameter passing, local-variable storage, return control, and access to nonlocal variables. A call stack is a last-in, first-out structure whose top frame represents the currently executing routine.

Learning objectives

By the end of this section, you should be able to:

• Define an activation record and explain its purpose.
• Identify the usual fields in an activation record.
• Describe how activation records support recursion.
• Distinguish a dynamic link from a static link.
• Explain the calling and return sequences.
• Compare access links with displays.
• Recognize the relationship between activation records, stack allocation, and debugging.

Footnotes

1. Activation Records/Stack Frames - Princeton University - Lecture material defining activation records, their lifetime, recursion, dynamic links, and static links. ↩

2. Call stack - Overview of stack frames, return control, recursion, and access links. ↩

1. Definition and purpose

When a program invokes a function, the runtime must preserve enough information to:

1. Receive the actual arguments.
2. Store the function’s local variables.
3. Remember where execution must continue after return.
4. Preserve registers and machine state when required.
5. Store intermediate expression results.
6. Access variables declared in enclosing scopes.
7. Return a result to the caller.

This information is grouped into an activation record. The exact layout depends on the programming language, processor architecture, compiler, optimization level, and calling convention.

A simplified activation record may be represented as:

The fields are conceptual rather than universal. Some values may be held in registers, passed in registers, or optimized away entirely.

Footnotes

1. Activation Records/Stack Frames - Princeton University - Lecture material defining activation records, their lifetime, recursion, dynamic links, and static links. ↩

2. Typical layout

A common conceptual layout is shown below. The physical order can differ between systems.

A frame pointer, often written as $FP$, provides a stable reference point for fields within the frame, while a stack pointer, written as $SP$, identifies the current stack position. In many implementations, arguments and local variables are accessed using offsets from $FP$.

For example:

$$\text{address of local variable} = FP - \text{offset}$$ $$\text{address of parameter} = FP + \text{offset}$$

The direction and exact offsets depend on stack-growth direction and the target architecture.

Footnotes

1. Activation Records - Discussion of parameters, local variables, frame pointers, and offsets. ↩

3. Important fields

Return value

The return-value area holds the value produced by a function or provides a location where that value can be written. Small scalar results are often returned in registers, whereas large objects may be returned through a hidden pointer or caller-provided memory area.

Parameters

Parameters contain the inputs supplied to a routine. Depending on the calling convention, arguments may be passed:

• In processor registers.
• On the stack.
• Through a mixture of registers and stack locations.
• By value.
• By reference or address.
• Through a hidden structure-return or environment parameter.

The activation record provides the callee with a predictable way to locate arguments, regardless of how the source-level call is written.

Return address

The return address identifies the point in the caller immediately following the procedure call. A call instruction commonly saves this address in a register or on the stack; the called routine or its prologue may then preserve it in the activation record.

Dynamic link

The dynamic link points to the activation record of the routine that made the call. It represents the dynamic calling relationship.

If procedure $B$ is called by procedure $A$, then:

$$DL(B) = AR(A)$$

The dynamic link is useful for restoring the caller’s frame and stack state. It also reflects the actual order of calls, not the lexical nesting written in the source program.

Static link

The static link—also called an access link—supports lexical or static scoping. It points to the most recent activation of the procedure that lexically encloses the current procedure.

If procedure $Q$ is declared inside procedure $P$, then an activation of $Q$ can use its static link to locate the activation record of $P$ and access nonlocal variables declared there.

Saved machine status

This area preserves registers, condition codes, frame pointers, and other machine state that must survive the call. The division between caller-saved and callee-saved registers is defined by the calling convention.

Local data

Local data includes variables whose lifetime is associated with the current invocation. Ordinary automatic variables are commonly stored in the activation record, although an optimizing compiler may place them in registers or eliminate them.

Temporaries

Temporaries hold intermediate values generated during expression evaluation, address calculations, argument preparation, and register spilling. Their presence and size depend heavily on compiler implementation.

Footnotes

1. Calling Conventions - Cornell lecture explaining return addresses, stack frames, stack pointers, and procedure calls. ↩

2. Activation Records - Summary of activation-record fields and distinction between access and control links. ↩

3. CSE 428 Lecture Notes 7.2 - Definition and purpose of static links. ↩

4. Activation records and the runtime stack

In languages with stack-disciplined procedure lifetimes, activation records are placed on the runtime stack.

When a routine is called, its frame is pushed or allocated. When it returns, its frame is popped or reclaimed. This works because a called routine normally finishes before its caller can finish.

The stack supports nested calls naturally:

$$AR(main) \rightarrow AR(f) \rightarrow AR(g)$$

When $g$ returns, $AR(g)$ is removed first. Control then resumes in $f$. This last-in, first-out behavior is the reason the stack is appropriate for ordinary procedure calls.

Stack allocation advantages

• Fast allocation and deallocation.
• Simple lifetime management.
• Natural support for nested calls.
• Efficient access through stack and frame pointers.
• Automatic isolation of local variables between invocations.

Limitations

• A routine whose data must outlive its caller cannot rely solely on a stack frame.
• Closures may require captured variables to move to the heap.
• Very deep recursion can exhaust available stack space.
• Variable-sized local objects complicate frame layout.
• Exceptions, coroutines, and nonlocal control transfers may require additional runtime metadata.

Footnotes

1. Call stack - Overview of stack frames, return control, recursion, and access links. ↩

5. Calling sequence and return sequence

The calling sequence is divided between caller and callee responsibilities.

Caller actions

A caller commonly:

1. Evaluates arguments.
2. Places arguments in registers or memory.
3. Saves caller-saved registers if their values are needed later.
4. Supplies a static-link or environment argument when nested procedures require one.
5. Executes the call instruction.

Callee prologue

The callee commonly:

1. Saves the old frame pointer.
2. Establishes a new frame pointer.
3. Saves callee-saved registers.
4. Allocates local-variable and temporary space.
5. Initializes runtime metadata if required.

Callee epilogue

Before returning, the callee commonly:

1. Places the return value in the designated location.
2. Restores saved registers.
3. Deallocates local storage.
4. Restores the caller’s frame or stack pointer.
5. Jumps to the saved return address.

A simplified sequence is:

The compiler and platform ABI determine which actions are performed by the caller, which by the callee, and which are optimized away.

Footnotes

1. Concepts Introduced in Chapter 7: Activation Records - Calling-sequence actions, storage allocation, access links, and displays. ↩

6. Recursion

Recursion requires a separate activation record for every active invocation. A procedure’s code may be shared, but its parameters, locals, return address, and intermediate state must be distinct for each call.

Consider:

$$factorial(n) = \begin{cases} 1, & n = 0 \\ n \cdot factorial(n-1), & n > 0 \end{cases}$$

For the call $factorial(3)$, the stack conceptually contains:

Each invocation returns to a different caller location. If all invocations shared one frame, the value of $n$ and the return addresses would be overwritten.

Tail recursion

In tail recursion, the recursive call is the last computation. A compiler may transform it into iteration and reuse the current frame, provided language semantics and calling conventions permit this optimization.

Footnotes

1. Call stack - Overview of stack frames, return control, recursion, and access links. ↩

7. Dynamic links and static links

The two links solve different runtime problems.

Dynamic link: call history

Suppose the actual call sequence is:

$$main \rightarrow A \rightarrow B$$

Then the dynamic links are:

$$DL(AR(B)) = AR(A)$$ $$DL(AR(A)) = AR(main)$$

This chain follows the call history.

Static link: lexical nesting

Suppose the source nesting is:

1procedure Outer
2    procedure Middle
3        procedure Inner

If Inner accesses a variable declared in Outer, the runtime must follow the lexical nesting relationship. The static-link chain may be:

$$SL(AR(Inner)) = AR(Middle)$$ $$SL(AR(Middle)) = AR(Outer)$$

To find a variable declared two lexical levels outward, the runtime follows two static links and then applies the variable’s frame offset.

A recursive call makes the distinction especially important: the most recent caller and the lexically enclosing procedure need not be the same frame.

Footnotes

1. CSE 428 Lecture Notes 7.2 - Definition and purpose of static links. ↩

8. Access links and displays

Access-link implementation

An access link points from the current frame to the frame of the immediately enclosing lexical procedure. To access a variable at a more distant nesting level, the runtime follows a chain of links.

If the current procedure is at nesting depth $N_p$ and the variable is declared at depth $N_x$, the number of links followed is related to:

$$N_p - N_x$$

The exact counting convention varies by textbook and implementation, but the key principle is that greater lexical distance generally means more indirect references.

Display implementation

A display stores one pointer for each active lexical nesting level. Instead of following a linked chain, the runtime indexes the display directly.

A display can reduce nonlocal access to an array lookup followed by a frame offset. However, procedure entry and exit must save and update the relevant display entry.

Footnotes

1. CSE 428 Lecture Notes 7.2 - Definition and purpose of static links. ↩

2. Concepts Introduced in Chapter 7: Activation Records - Comparison of access-link chains and display-based nonlocal access. ↩

9. Storage allocation strategies

Activation records are one part of a broader runtime storage model.

Static allocation

With static allocation, storage is reserved before execution and remains available throughout the program. It is simple but does not naturally support an arbitrary number of recursive or simultaneous activations.

Stack allocation

With stack allocation, frames are created and reclaimed as calls begin and end. This is efficient and supports recursion.

Heap allocation

With heap allocation, activation-related data can survive beyond the return of its defining routine. This is important for closures, first-class functions, coroutines, and objects whose lifetimes are not properly nested.

Footnotes

1. Concepts Introduced in Chapter 7: Activation Records - Overview of static, stack, and heap storage strategies. ↩

10. Activation records, closures, and escaping variables

A closure may be invoked after the routine that created it has returned.

Example conceptually:

1function makeCounter
2    local count = 0
3
4    function increment
5        count = count + 1
6        return count
7
8    return increment

The function increment uses count, although makeCounter may have already returned. A conventional stack-only activation record for makeCounter would no longer be valid. The compiler or runtime therefore creates a persistent environment, commonly on the heap, and stores the captured variable there.

This illustrates an important rule:

Stack allocation is safe when lifetimes are properly nested; heap allocation is needed when data escapes that nesting discipline.

11. Activation trees and call graphs

An activation tree represents the dynamic execution of a program. Each node is one activation, and a child node represents a call made by its parent.

For:

1main calls A
2A calls B
3A calls C

the activation tree is:

A call graph, in contrast, describes possible calling relationships in the program and may contain cycles due to recursion. An activation tree describes one particular execution and therefore contains concrete invocation instances.

Footnotes

1. Concepts Introduced in Chapter 7: Activation Records - Runtime call and activation concepts. ↩

12. Relationship to compiler implementation

The compiler must decide:

• Which values reside in registers.
• Which values require stack slots.
• How arguments and results are passed.
• Where the return address is stored.
• How frame pointers and stack pointers are managed.
• How nonlocal variables are accessed.
• Whether a frame can be omitted or reused.
• How exception handlers and debugging metadata are represented.

The generated machine code is commonly divided into:

• Prologue: establishes the new frame.
• Body: performs the routine’s computation.
• Epilogue: restores state and returns.

An optimizing compiler may use a frame-pointer omission optimization, where $SP$ or another register is used directly for addressing. It may also inline a function, eliminating a separate call and activation record altogether.

Therefore, an activation record is best understood as a runtime and compiler abstraction. Its logical fields may exist even when no literal contiguous block with those fields is emitted.

13. Security and reliability considerations

Activation records are also relevant to system reliability and security.

• Incorrect bounds handling can overwrite return addresses or saved control state.
• Stack exhaustion can terminate a program or trigger a runtime exception.
• Calling-convention mismatches can corrupt arguments, registers, or return state.
• Unsafe use of pointers to expired stack data can produce undefined behavior.
• Exception handling may require metadata that identifies handlers and frame-unwinding actions.

Modern systems commonly use defenses such as stack canaries, non-executable stack policies, address-space randomization, and control-flow protections. These mechanisms do not change the conceptual purpose of activation records, but they protect sensitive control information stored near or within stack frames.

Footnotes

1. Calling Conventions - Stack-based procedure-call mechanisms and preservation of return state. ↩

14. Model short note

An activation record, also called a stack frame, is a runtime data structure created for each invocation of a procedure or function. It stores the information required to execute that invocation and return control to its caller. Typical fields include the return value, actual parameters, return address, dynamic link, static or access link, saved machine status, local variables, and temporary values.

Activation records are commonly allocated on the runtime stack. A new record is created when a procedure is called and removed when the procedure returns. The return address identifies where the caller resumes, while the dynamic link points to the caller’s activation record. In languages with nested procedures and lexical scoping, a static link points to the activation record of the lexically enclosing procedure and permits access to nonlocal variables.

Activation records make recursion possible because every recursive call receives a separate frame containing its own parameters, local variables, and return address. The compiler manages the record through a calling sequence, a callee prologue, a procedure body, and a return epilogue. Although the conceptual fields are standard, their physical layout depends on the target architecture, ABI, programming language, and compiler optimizations. Data that outlives its defining call, such as captured variables in closures, may require heap allocation rather than ordinary stack allocation.

Footnotes

1. Activation Records/Stack Frames - Princeton University - Lecture material defining activation records, their lifetime, recursion, dynamic links, and static links. ↩

2. Activation Records - Summary of activation-record fields and distinction between access and control links. ↩