CmSc 315 DM Programming Languages


Chapter 9: Subprogram Control


Subprogram control: interaction among subprograms and how subprograms manage to pass data among themselves in a structured and efficient manner.

Terminology:

Function call subprograms that return values directly
Subroutine call subprograms that operate only through side effects on shared data.

  1. Subprogram Sequence Control
  2. Simple subprogram call return

    Copy rule view of subprograms: the effect of a call statement is the same as if
    the subprogram were copied and inserted into the main program.

    Implicit assumptions present in this view :

    • Subprograms cannot be recursive
    • Explicit call statements are required
    • Subprograms must execute completely at each call
    • Immediate transfer of control at point of call
    • Single execution sequence

    1. Simple call-return subprograms
    2. Execution of subprograms
      Outline of the method:

      1. Subprogram definition and subprogram activation.
      2. The definition is translated into a template, used to create an activation
        each time a subprogram is called.

      3. Subprogram activation: consists of
        • a code segment (the invariant part) - executable code and constants
        • an activation record (the dynamic part) - local data, parameters
          created anew each time the subprogram is called,
          destroyed when the subprogram returns.

      Execution is implemented by the use of two system-defined pointers:

      • Current-instruction pointer CIP-address of the next statement to be executed
      • Current-environment pointer CEP- pointer to the activation record.

      On call instruction:

      1. An activation record is created.
      2. Current CIP and CEP are saved in the created activation record as return point
      3. CEP is assigned the address of the activation record.
      4. CIP gets the address of the first instruction in the code segment
      5. The execution continues from the address in CIP

      On return

      1. The old values of CIP and CEP are retrieved .
      2. The execution continues from the address in CIP

      Restrictions of the model: at most one activation of any subprogram

      The simplest implementation: to allocate storage for each activation as an extension of the code segment. Used in FORTRAN and COBOL.
      The activation record is not destroyed - only reinitialized for each subprogram execution.

      Hardware support - CIP is the program counter, CEP is not used, simple jump executed on return.

      Stack-based implementation - the simplest run-time storage management technique

      call statements : push CIP and CEP
      return statements : pop CIP and CEP off of the stack.

      Used in most C implementations
      LISP: uses the stack as an environment.

    3. Recursive subprograms
    4. Specification

      Syntactically - no difference
      Semantically - multiple activations of the same subprogram exist
      simultaneously at some point in the execution.

      Implementation

      Stack-based - CIP and CEP are stored in stack, forming a dynamic chain of links.

      • A new activation record is created for each call and destroyed at return.
      • The lifetimes of the activation records cannot overlap - they are nested.

      Some language compilers (C, Pascal) always assume recursive structure of subprograms,
      while in others non-recursive subprograms are implemented in the simple way.

  3. Attributes of data control
  4. Data control features: determine the accessibility of data at different points during program execution.

    Central problem: the meaning of variable names,
    i.e. the correspondence between names and memory locations.

    1. Names and referencing environments
    2. Two ways to make a data object available as an operand for an operation.

      1. Direct transmission A data object computed at one point as the result of
        an operation may be directly transmitted to another operation as an operand
      2. Example: x = y + 2*z;
        The result of multiplication is transmitted directly as an operand of the addition operation.

      3. Referencing through a named data object
        A data object may be given a name when it is created, and the name may then
        be used to designate it as an operand of an operation.

      1. 1. Program elements that may be named

      1. Variables
      2. Formal parameters
      3. Subprograms
      4. Defined types
      5. Defined constants
      6. Labels
      7. Exception names
      8. Primitive operations
      9. Literal constants

      Names from 4 thru 9 - resolved at translation time.
      Names 1 thru 3 - discussed below.

      Simple names: identifiers, e.g. var1.
      Composite names: names for data structure components, e.g. student[4].last_name.

      1. 2. Associations and Referencing Environments

      Association: binding identifiers to particular data objects and subprograms
      Referencing environment: the set of identifier associations for a given subprogram.
      Referencing operations during program execution: determine the particular data object
      or subprogram associated with an identifier.

      Local referencing environment:

      The set of associations created on entry to a subprogram that represent formal parameters, local variables, and subprograms defined only within that subprogram

      Nonlocal referencing environment:

      The set of associations for identifiers that may be used within a subprogram
      but that are not created on entry to it. Can be global or predefined.

      Global referencing environment: associations created at the start of execution
      of the main program, available to be used in a subprogram,

      Predefined referencing environments: predefined association in the language definition.

      Visibility of associations

      Associations are visible if they are part of the referencing environment.
      Otherwise associations are hidden

      Dynamic scope of associations

      The set of subprogram activations within which the association is visible

      1. 3. Aliases for data objects: Multiple names of a data object

      • separate environments - no problem
      • in a single referencing environment - called aliases.

      Problems with aliasing

      • Can make code difficult to understand for the programmer.
      • Implementation difficulties at the optimization step - difficult to spot interdependent statements - not to reorder them

    3. Static and dynamic scope
    4. The dynamic scope of an association for an identifier is that set of subprogram activations in which the association is visible during execution.

      Dynamic scope rules

      relate references with associations for names during program execution.

      The static scope of a declaration is that part of the program text where a use of the identifier is a reference to that particular declaration of the identifier.

      Static scope rules

      relate references with declarations of names in the program text.

      Importance of static scope rules - recording information about a variable during translation.

    5. Block structure
    6. Block-structured languages (Pascal):

      • Each program or subprogram is organized as a set of nested blocks.
      • The chief characteristic of a block is that it introduces a new local referencing environment.

      Static scope rules for block-structured programs

    7. Local data and local referencing environments
    8. Local environment of a subprogram: various identifiers declared in the subprogram -
      variable names, parameters, subprogram names.

      Static scope rules: implemented by means of a table of the local declarations
      Dynamic scope rules: two methods:

      • Retention - associations and the bound values are retained after execution.
      • Deletion - associations are deleted.
        (For further explanation and example see Figure 9.9 on p. 369)

      Implementation of dynamic scope rules in local referencing environments:
      by means of a local environment table to associate names, types and values.

      Retention: the table is kept as part of the code segment
      Deletion: the table is kept as part of the activation record, destroyed after each execution.


Exam-like questions

  1. What are the assumptions in simple subprogram call-return?
  2. Describe the simple subprogram call-return. Outline the method.
    Describe what happens on call and what happens on return.
  3. Discuss the implementation of recursive subprograms.
  4. Describe two methods to make a data object available as an operand of an operation.
  5. Define the terms "association" and "referencing environment"
  6. What is local referencing environment?
  7. What is non-local referencing environment?
    List and define types of non-local referencing environments.
  8. What is the purpose of dynamic scope rules?
  9. What is the purpose of static scope rules?
  10. How are static scope rules implemented in local referencing environments?
  11. Describe two approaches for dynamic scope rules in local referencing environments and their implementation.

Back to contents
Created by Lydia Sinapova