CHAPTER 9

IMPLEMENTING SUBPROGRAMS

THE GENERAL SEMANTICS OF CALLS AND RETURNS

• The subprogram call and return operations of a language are together called subprogram linkage.
• Any implementation method for subprograms must be based on the semantics of the subprogram linkage.

IMPLEMENTING FORTRAN 77 SUBPROGRAMS

• The semantics of a Fortran 77 subprogram call requires the following:

- Save the execution status of the current program unit

- Carry out the parameter-passing process

- Pass the return address to the callee

- Transfer control t the callee

• The semantics of a Fortran 77 subprogram return requires the following:

- If pass by value, the current values of those parameters are moved to the corresponding actual parameter.

- If the subprogram is a function, the functional value is moved to a place accessible to the caller.

- The execution status of the caller is restored.

- Control is transferred back to the caller.

• The call and return actions require storage of the following:

- status information about the caller

- parameters

- return address

- functional value for function subprograms

• The function, or layout of the non-code part of a subprogram is called an activation record because the data it describes are only relevant during the activation of the subprogram.
• The form of an activation record is static. An activation record instance is a concrete example of an activation record, a collection of data in the form of an activation record.

Fortran 77 activation record

Functional value

Local variables

Parameters

Return address

• A linker is part of an operating system. When a linker is called for a main program, its first task is to find the files that contain the translated subprograms referenced in that program, along with their activation record instances and load them into memory.

• Subprogram linkage in Algol-like languages is more complex than the linkage in Fortran because:

- parameters can usually be passed by 2 different methods

- variables declared in subprograms are often dynamically allocated

- recursion adds the possibility of multiple activations of a subprogram

- Algol-like languages use static scoping to provide access to non-local variables

• the static link, which is sometimes called a static scope pointer, points to the bottom of the activation record instance of an activation of the static parent. It is used for access by nonlocal variables

• The dynamic link is a pointer to the top of an instance of an of the activation record of the caller.

• The stack that is part of the run-time system is called the run-time stack.

• A subprogram is active from the time it is called until the time that execution is completed.

• The collection of dynamic links present in the stack at a given time is called the dynamic chain.

• A static chain is a chain of static links that connect certain activation record instances in the stack.

• The only widely used alternative to static chains is to use display. For this approach, the static links are collected in a single array called a display, rather than being stored in the activation records. The contents of the display at any specific time is a list of addresses of the accessible activation record instances in the stack – one for each active scope – in the order in which they are nested.

• Blocks are treated as parameter less subprograms that are always called from the same place in the program

• The dynamic chain links together all subprogram activation record instances in the reverse of the order in which they were activated. So, the dynamic chain is exactly what is needed to reference nonlocal variables in a dynamic scoped language. This method is called deep access because access may require searches deep in the stack.