In order to illustrate the principles of storage allocation, we assume the following simplified picture of the data store (the stack), a fuller description being given in the section on the use of machine instructions.
Each cell or location represents a 48 bit word in the computer store and can be used to hold either a real or an integer variable. At any time during the running of a program, the stack pointer, St, points to the next available location i.e. it contains the address of the next free word. In the examples that follow, shaded areas represent locations which hold information essential to the program, such as array dimensions and origins, and are not of importance in the context of this section. Each area may in fact consist of several locations. Cells which are allocated to variables are indicated by the presence of the name given to the variable.
The declarations which allocate storage space are
real integer array integer array
and to illustrate the stack mechanism we consider the following example:
begin real a, b, c; integer i, max array A(1:2,1:2), x(1:3)
After the above declarations the stack picture would be as below
St1 is the position of St before begin and St2 its position after the declarations. Any further declaration advances St by an appropriate amount, likewise any activity initiated by the instructions in the body of the block causes St to be advanced(either explicity or implicity) still further. Finally when end or end of program is reached, then St reverts to St1.
Variables declared by real and integer are called fixed variables, because the amount of storage space required can be determined at compiler time. Array declarations, however, may have general integer expressions as the parameters and hence have dynamic significance. For example one might have a declaration such as
array A,B(1:m, 1:n),x(1:n)
In this case the space allocated will depend on the computed values of m and n and cannot be determined at compiler time. The stack pointer St is thus advanced in several stages following the initial step which reserves space for all the fixed variables.
This is illustrated by the following example:-
begin
real a,b,c
a = 1; b = 2
c = a+b
begin
real a,b,d
a = 2; d = 1
b = c
c = 4
end
a = a+b+c
end
The stack picture associated with the above block is given below:
Before the first begin St is at St1, and moves to St2 on entering the outer block. After the second begin St is at St3 and reverts to St2 when end is reached. At the second end, corresponding to the first begin, St assumes its original position, St1.
In the diagram, positions 1, 2, 3 correspond to the declarations of the outer block, and 4, 5, 6 to those of the inner block. After the instruction c = a+b, the value 3 is left in position 3; while the instructions of the inner block leave the values 2, 1, 3, 4 in the positions 4, 6, 5, 3 respectively. The last instruction of the outer block leaves the value 7 in position 1.
Thus the variables a, b of the inner block do not conflict with a, b of the outer block, while a reference to c in the inner block is taken to refer to the variable of that name declared in the outer block. We say that a,b are local names to the inner block and c is a non-local name. We also note that the information stored in the variables of the inner block is lost when the block is left, and that we could not refer in the outer block to a variable declared in the inner block.
Futher details of the structure of programs will be given in the section on routines, and for the present the following notes on blocks will be sufficient.
A simple and common use of block structure arises when reading arrays from tape, each array being preceded by its dimensions. For example:-
begin
integer m,n
1: read(m,n)
begin
array A(1:m,1:n)
---
---
end
->1
end
If the begin and end defining the sub-block were not included, then the stack pointer would be advanced further each time a new array was read, without ever being reset, and this could be very wasteful of storage space, particularly for very large values of m and n.