CSE 505 Lecture Notes:
Implementation of Block Structured Languages
September 1999
Subprograms in Fortran
- no recursive call
- variables are statically bound to memory locations
- location for return address can be statically allocated
Procedures and functions in Algol-like languages
activation record is dynamically allocated upon procedure call
activation record includes:
- dynamic link -- a pointer to the caller's activation record
- formal parameters
- static link -- a pointer to the environment of definition of the
procedure or function (another activation record)
subprogram invocation:
- pass parameters
- save the caller's state
- set up the dynamic link
- set up the static link
- start executing the callee
return from the subprogram:
- restore the caller's state
- resume the execution of the caller
subprograms are scope defining constructs.
local variables:
- simple variables are stored at a known offset from the base of the
activation record
- arrays of dynamic size are accessed indirectly, through an array
descriptor at a known location
nonlocal variables:
- need to access the activation record of the procedure where
this variable is local, using the static links
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 squid(n: integer);
begin
procedure octopus;
begin
print(global);
print(n);
end;
octopus;
end;
global := 3;
n := 100;
squid(1);
end;
Procedure squid has nesting depth 1. In squid,
n has static distance 0.
Procedure octopus has nesting depth 2. So in
octopus, n has static distance 1, and
global has static distance 2. (Note that we use the
n defined in squid.)
Example 2
(similar to example 1, except that squid is recursive)
begin
integer global, n;
procedure squid(n: integer);
begin
procedure octopus;
begin
print(global);
print(n);
end;
if n<4 then squid(n+1);
else octopus;
end;
global := 3;
n := 100;
squid(1);
end;
Procedure squid has nesting depth 1. In squid,
n has static distance 0.
Procedure octopus has nesting depth 2. So in
octopus, n has static distance 1, and
global has static distance 2. (Note that we use the
n defined in squid.)
Example 3
This is similar to example 2, except that octopus isn't nested
inside of squid.
begin
integer global, n;
procedure octopus;
begin
print(global);
print(n);
end;
procedure squid(n: integer);
begin
if n<4 then squid(n+1);
else octopus;
end;
global := 3;
n := 100;
squid(1);
end;
Procedure squid has nesting depth 1. In squid,
n has static distance 0.
Procedure octopus also has nesting depth 1. So in
octopus, 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.