(ii)

(iv)

2.

3.
PROGRAMMING IN ATLAS AUTOCODE

     This book is intended for those who wish to learn to write programs
in Atlas Autocode, a language available on both Atlas and KDF9 computers.

     A program consists of a detailed set of instructions to the computer,
explaining exactly hew it is to solve a certain problem.  It therefore
follows that the programmer must first:-

   (a) Formulate the problem and decide on the method to be used to
       obtain a solution.  Only then can he
   (b) Write a program describing the method already chosen.

     Although this book is mostly devoted to describing process (b), it
must be emphasised that, in any moderately large problem, it is
process (a) which contributes most to the success or failure of a
project.

     Two general suggestions can be made about this planning stage.
Firstly it often pays to draw a 'flow diagram' to help plan the logical
connections between different parts of the program.  The reader will
find many examples of flow diagrams in the subsequent pages.  Secondly,
considerable effort and money can often be saved by seeking, at the
earliest possible stage, the advice of someone who has successfully
completed a similar project.

     Figure 1 uses the formalism of a flow diagram to indicate the steps
involved in using a computer to solve a problem.

6.

          Moving information in or out of a location in the store is in
some ways similar to the operation of a tape recorder.  When withdrawing
information ('reading'), we take a copy of the contents of the location.
The original information is still there, and can be used again as often
as required.  When putting information in ('writing') the previous contents
of that location are destroyed.


Warning : If we road the contents of a location before putting anything
in, we are in danger of obtaining whatever was left behind at the end of
the previous program.


INPUT
          When we wish to use the computer, we normally need to feed in
two 'documents'     (1)  Program
                    (2)  Data
The difference between the two is shown by the two examples below:-

              Program                               Data
Method for solving a set of equations           Set of equations
Method for sorting words into dictionary order  List of words

          Most of the program consists of a series of instructions telling
the computer to carry out various operations.  These are kept in the store
in a code or 'language' which is not readily comprehensible to the programmer.
It is possible, but tedious, to write programs in this language (in the
early days of computers, nothing else was available).  Nowadays we can
write in a more convenient language, Atlas Autocode for example, and the
computer is supplied with a COMPILER which translates the program into its
own language.

          In the first place the program, and often the data as well, will be
written down with pencil and paper.  After careful checking, this will be
converted into suitable form (normally punched paper tape or punched cards)
for feeding to an INPUT device.

8.
     The sequence of events should be:-

(1)  Read in Program.
(2)  Compile (i.e. translate) into machine instructions.
(3)  Execute the compiled program which will contain instructions to
             (a)  Road in Data
             (b)  Carry out Calculation/Processing
             (c)  Print out Results

     However if any violations of the rules of the language are detected
during the compiling stage, no attempt is made to execute the program,
but instead a list of faults is printed out.

     Even after execution of the program has started, some part of the
translated program may turn out to be impossible for the machine to
execute.  For example, it cannot divide by zero.  The execution will
then cease and an appropriate fault signal will be printed.

9.
ORDER OF PRESENTATION TO COMPUTER

     In a small job, the preliminary information (Job Heading), program
and data are usually all supplied to the computer on one piece of tape ordered as follows:-


*** A                               )  Job Heading giving title of program
JOB                                 )  and stating which compiler is to
BLOGGS' FIRST PROGRAM               )  be used to translate the program
COMPILER AA                         )  following.  (AA=Atlas Autocode)


begin                               )
.....                               )
.....                               )
.....                               )  Program
.....                               )
.....                               )
end of program                      )



.....                               )
.....                               )
.....                               )  Data
.....                               )
.....                               )


*** Z                               ) Marks end of tape


NOTES
   (1) Programs written in Atlas Autocode can at present be run on either
an Atlas or a KDF9 computer.  If using an Atlas, we have the choice of
two compilers, both written at Manchester University
        (a) COMPILER AA
        (b) COMPILER AB
     The latter is a faster but somewhat restricted version of AA.
The Atlas Autocode compiler for KDF9 has been written at Edinburgh
University.
     Except where specially indicated, this book describes how to
write programs equally acceptable to all three compilers.  Precise
specifications of each compiler can be obtained from the appropriate
Computer Unit.

   (2) The example of a Job Heading given above is the minimum required.
New programmers should consult the Computer Unit of their own University
to discover what extra details need be given in any particular case.

12.

14.

16.

DECLARATIONS 
          Names are allocated to locations in the store by means of
declarations such as:-

    Declaration                                   Meaning

real a                      set aside the next unused location, call it
                            a and be prepared to put a 'real'
                            number in it later.
integer  b, c3              set aside the next two unused locations,
                            call them b and c3 and be prepared to
                            put integers (whole numbers) in them later.

Note  (1)  Generally speaking, a name allocated to a location will remain
fixed throughout the program.  However, the contents will vary whenever
new number is placed in it.
      (2)  The word 'variable' is used to describe locations which, have been
set aside to contain numbers, either real or integer.
      (3)  There are three distinctions between real variables and integer
variables:-
      (a)  An integer variable can only contain a whole number.  A real
variable may contain either an integer or a number such as 73.4827, with up
to 11 significant figures.
       (b)  There are certain purposes for which only integer variables
are allowed.  (e.g. To give the number of times a group of instructions
is to be repeated: repeating 1.7 times would be impossible).
   (c)  When we do multiplications and additions of integer variables, the
machine produces the exact answer.  When doing arithmetic on real variables,
the answers are 'rounded off' to 11 significant figures.


UNDERLINING 
     Note that the underlining of certain key words (real and integer above,
for example) is an integral part of the language.  At this stage the
reader is advised to accept, as arbitrary rules, that certain words are,
and others are not underlined.

19.

Output Instructions (Also see p. 86)

print (x, 3, 1)                         work out in the Mill the value of the
print (2x + y + 7, 3, 1) -              first expression in the brackets (i.e.
                                        x or 2x + y + 7) and print the value
                                        of the expression with 3 figures
                                        before the decimal point and one after.
                                        (The figures 3 and 1 can, of course,
                                        be varied).

newline                                 output printer is to go to the start
                                        of a fresh line, moving the paper up 
                                        accordingly.

newlines (2)                            equivalent to:- newline ; newline

space                                   output printer is to leave one blank
                                        space (printing takes place from
                                        left to right across the page)

spaces (3)                              equivalent to:- space; space; space

caption MORRIS1100                      output printer is to print out the
                                        set of characters MORRIS1100.

Note  The instruction caption ..... is chiefly used to obtain headings
and explanatory notes in the output.  These notes may be required to
include spaces, newlines, etc.
      A special method is provided for outputting the symbols space,
newline and semi-colon with a caption, since spaces are ignored by the
computer and a semi-colon or newline character marks the end of the
caption 'line':-

   s  or   s                            represents a space
   n  or   n                            represents a newline
   ;  or   ;                            represents a semi-colon,

Either
      (a)  caption n MORRIS ss 1100
or    (b)  newline ; caption MORRIS ; spaces (2)  ; caption 1100

will produce an output (at the beginning of a newline):-

MORRIS  1100

20.

SEPARATORS

     A few lines, neither declarations nor instructions, have to be written
into a program, chiefly to mark the begining and end of blocks and
routines. Examples are begin end and end of program, described on the 
next page.


COMMENTS 

     Any line starting with comment is disregarded by the compiler.  This
permits the insertion of explanatory notes, which must not contain a
semi-colon, for the benefit of the reader.  For example:-

            read (n)
            comment n is the number of cases to be solved.

For brevity, a single vertical bar can replace comment.  For example:-

            read (n)
            | n is the number of cases to be solved.

A third equivalent method of writing the above is:-

            read (n) ; | n is the number of cases to be solved.

21.
BLOCKS
     A program is normally split up into a number of blocks.  In general a
block consists of
                               begin
                               ......      )
                                           )
                               ......      )
                                           )
                               ......      )     declarations
                                           )
                               ......      )
                                           )
                               ......      )


                               ......      )
                                           )
                               ......      )
                                           )     instructions
                               ......      )
                                           )
                               ......      )

                               end

     At the end of the last block of a program, end is replaced by
end of program.

Example                        begin 
                               real array a(1:3)
                               real b

                               read (a(1),a(2),a(3))
                               b = a(1)+a(2)+a(3)
                               print (b,2,3)
                               end of program

     This causes the machine to read in three numbers, add them and print out
the total.

Note  The machine automatically terminates the calculation on reaching
end of program.  If it is required to stop the calculation at any other point,
the instruction stop is used.

22.

LABELS

     Any 'line' in the program can be labelled by writing on the left
a positive integer, followed by a colon.  The label has no effect other
than to give the line a reference number.

EXAMPLE
     i=i+j
10:  read (x)
     x=x+i


JUMP INSTRUCTIONS

     Normally, instructions are obeyed in the order in which they are
written.  In order to make the machine jump, either forwards or
backwards, to a labelled line in the program we can use a jump
instruction written, for example:-

             instruction                meaning 
             -> 10                      the next line to be
                                        obeyed is the one
                                        labelled 10:

Notes   (1)  By making the machine jump back to an earlier part of
the program we can make it go round a loop of instructions many times.

        (2)  Although jumps can be either forwards or backwards, we
are not allowed to jump from one block to another.

        (3)  Jump instructions are frequently made conditional, as
described in the next section.

23.
CONDITIONAL INSTRUCTIONS

     Assignment and jump instructions may be made subject to a condition.

            Examples                               Meaning
            a = b + c if x = 0              Carry out the instruction if
            -> 27 unless a > b + 2          (or unless) the condition is
            stop if n>100                   satisfied.  Otherwise skip and
                                            pass on to the next instruction.

     If preferred, instructions may be written with the condition first,
followed by then:

            if x = 0 then a = b + c
            unless a > b + 2 then -> 27
            if n > 100 then stop

Note   (1)  Note the different uses of '=' in the first example.  In x = 0
it has its normal mathematical significance.  In a = b + c it means an
assignment.
       (2)   In the condition we may use any of the relations = ≠ > ≥ < ≤


MORE  COMPLICATED  CONDITIONS

     These may be formed

(1)  with a two-sided condition **
            e.g. if 0 < x < 1 + y then .......
(2)  by writing several conditions separated by and with the obvious
significance.
            e.g. if x>0 and y = 0 and z ≠ 2 then ........
(3)  by a similar use of a succession of or's
            e.g. if x>0 or y = 0 or z ≠ 2 then .........
(4)  by combining (2) and (3) provided and's or or's are separated by
brackets.
            e.g. if (x>0 or y = 0) and z ≠ 2 then ..........


** This form of condition is not accepted by the Manchester Compiler AB.

24.

EXAMPLE OF A SIMPLE PROGRAM

     Suppose we want to road in a list of positive numbers and print
out their average.  Suppose we do not know in advance how many there will
be.  In order to inform the computer when we have come to the end of
the list, we terminate it with the number -1.

     We shall need the following variables:-

(1)  a place in which to put the numbers as they are read in.
(2)  a running total.
(3)  a count (integer n, say) of how many numbers have boon read in.

Note that (2) and (3) must be set to zero before starting.

     A possible flow diagram is given on the next page:-

26.

28.

29.

MANIPULATION OF SYMBOLS

     INTEGER variables can not only be used to store integer NUMBERS as
described in the last chapter, but can also hold SYMBOLS.  Possible symbols
include

            (a)  The letters of the alphabet (both upper and lower case),
            (b)  The numerical digits 0 to 9 (see note 1 below).
            (c)  (  )  [  ]  .  ,  :  ;  '  ?
            (d)  + - * / ↑ | = ≠ > ≥ < ≤ α π
            (e)  space and newline.


Notes
   (1) The symbol 9 is NOT the same as the number 9.

   (2) Symbols can be stored in integer variables, including elements of
integer arrays.


INPUT OF SYMBOLS (See also p. 87)

       Input Instruction                         Meaning

read symbol (a)                     Road the next symbol on the data tape 
                                    and place it in location a.  Move the 
                                    data tape on by one symbol,
                                    Note (1)  The instruction read symbol
                                    can only road one symbol at a time 
                                    (unlike the instruction read which may 
                                    read several numbers).
                                    Note (2)  a MUST be an integer variable 
                                    or an element of an integer array.

Important Note  When reading numerical data, spaces and newlines simply
mark the end of a number.  However, both spaces and newlines count as
symbols and will be road in by the routine read symbol.

30.

ASSIGNMENT OF SYMBOLS

     Instructions to assign symbols to integer variables are written in
a form very similar to those which assign numbers, but the symbol
concerned is written between a pair of 'quotation marks'.  For example:-

            integer i, j, k
            i = '*'
            j = 'P'
            k = '7'

Note that the last two instructions assign the SYMBOLS P and 7 to j and k
respectively. On the other hand, the instructions

            j = P
            k = 7

assign to j the NUMERICAL value currently stored in the variable named P,
and to k the NUMBER 7.



CONDITIONS

     Conditions depending upon the equality, inequality, etc. of symbols
may be written in a fairly self-evident manner e.g.

            if i = '*' then stop
            -> 9 unless k = '?' or j = 'A'

32.

RELATIONSHIP BETWEEN SYMBOLS AND INTEGERS

     Symbols are stored in integer variables, and in fact each symbol
has a numerical value to which it corresponds.  However, since this
correspondence may vary between compilers, programmers are advised not
to make use of this fact.  On the other hand, all the compilers are
arranged so that 'A' has a value one less than 'B', which is one less
than 'C', etc., thus preserving the natural dictionary ordering.  The
same is true of 'a', 'b',..... etc. and of '0', '1'..... etc.

Example

     To test whether the next symbol on the data tape is a lower case
letter in the first half of the alphabet we could write:-

            read symbol (i)
            if 'a' ≤ i ≤ 'm' then ...............

34.

36.

38.

Mathematical Symbol                   Meaning

        +                             addition
        -                             subtraction
        *                             multiplication
        /                             division
        ↑                             raise to a power (a↑3 means a3)

        ²                             squaring
        |                             used in pairs as modulus signs.

Notes
(1)  In normal mathematical notation we often omit the multiplication
sign (e.g. ab for a*b).  In Atlas Autocode we write the * sign,
otherwise the compiler will look for a variable with the name 'ab'.  The
* can be omitted where a constant is followed by a variable
(e.g. 3.5*y and 3.5y are equivalent)

(2)  a² and a↑2 are equivalent.  All other powers must be written with ↑.

(3)  In manuscript, the symbol ↑ is usually written ↑.

39.

PRECEDENCE OF OPERATORS (+ - * / ↑)

     There may be some uncertainty about the meaning of an expression such
as a*b+c.  Do we carry out the multiplication first, giving (a*b)+c, or
the addition first giving a*(b+c) ?
     In the absence of brackets, we have the rule that, of two adjacent
operators (like * and + above), the operator of higher precedence in the
table below is to be carried out first.
     (1)  ↑          (highest precedence)
     (2)  * or /
     (3)  + or -     (equal lowest precedence)
     Where two adjacent operators are of equal precedence by the above table,
the one appearing to the left (in the expression to be evaluated) is carried
out first.

Notes  (1)  The multiplication operator between a constant and a variable has
the same precedence whether written explicitly or 'implied' (see note 1 on
previous page)

       (2)  The symbol ² is treated as equivalent to the pair of symbols ↑ 2
and precedence is given accordingly.

       (3)  If we wish to over-ride the above rules, we must use brackets as
in normal mathematical notation.

       (4)  When in doubt it is wisp to insert brackets for safety and
clarity.

       (5)  The 'left-hand precedence' between + and - agrees with normal
usage.

            e.g.  By a-b+c we mean (a-b)+c and not a-(b+c)

                    Examples                Meaning
                    a/b*c                   a  x  c
                                            b

                    a/(b*c)                 a 
                                            bc

                    a↑(b*c)                 abc

Note  The first two examples show that it is necessary to bracket
denominators containing more than one term.  A common mistake is to write
a/2b when a/(2b) is intended.

40.

FUNCTIONS 

     In addition to variables and constants, functions may also be included
within expressions.  The basic functions available are:-

real function               meaning                 note
sin(x)     )                as in
cos(x)     )                elementary              x in radians
tan(x)     )                trigonometry

sq rt (x)                   +√x

log (x)                     logarithm of x          to base e

exp (x)                     ex

mod(x)                      modulus of x            mod(-3.7)=3.7;mod(3.7)=3.7
                            (i.e. Absolute          Can be written |x|, but
                            value of x)             see note below.

arctan (x,y)                tan-1 (y/x)             In radians. Value is in
                                                    1st or 4th quadrant if x>0
                                                    2nd or 3rd quadrant if x<0

radius (x,y)                +√x²+y²

frac pt (x)                 fractional part of x    frac pt(3.73)=0.73
                                                    frac pt (-3.73)=0.27

integer function            meaning                 note
int(x)                      nearest integer to x    int (3.73)=4

int pt (x)                  integral part of x      int pt (3.73)=3
                                                    int pt (-3.73)=-4

parity (n)                  +1 if n is even         n must be an
                            -1 if n is odd          integer variable.

Notes  (1)  The first group of functions (down to frac pt) all produce
a number of type real, which can only be assigned to a real variable.  The
last three produce a number of type integer.
       (2)  In particular, note that the function mod(x) produces a number
of type real, irrespective of whether x is of type real or integer. On the
other hand, a pair of modulus signs will give the same numerical value as the
modulus function, without altering the type, (i.e. integer remains integer).
Hence, if n is an integer,
                        n = |n|       is valid
                        n = mod(n)    will be faulted.
       (3)  The above functions are all understood by the compiler before
the program is read in.  The method used to define additional functions, if
required, will be given later (page. 70)
       (4)  As the names sin, log etc. are already in use, they should
not be used by the programmer in any of his declarations.

42.

FURTHER ASSIGNMENT INSTRUCTIONS

     The general form of an assignment is either
(1)  assign the value of an INTEGER expression to an INTEGER variable or
(2)  assign the value of a REAL or INTEGER expression to a REAL variable.


Examples  Suppose we have declared real a,b,c,x
                                   integer i,j,k

then possible instructions are:-

x = (-b + sq rt (b*b - 4a*c))/(2a)
i = int(j/k) + j*j
a = log (1 + cos (2! x)) 3.74b
x = i

Notes   (1)  As already explained i = x will cause a fault signal because
x is real.  If required, we can write: i = int(x)

        (2)  On the Atlas versions of the language we can, without a fault
signal, assign to an integer variable any integer expression. The
responsiblilty for ensuring that the expression will work out to be
an integer, lies with the programmer.  (division or raising to a negative
power are possible causes of non-integer results). See the second example
above.

        (3)  When using KDF9 there is the further restriction that,
whenever an integer expression is compulsary, each stage in the evaluation
of the expression must yield an integer result. Referring to the rules of
precedence for operators, we see that, with the previous declarations,

     j = i*(i+1)/2     will always work but that
     j = (1+1)/2*i     while having the same result as the previous line
when- (141) is even, will be faulted if (i+1) is odd.

        (4)  It is possible to use expressions inside larger expressions;
in particular we can have a function of a function as in the third example.

43.

CYCLES

     Suppose that we wish to carry out a certain part of a program
10 times with an integer i taking the values 1,3,5.........,19 on
successive occasions.

     Clearly it is necessary to indicate

   (1) the sequence of values which the integer is to assume, and
   (2) the beginning and end of that section of program which is
to be repeated.

     We achieve this by writing:-

               cycle i = 1,2,19

            (  orders making  )
            (  up the section )
            (  of program     )
            (  to be repeated )

               repeat
               ......

NOTES
   (1) The sequence of values i is to assume is indicated by writing 
'cycle i = ' followed by 3 integer expressions giving the initial
value, the increment, and the final value.

   (2) The control variable i must have been previously declared to be
an integer or an element of an integer array.

   (3) The separator repeat, is used to indicate the end of the section of
program to be repeated.

   (4) The expressions for the initial and final values and the increment
are evaluated on first reaching the cycle.  The number of times the cycle
is to be executed is

            1 + (final value - initial value)/increment,

and a fault is signalled if this is not a positive integer.

45.

NESTING OF CYCLES

     Cycles may be nested to any depth.  Each cycle must have exactly
one associated repeat.

Example
            cycle i = 1,1,4
            read (A(i))
            newline
              cycle j = 1,1,i
              print (A(i)↑j,2,0)
              spaces (2)
              repeat ; comment this refers to cycle j =
            repeat   ; comment this refers to cycle i =

Supplied with the data
       0   1   2   3

the output would be
       0
       1    1
       2    4    8
       3    9   27   81


NOTE
    Within cycles, either single or nested, the control variable(s)
may be used for two distinct purposes:-
(a) to count the number of times the cycle has been executed, and
(b) to vary systematically quantities occurring in arithemetic expressions.
(e.g. the integer i in the above example both counts the number of times
the outer cycle is executed, and also enables us to operate on different
array elements on each occasion).

48.

SWITCH LABELS

     It is sometimes required to jump to one of several points
of a program, depending upon the value of some (integer) expression.
One method is given below on the left, with the equivalent and. more
compact use of a switch given on the right:-

                                          switch A(0:3)
                                          ......
21: read (i)                        A(3): read (i)

    -> 22 if i = 0                        -> A(i)
    -> 21 if i = 3
    -> 23 if i = 2

22: a = b + c                       A(0): a = b + c
23: a = 2a                          A(2): a = 2a

NOTES
   (1) As with ordinary labels, jumps can be either forwards or backwards,
but cannot go outside the current block.

   (2) Switch declarations appear among the other declarations at the
head of the block, and hence the name is declared before being used
for either a label or a jump instruction.

   (3) The name of the switch must not be used for any other purpose
at the same level.

   (4) It is not necessary to use all the labels in the range declared
(note A(1) missing above), but a fault would be signalled if i had the
value 1 on reaching the instruction -> A(i).

   (5) The bounds given when declaring a switch must be integer constants,
although the jump instruction can use integer expressions such as -> A(i+2j).

   (6) The symbol -> can only be followed by a constant (ordinary label)
or an element of a switch.

50.

     It is easier to combine these two processes by means of a cycle within
a cycle
    cycle  i = 1,1,2
       cycle j = 1,1,4
       A(i,j) = 0
       repeat
    repeat

     The same method will be used to print out the results in a rectangular
table.
Data Suppose the data is supplied as follows:-
(1)  An integer giving the number of results to analyse.
(2)  Groups of three integers in which
     the first indicates sex            (1 for boy, 2 for girl)
     the second indicates subject       (1,2,3,4 as before)
     the third indicates success        (0 for fail, 1 for pass)

for example:-

    data                              meaning 
    999                               999 results to follow

    1                                 A boy has taken Maths
    1                                 and failed.
    0

    1                                 A boy has taken French
    4                                 and passed.
    1

    2                                 A girl has taken Latin
    3                                 and passed.
    1

    etc.

     A possible flow diagram and program are given on the following
pages.

52.-

begin
integer i,j,k,l,n
integer array A(1:2: 1:4)

cycle i = 1,1,2
    cycle j = 1,1,4
    A(i,j) = 0
    repeat
repeat

read (n)

cycle 1 1,1,n
read (i,j,k,)
if k = 1 then A(i,j) = A(i,j) + 1
repeat

newline

cycle i = 1,1,2
    cycle j = 1,1,4
    Print (A(i,j), 3,0)
    spaces (5)
    repeat
newline
repeat

end of program

Notes:  (1)  The inner cycles have been indented on the pages for clarity.
This is quite permissible as spaces in the program are disregarded by the
compiler.
        (2)  In order to achieve a rectangular layout of results, spaces
(5) are put in the inner cycle, and the newline in the outer cycle.

54.

57.

LOCAL AND GLOBAL VARIABLES

     It is important to appreciate the sphere of influence of the
declarations made in the inner and outer blocks.
     A declaration appears at the head of a block and normally remains
valid throughout that block until cancelled by the end terminating the
block.  It also remains in force upon descent to an inner block, UNLESS
the same name in declared in the inner block.  In the latter case, the
variable is held in abeyance while the machine is executing the inner
block, coming into force again when the end of the inner block is
reached.
     Within any particular block the term local variable is used when
referring to variables declared in this block, and the term global
variables when referring to variables declared in any exterior block.
These points are illustrated by the following example.

            (i)   begin                       (ii)   begin
                  real A                             real A
                  .......                            .......
                  A = 1                              A = 1
                    begin                              begin 
                    real A, B, C                       real B, C
                    ............                       .........
                     B = 1                             B = 1
                     C = 4                             C = 4
                     A = B+C                           A = B+C
                     end                               end
                   print (A,2,2)                     print (A,2,2)
                   end                               end

            Here the name A refers to         Here A is global to the inner 
            quite distinct variables          block since this time A has 
            in the inner block and the        not boon re-declared. In this 
            outer block. The print            case the print instruction 
            instruction will print            will print the value 5.
            the value 1.

Notes  (1)  To communicate between blocks, global variables must be used,
since local variables are cancelled upon exit from a block.
       (2)  Labels and switch labels, unlike variables, are always local to
a block. It is thus impossible to enter a block except through the head of
the block (which is just as well as the local declarations are written
there).  It is impossible to jump from one block to another.
       (3)  Similarly each repeat must be in the same block as the cycle
to which it refers.

59.
EXAMPLE OF A PROGRAM
0                           begin
1                           comment to arrange lists of positive integers in
2                           comment increasing order of magnitude
3                           integer p
4                         1:read(p)
5                           if p≤0 then stop
6                                begin
7                                integer i,j,AMAX,jMAX
8                                integer array A(1:p)
9                                cycle 1=1,1,p
10                               read(A(i))
11                               repeat
12                               -> 3 if p=1
13                               cycle i=p,-1,2
14                               AMAX=0
15                                    cycle j= 1,1,1
16                                    if AMAX ≥ A(j) then -> 2
17                                    AMAX= A(j) ; jMAX=j
18                                  2:   repeat
19                               A(jMAX)=A(i)
20                               A(i)=AMAX
21                               repeat
22                            3: cycle i=1,1,p
23                               newline
24                               print(A(i),5,0)
25                               repeat
26                               end
27                          newline
28                          newline
29                          -> 1
30                          end of program

62.

64.

Notes       (1)  A routine description has the same structure as a
block except that begin is replaced by routine followed by its name.

            (2)  In the routine description given above, x and y are
global variables.

            (3)  The first line of the description is always the same
as the declaration, but with spec omitted.

            (4)  A routine may be called in any block interior to the
one in which it is declared (and described).  In this way we can think
of local and global routines, in just the same way as local and global
variables.

            (5)  A routine call is an instruction and may be made
conditional:
            e.g. if p ≠ 10 then interchange

            (6)  Normally, instructions in the routine are obeyed in
sequence until reaching end.  If it is desired to stop the routine at
some other point, the instruction return may be used.  This is
equivalent to a jump to end and hence cannot be used in an inner block
of the routine, return may be made conditonal.

Example  Interchange x and y and square them if they are both positive.
            routine interchange and square
            integer z
            z = x; x = y; y = z
            if x≤0 or y≤0 then return
            x = x*x; y = y*y
            end

Note  A second return could be written immediately before end, but would
be redundant.

65.

STRUCTURE OF BLOCKS CONTAINING ROUTINES

     Routine descriptions are placed at the end of the block in which
they are declared.  The general structure of a block can now be
extended to :-

     begin 

        integer ......                      )
        real..........                      ) declarations, including
        routine spec interchange            ) declarations of routines.
        routine spec .......                )

        ...........                         ) instructions including
        interchange                         ) routine calls.
        ...........                         )

        routine interchange         )       )
        ........                    )       )
        end                         )       ) routine descriptions, each
                                            ) having a block-like
        routine ......              )       ) stucture of its own.
        ........                    )       )
        end                         )       )

     end

66.

ROUTINES WITH PARAMETERS

     The previously described routine 'interchange' will exchange the
values of x and y, but will be of no use if we wish to interchange any
other pair of variables.

     In Atlas Autocode, to facilitate the use of the same routine in
different contexts within a program, the user is permitted to write the
routine using formal (or dummy) names for some or all of the variables
global to it.  In each call of the routine, these formal names are replaced
by the appropriate actual names.

     If formal names are used in the writing of a routine, then the
following modifications must be made to the procedures for declaring,
describing, and calling the routine.

(a)  In declaring and in describing the routine its name must be
followed by a bracketed list of the formal parameters used, together with
a statement of their type.

(b)  In calling the routine the name must be followed by a bracketed list
of the actual parameters which are to replace the formal parameters
on this occasion.
     The designation 'parameter' has been used above in anticipation of
facilities which permit quantities other than names (for example elements
of arrays and arithmetic expressions) to be passed on to routines.

Example 1
        integer a,b,i
        integer array A(1:10)
        routine spec interchange (integer name x,y)      Declaration
        .............
        .............
        interchange (a,b)                                Call 1
        cycle i = 1,1,9
        interchange (A(i) , A(10))                       Call 2
        repeat
        ............. 
        routine interchange (integer name x,y)           Description
        integer z
        z = x;  x = y; y = z

        end

68.

     The parameter types real name and real are used in a similar manner.
The actual parameter corresponding to the parameter type real name must
have been declared as a real variable or as an element of an array.  The
actual parameter corresponding to the parameter type real may be a general
(i.e. integer or real) arithmetic expression.
     Parameters of type integer name and real name are said to be CALLED
BY NAME.
     Parameters of type integer or real are said to be CAIXRD BY VALUE.
     In Atlas Autocode parameters called by name are completely
determined by the actual values of all relevant quantities (including
global variables) of the time of call.  For example it may happen that a
routine with a parameter list containing say
        .........(real name x, integer name i, .......)
is called with the actual parameters
        .........(A(j), j, ..........)
where A is the name of a previously declared real array.  If the value of
j at the time of the call is, say, 10 then in the execution of the routine
the formal parameter x is replaced everywhere by A(10) no matter how
j varies.
     The reader is warned that the alternative convention ( whereby, in the
above example, the array element replacing x would be determined by the
current value of j during the execution of the routine) is used in some
other programming languages ( e.g. Algol).

PASSING ON ARRAYS TO ROUTINES
     A parameter of type real array name or integer array name is used in the
same manner as those of type real name and integer name. We can describe a
routine in terms of elements of an array with a formal (or dummy) name. In
each call, we give the actual name of the array which is to be used in
place of the dummy array on that particular occasion.
Example  The following routine will double the first 10 elements of any
one-suffix array (provided it starts with suffix 1 and has at least 10
elements).
        routine double (real array name X)
        integer i
        cycle i = 1,1,10
        X(i) = 2X(i)
        repeat
        end
     The routine is called by instructions such as:-
        double (A)
        double (B)
which will double A(1), A(2).....A(10) and B(1) .......B(10).
Note  The routine and the two arrays would, of course, have been previously
declared in the usual manner.

69.

Example  In the next example it is assumed that a number of square arrays
have been declared and a routine is required to print out certain sums
of consecutive diagonal elements such as A(5,5) + A(6,6) + ... +A(10,10).

            routine trace (real array name X, integer m,n).
            integer i
            real z
            z = 0
            cycle i = m,1,n
            z = z + X(i,i) 
            repeat
            newline
            print (z,5,5)
            end

and instructions to call this routine might be

            trace (A,5,10)
            trace (B,1,50)

Note  On all the Atlas Autocode compilers, there are four types of
parameters called by NAME:-

            integer name
            real name
            integer array name
            real array name

and two by value:-

            integer
            real

     On the Manchester COMPILER AA only, there are two extra types called
by value:-

            integer array
            real array

     For further details, see the appropriate reference manual.  These
'array by value' facilities should be used with caution, not only
because of incompatability with other compilers, but also because they
can use large amounts of storage space and because of the time taken to
copy all the elements of a large array.

72.

begin
comment to order lists of positive integers
integer p
1: read(p)
if p≤0 then stop
       begin 
       integer  i,j
       integer array A(1:p)
       integer fn spec MAX(integer array name V, integer k)
       routine spec interchange (integer name a,b)
       cycle i = 1,1,p
       read (A(i))
       repeat
       -> 2 if p = 1
       cycle i = p,-1,2
       j = MAX(A,i)
       interchange (A(j), A(i))
       repeat
    2: cycle i = 1,1,p
       newline ; print (A(i),5,0)
       repeat

       integer fn MAX(integer array name V, integer k)
       integer p,q,r
       r = 0
       cycle p = 1,1,k
       if r ≥ V(p) then -> 1
       r = V(P) ; q = p
    1: repeat
       result = q
       end

       routine interchange (integer name a,b)
       integer z
       z=a ; a=b ; b=z
       end

       end ; comment end of inner block
newlines (2) ; -> 1

end of program

74.

76.

begin 
integer i
real fn spec TRAP SUM(real x1,x2, integer n, real fn f)
real fn spec circle(real x)

cycle i=10,10,50
newline
print(i,2,0); spaces(2)
print(TRAP SUM(0,1,i,circle),1,9)
repeat
     real fn TRAP SUM(real x1,x2, integer n, real fn f)
     real fn spec f(real y)
     real h,SUM
     integer i
     h=(x2-x1)/n; SUM=f(x1)
     cycle i=1,1,n-1
     SUM=SUM+2f(x1+i*h)
     repeat
     SUM=SUM+f(x2)
     result =h*SUM/2
     end

     real fn circle(real x)
     result =sq rt(1-x²)
     end
end of program


notes   (1)  The print-out	from the program was:-

               10   0.776129582
               20   0.782116220
               30   0.783610789
               40   0.784236934
               50   0.784567128

                     (slowly approaching the true value of 0.785398163).

         (2)   The formal function parameter f is declared a second
time on line 2 of routine TRAPSUM.  This serves not as a declaration of
the name (this is made on the line above) but of the parameter list.


REMARK

     There are certain difficulties in the use of functions and routines
as parameters in all the existing compilers.  The user should consult
the appropriate reference manuals for further details.

79.

A possible description of this routine is:-


          routine real, quicksort(real array name X, integer a,b)
          comment sorts elements of real array X from X(a) to X(b)
          integer l,u
          real d

          return if a ≥ b

          l=a ; u=b                   ; | set pointers
          d=X(u)                      ; | dump partition bound
          -> 2

1:        l=l+1                       ; | this section moves
          -> 4 if l= u                ; | l forward until
2:        -> 1 unless X(1) > d        ; | we find a member > d
          X(u) = X(l)

3:        u=u-1                       ; | this section moves
          -> 4 if l = u               ; | u back until we
          -> 3 unless X(u)<d          ; | find a member < d
          X(l)=X(u)
          -> 1

4:        X(u)=d                      ; | partitioning complete

          real quicksort(X,a,l-1)     ; | sort from X(a) to X(l-1)
          real quicksort(X,u+1,b)     ; | sort from X(u+1) to X(b)
          end


Note   Although, as we have seen, our first example of recursion can
equally easily be written using a cycle, this is not true of quicksort.

80.


Example  The game of HANOI.

     This is another example where recursion greatly simplifies the
writing of a program.
     In this game one is given three pegs, and on one of these pegs
are a number of circular discs of different sizes, graded so that the
largest is at the bottom and the smallest at the top.  The aim of the
game is to transfer the discs to one of the other pegs (making use of
the third as required) in such a way that there is never a larger disc
on a smaller one.  Only one disc at a time may be moved.
     If the solution to the game for (n-1) discs is known, then the
solution for n can readily be obtained.  Let the pegs be numbered
1, 2 and 3, and let it be required that the n discs on 1 be transferred
to 3.  This can be done by transferring the first (n-1) to 2, the last
to 3, and then the first (n-1) from 2 to 3.  In the following program
n is the number of discs which have to be moved from peg i to peg j.

PROGRAM FOR GAME OF HANOI

          begin 
          integer n,i,j
          routine spec hanoi (integer m,p,q)
          read (n,i,j)
          hanoi (n,i,j)

            routine hanoi (integer m,p,q)
            if m=0 then return
            hanoi (m-1,p,6-p-q)   ; | if p,q are two pegs, other is 6-p-q
            newline
            print (p,1,0); caption s -> s ; print (q,1,0)
            hanoi (m-1,6-p-q,q)
            end

          end of program

    The output for the case n=2,i=1,j=3 is:-

1 -> 2
1 -> 3
2 -> 3

81.

STORE MAPPING FUNCTIONS

     The store mapping function provides the user with the possibility
of renaming storage locations which have previously been named by a
declaration of type real array or integer array.  The method of use of
a mapping function is almost identical to that of a function.  For
example it is declared either by real map spec or integer map spec
depending on the nature of the variables to be renamed.
     Like integer and real functions, mapping functions can appear in
arithmetic expression.  However as the result of the store map is a
variable, it can also be written on the left hand side of an assignment.
Example 

                  real x
                  real map spec W(integer i,j)
                  ..............
                  X = W(2,3)
                  W(1,2) = 1 + x ↑ 3
                  ..............

Note  This illustrates the use of the store map both on the left and
on the right hand sides of an assignment.

     The description of the store mapping function has the form
                  real map W(integer i,j,.....)
                  result = addr (A(integer expression, integer expression,..))
                  end

Notes  (1)  A is the name of the array to be renamed.
       (2)  Here it is assumed that A is global to the description of the
            mapping function.  However A could have been included in the
            function heading as a formal parameter of type array name.
       (3)  There is no restriction on the number of suffices that can be
            associated with either A or W.
       (4)  The integer expressions that determine the values of the
            suffices of the array A can be general integer expressions
            involving the formal parameters i,j,.....   .

Example
                  real array A(1:1000)
                  real map spec W(integer i)
                  .............
                  real map  W(integer i)
                  result = addr (A (i*i))
                  end

82.


Note  In the example W(i) and A(i*i) are equivalent.  For example W(10)
and A(100) are both valid titles for the same storage location.

     Store maps have the great advantage that they permit economical
use of storage on a computer.  For example if a two dimensional array is
symmetric (so that X(i,j) = X(j,i)) then it is completely specified by
the values X(i,j) with i ≥ j.  It is therefore necessary to store only
this (lower) triangular array with a saving in storage space of nearly
50 per cent.  An appropriate description of the mapping function might
be

            real map X (integer i, j)
            result = addr (A(i*(i - 1)/2 + j)) if i ≥ j
            result = addr (A(j*(j - 1)/2 + i))
            end

Note  The saving in storage space gained by using mapping functions is
obtained by sacrificing speed in the execution of the compiled program.
For this reason mapping functions are not recommended for general use.

84.

89.

LIBRARY ROUTINES
     Routines to carry out many of the standard computational processes
have been written in Atlas Autocode.  Using these within one's own
program saves considerable programming effort. The reader should obtain
details from his Computer Unit.

EFFICIENCY
     We give below some suggestions which may assist the reader to
write his programs in a form which will make efficient use of machine
time.  He should, however, keep a sense of proportion, remembering that
his own time is also valuable and that the first objective should be to
make his program work successfully.

(1).     The parts of a program in which efficiency is important are
those which are executed many times.  For example, any minor improvement
made in the area (A) below will cause a saving on each of the 10,000
times this section is executed.

                        cycle i=1,10,100
                        cycle j=1,10,100
                        ................           )
                        ................           )   (A)
                        ................           )
                        repeat
                        repeat
(2).     Division takes longer than multiplication, so that 0.1*x
is computed more quickly than x/10.

(3).     Whenever some part of an expression is required many
times, it should be evaluated once and stored, as in the right-hand
version below.
                                                  d=x*π/180
                    cycle i=1,1,100               cycle i=1,1,100
                    A(i)=A(i)*x*π/180             A(i)=A(i)*d
                    repeat                        repeat

(4).     It takes longer to move numbers in and out of array elements
than simple variables.  Again, the right-hand version below is the
more efficient.

                    X(i,j)=0                      d=0
                    cycle k=1,1,15                cycle k=1,1,15
                    X(i,j)=X(i,j) + Y(k)          d=d +Y(k)
                    repeat                        repeat
                                                  X(i,j)=d

90.

(5).     It is far quicker to calculate numbers inside the
machine than to read data in or print answers out.  Given some
reading taken during an experiment every 1/10 sec

                    time                      reading
                    12.0                      2.137
                    12.1                      3.657
                    12.2                      6.678
                    .....                     .....
                    .....                     .....
                    .....                     .....
                    59.9                      7.547
                    60.0                      2.652

it is wasteful to read in the left-hand column at all.  We can
read the first and last times (12.0 and 60.0), together with the
interval (0,1) and compute the intervening times.
     Similarly, output should be reduced to the minimum that
the programmer really wishes to read.  Apart from the saving  of
machine time and money, the computer can disregard all
uninteresting results (which have to be adequately defined) far
more quickly than we can tear up unwanted sheets of paper and
assign them to the waste paper basket.

(6).     When available, a Line Printer is a more efficient
method of output than punched paper tape.  With the Line Printer,
answers should be printed right across the page, as the cost is
proportional to the number of lines printed. (A line of output is
limited to 120 characters).

(7).     When fault finding, use 'query printing' with discretion.
Query printing within program loops is a common cause of large
quantities of output which are never read.

CHECKING OF PROGRAMS
     The need for checking of programs cannot be overemphasised.
A check sheet to assist the reader to avoid-some of-the more common
errors is given on the next page.

91.
                          PROGRAM CHECK SHEET

1.     General details  Are all the special words of the language
          correctly underlined ?

2.     Have I a corresponding number of
            (a)  begin / end         (also routine..../ end, etc)  ?
            (b)  cycle / repeat      (and at corresponding levels)  ?

3.     Declarations  (a)  Have I used the same name before at this level ?
                     (b)  Have I got my commas and colons correctly
            written in my array declarations ?
                     (c)  Have I assigned values to the variables used
            in the calculation of array bounds ?

4.     Names    Have they been declared (at an appropriate level) ?

5.     Labels   Have they been used before at this level ?

6.     Jump instructions    Has the label been set at this level ?  If a
         switch label, has it also been declared (at this level) ?

7.     Expressions    (a)  Do left and right brackets correspond ?
                      (b)  Have I any real quantities or functions being
         assigned to integer variables or used as an exponent ?
                      (c)  Can the expression got too large at any
         intermediate stage or in the final value ?

8.     Array elements   Are the suffices all integer expressions, and
         CAN THEY EVER TAKE VALUES OUTSIDE THE DECLARED BOUNDS ?

9.     Cycles   (a)  Is the control variable an integer ?
                (b) Are the 3 expressions all integer expressions ?
                (c) Is expr(3)-expr(1) a non-negative multiple of expr(2) ?

10.    Routine and function calls   Has the routine/function been
         declared and described at an appropriate level, and are the
         actual parameters of legitimate type and correct in number ?

11.    Functions   Have I given a result ?

12.    Division    (a)  Am I sure the denominator can never be zero or
         dangerously close to zero ?
                   (b)  In integer expressions on KDF 9, will all
         intermediate results be integral ?

13.    Square Roots  Can the argument ever be negative  ?

14.    Logarithms   Can the argument ever be negative or dangerously small ?

15.    Stopping     Have I arranged for the program to stop ?

16.    General      (a)  Have I supplied a valid Job Heading ?
                    (b)  Have I supplied data, and the right amount ?

92.