High level autocode for English Electric Deuce
Duncan and Huxtable English Electric 1959
Autocode for English Electric Deuce
computer. Two such machines* are in operation in Mathematical Services
The original programming manual (Ref.2) was published in 1955, before
a machine was available. In it there was an account of how to write pro-
grams but no mention was made of techniques used in program testing and the
methods that can be used to simplify programming. These techniques,
however, are important to all machine users and are not readily accessible
to beginners. Many of the methods now in general use, at R.A.E. and else-
where, are of more recent date than the programming manual. It was therefore
decided to write a new manual, which was to be a comprehensive guide to all
machine users, especially beginners.
The Note consists of five parts. Part I contains all that is necessary
for efficient use of the machine's facilities in the construction of programs.
Part II is concerned with program testing. The techniques described were
mostly developed at R.A.E. and are the result of much cooperative effort and
shared experience in Mathematical Services Department. Part III gives some
details of the library of programs and subroutines available for DEUCE, as
well as a list of recommended subroutines to perform standard operations.
Part IV is meant for the more advanced programmer. It contains sections
that deal with specialized topics, such as interpretive programs, and also
has a simple introduction to logical design. Part V consists of exercises
for the beginner, although others may learn something useful from the
The text is, to a large extent, based on a course given by Mathematical
Services Department in May 1957. The order of presentation of the subjects
in Part I is the result of experiment with this course.
One small point concerns the spelling of 'program'. There is a rather
meaningless controversy about this, some supporting 'program' while others
favour 'programme'. The spelling adopted here was used for the EDSAC in
Cambridge in 1949, when there were no other machines. We are therefore in
good company and the spelling has the virtue of English precedent but really
it is only a matter of personal taste.
A word of explanation is needed for the long delay between the time of
writing of most of this Note and its publication. The authors both left
R.A.E. at the end of the summer of 1957, when most of the text was in manu-
script form. Their commitments elsewhere allowed little time for writing
the remaining sections until late 1958. By this time certain alterations
had been made to the DEUCE, which required a further revision of some
sections of the text. Even now (early 1959) the exercises of Part V are
fewer than had originally been hoped and there is no index. For all these
delays and omissions we beg our readers' pardon.
Thanks are due to many people. To our colleagues in Mathematical
Services Department, especially Mr. E.J. York and Mr. J.M. Watt, we owe
much. Their comments and suggestions, when followed, have improved the
presentation in many places. Mr. J.M. Hahn, of Bristol Aircraft Company,
has allowed us to copy Fig.1, 'A Schematic Diagram of DEUCE'.
Dr. S.H. Hollingdale has been patient with us and supported our efforts
over a long and often frustrating period. To all these persons we say
* Affectionately known as 'Gert' and 'Daisy'
External link: Online copy
in 1959 IFIP Congress Paris, France view details
in 1959 IFIP Congress Paris, France view details
in 1959 IFIP Congress Paris, France view details
in The Computer Journal 1(4) January 1959 view details
The object of automatic programming is, of course, to reduce the effort required to write programs, and this is achieved by using, instead of ihe computer's own code of instructions, a pseudo-cork which is u«"illy closer to the programmer's habitual way of describing the operations which he wants the computer to perform. (The word 'programmer' is used here rather in the sense of'anyone wishing to write a program', than that of 'someone specially trained to write programs'.) A program having been written in a pseudo-code, there are two ways of making it produce the desired result, viz. by interpretation or by translation (or compiling, as it is often called).
In the first method, each code-word is interpreted as it is reached in the course of the calculation, and many of them will therefore be interpreted in my times. Since the interpretations occupy computer-time additional 11 11 at required for the actual computation, interpretative schemes produce |> grains which are slower than those written in the machine-code, though in some applications, e.g. in G.I.P. and T.I.P. (Ref. 1), the amount of computation specified by each code-word is usually so great that the interpretation time is negligible. Another feature of pseudo-codes which tends to produce slow programs when the interpretative method is used is that they do not fully reflect the storage-structure of the computer. It is, of course, desirable that a pseudo-code should be as free as possible from this structure, since it is alien to the conventional description of calculations, etc. On the other hand, the structure is designed mainly to achieve as high a speed of operation as possible for a given overall cost of the computer, and the neglect of it must cause a reduction in speed.
To satisfy both these requirements, which are incompatible in any interpretative scheme, and to avoid the repeated interpretation of codewords, we can use the computer to translate, once for all, a program written in a pseudo-code free from computer-determined structure into a fast program of computer-instructions, taking the storage-structure fully into account. The problems which are presented in the writing of a program for making such a translation are, however, far from trivial.
In many interpretative schemes, some translation is also done, i.e. the original code-words are first translated into others with properties nearer to those of the machine-code, e.g. symbolic addresses may be converted to absolute computer addresses. (We, at English Electric, usually reserve the term 'compiling' for this process, for convenience, although it is not essentially different from translation, as defined in the previous paragraph.) A 'compiler', i.e. a program for doing this preliminary work, is much easier to write than a 'translater', and may save a good deal of interpretation time.
Descriptions will be given of four interpretative schemes which have been prepared for DEUCE, one of which has been referred to by Mr. Robinson (Ref. 1). in each case, some compiling is done on the code-words before they are interpreted. The pseudo-code used in the first of these schemes, called George, is unusual, being in fact an extension of a notation ('reverse Polish') suggested for mathematics (Ref. 2). The second scheme, Alphacode, was inspired by the Manchester Autocode (Ref. 3), but attempts to make every code-word a statement in plain English. The third scheme, STEVE, employs a special-purpose pseudo-code, similar in form to those used by G.I.P. and T.I.P., but intended solely for calculations on the thermo-physical properties of steam and water. The fourth scheme, Easicode, is a general-purpose scheme with a form of compiled instruction giving rapid interpretation.
There follows a description of an existing translating program whose pseudo-code is known as Soda. Both this and Easicode retain some of the storage structure of DEUCE, which has in some degree facilitated their writing but which makes the writing of programs in these pseudo-codes rather more difficult than in Alphacode, for example. Finally, some of the difficulties which arise in translating from a pseudo-code which is free from computer-determined structure are discussed, together with some of the techniques which are to be used in a program for translating from Alphacode to DEUCE machine-code.
in Goodman, Richard (ed) "Annual Review in Automatic Programming "(1) 1960 Pergamon Press, Oxford view details
At the Cambridge Conference of The British Computer Society in June 1959, Dr. S. Gill, reviewing progress in automatic programming, stated (Gill, 1959):
Some examples of the second solution as applied to DEUCE were discussed in a recent paper (Robinson, 1959). These "autocodes" (G.I.P., T.I.P., Alphacode) arc, it was pointed out, complementary to each other in that each is suitable for its own certain class of problem. For example, G.I.P. is best suited to parallel operations on blocks of data, as in matrix manipulation, while Alphacode (which is not unlike Pegasus Autocode in many ways) is best for problems of single variables.
A G.I.P. program is very nearly as efficient as the corresponding DEUCE program. The reason is that, although the interpretation cycle is slow (< 1 sec), the instructions are powerful and call into operation highly efficient hand-made subroutines which are well buffered in the fast store. The interpretation time overall is negligible compared to the calculation time, and although the data are organized in the slowest part of the store, this happens to be the most efficient place. Alphacode, on the other hand, can be rather wasteful in its use of machine time. The interpretation cycle is quite fast (~ 17msec), but this is by no means negligible when compared with the times for obeying instructions, which are normally concerned only with single operations. Also, whereas Alphacode is confined to the slow backing store, an orthodox program for a problem suitable for Alphacode can make very good use of the faster levels of store for numerical quantities. As a result of this wide difference in efficiency, we find that G.I.P. is used both for "one-off" and for repeated jobs, whereas Alphacode tends to be limited to "one-off" work. In all other respects, however, Alphacode has been a highly successful user code, being very popular among "non-professional" programmers.
It is clear that if the inefficiency of Alphacode can be overcome in some way, the usefulness of the scheme will be much increased, and it will be able to cope with a much wider range of problems. Two difficulties are involved in this. One is the elimination of interpretation time, which could be achieved by taking the pseudo-code instructions one at a time and "transliterating" them into machine instructions. This is a fairly trivial matter. The other, more serious, difficulty is that mentioned by Dr. Gill, namely the efficient use of the multi-level structure of the real computer.
The present paper is concerned with an attempt to overcome these difficulties. A program, called the Alphacode Translator, is described which accepts an Alphacode program and produces an equivalent, more efficient, program in orthodox DEUCE code. The translator has been in use since the end of 1959. The object program is often between five and six times as fast as its original; the cost in machine time is between 20 and 50 minutes for a translation, according to the size and complexity of the program. (These figures relate to the magnetic-tape version of the Translator; for the punched-card version the translation time is between 30 and 75 minutes.) The Translator itself has about 22,000 instructions (cf. 24,000 for FORTRAN) and took between four and five man-years to make. As far as the authors are aware, it represents the first successful attempt to program the efficient allocation of storage in a multi-level machine.
Extract: The Translator in use
The Translator in use
Before describing the Translator it is convenient to describe how it is used. A program for translation is written in Alphacode and tested and corrected in the established manner, using the Alphacode Interpreter. The Interpreter has several useful program-testing facilities, such as optional punching of intermediate results, optional stopping, provision for altering instructions, and so on, and there is thus every hope of the program being right before translation is attempted. This is most important, since the translated (DEUCE) program, being very economically constructed, will have no special facilities, and though it will be always accompanied by a printed DEUCE flow diagram, the latter may not be readily understood by the original Alphacode user. There should normally be no need for interference with the DEUCE program. If modifications are necessary after translation, it is much easier for the user, even the sophisticated user, to alter the original Alphacode pack and do a complete translation again, than to attempt to alter the DEUCE program. It is also probably less wasteful of machine time.
Forms of input and output, and details of arithmetic, are exactly the same for the DEUCE program as for Alphacode. Therefore it is possible to check the work of the Translator by running both Alphacode and DEUCE programs with the same case data, and comparing the results mechanically; this in fact is standard practice and seems quite satisfactory.
It is extremely difficult to obtain a fair comparison between the performances of a translated program and a hand-written program for the same job. It is intended to obtain some direct comparisons by writing Alphacode versions of existing DEUCE programs. In the meanwhile, examination of translated programs seems to suggest that they operate at something like two-thirds the speed of the programs that would normally be produced by hand.
The allocation of storage is of course done more systematically by the Translator than by the human programmer, but the latter has the advantage of ad hoc knowledge of the problem, whereas the Translator, being designed for a wide range of problems, suffers by being forced to "play safe." In particular, the Translator, working only from the Alphacode program, has no information as to the dimensions of arrays, and so is prevented from accommodating them in the faster stores; it knows nothing about relative frequencies of alternative paths in the flow-diagram, and so has to make "intelligent guesses" as to priorities in storage allocation; and finally, it suffers from the stage division.
For practical reasons the stages are treated almost independently. Ideally, the program should be treated as a whole throughout, but this would mean a much more complicated, and slower, Translator.
In the section describing fast-store allocation, it was stated that about 75% of the number addresses were changed into fast store addresses. This was with four ordinary fast registers, and two fully addressable arithmetical registers (DS20, DS21). The system briefly described there has also been applied to a few programs assuming up to six ordinary fast registers. For each of these programs a histogram was drawn. They were quite consistent with each other, and one is shown in Fig. 7. The percentage of slow-store transfers remaining after allocation is plotted against the number of fast registers available. In the first column (a) there are no addressable fast stores; in the second column (0) the two arithmetical registers (called "accumulator" and "multiplier register" in some computers) are addressable; in the next columns there are, in addition, from one to six fast registers.
Two plots are superimposed on the diagram; the upper one is for the program as a whole, the lower (better) one for its main calculating loop. This illustrates the effect of the priority system described above.
It is clearly impossible to describe the Translator fully in a short paper. However, it is being made freely available to all DEUCE users as part of the normal DEUCE library service, and the report issued with it, which will be in several volumes and contain several hundred diagrams, will contain a complete description, detailed block diagrams, and coding.
Much of the initial planning and investigation of possible procedures, as well as the programming of considerable parts of the Translator, is due to Mr. E. N. Hawkins. Part of the programming of the storage allocation process was done by Mr. W. P. Gillott. The paper is published by permission of The English Electric Co. Ltd.
in The Computer Journal 3(2) July 1960 view details
in The Computer Journal 3(2) July 1960 view details
Most of the papers are written in a style and manner which seem to have become universally accepted for papers on computer programming, at least in the English-speaking world and probably in others. This style insists on a liberal dosage of impressively detailed flow charts which, considering the well-known and understandable reluctance of programmers to read their own programs much less those of others, one suspects most readers hastily skip over, willingly granting their authenticity. The flow charts are invariably accompanied by long lists of special instructions described in the private patois of the author, who seems blissfully unaware or unconcerned that his specially constructed vocabulary of acronyms may present;. rough going to the reader from the inlying provinces. Finally, the style demands long and wearisome descriptions of basic concepts (e.g., subroutine; symbolic instruction, etc.) long since familiar to the average reader, some indication of difficulties as yet to be surmounted (e.g., automatic storage allocation; easier debugging; et al). Nevertheless, the volume does give some idea of the status of automatic programming systems in Great Britain in early 1959. It also contains a concise description of the 709 SHARE operating system, and another brief account of FLOW-MATIC and MATH-MATIC. There are two interesting appendices worthy of mention. Appendix One consists of reprints of two papers by the late A. M. Turing, "On Computable Numbers with an Application to the Entscheidungsproblem", in which the "Turing machine" was conceived, and a brief corrective note on the same subject. Appendix Two contains the "Preliminary Report of ~ ACM-GAMM Committee on an International Algebraic Language", since published elsewhere.
The reviewer cannot suppress the question of whether this sort of material (Appendices excepted), so soon obsolescent or obsolete and so difficult to present adequately in short papers, deserves the effort and expense required to reproduce it between the bound hard covers of a handsome book.
in ACM Computing Reviews 2(03) May-June 1961 view details
The English Electric DEUCE grew out of an active collaboration between English Electric and NPL. The DEUCE was based closely on the Pilot ACE (Haley i956).
The initial software effort for the DEUCE lay in converting the existing Pilot ACE programs developed by NPL. Most of this work was done during 1955 in a combined effort between the users of the first three DEUCES, which were installed at English Electric, NPL, and the Royal Aircraft Establishment. This conversion work was in fact coordinated by NPL; it seems that in the mid-1950s English Electric did not see the provision of programming systems as part of their brief, although they did organize the DEUCE Users Group and a library service.
Several active programming groups were associated with DEUCE installations, and by 1958 three important interpretive schemes for the DEUCE had emerged: GIP, TIP, and Alphacode (Robinson 1959). These three schemes had complementary domains of application: GIP was, of course, the famous matrix interpretive scheme from NPL, TIP was used for calculations on vectors, and Alphacode was used for scalars.
The GIP matrix scheme was easily the most important programming system for DEUCE. Apart from its remarkably high speed, CIP was noted for its reliability. By means of check sums and other devices, complete confidence could be had in the results in spite of the inherent unreliability of the DEUCE (which had no parity checking, for example).
The TIP (Tabular Interpretive Program) scheme was in effect a variant of GIP restricted to vector operations. The system was designed by the DEUCE group at Bristol Aero Engines to simplify programming for engineers and was widely used. TIP was a rather elegant system and required no formal understanding of linear algebra. It was intended to be accessible to anyone who was familiar with a "desk machine ... and a sheet of paper ruled into rows and columns" (Robinson 1959). TIP is an interesting relic of the transition from machine language to true programming languages.
The third interpretive scheme, Alphacode, was specified by S. J. M. Denison of English Electric as an automatic coding system for naive users and for one-time jobs; Alphacode was directly inspired by the Manchester Mark I Autocode (Denison 1959). The interpreter produced programs that were typically about five times slower than conventionally coded programs, actually a considerable achievement considering the high speed of DEUCE when optimally coded.
In November 1957 a project for an Alphacode translator (as opposed to the existing interpreter) was begun (Duncan and Huxtable 1961). The aim was the exceedingly ambitious one of producing translated programs as good as hand-coded ones. The translator was developed by F. G. Duncan, working at first with E. N. Hawkins and later with D. R. Huxtable. The system came into use toward the end of 1959. It was one of the most impressive programming achievements of its day, both in terms of sheer size (22,000 instructions) and in the difficulty of producing code for a machine with a multilevel store. The translator in practice produced code that was about two-thirds as good as handwritten code, a truly remarkable achievement given the complexity and subtlety of programming for the DEUCE.
Several other programming schemes were produced for the DEUCE by other installations in the late 1950s. These included STAC, STEVE, GEORGE, SODA, and EASICODE (Robinson 1959). AH these systems were made available through the Users Group, but they do not appear to have been used as widely as the schemes already described.
The development of software for DEUCE can be summarized as follows. The existence of a large amount of high-quality software from NPL led English Electric into believing that it was unnecessary to develop further programming systems. English Electric did see the need to coordinate and distribute programs through the Users Group and to organize programming courses. English Electric's failure to make a timely provision of an autorpatic programming system for DEUCE led to a number of ad hoc developments at various DEUCE installations during the period 1957-1959, which was a wasteful duplication of effort. In underwriting the Alphacode translator, however, English Electric demonstrated that it had at last come to recognize its duty to provide programming systems for the DEUCE. In January 1960 English Electric transferred its programming staff to the Data Processing and Control Systems Division at Kidsgrove, where an automatic programming section was established under the management of F. G. Duncan (1979). At this point, machines such as the KDF 9, for which excellent software was produced, were on the horizon. Extract: Conclusions
When we compare the development of programming at the three centers -- Cambridge, Manchester, and Teddington -- there are several factors to consider. First, we must consider the quality of the programming system; this is a subjective issue that ranges from the purely aesthetic to the severely practical -- for example, from the elegance of an implementation at one extreme to the speed of a matrix inversion at the other. We must also consider the failures of the three centers, especially the failure to devise a programming system that exploited the full potential of the hardware. Finally, we must consider the influence of the programming systems on other groups; this is less subjective -- it was described in the previous two sections and is summarized in Figure 2.
Few could argue that Cambridge devised the best of the early programming systems. The work done by Wilkes and Wheeler stood out as a model of programming excellence. Cambridge made several outstanding contributions to early programming: the use of closed subroutines and parameters, the systematic organization of a subroutine library, interpretive routines, and the development of debugging routines. Perhaps the finest innovation was the use of a symbolic notation for programming, as opposed to the use of octal or some variant. It is difficult for us today to appreciate the originality of this concept.
If Cambridge can be said to have had a failure, it was the failure to develop programming languages and autocodes during the middle and late 1950s, as reflected in the second edition of Wilkes, Wheeler, and Gill (1957), of which Hamming said in a review,
It is perhaps inevitable that the second edition, though thoroughly revised, does not represent an equally great step forward, but it is actually disappointing to find that they are no longer at the forefront of theoretical coding. (Hamming 1958)]
By neglecting research into programming languages, Cambridge forfeited its preeminence in the programming field.
In the early 1950s, however, Cambridge was by far the most important influence on programming in Britain. This came about partly through the excellence of the programming system and partly through the efforts that Cambridge made to promote its ideas. Two machines (I`EO and TREAC) based their programming system directly on EDSAC, and five machines (Nicholas, the Elliott 401 and 402, MOSAIC, and Pegasus) were strongly influenced by it. It is also probably true that no programming group was entirely uninfluenced by the Cambridge work. Overseas, the influence of the EDSAC programming system was just as great, largely through the classic programming textbook by Wilkes, Wheeler, and Gill (1951) (see Campbell-Kelly 1980a).
At Manchester the programming system devised by Turing for the Mark I makes a disappointing contrast with the elegance of the Cambridge work. From the point of view of notation, it is difficult to find a single redeeming feature. Probably the only feature of real merit was the concept of dividing a program into physical and logical pages. Echoes of this idea can be discerned in today's segmented computers.
In its way, Turing's programming system did have considerable influence, for all efforts to replace it with something more suitable were curiously unsuccessful.
Thus programmers for both Mark Is and all seven Mark Iota's had to struggle with Turing's clumsy teleprinter notation throughout the life of these machines. Here is perhaps one of the most valuable lessons of this study: poor design decisions taken early on are almost impossible to correct later. Thus even when people with a Cambridge background arrived at Manchester, they were unable to make a really fresh start. By producing two successive input routines that were not much better than Turing's, they managed to combine the worst of both worlds: an unsatisfactory programming system that was not even a stable one.
The one real high spot of the Manchester programming activity was Brooker's Mark I Autocode. Brooker's achievement was the most important programming event of the mid-1950s in Britain. If Brooker had not devised his autocode at that time, programming in Britain might have developed very differently. The autocodes for DEUCE and Pegasus were directly inspired by Brooker's and had considerable notational similarities with it. Beyond the time scale of this paper, Brooker's Mark I Autocode and his later Mercury Autocode (1958) were a dominant influence on British programming until well into the 1960s, when languages such as ALGOL 60 and FORTRAN came onto the scene in Britain.
Of the three programming systems devised at Cambridge, Manchester, and Teddington, it is probably the latter that inspires the least passion. Ii the punching of programs in pure binary was an efficient method, it was also a singularly uninspiring one. Curiously, aficionados of the Pilot ACE and the DEUCE had great enthusiasm for programming these machines, which really had more to do with the joys of optimum coding and exploiting the eccentric architecture than with any merits of the programming system.
In many ways the crudity of the programming system for the Pilot ACE was understandable: the speed of events, the lack of a backing store, and so on. But perpetuating it on the DEUCE was a minor tragedy; by replicating the programming system on the 32 commercially manufactured DEUCES, literally hundreds of rank-and-file programmers were imbued in this poor style of programming. MOSAIC (Section 3.4) shows that it was entirely possible to devise a satisfactory programming system for machines of the ACE pattern; it is most unfortunate that this work was not well enough known to influence events.
NPL did, however, have one notable programming-success: the GIP matrix scheme devised by Woodger and Munday. This scheme became the sole reason for the existence of many DEUCES. The reliability of the mathematical programs produced by NPL, their comprehensiveness, and their speed have become almost legendary. A history of numerical methods in Britain would no doubt reveal the true role of NPL in establishing the methods of linear algebra as an analytical tool for the engineer.
In an interview, P. M. Woodward, one of the principals of the TREAC programming activity, recalled, "Our impression was that Cambridge mattered in software whereas Manchester mattered in hardware" (Woodward and Jenkins 1977). He might well have added that NPL mattered in numerical methods.
Because this paper has been primarily concerned with the development of programming during the period 1945-1955, Cambridge has received pride of place as the leading innovator. Had the paper been concerned principally with hardware or numerical methods, however, the ranking of the three centers would have been different. But considered purely as innovators of programming, there can be no question that Cambridge stood well above the rest.
Abstract: By 1950 there were three influential centers of programming in Britain where working computers had been constructed: Cambridge University (the EDSAC), Manchester University (the Mark I), and the National Physical Laboratory (the Pilot ACE). At each of these centers a distinctive style of programming evolved, largely independently of the others. This paper describes how the three schools of programming influenced programming for the other stored-program computers constructed in Britain up to the year 1955. These machines included several prototype and research computers, as well as five commercially manufactured machines. The paper concludes with a comparative assessment of the three schools of programming.
in Annals of the History of Computing 4(2) April 1982 IEEE view details