• Subprogram sequence control
• Simple call-return subprograms
• Recursive subprograms
• Attributes of data control
• Names and referencing environments
• Static and dynamic scope
• Block structure
• Local data and local referencing environments

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

Terminology:

1. Subprogram Sequence Control

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

Execution of subprograms
Outline of the method:

1. Subprogram definition and subprogram activation.

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

2. 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.

2. Recursive subprograms

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.

2. Attributes of data control

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

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

Example: x = y + 2*z;
The result of multiplication is transmitted directly as an operand of the addition operation.

2. 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
2. Static and dynamic scope

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.

3. Block structure

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



4. Local data and local referencing environments

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.

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.