Chapter 10   Subprogram Implementation

The General Semantics of Calls and Returns

FORTRAN77 - very simple linkage
ALGOL-Like : Pascal, Ada, FORTRAN 90
C, C++, Java: like "ALGOL-Like" but no nesting of subprogram  (simple)

Activation Record:

· Format is known at compile time.
· Size can be dynamic

FORTRAN 77   (figures 9.1 & 9.2)

 Space created ahead of time

Figure 9.1
Figure 9.2 (Everything decided in advance)

Dynamic Link
            Point to the top of Activation Record of caller
Static Link
            Point to bottom of Activation Record of the Static Parent
Return Address
            Point to caller

Figure 9.3

Figure 9.4 (Created on the run-time stack)

Program (Main -1)
ARI (Activation Record Instance)  (Figure 9.5)

Program (Recursion)
ARI (Activation Record Instance)-1  (Figure 9.7)
ARI (Activation Record Instance)-2  (Figure 9.8)

There are two major implementation techniques for creating accesses to nonlocal variables in a static-scoped language:
static chains and displays.

Static Chains:

offset:  (Read page 385)

In relative addressing methods, a number that tells how far from a starting point to a particular item is located.

static_depth: (Read page 390)

an integer associated with a static scope that indicates how deeply it is nested in the outermost scope.

Pascal main program has a static_depth of 0.

nested depth or chain offset: (Read page 390)

• the length of the static chain
• = the static_depth of reference to X - the static_depth of declaration of X.

The references to A at points 1, 2, 3 in the following program are:

(chain offset, local offset)
(0, 3) (local)
(2, 3) (two levels away)
(1, 3) (one level away)

Program  (Main-2)
ARI (Activation Record Instance) Figure 9.9

Displays:

The static links are collected in a single array called a display.
The contents of the display is a list of addresses of the accessible ARI in the stack.
display offsets is similar to chain offset in static chains.

Program (Main-3)
Q call P:
Qsd = Psd Figure 9.10 (Display)
Qsd < Psd Figure 9.11 (Display)
Program (Main-4)
Qsd < Psd Figure 9.12, 13 (Display)
Qsd > Psd Figure 9.14 (Display)

Program (Main-5)   and Figure 9.15

Deep Access:

Program (Main-6)
Figur 9.16

Shallow Access:

Figur 9.17

Program (Main-7)
Figur 9.18