Sebesta Chapter 10 -- Implementing Subprograms
. Subprogam Linkage
. Activation Records
. Static Chains
. Displays
. Deep access versus shallow access
. Referencing environments for subprograms passed as
parameters
subprogram linkage subprogram and call and return operations
CALL
- Call Semantics:
1. Save the execution status of the caller
2. Carry out the parameter-passing process
3. Pass the return address
4. Transfer control to the callee
SUBPROGRAM RETURN
- Return Semantics:
1. If pass-by-value-result parameters are used,
move the current values of those parameters to
their corresponding actual parameters
2. If it is a function, move the functional value to a
place the caller can get it
3. Restore the execution status of the caller
4. Transfer control back to the caller
STORAGE
. status information about caller . parameters
. return address
. functional value
SUBROGRAM PARTS fixed size
. actual code -- static
. local variables and data dynamic
ACTIVATION RECORD non-code portion of subprogram
. no recursion
. only one at a time
. can be statically allocated
Fortran 77 Activation Record
| return address |
| local variables|
| return address |
Fortran 77 Code and Activation Records
MAIN | COMMON storage |
| local variables|
| return address |
A | parameters |
| local variables|
data | return address |
B | parameters |
| local variables|
| return address |
C | parameters |
| local variables|
| |
MAIN | |
| |
| |
A | |
| |
code | |
B | |
| |
| |
C | |
| |
10.3 Implementing Subprograms with Stack Dynamic Locals
. call and returns
. mechanisms for non-local access
static
display
Complex Activation Records
. parameters passed by two methods
. variables in subprogram dynamically allocated
. recursion causes simulataneous activations of subprograms
each AR own copy of formals
copy of dynamic locasl
return address
. static scoping access to non-locals
void sub (float total , int part ){
int list [4]
float sum;
...
}
Typical activation record format for an ALGOL-like language
| local variables |
| Parameters |
| Dynamic link |
| Return address |
Activation record for procedure sub
| local | sum
| local | list[4]
| local | list[3]
| local | list[2]
| local | list[1]
| local | list[0]
| Parameter | part
| Parameter | total
| Dynamic Link |
| Return Address |
Without Recursion
PROGRAM MAIN_1;
VAR p : real;
PROCEDURE A ( X : integer);
VAR Y : boolean;
PROCEDURE C (Q : boolean);
BEGIN
... <----------3
END; {of PROCEDURE C}
BEGIN
... <----------2
C(Y);
...
END; { of PROCEDURE A}
PROCEDURE B (R: real);
VAR S,T : integer;
BEGIN
... <----------1
A(S);
...
END; {of PROCEDURE B)
BEGIN {MAIN_1 }
...
B(P);
...
END.
At 1
<-top
| Dynamic Link --|---
ARI | Return Address | |
for B | local | S |
| local | T |
| parameter |<R |
ARI for| local | P
MAIN_1
At 2
<-top
| Dynamic Link --|---
ARI | Return Address | |
for A | local | Y |
| parameter | X |
| Dynamic Link --|---
ARI | Return Address | |
for B | local | S |
| local | T |
| parameter |<R |
ARI for| local | P
MAIN_1
At 3
| Dynamic Link --|---
ARI | Return Address | |
for C | parameter | Q |
| Dynamic Link --|---|
ARI | Return Address | |
for A | local | Y |
| parameter | X |
| Dynamic Link --|---
ARI | Return Address | |
for B | local | S |
| local | T |
| parameter |<R |
ARI for| local | P
MAIN_1
Dynamic chain (call chain) collection of dynamic links present at any time
local_offset reference to local variables relative to beginning of activation record
RECURSION
PROGRAM Test;
VAR VALUE : integer;
FUNCTION Factorial (N : integer) : integer;
BEGIN <----------------1
IF N <= 1
THEN Factorial := 1
ELSE Factorial := N * Factorial (N-1);
END;
BEGIN {body of Test}
Value := Factorial (3);
writeln ('Factorial of 3 is : " , Value) <-----3
END.
Activation record format for factorial
| |
| Dynamic link |
| Static link |
| Return address |
| Functional value|
| parameter | N
| |top
| Dynamic link |--|----
| Static link | | |
| Return (to Test) | |
| Functional value| ?| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
| |top
| Dynamic link |--|----
2nd ARI| Return(to Factorial| |
| Functional value| ?| |
| parameter | 2|< N |
| Local | ?| VALUE
| Dynamic link |--|----
1st ARI| Return (to Test) | |
| Functional value| ?| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
| |top
| Dynamic link |--|----
3rd ARI| Return(to Factorial| |
| Functional value| ?| |
| parameter | 1|< N |
| Local | ?| VALUE
| Dynamic link |--|----
2nd ARI| Return(to Factorial| |
| Functional value| ?| |
| parameter | 2|< N |
| Local | ?| VALUE
| Dynamic link |--|----
1st ARI| Return (to Test) | |
| Functional value| ?| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
At position 2 in Factorial
| |top
| Dynamic link |--|----
3rd ARI| Return(to Factorial| |
| Functional value| 1| |
| parameter | 1|< N |
| Local | ?| VALUE
| Dynamic link |--|----
2nd ARI| Return(to Factorial| |
| Functional value| ?| |
| parameter | 2|< N |
| Local | ?| VALUE
| Dynamic link |--|----
1st ARI| Return (to Test) | |
| Functional value| ?| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
At position 2 in Factorial
| |top
| Dynamic link |--|----
| Static link | | |
2nd ARI| Return(to Factorial| |
| Functional value| 2| |
| parameter | 2|< N |
| Local | ?| VALUE
| Dynamic link |--|----
1st ARI| Static link | | |
| Return (to Test) | |
| Functional value| ?| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
At position 2 in Factorial
| |top
| Dynamic link |--|----
| Return (to Test) | |
| Functional value| 6| |
| parameter | 3|< N |
ARItest| Local | ?| VALUE
At position 3 in Factorial
ARItest| Local | 6| VALUE
10.4 Nested Subprograms
Fortran 95, Ada Javascript
main ----- static_depth = 0
A ----- static_depth = 1
B ----- static_depth = 2
C ----- static_depth = 1
- Def: The chain_offset or nesting_depth of a
nonlocal reference is the difference between
the static_depth of the reference and that of
the scope where it is declared
- A reference can be represented by the pair:
(chain_offset, local_offset)
where local_offset is the offset in the activation
record of the variable being referenced
10.4 Implementing Nested Subprograms with
Example Program:
program MAIN_2;
var X : integer;
procedure BIGSUB;
var A, B, C : integer;
procedure SUB1;
var A, D : integer;
begin { SUB1 }
A := B + C; <-----------------------1
end; { SUB1 }
procedure SUB2(X : integer);
var B, E : integer;
procedure SUB3;
var C, E : integer;
begin { SUB3 }
SUB1;
E := B + A: <--------------------2
end; { SUB3 }
begin { SUB2 }
SUB3;
A := D + E; <-----------------------3
end; { SUB2 }
begin { BIGSUB }
SUB2(7);
end; { BIGSUB }
begin
BIGSUB;
end. { MAIN_2 }
10.4 Implementing Nested Subprograms with
Call sequence for MAIN_2
MAIN_2 calls BIGSUB
BIGSUB calls SUB2
SUB2 calls SUB3
SUB3 calls SUB1
---> SHOW FIGURE 10.9 (p. 414)
At position 1 in SUB1:
A - (0, 3)
B - (1, 4)
C - (1, 5)
At position 2 in SUB3:
E - (0, 4)
B - (1, 4)
A - (2, 3)
At position 3 in SUB2:
A - (1, 3)
D - an error
E - (0, 5)
At the call (assume there are no parameters that are
subprograms and no pass-by-name parameters:
- The activation record instance must be built
- The dynamic link is just the old stack top
pointer
- The static link must point to the most recent ari
of the static parent (in most situations)
Two Methods:
1. Search the dynamic chain until the first ari
for the static parent is found--easy, but slow
2. Treat procedure calls and definitions like
variable references and definitions
(have the compiler compute the nesting depth,
or number of enclosing scopes between the
caller and the procedure that declared the
called procedure; store this nesting depth
and send it with the call)
e.g. Look at MAIN_2 and Figure 10.9
At the call to SUB1 in SUB3, this nesting
depth is 1, which is sent to SUB1 with
the call. The static link in the new ari for
SUB1 is set to point to the ari that is
pointed to by the second static link in
the static chain from the ari for SUB3
- Evaluation of the Static Chain Method
- Problems:
1. A nonlocal reference is slow if the number of
scopes between the reference and the
declaration of the referenced variable is large
2. Time-critical code is difficult, because the costs
of nonlocal references are not equal, and can
change with code upgrades and fixes
- Technique 2 - Displays
- The idea: Put the static links in a separate stack
called a display. The entries in the display are
pointers to the ari's that have the variables in the
referencing environment.
- Represent references as
(display_offset, local_offset)
where display_offset is the same as chain_offset
- Mechanics of references:
- Use the display_offset to get the pointer into the
display to the ari with the variable
- Use the local_offset to get to the variable within
the ari
- Display maintenance (assuming no parameters that
are subprograms and no pass-by-name parameters)
- Note that display_offset depends only on the static
depth of the procedure whose ari is being built. It
is exactly the static_depth of the procedure.
- There are k+1 entries in the display, where k is the
static depth of the currently executing unit (k=0 is
for the main program)
- For a call to procedure P with a static_depth of k:
a. Save, in the new ari, a copy of the display
pointer at position k
b. Put the link to the ari for P at position k in the
display
- At an exit, move the saved display pointer from
the ari back into the display at position k
- To see that this works:
- Let Psd be the static_depth of P, and
Qsd be the static_depth of Q
- Assume Q calls P
- There are three possible cases:
1. Qsd = Psd
2. Qsd < Psd
3. Qsd > Psd
Example skeletal program:
program MAIN_3;
procedure BIGSUB;
procedure SUB1;
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
end; { BIGSUB }
end. { MAIN_3 }
MAIN_3 can illustrate all three cases
Case 1: SUB2 calls SUB1
Before the call, we have:
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
After the call, we have:
ARI for SUB1
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
Case 2: SUB2 calls SUB3
Before the call, we have:
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
After the call, we have:
ARI for SUB3
ARI for SUB2
3
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
Case 1: SUB2 calls SUB1
Before the call, we have:
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
After the call, we have:
ARI for SUB1
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
Case 2: SUB2 calls SUB3
Before the call, we have:
ARI for SUB2
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
After the call, we have:
ARI for SUB3
ARI for SUB2
3
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
Case 3: SUB3 calls SUB1
Before the call, we have:
ARI for SUB3
ARI for SUB2
3
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
After the call, we have:
ARI for SUB1
ARI for SUB3
ARI for SUB2
3
ARI for BIGSUB 2
1
ARI for MAIN_3 0
Stack Display
- The display can be kept in registers, if there are
enough--it speeds up access and maintenance
- Comparing the Static Chain and Display Methods
1. References to locals
- Not much difference
2. References to nonlocals
- If it is one level away, they are equal
- If it is farther away, the display is faster
- Display is better for time-critical code,
because all nonlocal references cost the same
3. Procedure calls
- For one or two levels of depth, static chain is
faster
- Otherwise, the display is faster
4. Procedure returns
- Both have fixed time, but the static chain is
slightly faster
- Overall: Static chain is better, unless the display
can be kept in registers
10.5 Implementing Blocks
- Two Methods:
1. Treat blocks as parameterless subprograms
- Use activation records
2. Allocate locals on top of the ari of the
subprogram
- Must use a different method to access locals
- A little more work for the compiler writer
10.6 Implementing Dynamic Scoping
1. Deep Access - nonlocal references are found by
searching the activation record instances on
the dynamic chain (See Figure 10.16, p. 424)
- Length of chain cannot be statically determined
- Every activation record instance must have
variable names
2. Shallow Access - put locals in a central place
Methods:
a. One stack for each variable name (See Figure
10.11, p. 421)
b. Central table with an entry for each variable
name
10.6 Implementing Parameters that are
Subprogram Names (deep binding)
1. Static chain
- Compiler simply passes the link to the static
parent of the parameter, along with the
parameter
2. Display
- All pointers to static ancestors must be saved,
because none are necessarily in the
environment of the parameter
- In many implementations, the whole display is
saved for calls that pass subprogram
parameters
- Another look at the referencing environment for
a passed subprogram
program MAIN_7;
procedure SUB1;
begin { SUB1 }
...
end; { SUB1 }
procedure SUB2(procedure SUBX);
var SUM : real;
procedure SUB3;
begin { SUB3 }
SUM := 0.0;
...
end; { SUB3 }
begin { SUB2 }
SUBX;
SUB2(SUB3);
...
end; { SUB2 }
begin { MAIN_7 }
...
SUB2(SUB1);
...
end. { MAIN_7 }
- Which activation of SUB2 has the SUM that SUB3
assigns?