Contact us Heritage collections Image license terms
HOME ACL Associates Technology Literature Applications Society Software revisited
Further reading □ OverviewAssessingSystem OverviewPreprocessor DialectsExecution SpeedsAlgol Paper No 11Man or Boy?Algol LibraryAlgol Bulletin 1
ACD C&A INF CCD CISD Archives Contact us Heritage archives Image license terms

Search

   
ACLApplicationsAlgol :: Algol System
ACLApplicationsAlgol :: Algol System
ACL ACD C&A INF CCD CISD Archives
Further reading

Overview
Assessing
System Overview
Preprocessor Dialects
Execution Speeds
Algol Paper No 11
Man or Boy?
Algol Library
Algol Bulletin 1

Writing an Algol Compiler for the Atlas

Bart Fossey and Bob Churchhouse

December 1963

It was clear early on that the interest in Algol in the universities was sufficiently high that an Algol Compiler was needed on the Chilton Atlas that could handle programs originating from the Elliott and English Electric families as well as from Ferranti machines. A visit was made to Manchester in December 1963 and the original proposal was that a new compiler was needed written at the Atlas Computer Laboratory. The two papers here are the proposal by Bob Churchhouse to write a compiler and the notes on a visit to Manchester by Bart Fossey and Bob Hopgood on the 11 December 1963. In those days there was a flight schedule from Abingdon airfield to Manchester using an old Dakota. On the return trip there was fog in Abingdon and the plane had to land in Bournemouth. Then a long wait for a car to drive to Bournemouth and back from Abingdon.

A subsequent trip by Bob Hopgood and Alex Bell received a more positive response from Robin Kerr and John Clegg. In consequence, the Chilton compiler was abandoned in favour of enhancing the I.C.T. compiler

THE CASE FOR WRITING AN ALGOL COMPILER

1. The need for an ALGOL compiler. ALGOL is an international programming language, already important and no doubt becoming more and more so during the next few years. A computer laboratory with a status such as ours ought to have an ALGOL compiler simply because ALGOL is an important language. In addition, because of our responsibilities to the Universities and C.A.T's we should try to provide a good service for running computer programs which they have developed. Two of the main machines being provided for the Universities and C.A.T' s, KDF9 and Elliott 803 use ALGOL as their main autocode language. Some Government establishments (Winfrith, Culham, N.P.L.) will be having KDF9's and exchange of programs between us and them will be greatly facilitated if we have an ALGOL, compiler.

2. The Manchester ALGOL compilers. The case for the ATLAS Laboratory having an ALGOL compiler is very strong. It is not, however, obvious that we need to write a compiler ourselves. Two ALGOL compilers are being written in Manchester for ATLAS. One is being written by Dr. R. Kerr, of I.C.T; the other by Dr. D.J. Morris of the University Computing Laboratory. On 11th December, 1963, E. B. Fossey and F. R. A. Hopgood of the Atlas Laboratory visited Manchester to find out the details of these two compilers. Their report is attached. Briefly their conclusions are:

  1. the Morris compiler is being written mainly as an exercise and there is no hope of the Atlas Computer Laboratory using it.
  2. Both compilers are being written using Brooker's compiler compiler which can result in inefficiency of the recognition processes in the compiler.
  3. The Kerr compiler might be quite fast in its compilation but the object code produced is likely to be poor - with virtually no optimisation at all.
  4. The input to the Kerr compiler is tied firmly to 7-hole paper tape. We would want various alternative inputs:
    1. cards - for our own use;
    2. 8-hole paper tape, for KDF9 users;
    3. 5-hole paper tape, for Elliott 803 users.

If we don't write our own ALGOL compiler then we must write a pre-processor for each of (i), (ii), and (iii). This might take 3 - 6 man-months.

3. Points against writing our own ALGOL compiler. There are two principal objections:

  1. two compilers are being written at Manchester, one of which (Kerr's) might be usable if we write 3 pre-processors (cost about ½ man year);
  2. It would require 3 of our senior programmers for a year to write an ALGOL compiler. This represents a considerable percentage of the programming effort of the laboratory. (Taking all factors into consideration about 20% of the laboratory's programming effort would be involved.)

4. Counter-arguments to the above points.

  1. The Kerr compiler will produce poor object code unless Kerr puts in a lot of optimisation. He is unlikely to do this. He seems to have underestimated the problem and, in any case, he is probably going back to New Zealand next year, and so won't have time.
  2. Of the three programmers working on the ALGOL project two will be full-time (Hopgood and Bell). Fossey will be about half-time; he will continue to look after HARTRAN, mainly as an organiser. He will also assist the Rutherford Laboratory people to get their Bubble Chamber programs on to Atlas and will retain an interest in the Information Retrieval project proposed by Euratom (in which A.E.R.E. Library may become involved).

If we use Kerr's compiler we must write three pre-processors. This might take Hopgood (say) 3-6 months. From then on every time we use the ALGOL compiler we lose machine time in two ways:

  1. we must use the pre-processor;
  2. we have to use an inefficient object program.

Thus, our saving of 2 - 2½ man years would be offset by a loss of 10% (at least, a conservative estimate) machine time on all ALGOL programs.

5. Further points in favour of our writing an ALGOL compiler. In addition the above counter-arguments there are some other points in favour of our writing an ALGOL compiler.

  1. It would be very difficult, if not impossible, ever to make any changes (improvements!) in Kerr's compiler.
  2. Hopgood is very keen to write an ALGOL compiler and his experience or S2 well qualifies him for this. Fossey and Bell are more than happy to join in. Fossey's experience on the Atlas Fortran will be very useful and for Bell it should prove a major experience to work on a large project alongside two experienced programmers.
  3. If, as seems very likely, this team could produce a good ALGOL compiler in about a year the reputation of the Atlas Laboratory would be enhanced considerably.

6. Conclusion. I have no doubt whatsoever that we should write our own ALGOL compiler and I think that we should start work on it as soon as possible (1st January 1964 seems a. good date!). Hopgood should be formally in charge of the project, with Fossey and Bell working with him.

R. F. Churchhouse, 20th December, 1963

REPORT OF A VISIT TO MANCHESTER UNIVERSITY

ALGOL Compilers for Atlas

1. Introductory

The Atlas Computer Laboratory is likely to receive work written in ALGOL from several universities. Not only does the Atlas Computer Laboratory need a compiler for ALGOL but it is also strongly involved in the need for a compiler capable of processing the two more widely used implementations of ALGOL. These are the English electric compiler for their KDF9 machine, and the Elliott 803 ALGOL compiler. In addition, some programs written specifically for the I.C.T. ALGOL compiler for Atlas may also arrive for execution by the N.I.R.N.S. Atlas.

Language Compatibility

From the outset we are faced with a problem of language compatibility, not brought about so much by varying the interpretation of the language defined in the ALGOL 60 report, but rather incurred because of hardware limitations. In addition the decisions in the different compilers to treat input and output in particular ways leads to some further incompatibility. All Elliott 803 programs are coded at source on five hole paper tape and there is no real distinction between basic symbols and other identifiers. The treatment of input/output is by extension to the language, whereas both I.C.T. and English Electric make use of library procedures (a more satisfactory solution) but even these are not precisely equivalent. the source language is written on seven hole paper tape for I.C.T.'s Atlas implementation, but on eight hole paper tape for English Electric's implementation.

3. Possible Solution

If the I.C.T. compiler were sufficiently flexible, it might be possible to treat the three source languages by a single compiling program, providing the source language were translated into a more condensed but uniform intermediate language. the flexibility required of the I.C.T. compiler would be just that needed to enable it to process from this intermediate language.

Secondly, if the I.C.T. compiler were not too inefficient both in compiling and in the object code produced, the case for the Atlas Computer Laboratory to write its own ALGOL compiler would be very hard to justify, unless the volume of work from the Universities proved to be more than, say, 10 hours per week in ALGOL alone.

In diagram form we need:

ICT ALGOL KDF ALGOL 803 ALGOL ? ALGOL INTERMEDIATE ATLAS ALGOL COMPILER ASSEMBLY AND EXECUTION OPTIMSER

4. Approach to I.C.T. about their ALGOL compiler

On Wednesday, 11th December 1963, Messrs. Hopgood and Fossey visited Manchester University for discussions with Dr. R. Kerr of I.C.T. Ltd., who is in charge of the I.C.T. Algol compiler project. Later in the day they spoke to Dr. D. J. Morris of the University Computing Machine Laboratory.

5. I.C.T. ALGOL compiler

The I.C.T. compiler is split into two stages, a recognition stage roughly corresponding to the converters which Hopgood and Fossey had in mind. However, Kerr claimed it would be very difficult to allow other pre-processors to produce output to enter the. second stage. His argument was based on his experience with Mercury Autocode, where other people had transformed the language by being allowed to access the inner stages. It was clear he was reluctant to give us more assistance than to require a pre-processor to leave its output in the true I.C.T. ALGOL form. So far as the supervisor is concerned, this means defining an output stream as an input stream for a subsequent job, not too easy for an organisation such as the Atlas Computer Laboratory. Actually producing the output paper tape might prove probably the best procedure!

No consideration has been given to alternative peripheral representations of ALGOL and thus the I.C.T. ALGOL compiler is very rigorously tied to seven hole paper tape input. This is very unfortunate since underlining indicates basic symbols, and for card input the only alternative seems to be the inclusion of the symbol within parenthesis, whether by apostrophes or special underline markers is not really relevant.

The compiler was quoted as having a speed of 1000 instructions executed per instruction compiled. This seemed good, giving about 500 instructions compiled per second. He hoped to improve the compiling techniques to give 700 instructions compiled per second. The object code was not very clean, but even so for jobs requiring little or no execution this speed of compiling would be more than acceptable. (We learned from Dr. D.J. Morris that these figures were likely to be over optimistic by as much as a factor of 2, and the figure 250 instructions per second was more probable. Even so this would be acceptable.)

Broadly speaking the compiler restricts the ALGOL language in much the same ways as do the English Electric and Elliott 803 versions, for instance,

  1. No integer labels
  2. No dynamic own arrays

Its size is expected to be about 16K maximum, and as it is a compile and go system no binary output has been planned as yet. There is very little optimisation in the main senses,

  1. detection of common sub-expressions
  2. no index optimisation
  3. no detection of store/load conflicts

and certainly nothing of the FORTRAN type loop optimisation. Kerr states that some optimisation, which he regards as a fairly simple operation (!) will be included at a later date.

The compiler may be working by the end of 1963 but Dr. D.J. Morris thinks Easter 1964 is a more realistic date. Documentation includes:

  1. I.C.T. CS377 Little more than ALGOL 60 report
  2. Atlas Algol Compiler. Provisional specification of input/ output procedures.
  3. Provisional Reference Manual for Atlas Algol: - about to be published by I.C.T. in CS series.

6. Manchester University ALGOL Compiler

This is being produced under Dr. D.J. Morris' supervision more as an exercise in efficient compiling processes. It is not official nor is it expected before the I.C.T. compiler. Easter 1964. is the target date for its completion.

Both this and I.C.T.'s official compiler are being produced using the compiler compiler of R.A. Brooker. The essential point is that both compilers are defined in terms of phrases, the choice of which can critically affect the efficiency of the recognition processes in the compiler.

There is no hope of the Atlas Computer Laboratory using this compiler.

7. Conclusions

There does not seem to be much support for the idea of constructing a pre-processor for either the official I.C.T. compiler or for the unofficial Manchester University research exercise. It would be virtually pointless writing a special compiler for both Elliott 803 and KDF9 ALGOL codes.

The two remaining solutions are:-

  1. the production of pre-processors whose output could be converted to an input stream for the I.C.T. ALGOL compiler or whose output could be on seven hole paper tape for subsequent processing by the I.C.T. compiler.
  2. the production of a complete ALGOL compiler capable of taking a variety of input language representations by being split into three parts:
    1. Pre-processor
    2. Compiler
    3. Optimser (optional)

There is little doubt that of these the latter is slightly more attractive, both because we have then direct control over the efficiency of the compiling and also the object code, and also because, if properly designed, the compiler would be more easily extensible to cope with other implementations e.g. Burroughs ALGOL.

E. B. Fossey 15.12.63

⇑ Top of page
© Chilton Computing and UKRI Science and Technology Facilities Council webmaster@chilton-computing.org.uk
Our thanks to UKRI Science and Technology Facilities Council for hosting this site