Text preview for : PL516.pdf part of honeywell PL516 honeywell series16 software PL516.pdf
Back to : PL516.pdf | Home
PL516, An Algol-like assembly language for the DDP-516
B A Wichmann,
National Physical Laboratory
Teddington, Middlesex
January 19, 1999
Abstract
This report gives details of a high-level assembly language for a small 16-bit machine. The language
is based upon the work of N. Wirth on PL360.
The report is intended as a user's manual, a description of the Algol-like assembler for those not
familiar with the idea, and as a compiler-writer's guide to the system.
Contents
1 Introduction 2
2 What is an Algol-like assembly language 2
3 The DDP-516 3
4 The language 5
4.1 The syntax notation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
4.2 The language elements : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
4.2.1 Expressions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
4.2.2 Arrays and subscripting : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9
4.2.3 Conditions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
4.2.4 Constants : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
4.2.5 Assignment statement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16
4.2.6 Statements using conditions : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17
4.2.7 Loop control : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21
4.2.8 Goto statements : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24
4.2.9 Procedure calls : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25
4.2.10 Statements : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27
4.2.11 Code statement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29
4.2.12 Declarations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31
4.2.13 Program and procedures : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35
4.2.14 Identifiers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35
5 Further examples and programming advice 36
5.1 Condition test: a simple example : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36
5.2 A simple sort program and some input/output routines : : : : : : : : : : : : : : : : : : : 39
5.3 Positioning code in the core : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 40
5.4 A desk calculator program : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
5.5 A string editor : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
5.6 Array handling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
5.7 Program segmentation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
1
5.8 Use of code statements : : : :::::::::::::::::::::::::::::::: 42
5.9 Program checking : : : : : :::::::::::::::::::::::::::::::: 42
5.10 Good programming practice :::::::::::::::::::::::::::::::: 43
6 A program testing system 43
7 Structure of the compiler 44
7.1 The basic compiler routines : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44
7.2 The compiler tables : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44
7.3 Some syntactic routines : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 45
7.4 Some statistics on the compiler : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48
8 Comments on machine design 49
A Hardware representation 50
B Failure numbers 50
C Limitations and restrictions 50
1 Introduction
The language described in this report is based upon PL360 by N. Wirth [1]. As far as the hardware allows,
the language follows the same conventions as PL360. The short address length is exploited by using the first
sector of the machine in a similar way to the Program Reference Table of the B5500 (as will be explained
in more detail later).
This report is an attempt to combine (a) a manual for users (b) a description of an Algol-like assembler
for other interested parties, and (c) a compiler-writer's description of the language and compiler to assist
in future enhancements to the system. Clearly three reports should have been written but the author hopes
that this will be adequate.
It must be emphasized that this language is no substitute for Fortran or Algol 60, but rather a more
convenient and flexible system for writing large machine-code programs. The main advantage over DAP,
the assembler for the DDP-516, is that program texts are largely self-documenting due to their Algol-like
structure.
The author would like to thank all those who have contributed to the design and implementation of the
system, namely Miss Elizabeth Giles for preparing the compiler text, to D.A. Bell who wrote the compiler
in its own language and to G. Alway, F.G.Duncan, R. Scowen, P. Wilkinson and M. Woodger all of whom
made many suggestions and criticisms on the basis of the author's rough notes.
The work described in this paper was carried out as part of the research work of the National Physical
Laboratory.
2 What is an Algol-like assembly language
The basic idea of PL516 is to provide a facility for writing machine-code which makes the program text
look superficially like Algol. This can be done by separating the features of Algol 60 into two classes.
Firstly those which require no subroutines to implement them in the running program. These can be
implemented in PL516. For instance, identifiers for naming locations in store. Six characters are significant
in this compiler and additional characters can be added although they are ignored. This gives substantially
greater flexibility over DAP which only allows up to four characters in an identifier.
Secondly are those features which require subroutines in the program because the machine cannot
implement the feature in a straightforward manner. Dynamic storage allocation is such a facility. If the
machine had hardware for storage allocation like the B5500 then this would be a feature of the assembler.
Since there are no hardware facilities for floating point on the PPD-516, this language uses integers only.
2
Hence the following table can be constructed:
PL516 contains: identifiers, type-checking, scope to identifiers, procedures, compound statements, con-
ditional statements, simple for loops.
PL516 does not contain: dynamic storage allocation, multi-dimensional arrays, more than one parameter
to procedures, call by name, expressions involving temporary working store, real variables.
In addition to the Algol-like facilities of the assembler, one can write ordinary machine code (for
communicating with peripherals, for instance), refer to constants by identifiers to improve the legibility of
the program, and initialise the values of an array (possible because fixed storage is used).
Numerous examples of procedures and programs are given throughout this report and a glance at these
will illustrate many of the points made above. Those who prefer to learn by examples may like to start at
section 5.
3 The DDP-516
The assembler is, of course, a machine-dependent language. So to describe how the language is implemented
it is necessary to understand the addressing mechanism and instruction code. This is given in detail in [2, 3]
but this section is added to make the report as complete as possible.
The DDP-516 is a 16-bit machine with two main registers. The first register, called the A register, is the
main accumulator of the machine. The second is the X register which is the index register. The X register
is also word 0 of the machine.
There are four classes of instructions as follows:
Generic instructions. These addressless instructions usually operate on the contents of the accumulator.
An example is TCA (Twos Complement Accumulator) which negates A as a 16-bit signed integer.
In referring to machine instructions in this report, the DAP conventions will be used (see [3]).
Shift instructions. These instructions have a six-bit field giving the two's complement of the shift required.
Double length shifting can be done using the B register. The B register is not directly accessible
by instructions and so will not be mentioned very much in this brief account. Twelve shift orders
are available in total from all possible combinations of left, right, logical and cyclic and arithmetic,
single and double length.
Input-output instructions. These instructions have a 10-bit address field divided between the device
function code and the device address.
Memory reference instructions. (for DXA mode machines having 16K only). These instructions are
very important since they determine the addressing structure of the machine. The operation code
is 4-bits giving a basic repertoire of instructions for adding, subtracting etc, the accumulator to the
word accessed. The remaining 12 bits of the instruction are divided into 3 one-bit flags and a 9-bit
address. One flag is the `this sector bit'. If this is set, then the full 14 bit address is formed by taking
the most significant five bits from the current instruction address. This means that the machine is
sectored into blocks of 512 words so that one can either address the sector one's instructions are in
or sector 0, the first sector of the machine.
The other two flag bits are the `indirect' bit and the `index' bit which, together with the 14 bit address,
gives one machine word. If the `index' bit is set then the current contents of the X register are added
to the 14 bit address constructed from the instruction. After this, the indirect bit is inspected. If it is
not set then the address of the operand has now been calculated. If the indirect bit is set, then the 14
bit address is used to load a 16 bit word which is interpreted as an address with indirect and index
bits. This process of indirection can be carried to arbitrary depth. To illustrate this, consider three
examples:
3
1. One of the memory reference instructions is a jump order JMP. Ordinarily in the assembler
jumps are within the current sector and so a direct jump can be made. However, jumps to labels
not in the current sector can be done by putting in sector 0 the 14 bit address of the label. Then
the jump is an indirect jump i.e, with the indirect bit set in the instruction. The instruction
points to the word in sector 0. This word in sector 0 does not have the indirect bit set (nor index
bit) so the jump is effected to the 14 bit address given by this word.
This can be represented diagrammatically thus:
JMP 'indirect' ->
| | |........ word in sector 0
->
........ location of label anywhere in store
2. One of the memory reference instructions loads the accumulator (LDA). How does one use the
addressing to load the ith element of an array b into the accumulator? For each array in the
assembler there is an `array word' which has the 14 bit address of the zero-th element of the
array together with the index bit set. To load b[i] we do:
LDX I which loads the index register
LDA 'indirect' ->
| |*|........ 'array word' with index bit set in
current sector or sector 0
->
........ b[0]
I
........ b[i] anywhere in store.
In the assembler the array word is always directly addressable from the instruction and so is
either in the current sector or in sector 0.
3. The third example illustrates how the addressing is used to implement switches. Switches are
simpler than in Algol 60 in that each switch element is a label. The `switch word' s has both
the index and the indirect bit set, so diagrammatically this is:
LDX I which loads X register as with arrays
JMP 'indirect' ->
|*|*|........ 'array word' in
current sector or sector 0
->
........ s[0]
I
| | |........ s[i] address of ith label
-> label corresponding to ith
element of switch
So one level of indirection plus one level with both indirection and indexing is used to do the
required jump.
Control instructions. Apart from the unconditional jump other orders exist to transfer program control.
Generic control instructions. Instructions in this category see if a particular condition is true. If it
is, the next instruction is skipped over. So it is usual to place unconditional jumps after such
instructions, the jump being to code which deals with the case where the condition is false. An
example of such an instruction is SPL which skips the next instruction if the accumulator is
positive. Hence the instructions SPL followed by TCA takes the absolute value of the contents
of the accumulator.
Subroutine jump instruction. This instruction, JST, is a memory reference instruction and so the
address is calculated in the way described above. In this address is placed one more than the
address of the JST instruction itself. Control then passes to the next word in the computer store.
4
In the assembled code of PL516 the addresses of procedures are kept in sector 0, and so one
has diagrammatically:
JST 'indirect' ->
| | |........ address word of procedure in sector 0
->
| | |........ return address planted here
.............
............. code of procedure
JMP 'indirect' to return address above
As illustrated, the return is done by doing an indirect jump to the return address which is planted
by the JST instruction.
Note that code cannot be pure on this machine since the return addresses must be stored with
the code.
Increment in store instruction. This instruction IRS, is also a memory reference instruction. the
operand is incremented by one in the store without affecting the accumulator. If the result of
this incrementing is to give zero, then the next instruction is skipped. Frequently one knows
from the logic of the program that the result can never be zero so no jump order or special
coding is placed after the IRS (beware!). The instruction is very useful for loop control, but the
counting goes from ,n; :: , 1. The jump after the IRS returns control to the beginning of the
loop.
The compare instruction. The last instruction CAS is also a memory reference instruction which
does not alter the accumulator. It is a control instruction for comparing the accumulator with
the operand. If the accumulator > operand the next instruction is executed, with equality
one instruction is skipped and with accumulator < operand two instructions are skipped. By
inserting appropriate jump instructions after the CAS all various inequalities can be tested for.
4 The language
PL516 will be described in a manner similar to the Algol 60 report [4]. Each feature of the language is given
by a formal syntactic description using a variant of the Backus-Naur notation. For those not familiar with
this, a verbal explanation is also given as well as many examples. The semantics are given by explaining
the code generated by the compiler. This is given in DAP, so the reader is referred to [2, 3] or Section 3 of
this report for a shorter account.
4.1 The syntax notation
The notation used is the Backus-Naur form with a number of additions to shorten the description introduced
by F.G. Duncan [5]. The cross-reference technique of Coulouris [6] is also used.
The first addition is to abbreviate the fact that a symbol may or may not occur. For instance
a ::= b c
means
a ::= c j b c
That is an a is a c , or a b followed by a c .
To assist in searching for the appropriate syntax rule, these rules are all numbered and each reference
to a rule is preceded by the number. Hence the rule above might be
1 :3 a ::= f 1:2b g 4:8c
Symbols of the language itself are written in bold or the symbol itself like the Algol 60 Report. A
complete list of the symbols is given in Appendix A. Syntax rule n:r is to be found in section 4.2.n.
5
Another addition to the syntax notation is to deal with repetitions a
1 means one or more a 's.
Similarly a 0 means zero or more a 's.
The last addition is to deal with lists in a compact manner.
a list b means a b a . Usually
0 b is a separator such as a comma
or semicolon.
4.2 The language elements
4.2.1 Expressions
The purpose of expressions is to do some calculation from values already stored without using temporary
working store. All the calculation is done in the accumulator alone.
1:0expression ::= 1:3unary operator 1:1term
0
1:4binary operator 1:2cell
j 1:5shift operator 4:0constant 0
This means that an expression is any number of unary operators followed by a term followed by any
number of either a binary operator followed by a cell or a shift operator followed by a constant. The
evaluation of the expression is done by first evaluating the term, then applying the unary operators in the
reverse order to the appearance in the text, then applying the binary or shift operators in the order left to
right. Detailed examples are given later when the other terms have been defined.
1:1term ::= accumulator j
1:2cell j
1:0expression j
9:0procedure call j
zero j
codeword 11:5type identifier j
if 3:0condition then 1:0expression else 1:0expression
The purpose of term is to do the initial loading operation on the accumulator before the operators are
applied to it. This load operation is omitted in the case where the accumulator symbol is read. By this
means the current contents of the accumulator can be used in an expression (but only by explicitly stating
this). When the symbol zero is written, then the instruction CRA (CleaR Accumulator) is generated. The
possibility of nesting expressions by means of brackets means that quite complex expressions can be done
although no temporary working store is used.
1:2cell ::= 14:1integer identifier j
ind 14:1integer identifier j
14:3array identifier 2:0subscript j
4:0constant
All variables in this language are 16-bit integers. A cell is such an integer addressed in one of four ways.
Firstly, the integer may be declared as a simple integer and given an identifier, say i1 or int2. Secondly
the simple integer `addi' may contain the address of the integer required. In this case access must be made
with the indirect bit set in the instruction (see page 3). The case of arrays is dealt with when describing
subscripts. The last case is an explicit constant which is given a location by the compiler as necessary and
accessed directly like an ordinary integer.
1:3unary operator ::= addc j inc j neg j
setsignplus j setsignminus j not j
changesign j copysignandsetplus j icleft j
cleft j swop j icright j
abs j abug
These operators act upon the current contents of the accumulator. Except for the last two, they are
single generic instructions. The corresponding DAP instructions are:
addc ACA add the C register (a 1 bit overflow register and shift indicator) to the A register (ie, the
accumulator)
6
inc AOA add one to the A register
neg TCA negate the constants of the A register
setsignplus SSP clears the sign bit of the accumulator leaving the other bits unchanged
setsignminus SSM sets the sign bit of the accumulator leaving the other bits unchanged
not CMA all the bits in the A register are changed
changesign CHS change the sign bit of the A register leaving the other bits unchanged
copysignandsetplus CSA the sign bit of A is put into the C register, and the sign bit is cleared
icleft ICL This instruction is for manipulating the A register regarded as two 8 bit characters. The most
significant character is moved to the bottom of the A register and the top of the register cleared.
Instruction stands for Interchange and Clear Left, ie x; y ! 0; y
cleft ICA Interchange the two characters in the A register ie x; y ! y; x
swop CAR Clear the least significant character in the A register ie x; y ! x; 0
icright ICR The least significant character is moved up in the A register and the bottom of the A register
cleared, ie x; y ! y; 0
The penultimate operator is slightly different in that two instructions are generated namely:
abs SPL TCA. This gives the absolute value of the A register (see page 4).
abug is a compiler controlled diagnostic facility. When the appropriate compiling options are set the
instruction JST *'776 is generated, otherwise no code is output. The compiling options are explained in
the programming notes for the version of the compiler in use.
1:2term ::= + j , j and j
nev j j = j mod
It has been pointed out in 1:0expression that `term' caused the accumulator to be loaded, after
which the unary operators are applied. At this stage the binary operators can be invoked. The instructions
to do this are as follows:
+ ADD operand
- SUB operand
and ANA operand
nev ERA operand
The last three are somewhat different since more than one instruction is generated:
* MPY operand LLS 15 (long left shift 15 places)
/ LRS 15 (long right shift 15 places) DIV operand
mod LRS 15 (long right shift 15 places) DIV operand IAB (interchange A and B registers)
These instructions are the ones produced by the current version of the compiler. Since MPY and DIV
are not available on some machines, they must be replaced by a subroutine call or otherwise removed
altogether. The compiler itself does not use these instructions.
Some realistic examples of expressions can now be given.
1. abs a + b
This will generate the machine code:
7
LDA A since a is the term
SPL after the unary operators are
TCA applied, two instructions for abs
2. not (a + b) and c
The term (a+b) must be evaluated first, this gives:
LDA A form the term a
ADD B from the binary operator + and cell b
CMA from the unary operator not
ANA C from the binary operator and cell c
3. The same expression as above with the brackets missing: not a + b and c
LDA A
CMA
ADD B
ANA C
In other words, the brackets in expressions determine the positioning of the unary operators. Unlike
Algol 60 or Fortran all operators have the same priority.
4. For example: a + b * c
generates the code:
LDA A
ADD B
MPY C
LLS 15
since the binary operators are applied in the order left to right. No priority can be given to operators
as can be seen from this example. This is because once `a' has been loaded into the accumulator
there is no way of multiplying b and c. Temporary storage would have to be used to preserve the
contents of the accumulator but this is excluded.
5. accumulator + b * c
Here the current constants of the accumulator is being referred to so no load operation is done, so the
code generated is
ADD B
SUB C
6. not setsignminus zero
Instead of a load operation zero clears the accumulator so we have
CRA
SSM from setsignminus
CMA from not
Note that the unary operators are applied in the order right to left. The effect of this is to leave in the
accumulator the largest positive integer (zero sign bit, the rest all 1's).
7. neg (abs (not a + indb)/c) mod d
Just to illustrate how complex expressions can be. The code generated is
8
LDA A since the innermost term is evaluated first
CMA from the not
ADD* B * means set the indirect bit in instruction
SPL
TCA now abs (two instructions)
LRS 15
DIV C the /c completes the outermost term
TCA so now apply neg
LRS 15
DIV D
IAB finally the mod d
Expressions involving constants, arrays, procedure calls, conditions and type identifiers will be illus-
trated when the appropriate syntax has been described.
1:5shift operator ::= singlerightlogical j singleleftlogical j
singlerightarithmetic j singleleftarithmetic j
singlerightcyclic j singleleftcyclic j
doublerightlogical j doubleleftlogical j
doublerightarithmetic j doubleleftarithmetic j
doublerightcyclic j doubleleftcyclic j
The number following the shift operator is two's complemented and truncated to 6 bits and then placed
in the appropriate instruction. It is only possible to shift by a constant amount, since the amount is placed
in the instruction by the compiler.
The above operators generate the shift instruction (in the order above): LGR, LGL, ARS, ALS, ARR,
ALR, LRL, LLL, LRS, LLS, LLR and LLR. The double length shifts regard the B register as an extension
to the bottom of the A register.
The hardware representation of the shifts (see Appendix A) uses five characters to increase program
legibility.
4.2.2 Arrays and subscripting
One dimensional arrays of integers are part of the assembly language. Because of the fixed storage lay-out,
the size of the array must be given to the compiler. Array elements are accessed in the manner described
on page 4.
The syntax of the subscripting mechanism is:
2:0subscript ::= 14:1integer identifier j
4:0constant j
xsymbol
The purpose of the subscript is the load the X register, so that the appropriate element of the array can
be accessed. In the first case the integer is loaded into the register, in the second case the constant is loaded.
In the final case no LDX instruction is generated. This is used if the X register already contains the
required value. It will be noted that complex subscript expressions are not allowed. This is a consequence
of the fact that no arithmetic operations can be performed in the X register itself. When more complex
expressions are required, the relevant calculation must be done in the accumulator and the result assigned
to word 0 of the machine (which is the X register). This will be explained in section 4.5.2.
Some examples of expressions involving array accessing can now be given.
1. ar1[i] + ar[j] - ar[k]
Each subscript gives a LDX operation so the code for this is
LDX I
LDA* AR1
LDX J
ADD* AR
LDX K
SUB* AR
9
Note the indirect addressing via the array word in all the instructions accessing the array elements.
2. not(ar[i] and ar1[xsymbol]
The first subscript loads the X register with i so that the second array element accessed is ar1[i]. The
code generated is:
LDX I
LDA* AR
ANA* AR1
CMA
3. negabs(ar[i] * ar1[xsymbol]) / ar2[j]
This generates the code:
LDX I
LDA* AR which loads the first array element
MPY* AR1
LLS 15 multiplying by the second array element
SPL
TCA from abs
TCA from neg
LDX J
LRS 15 note the LDX operation is performed before any of
DIV* AR2 the divide operation
4.2.3 Conditions
There are no boolean variables in PL516. Apart from ordinary jump instructions control is effected by
means of conditions. This is done by making use of the test orders which skip one instruction if the
condition is true. The instruction which may be skipped over is a jump to the code which deals with the
case when the condition is false. This jump order is generated automatically by the compiler and in the
examples which follow is written as JMP false.
3:0condition ::= 1:0expression 3:3relational operator 1:2cell j
1:0expression 3:2accumulator condition j
9:1conditional procedure call j
3:1condition operator
The first type of condition uses the CAS instruction (see page pagerefsec354) to compare the current
contents of the accumulator (set by expression) with the word in store determined by cell.
The second case is where the expression sets the accumulator and is tested by a single instruction.
Thirdly, a procedure can be a conditional procedure. In this case the procedure may return control in
the ordinary position if the condition is false, or one instruction further on if the condition is true. This will
be explained in more detail when procedure calls are dealt with in section 4.2.9.
The last case is the simplest, the syntax of which is:
3:1conditional operator ::= sense1 j sense2 j
sense3 j sense4 j
anykey j nokey j
cset j notc
There are four sense keys on the machine, numbered 1 to 4. The instruction SS1 skips the next order if
sense key one is set. So the condition operator sense1 generates the code:
SS1
JMP false
and similarly with sense2, sense3 and sense4. anykey gives SSS, nokey gives SSR, cset gives SSC
and notc gives SRC.
10
The address planted in the JMP false instruction will become clear when examples of conditions in
pieces of program can be given.
3:2accumulator condition ::= zero j plus j
nonzero j odd j
even j minus
In this case, after generating code to evaluate the expression, the single instruction (SZE, SPL, SNZ,
SLN, SMI, respectively) followed by JMP false is generated.
Examples of such conditions are:
1. a + b zero
generates:
LDA A
ADD B from expression
SZE
JMP false
2. Using the convention true = ,1 and false= 0 then one would write the booleans expression bool1
and bool2 as:
bool1 and bool2 nonzero generating:
LDA BOOL1
ANA BOOL2
SNZ
JMP false
3. a + b[i] minus
generates:
LDA A
LDX I
ADD* B from expression
SMI
JMP false
4. zero zero is a valid condition since the first zero is from term and the second an accumulator condition.
The code is:
CRA
SZE
JMP false
Clearly the skip is always performed. Confusion is not likely to arise from the double use of A zero
since the context is clear in practical cases.
3:3relational operator ::= =j6=j j jj
After the evaluation of the expression and generation of a possible LDX if the cell is an array element
the code is:
=
CAS cell address
SKP skips one instruction
SKP
JMP false
11
6
=
CAS cell address
SKP skips one instruction
JMP false
CAS cell address
JMP *+3 this means jump forward three places
NOP dummy instruction
JMP false
CAS cell address
NOP dummy instruction
SKP
JMP false
CAS cell address
JMP false
NOP
The details of these instructions need not, of course, be remembered. The effect of the code is clear,
control passes according to the usual interpretation of the operators leaving the value of the expression in
the accumulator. It is worth remembering that using relational operators generates 3 or 4 instructions, but
has the advantage that the accumulator is compared with a word in store without disturbing the accumulator.
1. accumulator = a generates
CAS A
SKP
SKP
JMP false
Note there is no code from the expression.
2. a + b 6= c[i] generates
LDA A
ADD B from expression
LDX I
CAS* C from c[i]
SKP
JMP false
3. a / b[i] > c[xsymbol] generates
12
LDA A
LDX I
LRS 15
DIV* B
CAS* C
JMP *+3
NOP
JMP false
4. a mod b < c generates
LDA A
LRS 15
DIV B
IAB
CAS C
NOP
JMP false
Some examples can now be given of conditional expressions the syntax of which appeared in
1:1term .
The code generated is:
JMP false -------------------> a
JMP -------------------> b
a <----
b <----
So the effect is that if the expression is true the first expression is evaluated otherwise the second
expression is executed.
1. if xx > yy then xx else yy
Code to give the maximum of xx and yy in the accumulator.
The code generated is:
LDA XX
CAS YY
JMP *+3
NOP
JMP false ----> a
LDA XX
JMP ----> b
LDA YY <---- a
<---- b
2. if a+b=c if d 6= e then f[-6] else g[8] else neg (y+z)
This generates:
LDA A
ADD B
CAS C
SKP
SKP
JMP false -----------> a
13
LDA A
CAS E
SKP
JMP false -----> b
LDX =-6
LDA* F
JMP -----> c
LDX =8 b<-----
LDA* G
JMP c<-------->d
LDA Y a<------------
ADD Z
TCA
d<------
4.2.4 Constants
Facilities for constants in the assembler are somewhat different from Algol 60. There is no `literal' facility
in the instruction set for loading constants into the accumulator. Hence at binary machine-code level there
is no distinction between constants and ordinary integers. In PL516 however, there are three types of
constants. Firstly there are the explicit constants, a string of digits as in Algol 60. Secondly there is a type
of entity called constant. This is like an ordinary integer except that an initial value is given to it and the
assembler checks (as far as possible) that no assignment is made to it. Such constants are referred to by
their identifier. The third type of constant, called a compile constant, is also referred to by an identifier.
This, however, is not given any storage in the running program until it is referred to in a context which
requires that it should be given storage. The significance of this will become clear when examples of the
use of constants in complete programs is given.
The purpose of giving constants identifiers is to improve program legibility and yet preserve the static
nature of the constant in the program text. Explicit constants should be used very rarely since altering
one declaration of a constant is substantially easier than altering several occurences of the explicit constant
appearing throughout the program text.
4:0constant ::= 14:4constant identifier j
14:5compile constant identifier j
4:1number j
charsymbol string character string character j
addressoffindgfindexg 11:5type identifier j
4:0constant ; 4:0constant
4:1number ::= f,g octalsymbol octal sequence j
digit
1
An octal sequence is of course, a sequence of one or more digits excluding 8 and 9. The minus sign
has the usual interpretation, but note that it is not an operator. The unary operator written as - in Algol 60
is neg in PL516 (see 1:3unary operator ). The accumulator can be regarded as two 8 bit characters
so there is a facility to set constants appropriately. A string character is a space or a Teletype 33 graphic
character and so excludes control characters.
Indirect and indexed addressing is ordinarily dealt with for the user through the use of arrays (and the
layout to be explained later). However 16 bit addresses with the index or indirect bits set can be formed by
using the addressof type of constant. The form of the address is given in section 4.2.11.
The form of constant appearing in angle brackets (shown as ; ) is to allow each half of the word
to be set separately by the appropriate constant. In the example given below, -8 is placed in the most
significant 8 bits and octal 70 in the lower 8 bits.
1. Examples of constants
noinputs
692
-84
14
octalsymbol 123
charsymbol AB
<-8, octalsymbol 70 >
2. Examples of constants appearing in expressions
a + octalsymbol 77
generates
LDA A
ADD ='77 ' means octal, the
= means put address of '77 in
the instruction
interrupt singleleftlogical clockpulse
Note in this case `clockpulse' cannot be an integer, since the syntax for expression excludes this. The
code generated is
LDA INTERRUPT
LGL CLOCKPULSE
The two's complement of the value of the constant `clockpulse' is truncated to 6 bits and placed in
the instruction.
3. Constants in conditions
ar[-6] > b[-2]
generates
LDX =-6
LDA* AR
LDX =-2
CAS* B
JMP *+3
NOP
JMP false
Note that negative constants can be out into subscripts because the minus sign is part of the constant.
Assume that there is a compile constant `minus1' declared to have the value -1 then
a + -1 = minus1
would generate
LDA A
ADD =-1
CAS =-1
SKP
SKP
JMP false
Both the CAS and the ADD instruction refer to a word containing -1. Such repeated references to
the same constant use the same word in store. If minus1 was an ordinary constant, however, the CAS
operation would address the word set aside for `minus1' on its declaration.
The distinction between compile constants and ordinary named constants can be ignored initially since
it is of secondary importance. The point is covered in more detail in section 5.
15
4.2.5 Assignment statement
The purpose of assignment statements is that same as in Algol 60, namely to give new values to the variables
listed on the left-hand side of the statement. The syntax is as follows:
5:0assignment statement ::= 5:1lhs list ; 1:0expression
5:1lhs ::= 14:1integer identifier j
findg 14:1integer identifier j
14:3array identifier 2:0subscript j
accumulator
So an assignment statement is one or more `lhs's separated by commas followed by and then the
expression. The code generated is to first evaluate the expression and then to store the contents of the
accumulator to the variables listed in the left-hand side in the order left to right.
Various distinct types of element on the left hand side produce the following code:
integer identifier produces:
STA
ind integer identifier produces:
STA*
array identifier subscript produces:
code for subscript as described in 4.2.2
STA*
accumulator produces no code and so is included if the expression is to be evaluated but no assignment
made.
Some examples:
1. Zeroise a number of elements of an array
ar[i], a[j], a[k] zero
This generates the code
CRA from zero
LDX I
STA* A from a[i]
LDX J
STA* A from a[j]
LDX K
STA* A from a[k]
Note that the order of the assignment is the order the variables appear in the text. This can be
important if xsymbol appears as a subscript, for instance.
2. ar[i], b[xysymbol] c[j] + b[xysymbol]
generates
LDX J
LDA* C
ADD* B from expression
LDX I
STA* A from a[i]
STA* B from b[xsymbol]
Hence the assignment above is equivalent to
ar[i], b[i] c[j] + b[j]
but requires two fewer LDX instructions.
Programmers familiar with Algol 60 will no doubt be annoyed with the use of `,' in the assignment
statement. The purpose of this is to make the compiler somewhat simpler.
16
3. To add one to the current contents of the accumulator one writes:
accumulator accumulator + 1
which generates the single instruction
ADD =1
4. ind addv, i, j i + j
generates
LDA I
ADD J from expression
STA* ADDV
STA I
STA J
5. How does one write the equivalent of the Algol 60
a := b[i+j] ?
Clearly the X register must be loaded with i+j. The X register is word 0 of the machine, so the
assembler has a declaration set up for the integer x, which is given the address 0. So the above can
be written:
x i + j;
a b[xsymbol]
This generates the code
LDA I
ADD J
STA 0
LDA* B
STA A
To summarise, the facility provided by assignment statements in PL516 is very similar to that of Algol
60.
4.2.6 Statements using conditions
One of the distinguishing features of Algol 60 over Fortran is that fewer labels are required. This is because
flow of control can be expressed via conditional statements and for loops. This feature of Algol 60 is
present in PL516. Three forms of conditional control statements are available.
6:0if statement ::= if 3:0condition then 10:0statement
else 10:0statement
The effect of this statement is similar to the construction in Algol. If the condition is true the the first
statement is executed otherwise the second statement is executed. Representing the flow of control with
jumps by arrows, the code generated is as follows:
JMP false -------------> a
JMP -------------> b
a<------
b<------
Examples can be given using assignment statements as statements.
17
1. if a zero then
ab+c
else
bc+d
This generates the code
LDA A
SZE
JMP false -------------> a
LDA B
ADD C
STA A
JMP -------------> b
LDA C a<------
ADD D
STA B
b<------
2. Add 3 to a[i] if a[i] is even, otherwise subtract 6 from a[i].
if a[i] even then
a[xsymbol] accumulator + 3
else a[xsymbol] accumulator - 6
Note the use of xsymbol and accumulator which reduces the size of code generated, which is:
LDX I
LDA* A
SLZ
JMP false -------------> a
ADD =+3
STA* A
JMP -------------> b
SUB =+6 a<------
STA* A
b<------
3. In the above example two STA* A instructions are generated which would not be produced if it were
hand coded. However this can be avoided by writing:
if a[i] even then
accumulator accumulator + 3
else accumulator accumulator - 6;
a[xsymbol] accumulator
Which generates
LDX I
LDA* A
SLZ
JMP false -------------> a
ADD =+3
JMP -------------> b
SUB =+6 a<------
STA* A b<------
18
It must be remembered that repeated use of xsymbol and accumulator especially over a number of
statements, makes the program less clear, since the reader must scan the text backwards to work out
the value of the X or A register.
4. In fact the above example can be more elegantly coded using a conditional expression. For instance
a[xsymbol] if a[i] even then accumulator + 3 else accumulator - 6;
This produces the same machine code as the previous example.
5. There are no boolean variables, so integers must be used instead. The convention 0 = false and -1 =
true means that and and nev have the usual meaning.
Hence the Algol 60 statement
if a and b then
c := ar[i]
else
d := ar[j];
would be written in assembly code as
if a and b nonzero then
c ar[i]
else
d ar[j];
This generates the code
LDA A
ANA B
SNZ
JMP false -------------> a
LDX I
LDA* AR
STA C
JMP -------------> b
LDX J a<------
LDA* AR
STA D
b<------
Note that if statements always have an else. The reason for this is to avoid the ambiguity that existed
in the original Algol 60 report[4]. The revised report overcame this by making the syntax more
complex. This was not thought appropriate in this case, since being able to add a new statement type
would not be so easy. If no else is required then a when statement is written.
6:0if statement ::= when 3:0condition then 10:0statement
The machine code generated for this is:
JMP false -------------> a
a<------
19
1. when xx y then
accumulator y;
maxxy accumulator
Note that the A register is either set with xx by the condition or by y from the first assignment
statement.
This generates the code
LDA XX
CAS Y
JMP false -------------> a
NOP
LDA Y
STA MAXXY a<------
2. Load into the accumulator the sense key reading as a binary number.
accumulator zero;
when sense1 then
accumulator accumulator + 1;
when sense2 then
accumulator accumulator + 2;
when sense3 then
accumulator accumulator + 4;
when sense4 then
accumulator accumulator + 8;
Not surprisingly the accumulator symbol is a single character on the Teletype representation (see
Appendix A). The code generated for all this is
CRA
SS1
JMP false ( =+1 )
ADD =+1
SS2
JMP false ( =+1 )
ADD =+2
SS3
JMP false ( =+1 )
ADD =+4
SS4
JMP false ( =+1 )
ADD =+8
Such repeated use of the accumulator symbol makes this one of the few cases when the DAP is
shorter to write than PL516.
The last form of statement using conditions is the while statement - a surprising omission from Algol
60. The syntax is:
6:0while statement ::= while 3:0condition do 10:0statement
The code generated is:
b<-----
JMP false -------------> a
JMP -------------> b
a<------
20
So the statement is repeatedly executed while the condition is true.
1. Find the first non-zero element of an array form a[i] onwards
while a[i] zero then
i i + 1;
This generates the code
LDX I a<-----
LDA* A
SZE
JMP false
LDA I
ADD =+1
STA I
JMP ------>a
So a[i] now has a non-zero value.
2. Find the first differing elements of the two arrays a and b
while a[i] = b[xsymbol] then
i i + 1;
This generates the code
LDX I a<-----
LDA* A
CAS* B
SKP
SKP
JMP false --->b
LDA I
ADD =+1
STA I
JMP ------>a
b<---------
4.2.7 Loop control
The machine instruction IRS (IncRement in Store, see page 5) is clearly intended for loop control. If one
wishes to go round a loop 3 times, then a word in store `COUNT' is used for this which is given the value
initially of -3. The loop control is then done by:
IRS COUNT
JMP
This mechanism is very crude in that one must always increment by +1 up to -1 and one must always
go through the loop once. Nevertheless this mechanism is adequate for the vast majority of ordinary loops.
So it is adopted for PL516.
7:0for statement ::= for findg 14:1integer identifier 1:0expression j
7:1xassignment statement
do 10:0statement
7:1xassignment statement ::= xsymbol 1:2cell
21
A special case is where the count is word 0 of the machine. This is the X register which allows indexing
to be performed efficiently. In this case, loop control does not use the accumulator since the initial loading
of the X register can be done by an LDX operation. This is reflected in the syntax by the option using the
`xassignment statement'.
The code generated is as follows:
Without the xassignment statement. STA CONTROL
a<---------------
IRS CONTROL
JMP ----------------->a
The STA and IRS instructions have the indirect bit set if the integer control variable has ind in front
of it.
with the xassignment statement. LDX
a<---------------
IRS 0
JMP ----------------->a
One important consequence of this method of loop control is that it is convenient if array elements are
addressed for ,n, to -2, -1. Rather than produce arrays in either order (as in DAP) for consistency all arrays
are addressed from -(size of array in words) to -1. This means that control variables have the opposite sign
to what would be usual in Algol 60 and the scanning is in the opposite direction (although in the direction
of increasing address).
Examples:
1. Add two vectors element by element putting the result in a third vector. Assume that the number of
words in the vectors is -size.
This simple loop can be coded using the X register as the control variable thus:
for xsymbol size do
a[xsymbol] b[xsymbol] + c[xsymbol]
This generates the machine code
LDX SIZE
a<---------------
LDA* B
ADD* C
STA* A
IRS 0
JMP ----------------->a
Note that size is negative, and that -30 (for instance) could have been written instead of size. This
would be undesirable since changing the program for a different size of arrays would require going
through the entire program text altering all the constants.
2. Find the largest element of an array.
This might be written in Algol 60 thus:
j := c[1]; for i := 2 step 1 until size do
if c[i] > j then j := c[i]
22
The straightforward way of coding this in PL516 would be
j c[1]; for i inc size do
when c[i] > j then j accumulator
Note that i is used as the control variable since an expression is required initially (since xsymbol
inc size is not valid). the if in Algol must be changed to when since there is no else in the statement.
Th code generated is
LDX SIZE
LDA* C
STA J from j <- c[size]
LDA SIZE
AOA
STA I from i <- inc size
a<---------------
LDX I
CAS* C
JMP *+3
NOP
JMP false --->b
STA J since c[i] is in the A register
IRS I b<----
JMP ----------------->a
3. It is however possible to code this using the X register as the control variable. In this case, the largest
element of the array so far is kept in the accumulator.
This is written as
accumulator c[size]; for xsymbol inc sizep1 do
when accumulator < c[xsymbol] then
accumulator c[xsymbol]
The code generated is
LDX SIZE
LDA* C
LDX SIZEP1
CAS* C a<--------------
JMP *+3
NOP
JMP false --->b
LDA* C
IRS 0 b<----
JMP ----------------->a
Note that this code is very nearly optimal. This is achieved by use of xsymbol and accumulator but
as a consequence the program is much less intelligible. The new constant `sizep1' has the value one
more than size.
More complex for loops that exist in Algol 60 must be coded differently in PL516. This can usually be
done conveniently with a while statement without using labels.
For instance the Algol 60 for i := j step k until n do, where n could have a value of zero so that the
controlled statement is not executed. This can be code as:
23
i j;
while i n do
begin
;
ii+k
end
Note that the example 5 given in 4.2.5 could not have been written as
xsymbol i + j;
a b[xsymbol]
Since the first statement is not a valid assignment statement as i+j is not a cell. So x is used when one
is using the X register as an ordinary integer but xsymbol is used when its special properties as an index
register are being exploited.
4.2.8 Goto statements
Because of the generality of statements using conditions very few labels need be written in most programs.
Statements can be lebelled in a similar manner to Algol 60 as will be explained in section 4.2.10. Two
forms of goto are provided as follows:
8:0goto statement ::= goto 14:6label identifier j
14:7switch identifier 2:0subscript
The statement goto ll would generate the single instruction JMP LL.
Switches are set up in a manner similar to arrays as explained on page 4. As with arrays, the index is
negative, so a 3 element switch have index values -3, -2 and -1. Although there is no logical necessity to
have them with negative values it is convenient for the mechanism to be the same as arrays.
The code generated from goto SS[i] is
LDX I
JMP* SS
The switch word SS has the index and indirect bit set. Assuming i is within range (this is not checked!)
the next level of indirection (after indexing) will give the 14 bit address of the label in the switch. The way
the switch elements are set up is described in 4.2.12. Note that since the subscripting of switches is the
same as arrays, xsymbol can appear instead of an integer.
Examples
1. Find an element of an array `a' equal to i, and goto the corresponding element of a switch `branch'.
Otherwise goto the label `error'.
accumulator i;
for xsymbol size do
when accumulator = a[xsymbol] then
goto branch[xsymbol];
goto error
Note that the accumulator has been loaded with i outside the loop.
The code generated is
LDA I
LDX SIZE
LDX SIZEP1
CAS* A a<--------------
SKP
24
SKP
JMP false --->b
JMP* BRANCH
IRS 0 b<----
JMP ----------------->a
JMP ERROR
2. There is no designational expressions in PL516, so that the Algol 60
goto if xx > 0 then ll else error1
must be written as
if xx > 0 then goto ll else goto error1
This generates the code
LDA XX
CAS =0
JMP *+3
NOP
JMP false --->b
JMP LL
JMP --->a
JMP ERROR1 b<---
a<---
This is one of the few cases where PL516 generates code which is substantially worse than hand
coding. Note the non-executable jump round the `else statement'.
4.2.9 Procedure calls
There are four types of procedures in PL516. A procedure may expect a parameter and it may be a
`conditional' procedure. All four types exist but they may only be called in the appropriate context. All
procedures may leave a result in the accumulator. Procedure calls can occur in three different contexts. The
first is in 1:1term and the second 3:0condition which have been given. The last context occurs
in the next section as a statement. The syntax is:
9:0procedure call ::= 14:1procedure identifier f 1:0expression g
9:1conditional procedure call ::= 9:0procedure call
the second rule is written down separately to imply a check in the compiler that only conditional
procedures can be called in the context of a condition, and that they may not be called in the other
two contexts. Apart from being conditional a procedure may have one parameter. This parameter is
an expression which is evaluated before entering the procedure. Hence by analogue with Algol 60, one
value parameter is allowed in which case the value of the expression is in the accumulator on entry to the
procedure.
So the code generated is
{}
JST*
The procedure call is always