CSE 505 Lecture Notes:

Implementation of Block Structured Languages

October 17, 1994


Subprograms in Fortran

Procedures and functions in Algol-like languages

activation record is dynamically allocated upon procedure call

activation record includes:

subprogram invocation:

return from the subprogram: subprograms are scope defining constructs.

local variables:

nonlocal variables: Variables are represented as <static nesting level, offset> pairs in the symbol table.

static nesting level: number of containing scopes surrounding the the environment in which the name is defined

static distance: calculate the difference between the static nesting level of the use of the variable and that of its definiton.

to access a nonlocal variable v with static distance d, the compiler sets up code to traverse d static links, then load v at the known offset in that activation record

Optimization: statistically, most variables are local or global. Local variable access is already efficient. Also make it efficient to access the global stack frame, for example, by putting a pointer to the global stack frame in a register.


Example 1

begin integer global, n; procedure laurel(n: integer); begin procedure hardy; begin print(global); print(n); end; if n<4 then laurel(n+1); else hardy; end; global := 3; n := 100; laurel(1); end; Procedure laurel has nesting depth 1. In laurel, n has static distance 0.

Procedure hardy has nesting depth 2. So in hardy, n has static distance 1, and global has static distance 2. (Note that we use the n defined in laurel.)


Example 2

This is similar to example 1, except that hardy isn't nested inside of laurel. begin integer global, n; procedure hardy; begin print(global); print(n); end; procedure laurel(n: integer); begin if n<4 then laurel(n+1); else hardy; end; global := 3; n := 100; laurel(1); end; Procedure laurel has nesting depth 1. In laurel, n has static distance 0.

Procedure hardy also has nesting depth 1. So in hardy, both n and global have static distance 1. (Note that we use the n defined in the global scope.)


display: alternative to static links -- little stack of pointers to lexically enclosing stack frames

display is more efficient to access nonlocal variables but more expensive on procedure entry and exit


Procedures as Parameters: Closures

Procedure parameters are represented by closures, consisting of a pointer to the procedure's code, and a pointer to the the environment of the definition of the procedure.

To invoke a procedure passed as a parameter, set up the activation record as ususal, but use the pointer to the environment of the definition of the procedure to set the static link.

Nonlocal gotos require environment restoration: to pass an address for a nonlocal goto, also include a pointer to the environment.