The original copy of this paper is far from legible so almost certainly there are errors in the transcription. The paper appears to use a different notation from later papers. Where the notation is unclear, the notation that appears in future papers has been used.
An input program is described which would allow the user to define the meaning of the statements he uses. These statements are not restricted to procedural types as is the case with some existing systems for compiling macros from micros, but may also be of a declarative nature. This paper was presented at the Harrogate Conference of The British Computer Society on 5 July 1960.
An assembly program is described which may be thought of as an autocode to write autocodes. It is in fact complete in the sense that it could be used to write itself. Although the ideas described would be applicable to any large last computer, we think mainly in terms of Atlas. Atlas is a machine currently under construction at Manchester University in collaboration with Ferranti Ltd. For the purpose of this report it can be regarded as a conventional single-address machine. The standard word lengths are 24 and 48 bits.
The basic idea is to allow the user to define the meaning of expressions and statements (either imperative or declarative), which he is subsequently to present to the machine - as a string of symbols punched on cards or tape i.e. as a source program. We can regard the instruction sentences (statements) of the source program as causing the assembly program to call in a subroutine corresponding to the form of statement recognised. The particular expressions (also called phrases) in the statement become the parameters of the subroutine. In the case of an imperative statement the routine will compile the corresponding machine instructions, but if the statement is of a declarative nature then the action of the routine may be, for example, to complete previously compiled instructions, or make entries in lists which mav be referred to when compiling further instructions.
Thus to define the meaning of a statement is essentially to give the structure of the corresponding compiling routine. If the statement in question is simply an abbreviation for a sequence of lesser-order statements, in which the constituent expressions of the former are distributed among the latter, then the compiling routine will simply call for the sub routines of the lesser-order statements in the appropriate sequence, passing on to them, as parameters, expressions from the set with which it was itself provided. This process is referred to in American compiler circles as obtaining macros from micros. An example is provided by the instruction for addition of complex numbers:
(Y1,iY2) = (X1,iX2) + (X3,iX4)
which can be defined as
Y1 = X1 + X3
(assuming that Y1 is not associated with X2 or X4).
Y2 = X2 + X4
Here Y1 and Y2 are the names of variables and X1, X2, X3, X4 are either names of previously computed variables or numbers. The assembly program records such definitions as follows. Each of the lesser order statements are first looked up in a statement format dictionary (SFD) which provides the cues of the corresponding definitions (i.e. compiling routines). From these cues and the relevant parameters of the statement heading [in the above example
(Y1,iY2) = (X2,iX3) + (X3,iX4)
] a call sequence is assembled in the compiling routine under construction. Finally, the statement heading and the cue for the compiling routine are added to the SFD, so that statements of this type may he used as lesser order statements in later statement definitions.
There are. however, several features of most existing autocodes which cannot be met bv this simple concept of a self-expanding autocode. The first is that the parameters of the subroutines corresponding to the lesser-order statements (henceforth referred to as sub-statement routines) do not necessarily occur directly in the statement heading, but may be sub-expressions of its constituent expressions. Indeed, were it not for this feature, all statements would involve only elementary expressions. Thus it is necessary to be able, within any definition, to resolve selected expressions into sub-expressions consistent with their known structure (see below: phrase definition).
Secondly, there is the feature already mentioned of declarative statements which affect other statements, either foregoing or later, in an arbitrary complicated way. For example: dimension statements, floating labels, etc. Such statements cannot usually be built up from similar statements of lesser order, but can conveniently be expressed in terms of listing instructions. Thirdly, the translation may depend upon the particular form certain expressions take. It is necessary, therefore, to include some means of examining and comparing expressions in order to select different courses of action.
In general, compiling routines may consist of three types of instructions:
Instructions of the second type are executed by an interpretive routine operating on the data which results from the recognition of their written form (i.e. as punched) by the expression recognition routine (ERR).
This routine will be described in a subsequent paper: it is sufficient to remark here that the data takes the form of a tree which the interpretive routine searches. Before describing the properties of the list-compiling language it is convenient to describe the means of defining new expressions (i.e. phrases) in terms of lesser-order expressions, and basic expressions.
These are used to build up classes of (logically) similar phrases. To each class is assigned a name, the class identifier, which may then he used in statement formats to indicate that any phrase of the class in question can he substituted in its place. It is necessary to distinguish class identifiers from basic symbols. For this reason we shall resort, in general, to multi-character identifiers enclosed in square brackets, e.g. [TERM]. However. in the following examples from Mercury Autocode (Brooker. 1958). we shall take advantage of the fact that upper-case letters are not among the basic symbols of the language, hence they can be used as identifiers without any ambiguity arising. Thus the following phrase definitions could be the start of system for describing Mercury Autocode.
V = a, b, c, d, e, f, g, h, u, v, w, x, y, z, π I = i, j, k, l, m, n, o, p, q, r, s, t D = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 N = an arbitrary sequence of D's Y = V, V' , VN, VI, V(I+N)
Here the commas are meta-syntactical symbols denoting or. Naturally, if the , also appears in alternative phrases, it will be necessary to distinguish the two appearances in some way. The same applies to certain other meta-syntactical symbols.
It becomes apparent that certain useful classes are not straightforward, e.g. the arbitrary sequence of D's. Also the appearance of some items in a phrase may be optional. In order to describe these two situations we introduce the qualifiers * and ?. Thus:
A[B*]C means ABC, ABBC, ABBBC, etc. A[B?]C means AC, ABC A[B*?]C means AC, ABC, ABBC, etc.
Although convenient, these qualifiers are not essential, and the above classes could alternatively be defined by means of recursion and the nil class thus:
ADC where D BD, B AEC where E B, nil AFC where F D, nil
With these additional features, the classes for Mercury Autocode can be extended to include the general arithmetic expression [GE] as follows:
K = N[.?], [N?].N (general constant) Q = Y, K, I (factor) T = [Q*] [/Q?] [/Q] = /Q [±T] = + T, - T [GE] = [-?]T[±T*?]
(Note: The symbols in the stem of a multi-character identifier must not include the qualifier symbols * ? . ) If brackets within brackets were allowed in arithmetic expressions, then this could be described recursively by writing
Q = Y, K, I, ([GE])
We can now use the foregoing phrase definitions to describe the format of the basic compiling instructions. These are primarily concerned with processing information recorded in lists of indefinite extent. The unit of information is an (address) word, and it is assumed that there is a one-level store of word registers 0, 1, 2... .. n-1 addressed in the usual way. (In the case of Atlas n=221, although the word length is 24 bits.)
Two forms of list storage are used: the first represents conventional use of consecutive registers for consecutive words in the list; the second form of storage is the chain store in which the registers are arranged in pairs, so that each information word is accompanied by a link word giving the address of the next information word in the list. [This is somewhat similar to the storage techniques used in LISP (McCarthy, 1959) and IPL (Newell and Shaw, 1957).] A list of this second type has a direction and can only be scanned in that direction. Initially all the words of the store are connected together in a single chain, thus:
so that the odd register in each pair contains the address of the even register in the previous pair. This will be referred to as the main chain, and the last pair of registers n-2, n-1 is (initially) the head of the chain. The mechanism of using the storage system is to borrow register pairs from the head of the chain as they are needed for working lists (which take the form of subsidiary detached chains), and return them there when they are finished with. Since the registers will not, in general, be returned in the same order in which they were borrowed, the active part of the chain will soon lose its original ordering. Thus, if the first two pairs are borrowed and returned in reverse order, the head of the chain becomes
If, however, registers are returned as soon as possible, the disturbance will extend only a minimum distance from the head of the chain, and this enables the tail of the chain to be used for conventional purposes. This latter usage will destroy the links of the original chain, but we shall assume, for the present purpose, that the two forms of storage never meet. i.e. some central portion of the original chain always remains intact, and the absolute layout of the store is as shown below.
0 n-1 conventional i.e. undisturbed used portion of consecutive part of main chain, and storage original chain working chains
(It is, of course, fairly easy to provide for a floating partition, but the details are irrelevant here.)
There is a central group of single-word registers denoted by α1, α2, α3, ... for miscellaneous information. These are essentially individual variables and do not form a field (i.e. they cannot be referred to as αi). In addition to this global set there is a similar set of local variables β1, β2, β3, ... associated with each compiling routine (or statement definition). Each set is of indefinite extent but since they are individual variables, they are not expected to extend very far in practice. Systematic lists of information are kept in the main store in one of the two forms already described. (The α's and β's are, in fact, also kept in the main store, but from the user's point of view can be regarded as logically distinct.)
A floating-address system is employed for the purpose of control transfers, and any instruction may be labelled thus
N](compiling instruction)
These labels are local to the routine in which they occur. We can now describe the basic expressions. They are:
N = [D*] (already introduced) α = α1, α2, α3, etc β = β1, β2, β3, etc [αβ] = α,β [αβN] = α,β,N [addr] = [αβ], [αβ]+[αβN], [αβ]-[αβN], [αβ]⊕[αβN] [word] = [addr], ([addr]), N.D, .D, N θ = +, -, ×, /, &, ∨, ≢ φ = =, ≠, >, ≥, <, ≤
Notes
(1) ([addr]) denotes the contents of the given address.
(2) The symbol ⊕ refers to a chain of register pairs thus β1⊕2 is the location of the second information register following β1 in the chain.
(3)It has already been mentioned that Atlas provides for up to 221 registers of 24 bits. There are thus three bits to spare in address words, one of which is the sign digit while the other two are at the least-significant end of the word, thus
N D
0.....................00
In some contexts these digits are regarded as describing one of four 6-bit characters into which a word can be partitioned. In other circumstances they can be employed as a tag or punctuation mark which is easily accessible for discrimination purposes. The least-significant digits are normally zero unless the [word] is described in the form N.D or .D, where D is 0, 1, 2, 3.
In terms of the above classes the basic instructions are:
[αβ] = [word] changes contents of central registers (local or global) [αβ] = [word] θ [word] ([addr]) = [word] changes word in list ([addr]) = [word] θ [word] if [word] φ [word] →[αβN] conditional transfer →[αβN] unconditional transfer
For example
(β2-1) = β1 + (β2)
means replace contents of the address β2-1 by the sum of β1 and the contents of address β2 .
It should be mentioned thai the format descriptions are not all mutually exclusive, thus, for example, the right-hand expression β1+2 can be regarded either as [word] θ [word] or simply [word] of the form [addr] which is β1+2. The result, however, is the same in either case.
The elementary borrow and return operations can be described in terms of the foregoing instructions, adopting the convention that α0 refers to the head of the main chain. Thus
borrow [αβ] is equivalent to [αβ] = α0 α0 = α0⊕1 ([αβ]+1) = 0 and return [αβ] is equivalent to ([αβ]+1) = α0 α0 = [αβ]
Until a borrowed word is used it is provided with a zero link. This somewhat arbitrary convention is used in the next section to distinguish between an empty list and a list of one item.
We shall now describe some elementary subroutines for handling subsidiary storage chains. Two such chains can be distinguished: the circular list and the circular nest.
This takes the form
where [αβ], the location of the last item entered, is also taken as the location of the list. By making the list circular [αβ]⊕1 gives the start of the list. i.e. the location of the first item entered. Similarly, [αβ]⊕n refers to the nth item. With this arrangement a single quantity provides all the useful information about the list. Thus a new word is entered by inserting it into the loop between [αβ] and [αβ]⊕1 as shown:
The list is set up in the first place by borrowing a word, and then linking it to itself after the first item is entered. The general operation can be described by the following subroutine:
add [word] to list [αβ] if ([αβ]+1) ≠ 0 →1 tests whether list is empty ([αβ]) = [word] ([αβ]+1) = [αβ] enter first item END 1]borrow β1, prepare copy of [word] (β1) = [word] (β1+1) = ([αβ]⊕1) ([αβ]⊕1) =β1 include in loop [αβ] = β1 END
This routine provides a further example of a statement definition, the statement in question being add [word] to list [αβ]. When a particular form of this statement, say add α5 to list α6 appears as an instruction sentence of the source program, the above compiler routine will be called in. It will be supplied with the expressions α5 and α6 , which are to be substituted for the parameters [word] and [αβ] before the routine is executed.
The precise means by which this substitution is effected will be the subject of a further paper, and for the moment we refer to the remarks made earlier concerning the internal structure of the instructions. These take the form of trees, and parameter substitution is effected, when each instruction is executed, by connecting the subtrees, corresponding to the parameter expressions in the statement heading, to the appropriate ends of the instruction tree.
Like the list this is a circular chain, but now the reference location [αβ] is fixed and all items are inserted between [αβ] and [αβ]⊕1. Thus [αβ]⊕1 is the address of the last item entered, while [αβ] is always the address of the first item. Initially the nest is set up by borrowing an empty word which is then linked to itself after the first item is entered
and, for the general case
When employing a nest it is envisaged that words are withdrawn in the reverse order in which they are inserted, i.e. last in, first out. (The terms cellar and push down list are also used to describe this state of affairs.) The following routines provide the relevant operations.
add [word] to nest [αβ] if ([αβ]+1) ≠ 0 →1 test if nest is empty ([αβ]) = [word] ([αβ]+1) = [αβ] insert first word END 1]borrow β1, prepare copy of [word] (β1) = [word] (β1+1) = ([αβ]⊕1) (β1⊕1) = ([αβ]⊕1) include in loop ([αβ]⊕1) = β1 END withdraw [αβ]1 from nest [αβ] Here there are two parameters of the form [αβ] in the [αβ]1 = ([αβ]⊕1) heading and we employ a suffix to distinguish them delete [αβ]⊕1 END delete [αβ]⊕1 If nest (or list) has only one β1 = [αβ]⊕1 item then restore empty word if β1 ≠ [αβ] →1 ([αβ]1) = 0 END 1]([αβ]⊕1) = (β1+1) contract loop and return word deleted return β1 to main chain END
Much of the text in this section is guesswork. A better description can be found in the later paper.
It will be recalled that a statement definition comprises three kinds of instructions, namely, sub-statements, compiling instructions, and instructions for manipulating and testing the parameter expressions. The last of these we refer to as parameter operations. As already explained, the parameters of the statement heading do not necessarily appear directly as the parameters of the sub-statements (and basic compiling instructions). Instead, the latter parameters are often sub-phrases of the former, or perhaps phrases compounded from them. In either case the relationship between the phrases which appear in the sub-statements and those of the statement heading has to he made clear.
We discuss first the means by which the individual phrases are identified. Both the parameter phrases of the statement heading and those derived from them are normally referred to by writing the relevant class identifiers. If the same class of phrase appears more than once in any logical path through a definition, the different appearances of the class identifier are distinguished by means of a label (written inside the identifier brackets). Thus, for example, we may write
φdivide ([GE/1], [GE/2]).
The conventions of labelling are not rigid, and we only require that subsequent references to each expression bear the correct label, and that ambiguity is avoided. It is also desirable, as we shall see later, to be able to refer to a particular appearance of a repeated phrase. For this purpose we attach another label, in this case enclosed in brackets thus. ([αβN]).
For example, given the repeated phrase [Q*/1] we refer to the second Q in the sequence as [Q*/1(2)]. Alternatively, given [Q*], we would write [Q*(2)]. In the use of floating references such as [Q*/1(xi)] or [Q*/1(β1)] the current value of the α or β concerned determines the particular appearance of the phrase within a sequence. The above interpretation is not relevant in the case of [N(α1)] and [N(β1)], etc., and we attach a quite different significance to these identifiers. Either one can be written in place of a conventional N in a sub-statement, and means that the current value of the α or β in question is to be inserted at this point.
To return to the question of generating new phrases from those appearing in the statement heading, the instructions used for this purpose are:
let π ≡ some π expression and let π = some π expression
In the first of these the left-hand side refers to a particular phrase appearing in the statement heading (or introduced by a previous let instruction), while the right-hand side is an explicit phrase of a form consistent with foregoing definitions of the left-hand side and its sub-phrases.
For example, if the definitions
[+T] = + T and T = [Q*] [Q?]
have been previously given we may write
let [+T] ≡ T or even let [+T| ≡ Q
if it is known that the [+T] in question takes the form of a single Q. When alternative forms are possible, a single instruction can be used both to introduce the sub-phrases of a particular alternative, and to take some alternative course of action if (or unless) the specified alternative form appears. The formats of this instruction are:
if π1 ≡ π2 →[αβN] unless π1 ≡ π2 →[αβN]
Therefore in the above example, if the [+T] could take several forms yet we wished to treat the case [+T] = [Q] separately we would write>
unless [+T] ≡Q → 10
Throughout the logical path stemming from this instruction, the newly introduced phrase Q can be referred to; however, in the alternative path labelled 10 it remains unknown.
In the second type of let instruction the new phrase introduced is the right-hand side expression and this is subsequently referred to by the identifier appearing on the left-hand side. New phrases of this type are compunded from previously introduced phrases (and basic symbols), again in a manner consistent with the foregoing phrase definition of the left-hand side. This type of let instruction does not give rise to conditional forms. Two other conditional instructions are, however, required in order to compare different appearances of the same class of phrase. These are:
if π1 = π2 →[αβN] unless π1 = π2 →[αβN]
where both π1 and π2 are known expressions.
Finally, two further instructions should be mentioned, namely
[αβ] = category of π [αβ] = number of π
In both of these the π refers to a particular phrase. The former instruction determines the principal category to which the phrase belongs within the class π. That is, if a particular I (referring to the Mercury Autocode phrase definitions), [I/1] (say), happens to be a j then:
α2 = category of [I/1]
sets α2 to 2, because j is the second alternative in the definition of I.
The second instruction applies only to repeated (i.e. *) classes. It determines how many times the phrase in question has actually been repeated.
In order to illustrate the scope of statement definitions we include some examples from a description of Mercury Autocode. There is not space here to include a complete description, instead we have chosen only a few which illustrate the treatment of the principal features of an autocode.
Consider first the most elementary statement in the instruction hierarchy, a basic (Atlas) instruction. When compiled, these instructions occupy two consecutive 24-bit registers. They have the following structure:
function Ba Bm address 10 bits 7 bits 7 bits 24 bits
where Ba and Bm specify two of the 128 B-registers (the precise way in which the contents of these influence the instruction need not concern us). We define the format of these instructions as
[label?] [word /1], [word/2], [word/3], [word/4]
where
[label] = N)
This allows the user to write basic instructions in a variety of ways. e.g.
23) 690, 0, α3, β2+2
The following statement definition forms the compiling routine for translating these instructions.
statement defn: [label?] [word/1], [word/12], [word/3], [word/4] unless [label?] ≡ N) →1 if label present enter control number in label directory (α1 + N) = α2 1)β1 = 128 * [word/1] β1 = β1 + [word/2] plant function and B digits β1 = 128*β1 (α2) = β1 + [word/3] (α2+1) = [word/4] plant address part and advance control α2 = α2 + 2 END
Note
α1 gives the first of 128 consecutive locations in which the control numbers corresponding to the 128 labels of Mercury Autocode are recorded. α2, α2+1 are the addresses of the registers into which the current instruction is planted (i.e. α2 is control).
It is also of interest to consider the means by which control numbers are substituted for the labels in jump instructions. (In Atlas a jump is effected by transferring the new control number to B-modifier 127, which serves as the control register.) At the time of assembling a jump instruction, the label itself is provisionally planted in the instruction and its address is noted in a nest (α3), which we assume to have been set up at the beginning of the chapter. The substitution of the actual address is postponed until the close directive is read terminating the chapter. The required statement definitions are:
statement defn: jump N 81, 127, 0, N (81 is the function n+B) add α2+1 to nest α3 α2 = α2+1 END statement defn: close 1]withdraw β1 from nest α3 withdraws all jump references β2 = (β1) and replaces the N's by the control numbers (β1) = (α1 + β2) if (α3+1) = 0 →1 ends when nest is empty
Let us now assume that, by means of foregoing statement definitions, we have built up to instructions of the form:
A= A + F A= A * F F=Q , tsN where tsN denotes ts1, ts2, etc, miscellaneous working space A= A / F A=[±?]F G= Y , tsN G= A
We demonstrate below how these can be used to describe the more complex type of instruction: Y=[GE]. The order of the following definitions is not necessarily that which would be presented to the machine. That is, the more complex ones are given first. This does, however, become necessary when recursive definitions are used, and will be provided for.
statement defn: Y = [GE]
let [GE] ≡ [±?]T[±T*?]
A = [±?]T (see above)
unless [±T*?] ≡ [±T*] →1
β1 = number of [±T*]
β2 = 1(1)β1
let [±T*(β2)] ≡ [±] T
A = A [±] T (see below)
repeat
1]Y = A
END
statement defn A = [±?]T
let T ≡ [Q*][/Q?]
A = [±?][Q*(1)] (of the type A [±?]F)
β1 = number of [Q*]
if β1 = 1 →1
β2 = 2(1)β1
A = A * [Q*(β2)] (of the type A = A F)
repeat
1]unless [Q?] ≡ Q →2
A = A Q
2]END
statement defn A = A [±] T
Here we have taken advantage of the fact that, if T
consists of only one factor, then it can be added directly to the
existing contents of the accumulator
unless T ≡ Q →1
A = A ≡ Q
END
1]ts1 = A plant contents of A in temporary store
let T ≡ [Q*][Q?]
A = [±] [Q*(1)]
β1 number of [Q*]
if β1 = 1 →2 deals with product term
β2 = 2(1)β1
A = A [Q*(β2)]
repeat
2]unless [/Q?] ≡ Q →3 deal with divisor term if present
A = A + ts1 restores sum
3]END
The above example describes only the [GE] employed in Mercury Autocode. However, it is easily extended to deal with the more general form, in which brackets within brackets are allowed to any depth. In this case the statement compiling routines would be used recursively, since in that case Q is extended to include Y, K, I, ([GE]). Also, the temporary store ts1 becomes ts2, ts3 etc., according to the depth of the bracketed expression being dealt with. This is achieved by using a parametric representation ts[N(α)], where the α in question is advanced and retarded by the statement definition responsible for the recursion. Strictly speaking, the statement heading should provide for a label if one is allowed. This will correspond to labelling the first of the constituent sub-statements, so that, for example, the definition of Y=[GE] should read:
statement defn: [label ?] Y = [GE] let [GE] ≡ [±?]T[±T*?] [label ?]A = [±?]T etc.
The cycling instructions: β2 = 2(1)β1 and repeat fulfill the usual function. Though it is not described here, they can conveniently be expressed in terms of basic compiling instructions.
It is hoped that a scheme on the lines described will considerably reduce the time taken in writing autocodes, perhaps from a matter of man-years to man-weeks. The means by which the scheme can be mechanized will be the subject of a further paper. It will be seen that the basic compiling instructions are used for this purpose also.
BROOKER, R. A. (1958). "The Autocode Programs Developed for the Manchester University Computers." The Computer Journal. Vol. I. p. 15.
BROOKER, R. A. (1958). "Further Autocode Facilities for the Manchester (Mercury) Computer." The Computer Journal. Vol. I. p. 124.
BROOKER,. R. A. (1959). "Mercury Autocode (additional notes)." The Computer Journal. Vol. 2. p. (xi). (or. in Reprints, p. iii).
MCCARTHY. J. (1959). "The LISP Programming System." M.I.T. Report.
NEWELL. A., and SHAW. J. C. (1957). "Programming the Logic-Theory Machine." Proc. West. J.C.C., p. 230.