PREFACE
This manual is a reference manual which describes the Atlas
Autocode Compiler currently available (1/3/65) at Manchester
University. It is not a teaching manual though we have tried to
make it fairly readable. Further compilers may in the future
become available both on Atlas and other machines and it is
expected that they will be described with reference to this manual.
We would like to thank Mr. G. Riding for his many valuable
comments and suggestions and Miss Christina O'Brien who has typed
and re-typed the manuscript.
R.A. Brooker
J.S. Rohl.
1st March 1965
CONTENTS
1. INTRODUCTION
Example of an Atlas Autocode Program 1.1
Blocks and Routines 1.2
Phrase Structure Notation 1.2
2. THE BASIC LANGUAGE
Symbols of the Language 2.1
Names 2.1
Constants 2.2
Delimiters 2.2
Types 2.3
Declaration of Variables 2.3
Functional Dependence 2.5
Standard Functions 2.5
Arithmetic Expressions 2.5
Integer Expressions 2.6
Arithmetic Assignments 2.7
Simple Labels 2.8
Vector Labels 2.8
Conditional Labels 2.9
Conditional Operators 2.9
Cycle Instructions 2.10
Miscellaneous Notes 2.11
3. STORAGE ALLOCATION AND BLOCK STRUCTURE OF PROGRAMS
The Stack 3.1
Storage Allocation Declarations 3.1
Block Structure of Programs 3.2
4. ROUTINES
Basic Concepts 4.1
Formal Parameters and Actual parameters 4.3
Function Routines 4.5
Scope of names 4.6
Permanent Routines 4.6
Functions and Routines as Parameters 4.7
Recursive Use of Routines 4.8
Own Variables 4.9
5. INPUT AND OUTPUT OF DATA
Selection of Data Channels 5.1
Basic Input Routines 5.1
Basic Output Routines 5.4
Captions 5.6
Binary Input and Output 5.6
6. MONITOR PRINTING AND FAULT DIAGNOSIS
Compiler Time Monitoring 6.1
Run Time Monitoring 6.2
Fault Trapping 6.5
Fault Diagnosis 6.5
Query Printing 6.6
Routine Tracing 6.7
Jump Tracing 6.7
Array Bound Check 6.7
Other Checking Facilities 6.7
7. PRESENTATION OF COMPLETE PROGRAMS
Program and Data on Same Tape 7.1
Program and Data Tapes Separate 7.3
Program on Several Tapes 7.4
8. COMPLEX ARITHMETIC
Declarations 8.1
Standard Functions 8.1
Arithmetic Expressions 8.2
Arithmetic Instructions 8.2
Conditions 8.4
Routines and Functions 8.4
Input and output of Complex Numbers 8.5
9. STORE MAPPING
The Address Recovery Function 9.1
Array Functions 9.1
The Renaming of Variables within a Block 9.3
Store Mapping Routines 9.4
10. THE USE OF MACHINE INSTRUCTIONS
Stack Structure 10.1
Stack Instructions 10.4
Machine Code Formats 10.5
Example of Use of Machine Orders 10.7
11. THE PERMANENT ROUTINES
Linear Equations 11.1
Matrix Routines 11.2
Solution of Differential Equations 11.3
APPENDIX 1 PHRASE STRUCTURE NOTATION
APPENDIX 2 INDEX OF STANDARD FUNCTIONS AND PERMANENT ROUTINES
APPENDIX 3 INDEX OF DELIMITERS
APPENDIX 4 LIST OF MONITORED FAULTS
APPENDIX 5 NUMERICAL EQUIVALENTS OF BASIC AND COMPOSITE SYMBOLS
1.2
begin
real a, b, c, Sx, Sy, Sxx, Sxy, Syy, nextx, nexty
integer n
read (nextx)
2: Sx = 0; Sy = 0; Sxx = 0; Sxy = 0; Syy = 0
n = 0
1: read (nexty) ; n = n + 1
Sx = Sx + nextx; Sy = Sy + nexty
Sxx = Sxx + nextx² ; Syy = Syy + nexty²
Sxy = Sxy + nextx*nexty
3: read (nextx) ; ->1 unless nextx = 999 999
a = (n*Sxy - Sx*Sy)/(n*Sxx - Sx²)
b = (Sy - a*Sx)/n
c = Syy - 2(a*Sxy + b*Sy) + a²*Sxx - 2a*b*Sx + n*b²
newline
print fl(a,3) ; space ; print fl(b,3) ; space ; print fl(c,3)
read (nextx) ; ->2 unless nextx = 999 999
stop
end of program
BLOCKS AND ROUTINES
Complete programs are generally split up into a number of
self-contained units called ROUTINES, and each routine may be further
split into a number of BLOCKS. A detailed description of their
construction and use is deferred until later, but in the earlier sections
it is sufficient to note that the Autocode statements between begin
and end constitute a block. However when a block defines a complete
program as in the above example, end is replaced by end of program.
PHRASE STRUCTURE NOTATION
Atlas Autocode is a PHRASE STRUCTURE LANGUAGE and to assist in its
description we sometimes have resort to phrase structure notation. In
general, whenever a name appears in square brackets in the description of
an Autocode statement, we mean that in an actual statement it would be replaced
by a particular element of the class defined by the name. For example, in the
next section we define [NAME] and [EXPR] to denote a general name and a
general expression respectively, and with these definitions we could go on to
define a function of a single variable by
[NAME] ([EXPR])
and in an actual program this might be replaced by
g(x + y - 2)
since g is a name, and x + y - 2 is an expression. Further notes on phrase
structure notation will be found in Appendix 1.
2.2
Underlined names and mixed names such as RK2ST are NOT allowed.
There are certain names, e.g. log, sin, exp, print, read, etc.
which have a standard meaning (the PERMANENT routines) but all other
names must be declared before any reference is made to them (see below).
In future a general name will be denoted by [NAME].
CONSTANTS
Numerical (positive) constants are written in a straight forward
notation. For example:-
2.538 1 .25 17.28α-1 1α7
The last two examples mean 1.728 and 10000000.
The numerical part can be written in any number of ways. For example: -
15 015 15. 15.000
are all equivalent. The exponent, where present, consists of α
followed by an optional sign and decimal digits.
The symbol ½ is equivalent to the two symbols .5. Thus 2.5
may be punched as 2½.
There is a further specialised type of constant consisting
of a symbol (either basic or composite) enclosed in quotes. Its value
is that of the internal equivalent of the symbol, a list of which is
given in Appendix 5. Thus
'a' ≡ 33
'ø' ≡ 2063
Though this form of constant may be used whenever a constant is relevant
it is most often used when reading symbols off a data tape (see Section 5).
DELIMITERS
These are a preassigned set of symbols and underlined words. For example:-
+ - * / ( , ) > ≥ -> ; π
cycle repeat integer real if then caption comment
Note that -> consists of two symbols, - followed by >
Unlike names whose meaning can be defined by the user, delimiters
have fixed absolute meanings in the language.
2.3
TYPES
Calculations are performed on two principal types of operand,
real and integer (later on we shall introduce complex). Both are
represented by floating point numbers (in the form a*8↑b where a
is held to a precision of 40 binary digits and b is an 8-bit integer);
but those of integer type are kept in an unstandardised form
(so that the least significant 24 bits can be used directly for
B-modification; the precise method of storage is described in the
section on machine instructions).
The locations in the computer store holding numbers are
distinguished by assigning names to them (see later), and reference to
the number is made by giving the appropriate name. Both real and integer
numbers referred to in this way are called variables and denoted by
[VARIABLE].
Programs will consist mainly of operations on real operands,
the use of integer operands being generally confined to counting and subscript
arithmetic.
DECLARATION OF VARIABLES
The names of variables used in a block are declared at the head of
the block; For example:-
integer I, max, min
real t, Temp, VOL 1, VOL 2
The effect of these declarations is to allocate storage positions (ADDRESSES)
to the named variables, and any subsequent reference to one of the declared
names will then be taken as referring to the number stored in the appropriate
address. The format of these declarations is formally
[TYPE][NAME LIST]
where [TYPE] = integer, real
[NAME LIST] = [NAME][REST OF NAME LIST]
[REST OF NAME LIST] = [,][NAME][REST OF NAME LIST],NIL
N.B. This means of defining a list consisting of phrases separated
by commas is used throughout: See Appendix 1.
2.4
One dimensional arrays of elements may be declared by statements such as
array a,b(0:99), c(10:19)
which reserves space for three arrays of real variables a(i), b(i), c(i).
In the first two the subscript runs from 0 to 99, and in the third from
10 to 19.
To refer to a particular element of an array one might write
a(50) b(j) b(2n+2j-1) c(10+i)
It is the computed value of the argument, which may be a general integer
expression (see later), which determines the particular element.
Two dimensional arrays are declared in a similar way. For example:-
array A(1:20,1:20), B(0:9,0:49)
This defines and allocates storage for a 20 X 20 array A and a 10 X 50
array B. To refer to a particular element, one writes, tor example:-
A(1,1) A(i-1,j+1) B(9,2K+1)
Should an array of integer elements be required, the declaration is
qualified by integer. For example:-
integer array Ka (1:50).
Arrays of more than 2 dimensions may also be declared. For example:-
array CUBE 1, CUBE 2 (1:10,1:10,1:10)
reserves 1000 locations for each of the two arrays CUBE 1, CUBE 2.
Storage allocated by all the above declarations has dynamic significance, i.e.
they are implemented at run time and not at compiler time. Consequently,
the arguments in array declarations need not be constants but may be general
integer expressions. The significance of this will be explained in the sections
on block structure and dynamic storage allocation (see later).
The format of an array declaration is
[TYPE'] array [ARRAY LIST]
where [TYPE'] = integer , real , NIL
[ARRAY LIST] = [NAME LIST] ([BOUND PAIR LIST])[REST OF ARRAY LIST]
[BOUND PAIR] = [EXPR]:[EXPR]
Here the [EXPR]'S must be integer [EXPR]'S (see P2.6)
2.5
FUNCTIONAL DEPENDENCE
Functional dependence is indicated by writing the name of the
function followed by the list of arguments in parentheses (in a similar
fashion to array elements). For example: -
sin(2πx/a) arctan(x,y) TEMP(i) a(10,10)
Each argument can be an arithmetical expression (see below).
Within a block all names must be distinct, and it is not
possible to have a function with the same name as a scalar. Thus
a and a(i) or f and f(x) would NOT be allowed to appear in the
same block.
STANDARD FUNCTIONS
Certain standard functions are available and may be used
directly in arithmetic expressions (see next section) without formal
declaration:
sin(x) cos(x) tan(x) log(x) exp(x) sqrt(x)
arcsin(x) (-π/2 ≤ result ≤ π/2)
arccos(x) (0 ≤ result ≤ π)
arctan(x,y) (= arctan (y/x), -π ≤ result ≤ π)
radius(x,y) (= sqrt (x²+y²) )
mod(x) (= |x|)
fracpt(x) (= fractional part of x)
intpt(x) (= integral part of x)
int(x) (= nearest integer to x. i.e. intpt(x+.5))
parity(n) (= (-1)↑n)
The last three functions are of type integer (see later), the rest of type real.
The arguments of all these functions may be general expressions, except
that the argument of the last must be of type integer.
A complete list of standard functions is given in Appendix 2.
ARITHMETIC EXPRESSIONS
A general arithmetical expression is denoted by [EXPR] and consists
of an alternating sequence of operands and operators possibly preceded by a
sign symbol, thus *
[±'] [OPERAND][OPERATOR][OPERAND][OPERATOR] .... [OPERAND]
An [OPERAND] is a [VARIABLE], [CONSTANT], ([EXPR]), |[EXPR]|, or [FUNCTION],
and an [OPERATOR] is one of + - * / ↑ (the asterisk denoting multiplication).
**Or, more strictly, (See Appendix 1)
[EXPR] = [±'][EXPR']
[EXPR'] = [OPERAND][OP][EXPR'],[OPERAND]
[OPERAND] = [NAME][APP],[CONST],([EXPR]),|[EXPR]|
[±'] = +,-,NIL
2.6
An explicit multiplication sign is not required when ambiguity could not
arise from its omission. For example:-
2.5a1b means 2.5*a1*b
NOTE: When the compiler looks for a name, it finds the longest possible
name. Thus ab is taken as a name rather than a*b even if only a and b and not
ab were declared. In this case a fault (NAME ab NOT SET) would be indicated.
Examples of expressions are:-
A(i-1,j) + A(i+1,j) + A(i,j-1) + A(i,j+1) - 4A(i,j)
Z + log(1 + cos(2π(x/a + y/b + z/c)))
LENGTH * BREADTH * HEIGHT
1 + sqrt(x(i)² + y(i)² + z(i)²)
a * b/c * d/e
(x + y + z)/(a + b + c)
2.5x1b * (c + d)e
e = |x-y| + .00001
(1+x)↑(n-3) * (1-x)↑3
NOTES
1. Multiplication and division take precedence over addition and
subtraction and division takes precedence over multiplication. Thus
the fifth example means a * (b/c) * (d/e).
2. |[EXPR]| is interpreted as the positive magnitude of the
[EXPR]. Thus it is equivalent to mod([EXPR]).
3. An exponent is denoted by ↑ [OPERAND] and exponentiation takes
precedence over the other operations. Thus the last example means
((1 + x) to the (n - 3))*((1 - x) to the 3). In the formation of
a ↑ n, n must be an integer or integer [EXPR] (see next section);
then if
(i) n > 0, result = a*a*a.......*a (n times)
(ii) n = 0, result = 1
(iii) n < 0, result = 1/(a*a*a.......*a)
4. To form a ↑ b, where b is real we must write it in the form
exp(b*log(a)),where a must be positive.
INTEGER EXPRESSIONS
An [EXPR] is an integer [EXPR] if all the [OPERAND]'s are
scalars, array elements etc, declared to be of type integer, or are
integer constants or integer functions (e.g. int, intpt, or parity).
2.7
Thus if we assume that x is a real [VARIABLE] and i,n,j,k(1),k(2) are
integer [VARIABLE]'s the following are integer [EXPR]'s.
m*(n-1)/2
i + j + k(2) + int(x)
j ↑ k
intpt(n*(n-1)/3)
The definition given above does not guarantee that an integer [EXPR]
will always give an integral result, e.g., 10/3 and j↑(-1) are not
integral. There is no guarantee either that expressions like
n*(n-1)/2(which is integral) will always yield the exact answer (in this
particular case it does). When the result of such an operation is in doubt
it is preferable to use 'int' e.g., int(n*(n-1)/2) to give an exact integer
result.
Except in certain special cases integer [EXPR]'s are evaluated by floating
point arithmetic in exactly the same way as general (real) expressions, but
are destandardised on assignment (explicit or implicit) to their integer
destination. The definition of an integer [EXPR] is a basis for checking
that such assignments are sensible. The special cases mentioned above refer to
the subscript expressions in array elements. Such expressions, which should
always be integer [EXPR]'s are usually simple linear forms which are dealt
with more appropriately by B-modification. It is mainly to facilitate
such operations (and the associated operation of counting) that integer's
are used. Being destandardised quantities they can be transferred directly
to B-registers without using the floating point accumulator.
ARITHMETIC ASSIGNMENTS
The general arithmetic instruction is
[VARIABLE] = [EXPR]
Examples are:-
X(p,q) = 1+2cos(2π(x+y))
a = (b+c)/(d+e)+F
i = i+1
The action of the general arithmetic assignment is to place
the computed value of the [EXPR] in the location allocated to the l.h.s.
[VARIABLE]. If the l.h.s. is a real [VARIABLE], the r.h.s. [EXPR]
may be of type real or integer, but if the l.h.s. is integer then
the r.h.s. must be an integer [EXPR]. For example, if y had been declared
real and i integer then we could write y = i but not i = y even if we knew
that y had an integral value.
2.9
CONDITIONAL LABELS
Another kind of multi-way switch is test 4, 5, 6
illustrated by the accompanying diagram. ---
Here the conditions at the places indicated ---
are tested in turn and control passes to the 4 case x<1:---
instruction following the first to be successful. ---
If none is satisfied a fault is signalled. 5 case 0≤x≤1:---
The general form of the label is [N] case [COND]: ---
where [COND] denotes the general 6 case x>1:---
condition defined in the next section. A ---
simple label [N]: may be used in place of ---
the last alternative(i.e. 6:) in which case control
passes directly to the following instructions
if it reaches that point.
NOTE All labels are local to the block containing them and jump instructions
may only refer to labels within the block (see later).
CONDITIONAL OPERATORS
A CONDITIONAL OPERATOR of the form
if [COND] then or unless [COND] then
may be written before any unconditional instruction. These form the
FORMAT CLASS [UI] (see Appendix 1) and include arithmetic, jump and
test instructions.
The [COND] phrase takes one of the forms**
[SC] and [SC] and [SC] --- and [SC]
or [SC] or [SC] or [SC] --- or [SC]
or just [SC]
Here [SC] denotes one of the following 'simple' conditions
[EXPR][ø][EXPR] or [EXPR][ø][EXPR][ø][EXPR] or [(COND])
where [ø] denotes one of the comparison symbols = ≠ > ≥ < ≤
If (or unless) the condition is satisfied the instruction is obeyed,
otherwise it is skipped and control passes directly to the next
instruction.
Examples of conditional instructions and conditional labels are
if x < 0 then x = mod(y)
if 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 then -> 1
case (y > 1 or y < - 1) and x ≥ 0:
** or, more strictly, (see Appendix 1)
[COND] = [SC] and [AND-C], [SC] or [OR-C], [SC]
[AND-C] = [SC] and [AND-C],[SC]
[OR-C] = [SC] or [OR-C],[SC]
2.10
Alternatively, conditional operators may appear AFTER unconditional
instructions, in which case they are written
if [COND] or unless [COND]
for example x = 0 if |x| < .0000001
-> 1 unless z > R or z = 0
CYCLING INSTRUCTIONS
These are pairs of statements which allow a group of
instructions to be obeyed a fixed number of times. For example:-
cycle i = 0, 1, n-1
repeat
In the above example the instructions between cycle and repeat are
traversed n times, with i successively taking the values 0,1, ...,n-1.
After the final cycle, control goes to the statement following repeat.
The l.h.s. must be an integer name, but the r.h.s. quantities may be
general integer [EXPR]'s which are initially evaluated and stored. Thus
within the innermost cycle of the example below, the values of p,q and r
may be altered without affecting the number of times the cycle is traversed.
The initial value, increment, and final value must be such that
final value - initial value
increment
must be a positive integer or zero otherwise a fault is indicated.
For example:-
cycle i = 1,1,p
cycle k = 1,1,r
c(i,k) = 0
repeat
cycle j = 1,1,q
cycle k = 1,1,r
c(i,k) = c(i,k) + a(i,j)*b(j,k)
repeat
repeat
repeat
NOTE Statements such as cycle x = .2,.1,1 are NOT allowed,and
should be replaced by an equivalent permissible form. For example:-
cycle i = 2,1,10
x = .1i
where i has been declared integer and x real.
2.11
MISCELLANEOUS NOTES
1. end of program is the formal end of the program and appears after the
last written instruction; its action is to terminate the reading of the
program and to start obeying it from the first instruction.
2. The instruction stop can appear anywhere in the program and signifies
the dynamic end of the program; its action is to terminate the calculation.
3. The delimiter comment allows written comments to be inserted in a
program to assist other users in understanding it. The information
following comment (which may include composite characters) up to the
next newline or semi-colon is ignored by the computer. The delimiters page
and | are synonyms for comment, though the first has an obvious special use
in the pagination of programs.
4. It has been noted earlier that all spaces and underlined spaces in a
program are ignored and that Autocode statements are terminated by a semi-
colon or a newline. If a line is terminated by the delimiter c then the
following newline character is ignored by the computer. Thus a single
statement may extend over several lines of the printed page. It is not
anticipated that this facility will be frequently used, except when
writing comments and possibly long algebraic expressions.
5. If a programmer is prepared to exclude upper case letters from names
and captions, then he can effect a saving both in the size of the tape
and the speed of compilation, by using the special instruction
upper case delimiters
and then writing all following delimiters in upper case without the
underlining. Thus the example of P2.10 could then be written:-
CYCLE i = 1,1,p
CYCLE k = 1,1,r
c(i,k) = 0
REPEAT
CYCLE j = 1,1,q
CYCLE k = 1,1,r
c(i,k) = c(i,k) + a(i,j)*b(j,k)
REPEAT
REPEAT
REPEAT
The delimiter causes the compiler to replace each upper case letter by
the equivalent underlined lower case letter, so that a mixture of
normal and upper case delimiters can be used. If this is required only for
certain parts of a program then the instruction
normal delimiters
can be used to return the compiler to its normal operation.
3.1
3 STORAGE ALLOCATION AND THE BLOCK STRUCTURE OF PROGRAMS
THE STACK
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.
CELLS IN |St AVAILABLE CELLS
USE |
|\\\\\\\\| | | | | | | |
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.
STORAGE ALLOCATION DECLARATIONS
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 St2
| |
| |\\| a | b | c | i |max|\\|A(1,1)|A(1,2)|A(2,1)|A(2,2)|\\|x(1)|x(2)|x(3) |
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.
3.2
BLOCK STRUCTURE OF PROGRAMS
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:
St1 St2 St3
| | |
| |\\\\| a | b | c |\\\\| a | b | d | | |
1 2 3 4 5 6
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.
3.3
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.
1. Blocks may contain any number of sub-blocks and blocks may be nested to
any depth.
2. Names declared in a block take on their declared meaning in the block
and in any sub-blocks unless redeclared in the sub-block.
3. Labels are local to a block and transfers of control are only possible
between statements of the same block.
4. The outermost block of a program is terminated by end of program,
which causes the process of compiling to be terminated and transfers
control to the first instruction of the program.
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.
4.1
4 ROUTINES
BASIC CONCEPTS
A large program is usually made up of several routines
each of which represents some characteristic part of the calculation.
Such routines may be called in at several different points in the program,
and their design and use is a fundamental feature of the language.
The introductory example consisted of a main block only (delimited by
begin and end of program) although it makes reference to the routines 'read',
'print', 'newline', which are permanently available in the machine. In
exactly the same way however, the user may call in routines which he has
written himself in Autocode language. Consider for example a routine
to evaluate
y = a(m) + a(m+1)x+...........+ a(m+n)x↑n (n ≥ 0)
where the coefficients are selected from some vector a.
routine poly(real name y, array name a, real x, integer m,n)
integer i
y = a(m+n) ; return if n = 0
cycle i = m+n-1,-1,m
y = x*y+a(i)
repeat
return
end
Given the values of x,m,n and the addresses of y and the array
elements a(i), it evaluates the polynomial and sets y to this value.
The statement end is the formal or written end of the
routine while return is the dynamic end, i.e. it is the instruction
which returns control to the main routine. Where the formal end is also a
dynamic end as in the present example the return instruction preceding end
can be omitted; in this case end serves for both purposes.
NOTES
1: There can be any number of alternative exit points in a routine - i.e.
return can occur more than once.
2: return is a member of the FORMAT CLASS[UI] - i.e. it can be made conditional,
as above.
4.2
This routine can be EMBEDDED and used in a main routine as illustrated
below.
begin
real U, V, z, x ; integer m
array b(0:15), c(0:50)
routine spec poly (realname y, array name a, real x, integer m,n)
'
'
'
poly(U,b,z,0,m)
'
'
'
poly(V,c,x²,20,10)
'
'
stop
routine poly(realname y, array name a, real x, integer m,n)
integer i
y = a(m+n); return if n = 0
cycle i = m+n-1,-1,m
y = x*y+a(i)
repeat
return
end
end of program
The routine is called in by the main routine whenever the
name 'poly' appears. The first reference to 'poly' would cause the poly
routine to evaluate
U = b(0) + b(1)z + ... + b(m)z↑m
and the second would cause it to evaluate
V = c(20) + c(21)x² + ... + c(30)x↑20
The parameters in the routine specification and routine
heading are the FORMAL PARAMETERS and the parameters in the call statements
are the ACTUAL PARAMETERS (see next section).
The body of the routine may be considered as a block
delimited by routine and end, and the concepts of storage allocation, local
and non-local names etc. apply to routines in exactly the sane manner as
for blocks. In fact a block may be considered as being an open routine
without parameters.
4.4
In the example of a routine to evaluate a polynomial described earlier,
the formal parameter y is the name of the variable to which the result is assigned,
and the corresponding actual parameter must be a name, in this case the name of
a real variable. The formal parameter then is of type real name.
A reference to y inside the routine is essentially a reference to the non-local
variable named by the actual parameter. The same applies to the array name
parameter a, a reference to a inside the routine being a reference to
the non-local array whose name is substituted for a in the calling statement.
The formal parameter real x on the other hand can be replaced by a
general arithmetic expression, which is evaluated and assigned to the local
variable x which is specially created in addition to any local real
variables declared in the routine, The same applies to the formal parameters
integer m,n. These are essentially local quantities, and expressions are substituted
in place of them are evaluated and the resultant values assigned to the local
integer variables m and n, which are lost on exit from the routine. Consequently
the routine should place the information it produces in variables which are
called by NAME (such as x and a).
The formal parameters x, m, n are said to be called by VALUE in so far
as it is only the values of the corresponding actual parameters which are of
interest. This is the essential difference between the formal parameter types
array and array name (or integer array and integer array name). In the former
case the array named by the actual parameter is copied into a specially created
local array, and a reference to the name in the routine is taken as referring to
this local array. As the copying process can be time-consuming and space-consuming
arrays should be called by NAME if at all possible, especially if they are large.
Another example of a routine is the following
routine matmult(arrayname A,B,C integer p,q,r)
integer i,j,k ; real c
cycle i = 1,1,p
cycle j = 1,1,r
c = 0
cycle k = 1,1,q
c = c+A(i,k)*B(k,j)
repeat
C(i,j) = c
repeat
repeat
end
This forms the product of a p x q matrix A and a q x r matrix B. The
result, a p x r matrix, is accumulated in C. The routine assumes that the first
element of each matrix has the suffix (1,1). A typical call sequence might be
mat mult(N, x, y, 20, 20, 1)
where N, x, y had been declared by
array N(1:20,1:20), x,y(1:20,1:1)
4.5
FUNCTION ROUTINES
When a routine has a single output value it may be written as a
function routine and then used in an arithmetic expression in the same way as
the permanent functions (cos, sin etc.). For example, the polynomial routine
described earlier may be recast as a function routine as follows:-
real fn poly(arrayname a, real x, integer m,n)
integer i ; real y
y = a(m+n) ; if n = 0 then result = y
cycle i = m+n-1,-1,m
y = y*x+a(i)
repeat
result = y
end
NOTES
1: In general, the exit from a routine is of the form : result = [EXPR]
and this causes the EXPRESSION on the right hand side to be evaluated as
the value of the function.
2: result = [EXPR] acts as the dynamic end of a function (i.e. it corresponds
to return in a routine), and may appear any number of times within the function.
3: result = [EXPR] is a number of the FORMAT CLASS[UI] - i.e. it may
be made conditional.
The specification of the above routine would be written
real fn spec poly(arrayname a, real x, integer m,n)
and the routine can be called in an arithmetic statement, for example
y = a*b + 2h*poly(c,1/x,0,16)
An example of an integer function is given next. It selects the index of the
maximum element x(k) in a set of array elements x(m), x(m+1),....,x(n) (n≥ m)
integer fn max(arrayname x, integer m,n)
integer i,k
k = m
->1 if n = m
cycle i = m+1,1,n
k = i if x(i) > x(k)
repeat
1: result = k
end
A call sequence for this function routine might be
y = 1 + x(max(x,1,100))
4.6
SCOPE OF NAMES
In general all names are declared at the head of a routine
either in the routine heading or by the declarations integer, real, array, etc.,
and the various routine specifications.
Therefore they are local to that routine and independent
of any names occurring in other routines. However, if a name appears
in a routine which has not been declared in one of the above ways, then
it is looked for outside i.e. in the routine or block in which it
is embedded. If it is not declared there it is looked for in
the routine or block outside that and so on until the main block is reached.
Now the main block is itself embedded in a permanent block at
'zero level' which contains the PERMANENT material, so that if a
name is not found in the main block it is looked for among these.
The permanent names may in fact be redeclared locally at any level, but
clearly it would be unwise to assign new meanings to such routines as
'log', 'print', etc. This outer block also contains supervisory
material for controlling the entry to and exit from the main block.
Very often, the only non-local names used in a routine will be the
permanent names. The level at which a name is declared is sometimes
referred to as its 'textual' level.
PERMANENT ROUTINES
The permanent names include the standard functions, sin, log, int,
etc. and the basic input/output routines read, print etc.
These routines are used in a program without declaration and without
the necessity of inserting the routine bodies, since these are
permanently available at level zero. A full list of the permanent routines
is given in Appendix 2.
[NOTE : the standard functions (and the same applies to 'read')
are not strictly routines : THEIR NAMES CANNOT BE SUBSTITUTED AS
ACTUAL PARAMETERS IN PLACE OF FORMAL PARAMETERS OF ROUTINE TYPE.
they would first have to be redefined and renamed as formal
routines.]
4.7
FUNCTIONS AND ROUTINES AS PARAMETERS
This is illustrated by the following example involving an
integration routine
routine spec integrate(real name y, real a,b,integer n, real fn f)
which integrates a function f(x) over the range (a, b) by evaluating
y = (f(0) + 4f(1) + 2f(2) + ... + 4f(2n-1) + f(2n))(b-a)/(6n)
where f(i) = f(a + ½i*(b-a)/n)
An auxiliary routine is required to evaluate f(x) and details of it
must be passed on to the integration routine. This is done by means of the
formal parameter type [RT] as defined earlier, and the body of the routine
might then be:-
routine integrate (real name y, real a, b, integer n, real fn f)
real fn spec f(real x)
real h; integer i
h = ½(b-a)/n
y = 0
cycle i = 0,2,2n-2
y = y+2f(a+i*h)+4f(a+(i+1)h)
repeat
y = (y-f(a)+f(b))h/3
end
To enable instructions such as
y = y+2f(a+i*h)+4f(a+(i+1)h)
to be translated, a specification of the formal parameter f is required.
In this case the delimiter real fn spec can be replaced by spec since the type
of the function is given explicitly by the formal parameter itself.
Now consider a programme to evaluate
z = exp(-y)cos(b*y)dy
for various values of b read from a data tape, the last value being
followed by 1000, using for n the integer nearest to 10b.
4.8
begin
routine spec integrate (real name y,real a,b,integer n,real fn f)
real fn spec aux (real y)
real z, b
comment Simpson rule integration
1:read (b)
if b = 1000 then stop
integrate (z, 0, 1, int(10b), aux)
newline
print (b, 1, 2);spaces(2);print(z, 1, 4)
-> 1
real fn aux(real y)
result = exp(-y) cos(b*y)
end
| routine integrate |
| |
end of program
NOTES
1: That the names given to the auxiliary routine and its
parameters need not be the same in the integration routine as in the
main program, but they must correspond in type.
2: Since the result of the intergration is a single quantity, the routine
could be recast as a real fn :-
real fn spec integrate (real a,b, integer n, real fn f)
and called by, for example:-
print(integrate(0,1,int(10b),aux),1,6)
RECURSIVE USE OF ROUTINES
The name of a routine is local to the routine or block in which
its specification appears, and so the body of the routine is within the
scope of its own name. Hence it may call itself. It may also call itself
indirectly by invoking other routines which make use of it. On each activation
of the routine a fresh copy of the local working space is set up in the stack,
so that there will be no confusion between variables on successive calls.
(This does not apply however to own variables. See next section.) Some criterion
within the body of the routine must eventually inhibit the calling statement
and allow the process to unwind. Functions defined recursively, for example:-
n! = n(n-1)! , n > 1
= 1 , n = 1
can be implemented in this way, but it is always more efficient to use
recurrence rather than recursive techniques.
5.1
5. INPUT AND OUTPUT OF DATA
The input and output of data will generally be accomplished by
means of permanent routines. In this section these permanent routines are
described and the precise form of data is given.
SELECTION OF DATA CHANNELS
The selection of an input channel is performed by the routine:-
routine spec select input (integer i)
This selects the input channel corresponding to the value of i, and
this channel, together with the particular input device assigned to it
in the Job Description (see section 7), remains selected until
another 'select input' instruction is encounted.
Output channels are selected in a similar way, by means of the
routine:
routine spec select output (integer i)
In both cases channel 0 is initially selected, and in the absence of
a channel selection instruction, remains selected during the execution of a
program.
BASIC INPUT ROUTINES
Decimal numbers may be read from a data tape by means of the routine
routine spec read([VARIABLE])
This reads a decimal number from the currently selected data channel and
places it in the location specified by the [VARIABLE], which may be of
type integer or real. The routine reads numbers in either fixed or floating
point form, for example:-
-0.3101 18 7.132α-7 3.1872α14
A number is terminated by any character other than a decimal digit,
the first decimal point, or an exponent. An exponent consists of a followed
by an optional number of spaces, an optional sign, and the decimal digits.
Spaces and newlines proceeding a number are ignored, but all other symbols
cause the routine to signal a fault (but see NOTE on P5.4). A fault is also
indicated if a number assigned to an integer variable is not integral.
5.2
It should be noted that a single space is sufficient to terminate a
number, and that no spaces are allowed within the mantissa or within the numerical
part of the exponent (unlike constants appearing in a program where all spaces
are irrelevant and the number is terminated by the following name or delimiter).
Further since 'tabs' are converted to a number of spaces, numbers may
be separated by 'tabs'. Several numbers in a sequence may be read by the routine:-
routine spec read([VARIABLE LIST])
For example, read(a,i,X(i))
This is treated as if it were a series of instructions
read (a) ; read(i) ; read(X(i))
hence the subscript of X(i) takes the value just assigned to i.
The read routine is an exception to the general form of a routine, as
it may have an indefinite number of real name and integer name parameters.
Successive numbers on a data tape may be read so as to fill
an array by means of the routine
routine spec read array(arrayname A)
For example:- array A(1:20, 1:20)
read array (A)
would cause the next 400 numbers on the data tape to be read so as to fill
the array A, row by row. It is thus equivalent to
array A(1:20, 1:20)
integer i,j
cycle i = 1,1,20
cycle j = 1,1,20
read (A(i,j))
repeat
repeat
Three permanent routines are provided for manipulating alpha-numeric
data. The first:-
routine spec read symbol (integername i)
reads the next symbol (simple or compound) from the selected channel,
converts it into a numerical equivalent and places the result in the
the specified integer location.
For example, if the next character on the data tape were an
asterisk (numerical equivalent 14) the instruction 'read symbol (p)'
would set the value of the integer variable p to 14 and move to the next
character on tape.
5.3
The second allows the next symbol on the data tape to be inspected without
moving on to the following one. It is
integer fn spec next symbol
The third:-
routine spec skip symbol
passes over the next symbol without reading it.
A table of numerical equivalents and a description of the formation
of compound symbols is given in Appendix 5.
It is in testing symbols that the alternative form of a constant
is useful. For example, we could test if the next symbol on a tape were an
asterisk by
->1 if next symbol = 14
or ->1 if next symbol = '*'
Since spaces and underlined spaces are ignored in a program, and newline
and semicolon are used as terminators, special symbols are provided to
represent them. Thus a space can be tested for by
->1 if next symbol = 's'
The symbols are:-
s s representing a space
s s '' an underlined space
n n '' a newline
; ; '' a semi-colon
If the data itself contains these special symbols, then they can be tested only
by using the internal equivalent.
Finally there is a permanent input routine which permits the reading
of an indefinite number of decimal numbers into successive storage locations,
stopping when a particular symbol on the data tape is reached. This routine is
routine spec read sequence (addr s, integer p, integer name n)
The formal parameter type addr is explained in Section 9; for the
present purpose it is sufficient to say that the actual parameter will be the
name of a variable, representing the first location into which the numbers are
to go. p is the numerical equivalent of the terminating character, and on
exit from the routine, n contains the number of numbers that have been read.
5.4
As an example of the use of the above routine, suppose a data tape
contains an unknown number of numbers, but less than 1000, and that the
last number is followed by an asterisk. Then the instructions
array X (1:1000)
integer n
read sequence (X(1), 14, n) [or : read sequence(X(1),'*',n)]
would cause the successive numbers to be read into X(1), X(2), etc.
If there were 800 numbers in the sequence, then n would be set to 800
when the routine was left.
NOTE
On input, each line of data is reconstructed to give an image of the
print-out produced by the Flexowriter. Thus 'backspace','tab','upper case'
and 'lower case' do not appear as characters in the reconstructed line,
since they do not appear on the print-out. 'Tab' produces an equivalent
number of spaces, 'backspace' helps form a composite character, and
non-significant cases are ignored. Those positions containing an erase
are then deleted from this line. The line image is normally 160 characters,
but where the tab and backspace facilities are avoided, lines can be of any
length, sections of 160 characters being taken serially.
BASIC OUTPUT ROUTINES
The routines for the output of a single decimal number are
routine spec print fl (real x, integer m)
routine spec print (real x, integer m,n)
The first of these prints the value of x (which may of course be a
general [EXPR]) in floating point form, standardised in the range 1≤x<10,
with m decimal digits after the decimal point. The number is preceded by
a minus sign if negative, and a space if positive. The exponent is preceded
by α and consists of a space or a minus sign and two decimal digits, the first of
which is replaced by a space if it is not significant.
The second routine prints the value of x in fixed point form with m
digits before the decimal point and n after. Non-significant zeros, other than one
immediately before the decimal point, are suppressed, and a minus sign or space
precedes the first digit printed. If |x| ≥10↑m then extra digits are included
before the decimal point, the effect being to spoil any vertical alignment of
the printed page.
5.5
It should be noted that no terminating characters are included
by the above routines. They may be included by the user by means
of the routines:-
routine spec newline
routine spec space
routine spec newlines(integer n)
routine spec spaces (integer n)
routine spec tab
routine spec print symbol (integer i)
The first of these resets the carriage of the appropriate printer
(or punches the newline character), and the second causes the printer to
skip a character position. If a number of consecutive spaces or newlines
are required, the third and fourth routines may be used, for example:-
spaces (5)
newlines (3)
The fifth routine punches the tab character or causes the printer to move to the
next tab setting. These settings are at positions 8, 16, 24, 32, 48, 64, 80,
96, 112, 128, 144, and 159. The sixth prints the symbol corresponding to the
value i.
The routine:-
routine spec newpage
causes the lineprinter to commence a new page, if the output
device is a line printer, or punches 30 newline characters if it is a punch.
The routine:-
routine spec runout (integer n)
punches n runout characters (used to seperate sets of results, for example)
on the punch. It has no effect if the output is on a line printer.
Arrays of numbers may be output by means of the routines
routine spec print array fl (array name A, integer m)
routine spec print array (array name A, integer m,n)
For a one-dimensional array, the elements of the array are printed
across the page, each number being terminated by two spaces, or a newline
if the right hand edge of the page has been reached. The successive rows of
a two dimensional array are printed as above, successive planes of a three
dimensional array are printed as two dimensional arrays, and so on. Each
array is started on a newline and the printing style for the individual
numbers is the same as that of the 'print fl' and 'print' routines.
5.6
CAPTIONS
There is a special facility for printing captions. For example
caption ssss TABLE s OF s TEMP s AGAINST s; VOL
This prints the information after caption up to, but not including, the
terminating symbol 'newline' or 'semi-colon', since spaces and underlined space
are ignored and 'newline' and 'semi-colon' are used as terminators, we also use
the special characters:-
s or s
s '' s
n '' n
; '' ;
Thus
newline
caption A s = ss ; print (y,1,3); newline
caption B s = ss ; print (2,1,3); newline
would be printed as
A = 1.712
B = -2.380
In general c can be used (in its usual sense) in a caption if the information
is too long to fit on one line across the page. In view of this if an
underlined word ending in c is used at the end of a caption, it must be
terminated by 'semi-colon' not 'newline'.
BINARY INPUT AND OUTPUT
Binary tape may be read and punched by means of the routines
routine spec read binary (integername i)
routine spec punch binary (integer i)
The first reads the next row of holes on the tape as a binary number
(in the range 0-127, with the tape so oriented that the sprocket hole comes
between the digits of value 4 and 8), and places it in the named variable.
Binary data tapes must be preceded by ***B or, if they contain characters of
of even parity, by
***P
***B
The second punches the seven least significant binary digits of the
integral part of the integer expression as a row of holes on the output
tape.
NOTE: Cards or 5-hole tape may be used in which case the operations are on
5 or 12 digits rather than 7.
6.1
6 MONITOR PRINTING AND FAULT DIAGNOSIS
FAULT MONITORING
There are two types of fault which can be detected by the compiler,
those which can be found during compiling and those which become evident during
the running of the compiled program. To aid the programmer in correcting
these faults information is automatically printed out where a fault occurs.
COMPILER TIME MONITORING
During compiling an outline of the program is produced as an aid to the
finding of faulty instructions. It also associates each block and routine with
its serial number, for use in tracing faults found at run time (see later).
All faults during compiling are monitored. Those to which a line
number can be attached, such as NAME NOT SET, are preceded by it, while
those which can only be found at the end of a routine such as TOO FEW
REPEATS are monitored after the END. In calculating the line number, blank
lines are ignored, and lines joined by the continuation symbol c count as one.
Finally at the end of each routine all the non-local variables except the
permanent routines and functions are printed out. Although these do not
necessarily indicate a fault, they may indicate a name which should have been
declared locally. A typical program monitor might be
0 BEGIN BLOCK : SERIAL NO = 89, M/C ADDRESS = 2721
26* NAME TEMP NOT SET
55* LABEL 7 SET TWICE
70 BEGIN ROUTINE POLY:SERIAL NO = 90, M/C ADDRESS = 3210
115* NAME TEMP NOT SET
115* REAL NAME X IN EXPRESSION
120 END ROUTINE POLY : OCCUPIES 256 M/C INSTRUCTIONS
* LABEL 18 NOT SET
NON-LOCAL VARIABLES A TEMP1 S1
182 END OF PROGRAM: OCCUPIES 800 M/C INSTRUCTIONS
The above should be self-explanatory. It indicates that the program
started at line 0 and finished on line 182. These are physical lines
and exclude all blank lines on the print-out. The outer block is given
the serial number 89. The routine POLY started on line 70 and was given
the serial number 90. There were mistakes in lines 26 and 55 and two in line
115. Finally label 18 was not set in the routine POLY.
6.2
Since there may be more than one statement on a line, it is not possible
to tell specifically which statement is involved but the faults are printed
in the order in which they are discovered. A full list of faults is given
in Appendix 4 together with a brief description of their nature.
RUN TIME MONITORING
During the running of a program certain faults may be detected
both by the compiler and by the machine and its supervisor program.
For example, the supervisor program detects the case where the square
root of a negative argument is being requested and the compiler detects
faults connected with switch and test instructions.
The standard procedure is to print out 2 lines of information
specifying the fault and the line on which it occurs followed by a list
of useful information found in the FIXED part of the stack. For example:-
LINE 117 ROUTINE 90
EXP OVERFLOW
ROUTINE 90
ARRAY(1:10,1:5)
ARRAY(1:10,1:5)
10 5
0.3333333341α 0 -1.1249999997α -1 0.0000000000α-99
6 4
CYCLE(CURRENT VALUE = 6, FINAL VALUE = 10, INCREMENT = 1)
CYCLE(CURRENT VALUE = 4, FINAL VALUE = 5, INCREMENT = 1)
BLOCK 89
0.0000000000α-99 3.7152463802α 3
10 5 3 6
ARRAY(1:10,1:5)
ARRAY(1:10,1:5)
6.3
indicates that an instruction in line 117 routine 90 (the line number
refers to the entire program, not just the routine), resulted in exponent
overflow. Then follows a list of the scalars, array dimensions and cycles
of the routine in the order in which they were originally declared,
followed by the list for the routine or block which called this routine,
then that of the routine which called it and so on until the main block
is reached. Thus the above might correspond to:-
begin
real a,b
integer i,j,k,l
array X,Y(1:10,1:5)
'
'
'
'
matrix fn (X,Y,i,j)
'
'
'
routine matrix fn(arrayname A,B integer m,n)
real a,b,c ; integer i,j
'
'
'
cycle i = 1,1,m
cycle j = 1,1,n
'
'
'
repeat
repeat
end
end of program
6.4
NOTES
1: This fault print out must be interpreted with care. When the fault occurs,
the fault print out routine looks in the STACK to find the fixed variables and
interpret them (see section 10). Now every location in the store initially looks
as if it contains a real quantity. Thus:-
(i) until an integer is assigned a value, it will appear as (and be printed
as) a floating point quantity (probably zero).
(ii) until an array declaration is obeyed, it will appear as 2 floating-
point quantities.
(iii) until a cycle has been entered, it will appear as 3 floating-
point quantities.
Conversely, since all sub-routines of a program share the same space,
then on entry to the second and subsequent routines, the stack will contain
the values left by the previous routine and these will be interpreted accordingly,
if the current routine does not alter them.
2: The 'CURRENT VALUE' attributed to a cycle is the value of the integer
name used on the left hand side of the instruction at the time of the fault.
Thus if a program consisted of a number of cycles one after other, controlled
by i, and the fault were inside the last cycle, then all cycles would have the
same 'CURRENT VALUE' - the current value of i.
3: Only cycles, arrays, integers and reals are distinguished.
(i) for integer name's and real name's the address of the actual paramter
is printed (as an integer) .
(ii) for array fn's (see Section 9) its parameters are printed (as integers).
(iii) for routines and function's used as parameters, six real quantities
are printed.
(iv) for complex quantities, the real and imaginary parts are printed in
floating point style.
6.6
The first pair of statements are DECLARATIVES which delimit the areas of
the program in which provision is to be made for the particular checking facility.
The second pair are INSTRUCTIONS which turn the facility on or off (initially they
are on). They do this by setting a certain switch which is examined whenever
the facility is about to be executed. If the relevant switch is on then the
facility is executed, if off it is skipped. If the facility has not been
compiled in the first place then the instructions have no effect. This switch
setting is extremely fast so that there is nothing to be gained from recording
the current state of the switch (in some integer, say), and testing this before
each setting order. For example, the following sequence causes queries to be
printed every tenth time round the cycle.
cycle i = 1,1,m
queries off
if fracpt(1/10) = 0 then queries on
'
'
'
'
repeat
The switch sensing on the other hand is a time consuming operation and it
is for this reason that the declaratives are provided to delimit the areas of the
program in which this takes place. In most cases, however, the check is compiled
over the entire program.
The checking facilities in question are described by the phrase:-
[check] = queries, routine trace, jump trace, array bound check
They will be described in turn.
QUERY PRINTING
Any arithmetic instruction (including complex) can be followed by a ?,
for example:-
a = b(i) + c?
When the facility is operative the new value on the l.h.s. is printed every
time the instruction is obeyed. The style of printing will be fixed, floating,
or complex floating according as the l.h.s. is of integer, real, or complex
type.
[Unlike the other facilities, ?'s are normally compiled so that a
compile queries at the head of a program is redundant. Also ignore queries
is equivalent to stop queries.]
7.2
2. The OUTPUT information says that reference to channel 0 in the
program means the lineprinter (if no output channel is selected in the
program channel 0 is used). The number of LINES gives an upper limit
to the amount of output that is to be permitted.
2. STORE gives an upper limit on the number of 512 word main store
blocks used by the program and data.
3. COMPUTING gives a limit on the running time of the program. An
'INSTRUCTION' is equivalent to 2048 machine instructions.
The OUTPUT, STORE, and COMPUTING sections are optional, both
individually and collectively. If they are omitted the allowances given
in the above example are assumed, i.e., 100 LINES, 32 BLOCKS, 10000
INSTRUCTIONS. These should in fact be adequate for most small problems,
except possibly the 100 LINES. The foregoing example could therefore be
shortened to:-
JOB
UMA, JONES 5/2
COMPILER AA
begin
| |
| PROGRAM |
| |
| |
end of program
| |
| DATA |
| |
| |
***Z
A program tape is always assumed to be on input channel 0 so that in the above
case, the data for the problem is also on channel 0, which is the channel
used in the absence of a contrary 'select input' instruction in the
program. ***Z is an end of tape marker and indicates that all the
information on that tape has been read. This must be on a line of
its own, and must be followed by at least one 'newline'.
8.1
8 COMPLEX ARITHMETIC
As indicated previously, facilities exist for the manipulation
of complex as well as real and integer quantities. complex quantities
are stored as a pair of real numbers in consecutive locations (the real and
imaginary parts respectively). The address of the complex quantity is
that of the real part.
DECLARATIONS
All quantities must be declared before they are referred to.
For example:-
real R1, R2, R3
complex z
complex array P(1:10), Q(1:10,1:10)
causes 3 locations to be reserved for R1, R2, R3, 2 for z, 20 for P and
200 for Q.
STANDARD FUNCTIONS
The following standard functions are added to those previously
given:-
re(z) (real part of z)
im(z) (imaginary part of z)
mag(z) (modulus of z)
arg(z) (argument of z - in radians)
conj(z) (complex conjugate of z)
The argument z may be any [EXPR] (in the complex sense as described below)
The functions
csin, ccos, ctan, cexp, clog, csqrt
have complex [EXPR]'s as arguments and yield results of complex type.
For example if z = x + iy, cexp(z) = exp(x)(cos(y) + i sin(y))
In the case of clog and csqrt it is the principal value which is computed,
i.e., the value for which the argument θ lies in the range -π≤θ<π
8.3
NOTES
1. Just as real quantities may not appear on the r.h.s. of an integer
assignment (except as arguments of integer functions), so complex
quantities may not appear in real or integer expressions.
However, the functions
re(z), im(z), mag(z), arg(z)
convert from complex to real quantities and may therefore appear on
the r.h.s. of a real assignment. In fact any function whose
value is real regardless of its arguments may be used in a real
expression (just as any integer function, regardless of its argument,
may appear in an integer expression). Thus if X and B are real and Y
complex then:-
X = B + im(Y)
is valid.
2. re(z) and im(z) are actual locations in the store and can therefore
be used on the l.h.s. of an instruction (whose mode is then real).
For example:-
re(z) = sqrt(2)
im(y) = 5 + im(z1)
However, mag(z) and arg(z), even though they do define z, are not locations
in the store and cannot be used on the l.h.s. If a complex quantity
is being evaluated by means of the evaluation of its magnitude (m) and
argument (a), the assignment is done by
z = m*(cos(a) + i sin(a))
or z = m*cexp(ia)
9.1
9 STORE MAPPING
THE ADDRESS RECOVERY FUNCTION
The absolute address of any variable is not generally known in
an Autocode programme, but it may be obtained by means of a standard
function. For example:-
s = addr(A(0,0))
This places the address of A(0,0) into the variable s. The argument
may be any variable, real, integer, or complex and the result is an integer
giving the absolute address of the storage location allocated to that
variable.
Absolute addresses are used in conjunction with array functions
(see below) and with the 'storage' functions
integer (integer n)
real (integer n)
complex (integer n)
These give the contents of the address in question as an integer,
real, or complex number. In the last case the real and imaginary parts
of the number are assumed to be in n and n+1. The actual parameter
may of course be an integer expression e.g., s+k-1. These functions
may be employed on the left hand side of an assignment statement as
well as in an expression. Thus the pair of instructions
s = addr(a)
real(s) = b
are equivalent to
a = b
ARRAY FUNCTIONS
The declarations of Section 2, define variables and allocate
storage space for them. In this section we introduce a declaration
which defines variables as the numbers contained in storage locations
that have already been allocated. This is of importance in communicating
between routines with the addr type of formal parameter and in renaming
variables (see below).
An example is
array fn X(s,p)
which defines X(i) as the real number in the storage location whose
address is given by s+i*p. Thus it defines a vector X(i) in
terms of an origin s and a dimension parameter p.
9.2
Array functions may define rectangular arrays with any number
of subscripts. For example:-
array fn Y(s,p,q)
defines Y(i,j) ≡ real (s+i*p+j*q)
integer or complex array functions may be defined by prefixing the declaration
by integer or complex, (i.e. integer array fn X(s,p))
Array functions may also describe scalars. For example :-
array fn A(s)
defines A to be real (s). In this way, elements of a vector, say, can be
given individual names.
The parameters in array functions may lie general integer expressions.
As an example, assume that 100 storage locations have keen allocated
in some way, and that the starting address is given by the integer
variable s1. Then to define the contents of these locations as a
vector x(i), one could write
array fn x(s1,1)
x(0) would then correspond to the number in address s1, x(1) to that
in s1+1 etc. If it is desired that the first location should
correspond to x(1), the declaration would be written
array fn x(s1-1,1)
If we had wanted to define a 10 x 10 matrix, stored row by row
rather than a vector, we could have written
array fn A(s1,10,1)
and A(0,0) would correspond to address s1.
array fn A(s1-11,10,1)
would define a matrix in the available space whose first element
was A(1,1).
NOTES
1. If the suffices of arrays are to start from (1,1,---1) rather than
(0,0,---0), an appropriate adjustment must be made to the expression giving
the origin in the array function declaration.
2 Space redefined by array fn's may still be referred to by its original
name.
9.3
THE RENAMING OF VARIABLES WITHIN A BLOCK
We illustrate this with an example, suppose we wait to define and
allocate storage for pairs of real variables x(i), y(i) so that they
are in succesive locations. The array declaration will only define
a vector or matrix array stored in the conventional manner, so we
adopt the following device
begin
integer s
array a(1:2000)
s = addr(a(1))
array fn x(s-2,2), y(s-1,2)
------
------
------
The first pair of numbers could then be referred to either as
x(1), y(1) or a(1), a(2), the second by x(2), y(2) or a(3), a(4) etc.
Since the array declaration is for 2000 variables, up to 1000 pairs
x(i), y(i) can be accommodated.
As another example, suppose we have defined a matrix A and allocated
storage for it by the declaration
array A(1:10,1:10)
and we wish to define the first column of A as a vector, then we could
write
array fn y(addr(A(1,1)) - 10,10)
which defines y(i) ≡ real (addr(A(1,1)) - 10 + 10*i)
i.e. as the first column of A. Thus y(1) is equivalent to A(1,1), y(2)
to A(2,1), - - - -,y(10) to A(10,1).
In the case of complex array functions the user must take into account
that a complex number occupies 2 consecutive locations. Thus if s1 is
the address of Q(1,1) of a complex array Q(1:10,1:10), then
complex array R(s1-20,20)
defines a vector R(i) whose elements are the first column of Q, i.e.,
R(1) ≡ Q(1,1)
10.1
10:THE USE OF MACHINE INSTRUCTIONS
STACK STRUCTURE
Machine instructions can be used in routines either to make an
inner loop more efficient or to effect some operation which cannot
easily be done otherwise. It is assumed that the reader is reasonably
familiar with the logical structure of the machine, that is with the
basic order code. It also essential to know how data is stored in the
stack. We illustrate this with reference to the following routine.
routine matrix fn (array name A,B integer m,n real fn F)
real a,b,c ; integer i,j
array C(1:m,1:n),E(1:m)
real fn spec F (real x)
'
'
'
cycle i = 1,1,m
cycle j = 1,1,n
'
'
'
'
repeat
repeat
'
'
'
end
NOTES
1. The first word of the local stack section contains the control number
for returning to the calling routine (the first half word) and the previous
contents of Bd, the current level B-line (the second half word). The 1st
half word of the second word contains the test link (which records the position
within the label list of a test instruction), and the 2nd half word contains
information ( the number and type of the routine and the number of fixed
variables) required by the run-time fault monitor routine. Here Bd refers
to the B-line associated with the routine, and corresponds to the textual
depth of the routine in the program in which it is embedded. If (say)
this is 2 then Bd ≡ B2. The relative locations of the fixed variables A,
B, m, n etc., are assigned at compile time. Immediately on entry to the routine
the current value of B90, which always points to the next available location
in the stack, is recorded in Bd and the previous contents of Bd recorded in
the stack (as already noted). B90 is then advanced to the end of the fixed
storage allocation. When the declarations for C and D are 'obeyed' it is
advanced again to the final value shown.
10.3
2. Destandardised quantities are formed by adding 0*8↑(-12) to the standardised
form. This constant will be found in location *1000001. This octal form
of the address can be used in machine instruction formats(see later).
There are no integer name or real name parameters in this example; if
present they would be represented (at the appropriate place among the fixed
variables) by single words, namely their addresses, in a destandardised form.
They are at present indistinguishable from integer's. Similarly for
complex name parameters. A complex quantity requires two consecutive
words, representing the real and imaginary parts.
3. ARRAYS. The primary reference to an array consists of a pair of words. The
second half of the 1st word points to the (1st word of the) 'dope vector',
that of the second word to the 'Iliffe vector'. The dope vector contains
the values of the bound-pair list together with the number of pairs, i.e. the
dimensionality of the array. If there is more than one array associated
with same bound-pair list they share the same dope vector. The Iliffe vector
gives the origin of each row of the matrix (which is stored by rows). The
purpose of this is to simplify computation involved in accessing an element
of the array. Thus for example to add C(i+5,j-6) into the accumulator
the instructions are:-
101, 96, d, i + ½ put i in β96
104, 96, 0, c + 1½ β96 = β96 + 10
101, 97, d, j + ½ put j in β97
104, 97, 96, 5½ β97 = β97 + entry for row (i+5)
320, 0, 97, -6 acc = acc + real (β97 - 6)
Similarly to add the element D(i+5) of the one-dimensional array D
(which has no Iliffe vector) one may write
101, 97, d, i + ½ put i in B97
104, 97, 0, D + 1½ B97 = B97 + addr (D(0))
320, 0, 97, 5 acc = acc + real (B97 + 5)
In these instructions i, C, j, D refer to the addresses of these quantities
(see later)
Arrays of k dimensions (>2) are stored in hierarchical fashion.
The primary Iliffe vector points to a set of arrays of k - 1 dimensions
stored end to end. Each such array consist of an Iliffe vector referring
to a set of k - 2 dimensional arrays, and so on.
10.4
4. THE PARAMETRIC FUNCTION F. Six words of information are kept here.
In addition to the control number for entering the routine it is
necessary to keep a record of the display of the relevant B-lines
when the routine is first substituted as an actual parameter. For
further details see the Compiler.
5. THE CYCLES. As explained in the text the initial and final values and
increment in a cycle are evaluated and checked for compatibility before
the cycle is commenced. The increment and final values, together with
the address of the controlled integer variable are recorded for use in
the execution of the cycle. The diagram illustrates how they are stored.
STACK INSTRUCTIONS
The following autocode formats involving the stack pointer (B90)
are available
st = st ± [EXPR']
st = [EXPR]
[NAME] = st
st represents the contents of B90. In the last instruction the [NAME]
must be local to the routine containing the instruction, otherwise a
fault is indicated.
MACHINE CODE FORMATS
Some 'machine code' formats are now described.
1. Where there is no symbolic address involved an instruction is written in
the form
[FD],[N],[N],[ADDRESS PART]
(and terminated as usual by ; or newline). Here [FD] refers to the
function digits, [N] to the Ba and Bm digits, and [ADDRESS PART] to the
address part, which may take a number of forms. It may be written as a
constant in the usual way (preceded possibly by a sign) bearing in mind
that the binary point is located 3 places from the right hand end. Thus
0121, 80, 0, 2.5 is equivalent to
05064000 00000024
10.5
It may also consist of an octal number which consists of an * followed
by up to 8 octal digits, including any significant zeros. Thus
O101, 91, 0, *1001 is equivalent to
04066600 10010000
in octal notation.
Finally it may consist of a label or a (possibly signed) constant plus
a label. The label is replaced by the control number corresponding to it. We
may refer to labelled constants (see next section) in this way. For example
0334, 0, 0, 14:
0101, 99, 0, ½ + 14:
'
'
'
14: *03, *0000012
puts an unstandardised 10 in the accumulator, and a halfword 10 in β99
NOTE : The formal definition of [ADDRESS PART] is
[ADDRESS PART] = [±'][CONST]+[N]:,[N]:,[±'][CONST],[OW]
2. The format
[±'][CONST]
is used to plant a standardised 48-bit floating point number in the current
location of the program.
3. Pairs of 24-bit words may be planted in the object program by means of the format
[ADDRESS PART][,][ADDRESS PART]
Thus we may plant tables of integers or labels, for example:-
3,4
7:,8:
4. We now have an instruction format which uses a symbolic address.
[FD],[N], -,[NAME][±CONST']
where [±CONST']=[±][CONST], NIL
Here the [NAME] can refer to anything which is represented in the fixed storage
sections of the stack. The resulting instruction is
[FD],[N], d, p [± CONST']
10.6
where (Bd, p) is the 'address' of the name, Bd being the B-line pointing
to the appropriate section of the stack, and p being the address relative
to the origin of that section. Thus an instruction
0324, 0, -, a
appearing in the routine under discussion would be translated as
0324, 0, 2, 14
assuming Bd ≡ B2, and that F occupies 6 words.
The effect would be to put a in the accumulator.
If the [NAME] refers to an unstandardised floating point integer then we
may wish to select the integral half for use in a B-line. For example
0101, 80, -, m+½
is equivalent to
0101, 80, 2, 6.5
If a and m had been real and integer name's then 2 instructions would
be necessary in each case, thus
0101, 99, -, a + ½
0324, 0, 99, 0
and
0101, 99, -, m + ½
0101, 80, 99, ½
If a is complex then
0324, 0, -, a
would put the real part into the accumulator, and
0324, 0, -, a+1
would load the imaginary part.
In the case of arrays we can select by similar means the two primary
reference words, and with their aid obtain access to the dope vector and/or
the array itself.
10.7
EXAMPLE ON THE USE OF MACHINE ORDERS
The following example forms the sum of three routines A, B, C of
similar dimensions. (It is in fact the permanent routine 'matrix add')
routine matrix add (array name A, B, C)
comment The routine forms A = B + C
real dump
0101, 61, -, A + ½ ;comment dope vector of A
0101, 62, -, B + ½ ;comment dope vector of B
0101, 63, -, C + ½ ;comment dope vector of C
0121, 65, 0, 4 ;comment check dimensions
0101, 64, 61, ½
0172, 64, 0, 2
0225, 127, 0, 1:
2: 0101, 64, 61, ½
0152, 64, 62, ½
0225, 127, 0, 1:
0152, 64, ,63, ½
0225, 127, 0, 1:
0124, 61, 0, 1
0124, 62, 0, 1
0124, 63, 0, 1
0203, 127, 65, 2:
0101, 65, -, A + ½ ;comment β65 = dope vector of A
0324, 0, 65, 1 ;comment β64 = no of elements in matrix
0322, 0, 65, 2
0320, 0, 0, *10000040
0356, 0, -, dump
0324, 0, 65, 3
0322, 0, 65, 4
0320, 0, 0, *10000040
0362, 0, -, dump
0330, 0, 0, *10000010
0356, 0, -, dump
0101, 64, -, dump + ½
0101, 66, 65, 1½ ;comment set β61 = address of 1st element of A
0104, 66, -, A + 1½
0101, 61, 65, 3½
0104, 61, 66, ½
0101, 66, -, A + 1½ ;comment set β62 = address of 1st element of B
0120, 66, 61, 0
0101, 62, -, B + 1½
0124, 62, 66, 0
0101, 63, -, C + 1½ ;comment set 063 = address of 1st element of C
0124, 63, 66, 0
0122, 64, 0, 1 ;comment perform addition
5: 0324, 04, 62, 0
0320, 64, 63, 0
0356, 64, 61, 0
0203, 127, 64, 5:
->4
1: 0121, 91, 0, 34
fault monitor ;comment DIMENSION FAULT
4: end
11.1
11.THE PERMANENT ROUTINES
In Section 5, we decribed the input and output routines.
The permanent material also includes routines for the solution of linear
equations, the solution of systems of ordinary differential equations and
operations on matrices. Further routines may be added from time to
time.
LINEAR EQUATIONS
routine spec eqn solve(arrayname A,b, realname det)
This routine solves the equations
A(1,1)x(1) + A(1,2)x(2) +....+ A(1,n)x(n) = b(1)
A(2,1)x(1) + A(2,2)x(2) +....+ A(2,n)x(n) = b(2)
' ' '
' ' '
' ' '
A(n,1)x(!) + A(n,2)x(2) +....+ A(n,m)x(n) = b(n)
(i.e. Ax = b), where the coefficients A(i,j) are stored in the
matrix A, and b(i) in the vector b. A is destroyed and the solution
is placed in b. If during the elimination process, the equations are
found to be linearly dependant, then 'det' is set to zero and the
routine is left, with both A and b upset, otherwise 'det' is set to
the determinant of A. Consequently 'det' should be tested after each
call of the routine.
MATRIX ROUTINES
The matrix routines operate on two dimensional arrays(i.e. matrices
not vectors). The dimensions of the arrays are not required as parameter
as the routines automatically find these from the declarations, and check
them for compatibility. The programmer may insert similar tests
in his own routines by means of the functions
integer fn spec dim (arrayname A)
integer fn spec bound (arrayname A, integer n)
The first gives the dimensionality of the array(1 for a vector, 2 for a
matrix etc.), and the second the nth bound (upper or lower) of the array
counting from left to right. For example, if A were declared by:-
array A(-5:+5, 1:p) where p = 10 then
dim(A) would have the value 2
bound(A,1) ' ' ' ' -5
bound(A,2) ' ' ' ' +5
bound(A,3) ' ' ' ' 1
bound(A,4) ' ' ' ' 10
11.2
The routines
routine spec unit (arrayname A)
routine spec null (arrayname A)
set A to be a unit matrix (checking that it is square) and a null matrix
respectively. The routines
routine spec matrix add (arrayname A,B,C)
routine spec matrix sub (arrayname A,B,C)
routine spec matrix copy (arrayname A,B)
set A to B+C, B-C and B respectively. Although the parameters are of
type arrayname, the operation of the routines is such that the same array
can be substituted for more than one of the parameters. For example:-
matrix add(A,A,A)
doubles A. The same is not true of the following routines:-
routine spec matrix mult(arrayname A,B,C)
routine spec matrix mult'(arrayname A,B,C)
routine spec matrix trans (arrayname A,B)
These set A to B*C, B*C' and B' respectively where the ' denotes transposition.
If it is required to, say, set a matrix to the product of itself and another
then the call
matrix mult(A,A,B)
will fail. It is necessary to declare another array, 'dummy' say, and
then use 'matrix copy' and'matrix mult':-
matrix copy (dummy,A)
matrix mult(A,dummy,B)
Alternatively, a routine with parameters of type array may be defined which
calls the permanent routines :-
routine MATRIX MULT(arrayname A, array B,C)
matrix mult(A,B,C)
end
In this case a call of the form
MATRIX MULT(A,A,B) or even MATRIX MULT(A,A,A)
is possible.
11.3
The routines
routine spec matrix div(arrayname A,B, realname det)
routine spec invert(array name A,B, realname det)
set A to inv(B) A and inv(B) respectively. In the process B is destroyed
and the value of its determinant placed in det. Should the matrix be
found to be singular, 'det' is set to zero. Consequently 'det' should be
tested after every call for these routines. If B is required at the end
of the routine, then the techniques described above should by used. The
function
real fn det (arrayname B)
sets 'det' to the determinant of B and destroys B.
SOLUTION OF DIFFERENTIAL EQUATIONS
There are two routines available for advancing the solution of
a system of first order ordinary differential equations
dy(i)/dx = f(i)(x,y(1),y(2),....,y(n)) i=1,2,...,n
from x to x+h, using the Kutta-Merson fourth-order integration method.
The system is defined by means of an auxiliary routine, which must be
supplied by the user, of the form :-
routine spec aux(arrayname f, real x)
which must evaluate the derivatives f(i) in terms of y(1),y(2),..,y(n)
and x and then place them in f(1),f(2), ....., f(n).
The first routine
routine spec int step(arrayname y,real x,h, integer n c
realname e, routine aux)
advances the solution by a single step of length h of the Kutta-Merson process.
[2] Reference, L.FOX (Ed. ) Numerical Solution of Ordinary and Partial
Differential equations. Pergamon 1962, P.24.
11.4
The parameters are :-
y name of a (real)array. On input y(1),y(2)...y(n) should
contain the solution at x. on output they will
contain the solution at x+h.
x the initial value of the independent variable
h the increment of the independent variable.
n the number of equations in the system.
e the name of a real variable, which on output will contain
an estimate of the maximum truncation error over the step.
aux the name of the routine which evaluates the derivatives at a
general point (see above).
The second routine
routine spec kutta merson(array name y,real x0,x1, realname e c
integer n,k, routine aux)
advances the solution, by means of a series of calls for 'intstep', from
x0 to x1, keeping, if possible the estimate of the maximum truncation
error less than e. An initial step length of (x1-x0)/2↑m where 2↑(m+1)
>k ≥ 2↑m, is taken. If over a step the local truncation error (given
by 'int step') is greater than e, then the step length is halved; if
the error is less than .01e then the step length is doubled.
If three successive reductions in step length give no improvement in the
estimated truncation error, then e is replaced by twice the smallest error
achieved, and the integration process continued. The parameters are :-
y the name of a (real)array. On input y(1),y(2),..,. ,y(n)
should contain the solution at x0. On output they will
contain the solution at x1.
x0 the inital value of the independent variable.
x1 the final value of the independent variable.
e the name of a real variable, on input this should contain
the accuracy criterion. On output it will be unchanged if this
accuracy has been achieved ; if not, it will be replaced by a
more realistic value(see above).
n the number of equations in the system
k an estimate of the number of steps required to cover the
range(see above)
aux the name of the routine which evaluates the derivatives
at a general point(see above).
A1.1
APPENDIX 1. PHRASE STRUCTURE NOTATION
In describing Atlas Autocode we use square brackets round an
entity to denote that it represents a class of entities and may be replaced
by any member of the class. We call an entity in square brackets a PHRASE.
For example we could define a decimal digit by
PHRASE[DIGIT] = 0,1,2,3,4,5,6,7,8,9
where the commas are interpreted as meaning 'or'. Thus there are ten
different things which can be called [DIGIT], and when we refer to [DIGIT]
elsewhere we mean that any of the ten will be legitimate.
We can then build up from this basis and describe, for example,
a signed digit as
PHRASE[SIGNED DIGIT] = +[DIGIT], -[DIGIT]
There are also places where a phrase may or may not appear and to
signify this a special phrase 'NIL' may be written as the last alternative
in a phrase definition. For example the switch limits in a switch
declaration can be proceeded by a + or - sign if desired. (Absence of
a sign corresponds to +.) The relevant definition is
[NAME LIST]([±'][N]:[±'][N])
where PHRASE[±'] = +,-,NIL
Thus -4:+4
-4: 4
1: 3
are examples of switch limits.
Alternatively we can use the special ? qualifier as follows.
PHRASE[±] = +, -
PHRASE[±?] = [±],NIL
The last is implicit and we can use [±?] (e.g., in place of [±']) without
explicity giving the latter definition.
In the interest of efficiency however, it is preferable to
keep the depth of analysis as small as possible and for this reason we
use the former scheme.
The phrase structure notation can be used recursively, i.e., phrase
definitions may,directly or indirectly, use themselves. For example we
may define a 'list of names separated by commas' by
PHRASE[NAME LIST] = [NAME][REST OF NAME LIST]
PHRASE[REST OF NAME LIST] = [,][NAME][REST OF NAME LIST],NIL
A1.2
[Since a ',' is used to separate the alternatives of a phrase definition
it cannot stand for itself like the other basic symbols. Instead we
must write [,]. Similarly [EOL] and [SP] are used to denote 'end of line'
and 'space' in the source language.]
The qualifier * also indicates recursiveness and a [NAME LIST]
could be defined as
PHRASE[NAME LIST] = [NAME][,NAME*?]
PHRASE[,NAME] = [,][NAME]
the definitions
PHRASE[,NAME*?] = [,NAME*],NIL
PHRASE[,NAME*] = [,NAME][,NAME*],[,NAME]
being implicit. Again, however, for reasons of efficiency we use the former definition
Given the phrases of the language it is then possible to describe all the format
allowed in a program. For example, if we introduce the phrase[TYPE] as
PHRASE[TYPE] = integer, real, complex
we can define the format for the scalar declarations as
FORMAT[SS] = [TYPE][NAME LIST][S]
The [SS] indicates that it is a source statement, which means it appears on
its own in an Autocode program.
In Atlas Autocode there is a further type or CLASS of format,
the unconditional instructions [UI], which have the special property that
they may be preceded by the conditional operators if [COND] then and
unless [COND] then.
A list of the phrases and formats of Atlas Autocode follows.
Note that some phrases ([S],[CONST],[NAME] and [TEXT]) are not formally defined.
These are defined by special built-in routines which we will not consider here,
but those interested may refer to the references given below.
A1.3
Finally we should point out that some of the definitions are not
completely rigid. For example, the arithmetic assignment statement is
defined as
FORMAT[UI] = [NAME][APP] = [EXPR]
In the routine which deals with this format, tests are made to ensure that
the [NAME][APP] does in fact describe a variable, and is not, for example,
a function.
References
[3]. Brooker,R.A., Morris,D. and Rohl,J.S. ''Trees and Routines'',
Computer Journal, Vol. 5. No. 1.
[4]. Brooker,R.A., MacCallum,I.R., Morris,D. and Rohl,J.S.
''The Compiler Compiler'' 3rd Annual Review of Automatic Programming
(ed. Goodman), Pergamon Press.
A1.4
PHRASE [EXPR] = [±'][EXPR']
PHRASE [±] = +, -
PHRASE [±'] = +, -, NIL
PHRASE [EXPR'] = [OPERAND][OP][EXPR'],[OPERAND]
PHRASE [OPERAND] = [NAME][APP],[CONST],([EXPR]),|[EXPR]", i, BUT NOT if
PHRASE [APP] = ([EXPR-LIST]), NIL
PHRASE [EXPR-LIST] = [EXPR][REST OF EXPR-LIST]
PHRASE [REST OF EXPR-LIST]= [,][EXPR][REST OF EXPR-LIST], NIL
PHRASE [OP] = +, -, *, /, ↑, ., NIL
PHRASE (CR)[acc] = dsa, acc, ca, sac
PHRASE [A0] = acc +, acc-, acc*, acc/, acc|, addr, -, NIL
PHRASE [QUERY'] = ?, NIL
PHRASE (CR)[program] = programme, program
PHRASE [,'] = [,], NIL
PHRASE [iu] = if, unless
PHRASE [acc'] = acc, ca, sac
PHRASE [TYPE] = integer, real, complex
PHRASE [TYPE'] = integer, real, complex, NIL
PHRASE [NAME LIST] = [NAME][REST OF NAME LIST]
PHRASE [REST OF NAME LIST]=[,][NAME][REST OF NAME LIST], NIL
PHRASE [ARRAY LIST] = [NAME LIST]([BOUND PAIR LIST])[REST OF ARRAY LIST]
PHRASE [REST OF ARRAY LIST]=[,][NAME LIST]([BOUND PAIR LIST])[REST OF ARRAY LIST], NIL
PHRASE [BOUND PAIR LIST] = [BOUND PAIR][REST OF BOUND PAIR LIST]
PHRASE [REST OF BOUND PAIR LIST]=[,][BOUND PAIR][REST OF BOUND PAIR LIST], NIL
PHRASE [BOUND PAIR] = [EXPR] : [EXPR]
PHRASE [ARRAY FN LIST] = [NAME]([EXPR-LIST])[REST OF ARRAY FN LIST]
PHRASE [REST OF ARRAY FN LIST]=[,][NAME]([EXPR-LIST])[REST OF ARRAY FN LIST], NIL
PHRASE [SWITCH LIST] = [NAME LIST]([±'][N]:[±'][N])[REST OF SWITCH LIST]
PHRASE [REST OF SWITCH LIST]=[,][NAME LIST]([±'][N]:[±'][N])[REST OF SWITCH LIST], NIL
PHRASE [RT] = integer map, real map, complex map, integer fn,
real fn, complex fn, routine
PHRASE [FPP] = ([FP-LIST]), NIL
PHRASE [FP-LIST] = [FP][REST OF FP-LIST]
PHRASE [FP] = [FP-DELIMITER][NAME]
PHRASE [REST OF FP-LIST] = [FP][REST OF FP-LIST], NIL
PHRASE [FP-DELIMITER] = [,'][RT],[,'] integer array name, [,'] integer array,
[,'] integer name, [,'] integer,
[,'][real'] array name, [,'][real'] array,
[,'] real name, [,'] real,
[,'] complex array name, [,'] complex array,
[,'] complex name, [,'] complex, [,'] addr, [,]
PHRASE [COND] = [SC] and [AND-C],[SC] or [OR-C],[SC]
PHRASE [AND-C] = [SC] and [AND-C], [SC]
PHRASE [OR-C] = [SC] or [OR-C],[SC]
PHRASE [SC] = [EXPR][COMP][EXPR][COMP][EXPR],
[EXPR][COMP][EXPR],([COND])
PHRASE [COMP] = =, ≠, >, ≤, <, ≥
A1.5
PHRASE [N-LIST] = [N][REST OF N-LIST]
PHRASE [REST OF N-LIST] = [,][N][REST OF N-LIST], NIL
PHRASE [ALPHA'] = α, NIL
PHRASE [± CONST'] = [±][CONST], NIL
PHRASE [real'] = real, NIL
PHRASE [ADDRESS PART] = [±'][CONST] + [N]:,[N]:,[±'][CONST],[OW]
PHRASE [check] = routine trace, jump trace, queries, array bound check
PHRASE [FAULT LIST] = [N-LIST] -> [N][REST OF FAULT LIST]
PHRASE [REST OF FAULT LIST]=[,][N-LIST] -> [N][REST OF FAULT LIST], NIL
PHRASE [SIMPLE LABEL] = [N]:, BUT NOT [N]:[,]
PHRASE [RT'] = [RT],NIL
FORMAT CLASS[UI]
FORMAT [UI] = [NAME][APP] = [EXPR][QUERY']
FORMAT [UI] = [NAME][APP]
FORMAT [UI] = ->[N]
FORMAT [UI] = ->[NAME]([EXPR])
FORMAT [UI] = caption [TEXT]
FORMAT [UI] = result = [EXPR]
FORMAT [UI] = return
FORMAT [UI] = stop
FORMAT [UI] = test [N-LIST]
FORMAT [UI] = [check]on
FORMAT [UI] = [check]off
A1.6
FORMAT [SS] = [UI][S]
FORMAT [SS] = [UI][iu][COND][S]
FORMAT [SS] = [iu][COND] then [UI][S]
FORMAT [SS] = cycle [NAME][APP] = [EXPR][,][EXPR][,][EXPR][S]
FORMAT [SS] = repeat [S]
FORMAT [SS] = [SIMPLE LABEL]
FORMAT [SS] = [N] case [COND]:
FORMAT [SS] = [NAME]([±'][N]):
FORMAT [SS] = [TYPE][NAME LIST][S]
FORMAT [SS] = [TYPE'] array [ARRAY LIST][S]
FORMAT [SS] = [TYPE'] array fn [ARRAY FN LIST][S]
FORMAT [SS] = [RT'] spec [NAME][FPP][S]
FORMAT [SS] = [RT][NAME][FPP][S]
FORMAT [SS] = begin [S]
FORMAT [SS] = comment [TEXT][S]
FORMAT [SS] = end [S]
FORMAT [SS] = end of [program][S]
FORMAT [SS] = ignore queries [S]
FORMAT [SS] = production run [S]
FORMAT [SS] = page [TEXT][S]
FORMAT [SS] = switch [SWITCH LIST][S]
FORMAT [SS] = compile [check][S]
FORMAT [SS] = stop [check][S]
FORMAT [SS] = own [TYPE][NAME LIST][S]
FORMAT [SS] = own [TYPE'] array [ARRAY LIST][S]
FORMAT [SS] = fault [FAULT LIST][S]
FORMAT [SS] = [FD][,][N][,][N][,][ADDRESS PART][S]
FORMAT [SS] = [FD][,][N][,]-[,][ALPHA'][NAME][±CONST'][S]
FORMAT [SS] = [±'][CONST][S]
FORMAT [SS] = [ADDRESS PART][,][ADDRESS PART][S]
FORMAT [SS] = [NAME] = st [S]
FORMAT [SS] = st = [EXPR][S]
FORMAT [SS] = st = st [±][EXPR'][S]
FORMAT [SS] = prepare to read perm [S]
FORMAT [SS] = define compiler
FORMAT [SS] = define master compiler
FORMAT [SS] = define special compiler
FORMAT [SS] = advance β8 [S]
FORMAT [SS] = pl [NAME]([N][,][N][,][N])[S]
FORMAT [SS] = real exponentiation [s]
FORMAT [SS] = |[TEXT][S]
FORMAT [SS] = now compile from input [N][S]
FORMAT [SS] = upper case delimiters [S]
FORMAT [SS] = normal delimiters [S]
FORMAT [SS] = [TEXT][S]
A2.1
APPENDIX 2 INDEX OF STANDARD FUNCTIONS AND PERMANENT ROUTINES
All the functions and routines listed below are declared at level
0 and hence are permanently available unless the names are redeclared locally
by the user. The number in the right hand margin indicates the page on which
they are described more fully.
STANDARD MATHEMATICAL FUNCTIONS
integer fn spec intpt(real x) 2.5
integer fn spec int(real x) 2.5
integer fn spec parity(integer n) 2.5
real fn spec sin(real x) 2.5
real fn spec cos(real x) 2.5
real fn spec tan(real x) 2.5
real fn spec log(real x) 2.5
real fn spec exp(real x) 2.5
real fn spec sqrt(real x) 2.5
real fn spec arctan(real x,y) 2.5
real fn spec radius(real x,y) 2.5
real fn spec arcsin(real x) 2.5
real fn spec arccos(real x) 2.5
real fn spec fracpt(real x) 2.5
real fn spec mod(real x) 2.5
real fn spec re(complex z) 8.1
real fn spec im(complex z) 8.1
real fn spec mag(complex z) 8.1
real fn spec arg(complex z) 8.1
complex fn spec csin(complex z) 8.1
complex fn spec ccos(complex z) 8.1
complex fn spec ctan(complex z) 8.1
complex fn spec clog(complex z) 8.1
complex fn spec cexp(complex z) 8.1
complex fn spec csqrt(complex z) 8.1
complex fn spec conj(complex z) 8.1
STORAGE FUNCTIONS
integer fn spec addr(addr s) 9.1
integer fn spec integer(integer s) 9.1
real fn spec real(integer s) 9.1
complex fn spec complex(integer s) 9.1
MISCELLANEOUS FUNCTIONS
integer fn spec control no([ROUTINE NAME])
This gives the address of the first word of the routine in question
integer fn spec dim(arrayname A) 11.1
integer fn spec bound(array name A,integer i) 11.1
NOTE : The above classes of function cannot be substituted as an actual
parameter in a routine call, since they are implimented in a different way.
A2.2
INPUT ROUTINES
routine spec select input(integer n) 5.1
routine spec read(addr s) 5.1
routine spec read array(array name A) 5.2
routine spec read symbol(integername i) 5.2
integer fn spec next symbol 5.3
routine spec skip symbol 5.3
routine spec read sequence(addr s,integer p,integername n) 5.3
routine spec read binary(integername i) 5.6
OUTPUT ROUTINES
routine spec select output(integer n) 5.1
routine spec print(real x, integer m,n) 5.4
routine spec print fl(real x, integer n) 5.4
routine spec space 5.5
routine spec spaces(integer n) 5.5
routine spec newline 5.5
routine spec newlines(integer n) 5.5
routine spec tab 5.5
routine spec newpage 5.5
routine spec runout(integer n) 5.5
routine spec print array(arrayname A, integer m,n) 5.5
routine spec print array fl(arrayname A, integer m) 5.5
routine spec print symbol(integer i) 5.5
routine spec print complex(complex z,integer m,n) 8.5
routine spec print complex fl(complex z,integer m) 8.5
routine spec punch binary(integer n) 5.6
MATRIX ROUTINES
routine spec null(arrayname A) A=0 11.2
routine spec unit(arrayname A) A=I 11.2
routine spec matrix add(arrayname A,B,C) A=B+C 11.2
routine spec matrix sub(arrayname A,B,C) A=B-C 11.2
routine spec matrix copy(arrayname A,B) A=B 11.2
routine spec matrix mult(arrayname A,B,C) A=B*C 11.2
routine spec matrix mult'(arrayname A,B,C) A=B*C' 11.2
routine spec matrix trans(arrayname A,B) A=B' 11.2
routine spec matrix div(arraynameA,B,realname det) A=inv(B)*A 11.3
routine spec invert(arrayname A,B,realname det) A=inv(B) 11.3
real fn spec det(arrayname B) result=|B| 11.3
MISCELLANEOUS ROUTINES
routine spec eqn solve(arrayname A,b realname det) 11.1
routine spec kutta merson(arrayname y,real x0,x1,realname e
integer n,k routine aux) 11.4
routine spec intstep (arrayname y, real x,h, integer n
real name e, routine aux) 11.3
A3.1
APPENDIX 3 INDEX OF DELIMITERS
addr 9.1 jump trace off 6.5
and 2.9 jump trace on 6.5
array 2.4
array fn 9.1 now compile from input 7.4
array bound check off 6.5 normal delimiters 2.11
array bound check on 6.5
own 4.9
begin 3.1 or 2.9
c 2.11 queries off 6.5
caption 5.6 queries on 6.5
case 2.9
comment 2.11 page 2.11
compile array bound check 6.5 production run 6.7
compile jump trace 6.5
compile queries 6.5 real 2.3
compile routine trace 6.5 (real)array 2.4
complex 8.1 (real)array fn 9.1
complex array 8.1 (real)arrayname 4.1
complex array fn 9.2 real fn 4.5
complex array name 8.4 real fn spec 4.5
complex fn 8.4 real map 9.4
complex fn spec 8.4 real map spec 9.4
complex map 9.4 real name 4.1
complex map spec 9.4 repeat 2.10
complex name 8.4 return 4.1
cycle 2.10 result 4.5
routine 4.1
end 3.2 routine spec 4.2
end of program(me) 2.11 routine trace off 6.5
routine trace on 6.5
fault 6.5
spec 4.7
i 8.2 st 10.4
if.....then 2.9 stop 2.11
.....if 2.9 stop array bound check 6.5
integer 2.3 stop jump trace 6.5
integer array 2.4 stop queries 6.5
integer array fn 9.2 stop routine trace 6.5
integer array name 4.1 switch 2.8
integer fn 4.5
integer fn spec 4.5 test 2.9
integer map 9.4
integer map spec 9.4 unless......then 2.9
integer name 4.1 ......unless 2.9
upper case delimiters 2.11
B1.1
Atlas Autocode Reference Manual
Amendments for COMPILER AB
The major deviations of AB from the AA description are:
No complex. Ignore all references to same.
No test - case. Use a sequence of conditions.
No routine or jump tracing.
No distinction between real....and integer [EXPR]s.
No array or integer array formal parameters.
No maps, array fns, own variables.
New program map and stack print, see attached examples.
A detailed (but incomplete) list of textual alterations follows.
2.6 after line 3
''2.5a1b means 2.5*a1*b'
insert
''c(b+1) means c*(b+1) if c is a scalar, but 2|a+b| is not
allowed for 2*|a+b|; * before | | may not be omitted.''
2.6 NOTES 3/4: replace lines 8-15
''In the formation ... must be positive.''
by
''a² or a↑2 is compiled as a*a.
All other cases of a ↑ n are distinguished at run
time by subroutine: if
(i) n = int (n) > 0, result = a*...*a
(ii) n = 0, result = 1
(iii) n = int (n) < 0, result = 1/a*...*a
(iv) n ≠ int (n) and a > 0, result = exp (n*log(a)) ''
2.7 ARITHMETIC ASSIGNMENTS: replace lines 10-13
''but if the l.h.s. ... an integral value''
by
''but if the l.h.s. is integer and the r.h.s. turns out at
run time to be non-integral, it will be rounded to the
nearest integer. For example, if i is of type integer,
i = 2.7 will leave 3 in i.''
2.9 CONDITIONAL LABELS: delete this section.
2.9 CONDITIONAL OPERATORS: replace line 11
''[EXPR] ... ([COND])''
by
''[EXPR]ø[EXPR] or ([COND])''
4.3 FORMAL PARAMETERS AND ACTUAL PARAMETERS: delete entry 4 of the table
''integer array ... explained below)''
4.5 FUNCTION ROUTINES: insert after the end
''There is no distinction between integer fn
and real fn, and both may be written fn.''
4.9 OWN VARIABLES: delete this section.
B1.2
6.1-6.3
COMPILER / RUN TIME MONITORING: The examples on pp. 6.3,6.1,6.2
should be replaced by those on pp. B1.3 - B1.4 in order. Note that
the first line of program is line 1.
6.5 FAULT DIAGNOSIS: delete lines 7-8
'[check] on [check] off''
6.6 delete lines 3-23
''The second pair ... entire program.''
6.6 replace line 25
''[check] a ..''
by
''[check] = queries, array bound check''
6.7 ROUTINE TRACING: delete this section
6.7 JUMP TRACING: delete this section
6.7 OTHER CHECKING FACILITIES: insert after the end
''the checks may be restored again by
normal run''
6.7 After the end of the chapter insert a new section
''USE OF B-LINES AT COMPILE TIME
If the program fails in compiling B49 should
contain the current line number.
Various aspects of compiling are controlled by
digits of B2, and can be altered by compile time machine
instructions (see section 10.1a)*. Initially B2 = 0.
i | B2 & 2↑i ≠ 0 | B2 & 2↑i = 0 |
--|-------------------------|---------------------------|
2 | ignore queries | compile queries |
4 | production run | normal run |
7 | print compiled code | don't print compiled code |
8 | don't print program map | print program map |
9 | upper case delimiters | normal delimiters |
--------------------------------------------------------
*Amendment on this page
8.1-8.5
COMPLEX ARITHMETIC: delete this chapter
9.1-9.3
ARRAY FUNCTIONS: delete this section
9.4 STORE MAPPING ROUTINES: delete this section
10.5 MACHINE CODE FORMATS; insert after subsection 1
''1a. If such an instruction is followed by =, it is
obeyed immediately on compilation, not at run time.''
APPENDICES: delete all inapplicable syntax definitions, and complex
library routine specs.
A1.4 line 13
''PHRASE (CR) [program] = programme, program"
delete "programme''
A2.1 MISCELLANEOUS FUNCTIONS: delete line 1
''integer fn spec control no ([ROUTINE NAME])''
A4.1 COMPILING TIME FAULTS subsection 3: delete lines 3-4
''REAL [NAME] IN EXPR
REAL CONST IN INTEGER EXPR''
B1.3
begin
real a, b, c, alpha, a1, a'
integer i, j, k, theta
array x (1:10)
routine spec test1 (real d, integer m)
routine spec test2 (real name e, integer name n, real fn test3)
real fn spec test3 (array name y)
cycle k = 1, 1, 10
x(k) = k
repeat
k = 0
a = 1 ; alpha = 7.663 , a1 = 10.4 ; a'' = 21.6
j = 2 ; theta = 123
test1 (2, 3)
routine test1 (real d, integer m)
real f
integer o
f = 1.5 ; o = 3
test2 (f, o, test3)
end
routine test2 (real name e, integer name n, realfn test3)
spec test3 (array name y)
real g
integer p
g = 6.7 ; p = 4
g = test3 (x)
end
real fn test3 (array name y)
real h
integer g
h = 6.43
cycle g = 1, 1, 10
h = sqrt(-2)
repeat
cycle g = 1, 1, 3
h = h + g
repeat
result = h
end
end of program
***Z
COMPILER AB/3
1 BEGIN BLOCK NO = 91 ADDRESS =00115100
15 BEGIN ROUTINE<test1> NO = 92 ADDRESS =00116320
20 END ROUTINE<test1> OCCUPIES 37 LOCATIONS
21 BEGIN ROUTINE<test2> NO = 93 ADDRESS =00117000
27 END ROUTINE<test2> OCCUPIES 42 LOCATIONS
28 BEGIN REAL FN<test3> NO = 94 ADDRESS =00117530
39 END REAL FN<test3> OCCUPIES 79 LOCATIONS
40 END BLOCK OCCUPIES 244 LOCATIONS
PROGRAM ENTERED
A RUN TIME FAULT HAS OCCURRED AT
LINE 33 REAL FN <test3>
SQRT -VE
THE FOLLOWING BLOCKS AND/OR ROUTINES WERE EXECUTED
BLOCK 91
a= 1.0000α 0 alpha= 7.6630α 0 a1= 1.0400α 1 a''= 2.1600α 1
j= 2 theta= 123
CYCLE <k> EXECUTED 10 TIMES
THE PROGRAM NEXT CALLS IN AT LINE 14
ROUTINE <test1>
f= 1.5000α 0 o= 3
THE PROGRAM NEXT CALLS IN AT LINE 19
ROUTINE <test2>
g= 6.7000α 0 p= 4
THE PROGRAM NEXT CALLS IN AT LINE 26
REAL FN <test3>
h= 6.4300α 0 g= 1
CYCLE <g> EXECUTED 0 TIMES
CYCLE <g> NOT ENTERED
THIS IS THE REAL FN IN WHICH THE FAULT OCCURRED
