to perform optimisations that can be better done by the programmer. No attempt is made to move constant operations out of loops, and common sub-expression optimising is restricted to expressions which cannot be further simplified by the programmer.

Bootstrapping Compilers have been produced which implement substantial subsets of IMP on PDP8, PDP9, PDP11, PDP15, Modular I and Univac 1108 machines.

The easiest way to produce an IMP compiler for a new machine requires EMAS or some other large IMP system. The most suitable existing IMP compiler is altered to produce object code for the new machine. This compiler compiles itself and its supporting input/output routines using a binary output routine that produces cards suitable for loading onto the new machine. Eventually this new compiler compiles itself on the new machine to produce a self-supporting IMP compiler.

Where a suitable large IMP system is not available, the SKIMP bootstrap method is used. SKIMP is a subset of IMP (roughly the Atlas Autocode compatible subset), and a compiler exists written in SKIMP to produce hypothetical assembly code (HAL) for an austere, one accumulator, three index register machine. Most of the compiler support material is written in SKIMP and exists in source and compiled (HAL) form. HAL has been designed to be assembled by most current macro assemblers. To implement SKIMP on a new machine, it is necessary to write the macros to enable the HAL version of the SKIMP compiler to be assembled, and also to write a small amount of input/output software in machine code. Once the HAL version is operational, it can be used to bootstrap an orthodox compiler or to improve itself by iteration. The IMP compiler for Univac 1108 was produced via this route in less than six months.

The efficiency* of IMP There is no doubt that EMAS has gained immensely by being written in IMP, yet the question often asked by visiting system programmers is 'How efficient is IMP?' This question is not easy to answer.

Two routines in EMAS and twenty in the compiler have been hand-coded. The gains in performance or reductions in size have varied from an encouraging 2 per cent to a rather discouraging 40 per cent. The majority have fallen into the 10 per cent to 20 per cent range. One routine in EMAS—the interrupt analysis routine—was originally written in assembler code. This routine has recently been rewritten in IMP and this time the IMP version is smaller by 11 per cent and presumably faster by a like amount. It is probably fair to conclude that the IMP compiler produces code about as efficient as assembler written by programmers under the usual pressures. Both of these fall short of the optimum possible.

In the matter of variable space, the advantage seems to lie with IMP. The stack system economises on storage by allocating it only to those routines currently active. There is no reason why assembler programmers should not use a stack, but in practice they usually prefer to allocate private storage to each subroutine. The total local variable space required by the routines of the current EMAS supervisor is 17848 bytes, but a stack of 3000 bytes has proved adequate, giving a substantial saving of 14848 bytes. For paged software, the stack system has the added attraction of economising on page faults.

Programming effort The work described in this paper took the author about four years spread over the years 1967-1972 inclusive. The production of the 1108 compiler took about six months. It is estimated that a tolerable compiler could be produced for any conventional machine in about the same time. A further period might be required to improve the object code to the standard of the current EMAS compiler, but much would depend on the order code of the new machine.

On system programming in IMP All members of the EMAS project agree that working in a high level language was a great advantage. The volume of coding was greatly reduced—a listing of all the system source code will fit in an average briefcase and still leave room for sandwiches. This meant that the programmers working on the system could be reasonably familiar with all the code, not just their own section. Consequently, a system crash could be diagnosed and solved by one programmer rather than a committee. The checking facilities pinpointed many (but alas not all!) coding errors before they appeared as mysterious, transient bugs. The runtime diagnostics were valuable to the subsystem writers, although of considerably less value in detecting an error in, for example, the page fault routine.

Probably the most valuable feature of IMP was the encouragement it gave to structured programming. Within the structure, an unsatisfactory routine or component could be identified, redesigned and recoded in a short time, without disturbing the rest of the system.

The EMAS programmers who had previous experience of high-level languages adapted easily to system programming in IMP. They produced compact, highly structured programs which were easy to maintain or amend despite defects in commentary and/or documentation. They seldom worried about the efficiency of object code produced by the compiler, but their programs generally performed well. This group included the most productive programmers working on the project. Programmers with a background of assembly languages were less happy with IMP and seldom used its more advanced features such as recursion. They produced well commented and documented programs that nevertheless proved difficult to maintain since they lacked structure. This group worried about the efficiency of object code produced by the compiler to the extent of examining the listings of code produced, yet their programs were often large in size and slow in execution. Some of the least productive programmers were included in this group.

In view of our experiences with IMP, it is demoralising to thumb through the 'situations vacant' columns of the newspapers and read that one has no chance of being recruited to write the 'software of the future' without 'several years experience of assembly language programming, preferably on an IBM 360'!

Acknowledgements The debt to the designers and implementers of Atlas Autocode is as large as it is obvious. Particular credit is due to P. Bratley, D. Rees, P. Schofield and H. Whitfield who wrote the Atlas Autocode compiler for KDF9.

H. Dewar wrote the IMP compiler for the PDP9 and PDP15 machines while S. Hayes, N. Shelness and K. Yarwood contributed IMP compilers for the PDP8, Modular I and PDP11 respectively. The SKIMP/HAL bootstrapping method was developed from a teaching project designed by D. J. Rees. The above, and many others too numerous to mention individually, contributed ideas and suggestions, or joined in the heavy but good-natured criticism with which innovations were invariably received.

Appendix 1 The following example shows the diagnostics given after an array bound exceeded fault with the given program and data.

Program 1 %BEGIN 2 %INTEGER GIVEN,SQ 3 %INTEGERFNSPEC MAX FACTOR(%INTEGER N)