Call stack

A call stack stores active procedure calls and the information needed to resume each caller, such as its return location and local variables. A call adds a frame; returning removes that frame and resumes the previous call. When depth-first search uses recursion, a frame also records where its adjacency list scan paused. The active frames describe a graph path from the starting vertex to the current vertex; finished calls have left the call stack, although their vertices remain marked as discovered.

A table of pointers supporting direct access to active lexical environments without traversing a static chain. A conventional display is indexed by lexical level; a procedure-indexed alternative keeps the newest activation of each procedure and saves and restores the previous table entry on entry and return.

For direct calls under lexical scope, the executing activation's static chain contains the newest surviving activations of its enclosing procedures. This follows by mathematical induction on calls and returns: a direct call inherits a suffix of the caller's chain, and a return restores the previous chain after intervening activations finish. With procedural parameters, a passed programming closure can instead refer to an older still-active enclosing activation, so simply consulting the newest-activation table is insufficient.

The chain of active callers obtained by following dynamic links from the current stack frame. It records call history, whereas a static chain records lexical environments.

The sequence of stack frames reached by following static links. A variable declared $d$ lexical levels outside the current procedure is accessed by following $d$ static links and applying its known frame offset.

Stack alignment constrains the stack pointer to a multiple of a specified byte boundary. AAPCS32 requires word alignment generally and eight-byte alignment at public interfaces. Saving four 32-bit words preserves eight-byte alignment; saving three would change it by four bytes and may require padding before another call. Frame size and the alignment of local objects must be considered together.^[ref]

The record for one active invocation in a call stack, containing information such as local variables and the place to resume its caller. Returning removes that invocation's stack frame, allowing the caller's computation to continue.

A processor register or equivalent value designating a stable reference location within the current stack frame. Parameters, local variables and saved links can be accessed at fixed offsets from the frame pointer even if the evaluation stack changes height.

A pointer from an activation's stack frame to its caller's stack frame, used to restore the caller when the activation returns. The dynamic link is independent of a static link to the lexically enclosing environment.

A pointer from an activation's stack frame to the activation providing its immediate lexical environment. A static link follows lexical enclosure rather than necessarily pointing to the caller. Calls through a programming closure obtain the environment from the passed closure.