Chapter 10 Notes

10 Implementing Subprograms

10.1 The General Semantics of Calls and Returns

• Subprogram call and return operations are collectively termed subprogram linkage, which encompasses all the actions necessary to initiate and conclude the execution of a subprogram.

• Effective implementation of subprograms necessitates a thorough understanding of the specific semantics of subprogram linkage as defined by the programming language being used.

• A subprogram call involves a sequence of critical actions that set up the execution environment for the called subprogram:

  • Implementation of the parameter-passing method: This involves determining how actual parameters are transmitted to formal parameters (e.g., by value, by reference, by result, by value-result, or by name). This often includes copying values, passing addresses, or creating aliases.

  • Allocation of storage for local variables: If local variables are not static (i.e., their lifetimes extend beyond a single subprogram activation), storage must be dynamically allocated for them, typically on the run-time stack. For static local variables, storage is fixed at compile time and persists throughout program execution.

  • Binding of local variables to the allocated storage: This process associates the names of local variables with their newly allocated memory locations.

  • Saving the execution status of the calling program unit: This is crucial for correctly resuming the caller after the subprogram completes. Information saved typically includes:

    • Register values: The contents of CPU registers (e.g., general-purpose registers, floating-point registers) are saved to prevent corruption by the called subprogram.

    • CPU status bits (condition code register): These bits reflect results of recent arithmetic or logical operations.

    • Program Counter (PC): The address of the next instruction to be executed in the calling program unit, which serves as the return address.

    • Stack Pointer (SP): The current top of the run-time stack.

    • Frame Pointer (FP): Also known as the Environment Pointer (EP), this pointer maintains the base address of the current subprogram's activation record on the stack, allowing access to its parameters and local variables. Its role is elaborated in Section 10.3.

  • Transfer of control to the subprogram: This typically involves loading the subprogram's entry point address into the Program Counter. Simultaneously, the return control point (the saved PC) is established so that control can be correctly given back to the caller upon subprogram completion.

  • For nested subprograms: An additional mechanism is required to enable the called subprogram to access nonlocal variables defined in its enclosing static ancestor scopes.

• The return procedure is generally less complex but equally vital for proper program execution:

  • Moving values of out-mode or pass-by-value-result parameters: If a parameter-passing method dictates, the current values of formal parameters are copied back to their corresponding actual parameters in the calling program unit.

  • Deallocating storage of local variables: Any stack-dynamic local variables allocated during the call are deallocated, typically by adjusting the stack pointer.

  • Restoring the execution status of the calling program unit: The saved register values, CPU status bits, and other critical state information are reloaded into the CPU, essentially reinstating the caller's execution context.

  • Returning control to the caller: The saved return address is loaded back into the PC, causing execution to resume at the instruction immediately following the subprogram call.

10.2 Implementing "Simple" Subprograms

• Here, simple subprograms are characterized as those that cannot be nested and whose local variables are static (i.e., they have fixed memory locations allocated at compile time and retain their values across multiple calls). Early versions of Fortran exemplify such subprograms, notably lacking recursion or nested scopes.

• Call semantics for simple subprograms entail the following precise actions:

  1. Save execution status of the current program unit: This involves storing essential CPU state, such as relevant register values and condition codes, which are later restored to allow the caller to resume execution seamlessly.

  2. Compute and pass parameters: Actual parameters are evaluated (if expressions) and then passed to the formal parameters of the called subprogram. In simple subprograms, this often involves passing values on the stack or in dedicated registers.

  3. Pass the return address to the called subprogram: The memory address of the instruction immediately after the call in the caller is made available to the subprogram, typically on the stack or in a register, to facilitate the return.

  4. Transfer control to the called subprogram: The program counter is updated to point to the entry point of the subprogram, initiating its execution.

• Return semantics for simple subprograms require inverse actions to restore the caller's state:

  1. For pass-by-value-result or out-mode parameters: If these mechanisms are supported, the updated values of the subprogram's formal parameters are copied back to the actual parameters in the caller's context.

  2. If the subprogram is a function: The computed functional value must be placed in a location designated for return values (e.g., a specific register or a stack location) that is accessible by the caller.

  3. Restore the execution status of the caller: The previously saved CPU status (registers, condition codes) is reloaded.

  4. Transfer control back to the caller: The stored return address is placed into the program counter, causing execution to resume in the calling unit.

• Required storage for call and return actions during runtime typically includes:

  • Status information about the caller: Saved contents of the Program Counter, Stack Pointer, Frame Pointer, and other CPU registers.

  • Parameters: The actual values or addresses of parameters being passed.

  • Return address: The memory address for resuming execution in the calling unit.

  • Return value for functions: Temporary storage for the result of a function call.

  • Temporaries used by the code of the subprograms: Compiler-generated temporary variables needed for intermediate calculations within the subprogram.

Activation Record

• The activation record (AR), often referred to as a stack frame, is a logical block of information created on the run-time stack each time a subprogram is invoked. It represents the layout for the noncode parts of a subprogram, holding all information relevant during that subprogram's activation.

• In simple subprograms, both the code and the noncode parts (i.e., the activation record) have fixed sizes determined at compile time because recursion is not allowed and local variables are static.

• An activation record instance (ARI) is a concrete occurrence, or a specific instantiation, of this record for a particular subprogram call.

• Since recursion is not allowed in simple subprograms, a subprogram can only be active once at any given time. Therefore, only a single instance of an activation record exists per subprogram, and its storage can sometimes be allocated statically rather than on the stack.

10.3 Implementing Subprograms with Stack-Dynamic Local Variables

• This section discusses languages that employ stack-dynamic local variables, which are allocated on the run-time stack when a subprogram is called and deallocated when it returns. This dynamic allocation scheme is critical for facilitating recursion.

10.3.1 More Complex Activation Records

• Subprogram linkage is significantly more complex in languages supporting stack-dynamic local variables and recursion, primarily due to two factors:

  1. Implicit allocation and deallocation of local variables must be managed by the compiler at runtime: Storage for local variables is no longer fixed; it must be requested when the subprogram is called and released when it exits. This typically involves adjusting a stack pointer.

  2. Supporting recursion permits multiple simultaneous activations of a subprogram: Each recursive call creates a new, independent execution context. This necessitates separate ARIs for each active invocation of the subprogram, all residing concurrently on the run-time stack.

Activation Records' Structure for Stack-Dynamic Variables

• The activation record layout for subprograms with stack-dynamic local variables is designed to accommodate the variable nature of runtime execution. It typically involves storage for:

  • Return address: The memory location where execution should resume in the caller.

  • Dynamic link: A pointer to the base of the ARI of the caller. This link forms a chain of ARIs on the stack, representing the dynamic (call-time) sequence of subprogram invocations.

  • Static link (if nested subprograms are supported, as discussed in 10.4.2): A pointer to the base of the ARI of the subprogram's static parent (the immediately enclosing scope in the source code), used for accessing nonlocal variables.

  • Parameters: The values or addresses of the actual parameters.

  • Local variables: Scalar local variables (e.g., int, float) are typically stored directly within the ARI. For structured types (e.g., arrays, records, objects), the ARI might contain only descriptors and pointers to where the actual data is stored on the heap or another part of the stack.

  • Saved registers: Values of registers that the subprogram might modify, which need to be restored for the caller.

  • Return value: Space for the function's result.

  • Temporaries: Storage for intermediate expression results used by the compiler.

Example: Consider a skeletal C function:

c void sub(float total, int part) { int list[5]; float sum; . . . }

• An activation record for sub would be structured on the stack to include the return address, dynamic link, the total and part parameters, the list array, and the sum float variable, along with any other necessary control information.

Execution Control

• Each activation of a subprogram creates a new instance of its AR on the run-time stack. Calls push ARIs onto the stack, and returns pop them off.

• The Environment Pointer (EP), also often called the Frame Pointer (FP), is a register that always points to the base of the current ARI. This allows the subprogram to access its parameters and local variables efficiently using fixed offsets from the EP (e.g., EP + offset_for_variable_X). Each ARI, therefore, provides a unique and separate storage area for its parameters and local variables, crucial for recursion.

• When a subprogram is called, the current EP is saved (often as part of the dynamic link or a separate field within the new ARI), the stack pointer is adjusted to allocate space for the new ARI, and the EP is then updated to point to the base of this new AR. The dynamic link field in the new ARI contains the prior value of the EP, which points to the caller's ARI.

• Upon returning from a subprogram, the stack pointer is updated to deallocate the current ARI (typically by setting it to the value stored in the dynamic link of the current ARI), and the EP is reset to point to the ARI of the calling program unit (by restoring the value from the dynamic link).

10.4 Nested Subprograms

• Languages supporting nested subprograms allow one subprogram definition to be enclosed within another. When combined with stack-dynamic local variables, this adds complexity to variable access. Examples include Ada, Python, JavaScript, Ruby, and Swift.

10.4.1 The Basics

• Access to a nonlocal variable (a variable declared in an enclosing scope, but not the current one) within a static-scoped nested environment requires a two-step process:

  1. Locating the appropriate ARI in the stack from which the variable was allocated: This involves identifying which specific activation record instance, among all those currently on the stack, corresponds to the static scope where the nonlocal variable was declared.

  2. Utilizing the local offset to access that variable: Once the correct ARI's base address is found, the variable's value can be retrieved using its known offset from that base address.

• The correct ARI is determined through static parent scope rules, which dictate that a subprogram can only access variables declared in its own scope or in the scopes of its directly or indirectly enclosing (static ancestor) subprograms that are currently active. This means the search for a nonlocal variable follows the static nesting structure of the program.

10.4.2 Static Chains

• Static chaining is a common technique used to implement static scoping for nonlocal variable access. It works by adding a pointer, called a static link, to each ARI.

• This static link in an ARI points to the bottom (or base) of the ARI of the subprogram's static parent (the immediately enclosing textual subprogram definition) that is currently active on the stack. Essentially, it points to the ARI of the subprogram that textually encloses the current subprogram, not necessarily the one that called it (which is pointed to by the dynamic link).

• These static chains form a linked list of ARIs, where each link connects an ARI to its static parent's ARI. To access a nonlocal variable declared $k$ levels up in the static nesting hierarchy, the processor traverses $k$ static links starting from the current ARI's static link. For example, if a variable is in the scope of the grandparent, two static links would be followed.

• The number of static links to be traversed can be determined at compile time for each nonlocal reference, making access efficient. The final address of the nonlocal variable is then found by applying its known offset to the base address of the found ARI.

10.5 Blocks

• Blocks are user-specified local scopes, usually delimited by curly braces (e.g., in C, C++, Java) or do/end (in Ruby/Lua), allowing for the declaration of variables whose scope and lifetime are restricted to that block. They provide a way to create temporary variable storage without interfering with variable names outside the block's scope, enhancing modularity and reducing name collisions.

• For example, in C:

void foo() {
    int x = 10;
    {
        int y = 20; // y is local to this block
        // x and y are accessible here
    } // y is deallocated here
    // y is not accessible here, but x is
}

• Blocks can function similarly to parameter-less subprograms in terms of their execution. Upon entry to a block, a small, block-specific activation record (or a portion of the current AR) might be created on the stack to hold its local variables. These variables are allocated upon block entry and deallocated upon block exit.

10.6 Implementing Dynamic Scoping

• Dynamic scoping dictates that the meaning of a nonlocal variable reference is determined by the most recent subprogram activation that defined the variable. This means the scope is based on the dynamic call sequence rather than the static textual nesting.

10.6.1 Deep Access

• In deep access for dynamic scoping, when a nonlocal variable is referenced, the runtime system searches through the dynamic chain (formed by the dynamic links in the ARIs on the stack). The search begins with the current ARI and proceeds up the chain towards the caller's caller, and so on, until the first ARI containing a declaration for the variable is found.

• The variable from that ARI is then used. This method accurately implements dynamic scoping because it always finds the most recently active definition. However, it can incur significant runtime overhead due to the potentially long search chain for each nonlocal variable access.

10.6.2 Shallow Access

• Shallow access provides a more efficient approach to implementing dynamic scoping by simplifying variable management. Instead of searching through ARIs on a stack, it uses a central table (or separate stacks) for each unique variable name.

• When a subprogram is called, if it redeclares a variable name, the current value of that variable from the central table is saved (e.g., pushed onto an auxiliary stack associated with that variable name), and the new definition's value (or reference) is placed into the central table.

• When a subprogram returns, the previous value of any variables it shadowed is restored from the auxiliary stack. This means that access to any nonlocal variable simply involves looking up its current binding in the central table, which is a constant-time operation ($O(1)$).

SUMMARY

• Implementation of subprograms, particularly those with dynamic or nested behaviors, introduces more complex state management strategies such as maintaining activations records, dynamic/static links, and enhancing variable access mechanisms.