Block Structure
We are interested in the semantics and implementation
of blocks here, not in the syntax -- variously
begin...end
(Algol-60,
Pascal),
{...}
(C, Java), etc.),
let...in...
(SML,
Haskell, etc.).
Procedures and Functions
|
Note that a procedure name is one level lower than the inside of the procedure body. When this program runs, main calls C which calls D which calls A which calls B.
The Stack
The variables for procedures in a stack-based language such as Ada, Algol, Pascal are allocated in the stack. When a procedure is called an activation record is created for its variables. The scope rules of the language determine which objects can be used at each point in the program.
Note that the stack is shown growing up, from a low address to a high address, but some implementations have stacks growing down.
Main
| | <----- SF, Stack Front register
|v2|
main:|v1| <----- SB, Stack Base
----
|
calls C
| | <----- SF
C:|v5|
----
|v2|
main:|v1| <----- SB, Stack Base
----
|
calls D
| | <----- SF
D:|v6|
----
C:|v5|
----
|v2|
main:|v1| <----- SB, Stack Base
----
|
calls A
| | <----- SF
A:|v3|
----
| |
----
| |
----
|v2|
main:|v1| <----- SB, Stack Base
----
|
calls B
| | <----- SF
B:|v4|
----
A:|v3|
----
| |
----
| |
----
|v2|
main:|v1| <----- SB, Stack Base
----
|
And then the calls return and the stack contracts.
The stack management method must implement the scope rules of the programming language.
Stack Management
The first method of stack management uses static and dynamic links. A dynamic link points from each activation record to the activation record of the calling routine. This chains activation records together in reverse order of calling - it reflects the dynamic call history of the program. It allows the stack to be retracted on routine exit. The length of the dynamic chain is the number of active routines at any given time.
 |
A static link points from each activation record to the activation record of the immediately enclosing routine. It allows accessing of non-local variables and objects. It reflects the static textual layout of the program. The length of the static chain is the nesting depth of the current block or routine. The maximum possible length is the maximum nesting depth in the program.
Other linkage information for a routine includes its return address and in the case of a function, its result. An activation record is usually organised as linkage information, parameters and then local variables.
Local variables are accessed relative to activation record base (ARB).
Global (main's) variables are accessed via stack base (SB).
Non-local variables are accessed by following the static-chain the
appropriate number of links to their activation record
and accessing via the offset in that
activation record.
local var:
load reg, offset[ARB] |
from level n, access non-local var at level m:
load r, ARB load r, 2[r] | . | . | n-m times . | load r, 2[r] | load reg, offset[r] |
global var:
load reg, offset[SB] |
A second method of stack management uses a "display".
Calling Sequences
A procedure 'p' at level n calls a procedure 'q' at level m. Note that m<=n (unless proc is a parameter). Note that q may be called from many places and from different levels so q cannot set up its own environment, but p can.
Caller p, in the case that m<n:
load ENV, 2[ARB] -- ENV is some register load ENV, 2[ENV] -- repeat n-m-1 times ... BAL RA, q -- RA is some register |
NB. BAL RA q, Branch and Link,
store the program counter in RA (return address) and
jump to address q.
Also known as 'jump subroutine', JSR, etc..
Caller p, in the case that m=n:
LR ENV, ARB BAL RA, q |
Since a routine q is written once but may be called from many places, as much of the calling code should be put in q as possible:
callee, q:
-- entry sequence...
sto RA, 0[SF] -- return address
sto ENV, 2[SF] -- static link
sto ARB, 1[SF] -- dynamic link
ARB := SF
SF := SF+space -- reserve local space
.
. -- body of q
.
-- exit sequence...
SF := ARB -- retract stack
load ARB, 1[SF]
load RA, 0[SF] -- return address
JMP RA -- return
|
Function Results
A function result can be treated as an output parameter. Alternatively it can be returned in a register or it can be left at word 0 of the activation record; this requires moving the other items up by 1 word. Word 0 becomes 0[SF] when the function has returned; this can be convenient for compiling expressions, especially if using the stack to evaluate expression:
expression: factorial(2)+3 code: load ACC, 2 -- load param, 2 sto ACC, 4[SF] -- store param call sequence for factorial -- factorial load ACC, 0[SF] -- load result add ACC, 3 -- +3 |
Parameters
The parameters are allocated in the activation record of a routine immediately after the linkage information, from word 3 onwards. A caller must evaluate the actual parameters and store them in the space the formal parameters will occupy. When the caller is running, this space will be from 3[SF] onwards.
There are various methods of passing parameters. The simplest method is to pass a parameter by-value or by-input. Here the actual parameter is evaluated and this value stored in the formal parameter.
A more complex method is to pass a parameter by-reference. Here the address of the actual parameter is stored in the formal parameter. Any access of the formal parameter accesses the actual parameter by indirection.
The most complex method is to pass a parameter by-name. The effect as if the formal parameter has been replaced everywhere in the routine by the actual parameter. In fact a closure, or thunk which calculates the actual parameter's value or address is passed.
The following example distinguishes the 3 methods:
begin [1:5] int a; int i:=2;
a := (1, 2, 3, 4, 5);
proc p = ( x );
begin i:=i+1;
x:=x+1
end;
p( a[i] );
print( a )
end
|
Under by-value, the value of a[2], that is 2, is passed to x. i becomes 3, so does x, but a is unchanged. Output:
1 2 3 4 5 |
This would be the case in Pascal if x were a value parameter. The example is technically badly typed in Algol-68 because x is a value and Algol-68 argues that a value (eg 2) cannot be incremented.
Under by-reference, the address of a[2] is passed to x. i becomes 3, as does a[2]. Output:
1 3 3 4 5 |
This is the case in Pascal with a var parameter. Strictly, the actual parameter must have an address to pass to x. a[i] does have an address but '7' as in p(7) does not have an address. Fortran uses by-reference but 1+6, say, would be evaluated to 7 and stored in a temporary variable. This hidden variable's address would be passed to x. On some compilers, p(1), would result in 1=2 thereafter!
Under by-name, x "becomes" a[i]. i becomes 3, so x becomes a[3]. a[3] becomes 4. Output:
1 2 4 4 5 |
Algol-60 has by-value and by-name parameters. By-name parameters are implemented in a way similar to procedure formal parameters (see later). Many functional languages implement by-name parameters in an efficient way called by-need or lazy evaluation. This is possible because there are no side-effects in a functional language (see later).
One further method is by-input-output. Here the actual parameter is evaluated and copied to the formal parameter before routine entry and copied back afterwards. It usually behaves like by-reference unless an actual parameter is altered in a routine both via the formal parameter and via the actual parameter (as a non-local).
By-value requires an expensive copy if the actual parameter is a large structure. By-reference requires one indirection for each parameter access. By-name requires an implicit function call for each access.
Jensen's Device
The following technique, known as Jensen's device, uses call by-name parameters to sum a series:
begin
INT i;
proc sum = (INT lo, hi, BYNAME REAL term)REAL:
begin REAL s:=0.0;
for i from lo to hi do s +:= term
end {sum};
print( sum(1, 10, 1/i) )
end
|
Note that it depends on the loop control variable being non-local to sum (forbidden in Pascal) and on 1/i being passed by-name.
Procedure Formal Parameters
In the absence of by-name parameters, series can be summed in a more obvious manner by passing a procedure or function as a parameter. Such a parameter is known as a procedure formal parameter.
begin
proc sum = (proc(int)int term; int lo, hi)int;
begin
int s := 0;
for i from lo to hi do
s +:= term(i)
od;
s
end;
proc p = void:
begin
proc fact = (int n)int:
if n<=1 then 1 else n*fact(n-1) fi;
int tot = sum(fact, 6, 9);
print(tot)
end;
p
end
|
Note that term is a procedure formal parameter. fact is passed to sum as an actual procedure parameter. The environment that fact runs in is derived from p not from sum. Yet sum calls fact (via term), p does not call fact. Therefore p must give the environment for fact to sum as part of the procedure value. A procedure value is a closure. It consists of a pointer to the code and a pointer to the addressing environment for the code to run in. The stack situation as fact runs is:
^ ^
| |<-----------------------SF
fact: |n |
---<--. |
| |.-->---------|
| |ra | |
v ----------- |
sum: | |term env----------->---------------|
| |term code----------> fact's code |
| |lo=6 | | |
| |hi=9 | | |
| |s | v |
| |i | | |
| |. | | |
| |. | | |
| |ra |<--- v
v ----------- |
p: | |tot | |
-----<---. | |
| | |. | |
| ---->|ra |<-------------------------
v -----------
main: | |. |
| |. |
------->|ra |
-----------
|
p has access to its own ARB and so can store it as part of the routine value as term's env. Fact can access its own local variables, p's variables and main's variables.
Examples of Procedure Parameters
Procedure formal parameters can be used to implement call-by-name parameters if the latter are not provided by a language.
Procedure parameters can be used in a recursive descent parser to good effect:
procedure sequence(procedure nonterminal;
sep :symbol);
begin nonterminal;
while sy=sep do
begin insymbol;
nonterminal
end
end;
{as in sequence(statement, semicolon)
or in sequence(expression, comma) etc. }
procedure optional(starter:symbol;
procedure nonterminal);
begin if sy=starter then
begin insymbol; nonterminal end
end;
{as in optional(elsesy, statement)
or in optional(varsy, vardecs) etc.}
|
Algol-68 Parameters
Algol-68 passes parameters by-value, but the notion of 'value' is very general so that all other methods can easily be programmed:
PROC p = (INT byvalint): ... #call:# p(7); p(i); p(a[i]) |
Here the value is an INT value.
A REF INT value, an integer variable location value can also be passed:
PROC p = (REF INT byrefint):
... byrefint := ... ;
#calls:# p(i); p(a[i]); but not p(7)
|
Note that '7' has no address to pass as a REF INT.
Lastly, a procedure value can be passed:
PROC p = (PROC REF INT bynameint):
... bynameint := ... ;
#call:# p( PROC REF INT:a[i] )
|
The value in this case is an anonymous procedure value.
Local Space Allocation
Each routine allocates space for its parameters and other local variables in the stack. This space can be reserved by adding its size to the stack front register. In Pascal, all arrays and therefore all structures in the stack have a fixed size calculable at compile time. Therefore the stack space for each routine activation is known at compile time. Many languages allow dynamic array bounds:
begin read(n);
[1:n] int arr; ...
end
|
It is impossible to know the size of arr until the program runs. However a descriptor for arr does have a fixed size:
Before:
Activation Record:
^ ^ 4: |arr descriptor| 3: |n | 2: |dynamic link | 1: |static link | 0: |return address| ---------------- |
Code:
-- [1:n] int arr
sto SF, arr[ARB]
add SF, n
|
After:
Changed Activation Record:
Code:
^ ^ |arr[n] | | ... | |arr[2] | |arr[1] |<---<---------| 4: |arr descriptor--------->-----^ 3: |n | 2: |dynamic link | 1: |static link | 0: |return address| ---------------- |
Note that this declaration of arr has had a side-effect in advancing SF. Languages, such as Algol-68, allowing this must prohibit jumps forward over such declarations or the effect will be avoided. Also, a jump backwards over the declaration must be banned or the effect can happen several times.
In the above, an array's size could not change once it was created. The size of an Algol-68 flex array can change after creation. Such an array must be allocated in a heap (see later). The descriptor can still be allocated in the stack.
Jumps, Goto
Goto's involve more than is immediately obvious in a block structured language. The first minor difficulty is due to forward jumps or forward references to labels (and routines). This problem also appears in assemblers.
begin ...; goto lab; ...; lab: ... end |
A multi-pass compiler may be able to evaluate the location the label will refer to before the goto is compiled. If this information is not available a jump to an unknown location must be generated for the goto. A list of such incomplete jump instructions can be kept (a well known trick is to use the incomplete address fields in the jump instructions to link them together). The correct jump destination must be filled in when known. An alternative technique is to compile all forward jumps as indirect jumps via a jump table. The location of the jump table can be fixed at the start of compilation and its contents can be filled in at the end. Another technique is to have the linker-loader fill in forward jumps in the same way that it deals with external references.
The second difficulty is identifying the correct label with the appropriate name:
begin
lab: ...
begin ...;
goto lab; {compiler has just reached here}
???
|
The question is, does the goto go to the lab already seen as in:
begin lab: ... {this one}
begin ....;
goto lab;
end
end
|
or is it a forward jump as in:
begin lab: ...
begin ....;
goto lab;
... lab: {this one}
end
end
|
A one-pass compiler may not be able to decide at the goto. Delaying action similar to that for forward references is needed. Note that Pascal avoids this problem by forcing labels to be declared at the head of a block separate from the defining instance of the label. All applied uses of a label follow the declaration and the lexical level of the destination of each goto is known at the goto.
Non-local jumps
The last problem is that of the non-local jump out of a routine:
proc p =
begin
proc q =
begin ...;
goto lab; ...
end{q};
...; {call} q;
lab: ...
end {p}
|
p calls q and q jumps to lab outside q and inside p. When the jump happens the stack must be retracted to discard q's activation record and to use p's again. The label, lab, is visible in q so it is in q's environment. Therefore the label's environment is a subset of q's and the goto can retract the stack before doing the jump.
A few languages allow labels to be passed as parameters and allow label variables. In this case a label value consists of a code address and an addressing environment - a closure - labels have much in common with routines. A local label cannot be returned from a routine in a stack based language because it refers to an environment that vanished when the routine returned. If the language allows such results, activation records must persist after return and must be placed in a heap.
Stack Management by Display
An alternative method of managing the stack uses a display. This consists of the pointers that form a static chain removed from the activation records and placed together in a block, usually in a block of fast registers.
Main
main <------------display 1 |
calls C
C <---------------display 2 main <------------display 1 |
calls D
D <---------------display 3 C <---------------display 2 main <------------display 1 |
calls A
A <---------------display 2 D C main <------------display 1 |
calls B
B <---------------display 3 A <---------------display 2 D C main <------------display 1 |
If we ignore procedure formal parameters for now, a procedure body p at level n calls a procedure q at level m, then m<=n. If m=n then q is local to the body of p and the body of q is at level n+1. The display when q runs is the same as that for p plus one extra entry (n+1). If m<n then q is a non-local procedure to p. The display when q runs should be the first m entries from p's display plus one new entry for q's activation record.
Assume word 0 of activation record holds return address, word 1 of record holds saved display entry.
calling sequence:
BAL RA, q |
entry sequence:
sto display[m+1], 1[SF] -- save display entry
display[m+1] := SF -- set ARB; body at...
-- 1+level of name q
sto RA, 0[SF] -- return address
SF := SF + space
.
. -- body of q
.
|
exit sequence:
SF := display[m+1] -- retract stack load display[m+1], 1[SF] -- reset display load RA, 0[SF] -- return address jmp RA -- return |
If there are enough registers to hold the display then access to all variables is fast. To access a variable at 'offset,level' where d=display[level]:
load reg, offset[d] |
Alternatively the display is held in memory and entries are loaded into registers when needed.
The maximum number of display entries, equals the maximum length of a static chain, equals the maximum textual nesting depth in a program. In principle there is no limit to this. In practice it rarely exceeds 10. The Burroughs 7600 dedicated 16 registers for the display; these are automatically set and reset by subroutine entry and exit instructions.
In practice most procedures access local variable most of the time, global variables a few times and non-local variables rarely. Therefore the potential speed advantage of displays over static links is small if non-existent.
Further, the simple scheme above does not work when procedure formal parameters are allowed. A procedure value consists of (a pointer to) code and an addressing environment. The environment must contain of a complete display (several words) or a pointer to such a display. This means that the entry sequence must store all the display and load a new given one and that the exit sequence must restore the old display. This is a large overhead on procedure call.
Recursion Without Nesting.
BCPL and C allow recursive routines but not nesting of routines. This means that there are only local variables and global (static) variables; there are no intermediate non-local variables. A static link is therefore unnecessary.
calling sequence:
BAL RA, q |
entry sequence:
sto RA, 0[SF] -- return address sto ARB,1[SF] -- dynamic link ARB:= SF -- activation record base SF :=SF+space -- reserve local space . . -- body of q . |
exit sequence:
SF :=ARB -- retract stack load ARB, 1[SF] -- restore ARB load RA, 0[SF] -- return address jmp RA -- return |