Chapter 10 PPT

Chapter 10: Implementing Subprograms

1. Subprogram Linkage

• Definition: The subprogram call and return are referred to as subprogram linkage.

• Activation Record: The format and layout of the non-code part of a subprogram.

  • An activation record instance is a concrete example of an activation record.

2. General Semantics of Calls to a Subprogram

• Parameter Passing Methods: Various methods to pass parameters to subprograms.

• Stack-Dynamic Allocation of Local Variables: Dynamic allocation of local variables as needed.

• Save Execution Status: Save the execution status of the calling program before control is transferred.

• Transfer Control: Control is transferred to the called subprogram.

• Access Nonlocal Variables: Arrangements must be made to access nonlocal variables if subprogram nesting is supported.

3. General Semantics of Subprogram Returns

• Parameter Modes: In in mode and inout mode, parameters must have their values returned to the caller.

• Deallocation: Stack-dynamic locals should be deallocated when the subprogram completes.

• Restore Execution Status: The execution status of the caller must be restored.

• Return Control: Control is returned to the caller once the subprogram execution completes.

4. Implementing "Simple" Subprograms

• Simple Programs: Defined as subprograms that cannot be nested, where all local variables are static.

• Structure of Subprogram: Consists of:

  • Actual code

  • Non-code part (local variables and mutable data)

  • The format of this non-code part is known as activation record.

• Static Activation Record: The activation record form is static; however, it can be statically allocated.

• There exists only one activation record instance per program execution.

5. Call Semantics for Simple Subprograms

• Actions During Call:

  • Save the execution status of the caller.

  • Pass the parameters to the called subprogram.

  • Pass the return address to the called subprogram.

  • Transfer control to the called subprogram.

6. Return Semantics for Simple Subprograms

• Actions During Return:

  • If parameters are passed by value-result or out-mode, their current values are copied back to the corresponding actual parameters.

  • If the subprogram is a function, its return value is moved to a place accessible to the caller.

  • Restore the execution status of the caller.

  • Transfer control back to the caller.

• Required Storage: Includes status information, parameters, the return address, the return value for functions, and temporary storage.

7. Activation Record Structure for Simple Subprograms

• Contains:

  • Local variables

  • Parameters

  • Return address

8. Implementing Subprograms with Stack-Dynamic Local Variables

• Challenges: More complicated as it necessitates code for implicit allocation and deallocation of local variables and supports recursion.

• Activation Record Format: Known at compile time but its size may be dynamic.

  • Example: Size of a local array may depend on actual parameters.

• Dynamic Links: Points to the base of an instance of the activation record of the caller (known as the dynamic parent).

• Environment Pointer (EP): Maintained by the runtime system, points to the base of the activation record instance of the currently executing program unit.

9. Typical Activation Record Structure for Languages with Stack-Dynamic Local Variables

• Contents of Activation Record:

  • Local variables

  • Parameters

  • Dynamic link

  • Stack top

  • Return address

10. Revised Semantic Call/Return Actions

• Caller Actions:

  • Create an activation record instance.

  • Save execution status of the current program unit.

  • Compute and pass parameters.

  • Pass return address to the called subprogram.

  • Transfer control to the called subprogram.

• Prologue Actions of the Called:

  • Save the old EP in the stack as the dynamic link, create the new value, and allocate local variables.

11. Example of C Function

• Example Function:

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

12. Implementing Subprograms without Recursion in C

• Example Functions:

  • void fun1(float r) with local variables s, t. Calls fun2(s).

  • void fun2(int x) calls fun3(y).

  • void fun3(int q) has another logic and returns to fun1.

13. Stack Content Description for Each Function

• Each function has associated stack contents described in terms of local variables, parameters, and dynamic links.

14. Implementing Subprograms in ALGOL-like Languages

• Dynamic Chain: Collection of dynamic links forming the stack at a given moment, allowing access to local variables by their offsets from the activation record start.

• Local Offset: Can be determined by the compiler; determined by the position of the local variable relative to parameters.

15. Recursion Example

• Factorial Function:

  int factorial(int n) {
      if (n <= 1)
          return 1;
      else
          return (n * factorial(n - 1));
  }

• The recursive aspect creates multiple activation records for each function call.

16. Stack for Calls to Factorial Function

• Diagram or description of stack contents for each activation and how local variables correspond to parameters and execution links for recursive calls.

17. Nested Subprograms

• Static-scoped languages using stack-dynamic local variables allow for subprogram nesting.

• Access to Nonlocal Variables: Requires finding the correct activation record instance and determining offsets within that instance.

18. Finding Nonlocal References

• Finding Offsets: Straightforward, but determining the activation record instance involves static semantic rules to ensure nonlocal variables have been allocated.

19. Static Chains

• Static Links: Chains connecting activation records to their static parents, essential for resolving nonlocal references.

• Static Depth: Indicates the level of nesting in the scope hierarchy, defined as an integer related to the nesting of subprograms.

20. Representing Nonlocal References

• Represented as a pair of static depth (chain offset) and local offset.

21. Example Pascal Program

• Details an example of nested subprograms in Pascal with a call sequence and variables reflecting different activation record instances.

22. Static Chain Maintenance

• Maintaining Static Chains: Techniques for maintaining the static linkage during program execution, particularly during calls and returns.

23. Evaluation of Static Chain Method

• Problems include inefficiencies in nonlocal reference lookups and variability in performance.

24. Blocks

• Definition: User-defined local scopes in programming that limit variable lifetimes, improving encapsulation.

25. Implementing Blocks

• Two methods:

  1. Handle blocks as parameter-less subprograms (activation records created every execution).

  2. Allocate maximum storage for blocks dynamically based on static analysis of usage.

26. Implementing Dynamic Scoping

• Deep Access: Nonlocal references resolved dynamically through activation record chains.

• Shallow Access: Varied methods such as central tables for variable names.

27. Programming Example for Dynamic Scoping

• Illustrates how dynamic scoping could be accomplished with example function declarations.