IMP77

IMP77 is a portable version of Edinburgh IMP, the ALGOL-descended systems language in which the University of Edinburgh wrote its EMAS multi-access operating system. Peter S. Robertson of the Department of Computer Science wrote it and documented it in a reference manual dated December 1977. What made IMP77 last was its compiler more than its syntax. Robertson split compilation into a language-specific front end and machine-specific back ends that communicated through a carefully designed intermediate code, I-code. That split let one language follow Edinburgh onto PDP-11s, Interdata and Perkin-Elmer minicomputers, the VAX, 68000 workstations and the ARM. In 2002 the same structure supported a revival on x86 PCs.

History & Origins

From Atlas Autocode to IMP

IMP’s ancestry runs through Atlas Autocode, Tony Brooker’s ALGOL-like language for the Manchester Atlas. In the 1960s Edinburgh adapted Atlas Autocode into IMP to serve as the implementation language for the Edinburgh Multi-Access System (EMAS), and the name comes from that role. The IMP80 manual’s historical introduction, by Peter D. Stephens, lists the changes made to Atlas Autocode along the way: the ISO character code, logical operators, %byte %integer and %short %integer, records, text handling “specifically to aid writing of command interpreters”, and pointer variables for storage outside the compiler-managed stack.

When EMAS was finished, responsibility for the system and its IMP compiler passed from the Department of Computer Science to the Edinburgh Regional Computing Centre (ERCC). Stephens describes what followed. The Computer Science department “encountered a variety of machines and wrote IMP compilers for a substantial proportion of them”, and “as befits an academic department these compilers contained novel features and gradually diverged from EMAS IMP and from each other.”

Robertson’s IMP-77

IMP77 was the department’s answer. The first edition of its reference manual, The IMP-77 Language, is dated December 1977 and describes the language “as implemented by Peter S. Robertson”. Its introduction says the language was designed for EMAS “but has since been used successfully for implementing systems, teaching programming and as a general-purpose programming language on many different machines”. It also admits that “the main disadvantage of IMP is that it is not currently in widespread use.”

The compiler work grew into Robertson’s PhD thesis, The Production of Optimised Machine-Code for High-Level Languages using Machine-Independent Intermediate Codes, accepted by the University of Edinburgh in 1981. Its abstract reports that I-code “has been used successfully to develop optimising and diagnostic compilers for the IMP77 language on a large number of different computer systems.” The thesis says I-code was designed specifically for IMP-77 and is not meant as a universal intermediate code. It adds that I-code, with minor extensions, had also been used in an ALGOL 60 compiler and was then proving viable in Pascal and Fortran 77 compiler projects. It also laid groundwork for a project on portable SIMULA compilers.

IMP77 and IMP80

By 1980 the department’s IMP77 and the ERCC’s EMAS IMP had drifted far enough apart that code did not always move between them. Stephens writes that “in 1980 a stock-taking was instituted”, and this produced IMP80, a common core that compilers would support. The Edinburgh IMP80 Language Manual, edited by John M. Murison and dated October 1981, draws on the third edition of The IMP-77 Language (1980). It names only two IMP80 implementations: EMAS IMP80 on the ICL 2900 by Peter Stephens, and “IMP77, implemented on several different machines by Peter Robertson, Lattice Logic Ltd., Edinburgh.”

Design Philosophy

The 1977 manual states two major design aims:

1. “The language should compile to efficient machine code.”
2. “The syntax of the language should be verbose rather than obscure.”

Relative to ALGOL 60, IMP-77 “adds program structuring, data structuring, event signalling, and string handling facilities, but removes (or retains in a modified form) intrinsically inefficient features such as the ALGOL 60 name (substitution) parameter.” Input and output are not part of the language. They come through the external-procedure mechanism, so they are “open-ended and can be defined as required”, with a standard set of procedures such as READ SYMBOL, PRINT STRING, WRITE, NEWLINE and SPACES.

IMP also takes run-time checking seriously. The manual notes that most IMP systems provide “comprehensive compile-time and run-time diagnostics, together with an option to suppress generation of run-time checks when compiling tested programs”. Diagnostics were a stated aim of Robertson’s thesis alongside code size.

Key Features

Keywords by underlining

IMP was designed for an underlined alphabet. Keywords were underlined words, and in ASCII source the percent sign is a “shift” that underlines every following letter until a non-letter appears. Spaces are ignored outside quotes, so these two lines mean the same thing:

1
2

%STRING (7)%ARRAY %NAME P
%STRING (7)%ARRAYNAME P

Identifiers can therefore contain spaces (CASE 2B and SKIP SYMBOL are legal), and lower case is equivalent to upper case outside quotes. Statements end at a newline or semicolon. A line continues after a comma or after the keyword %c.

Control structures

IMP-77 has %if ... %then ... %else, %unless, and %start ... %finish blocks for multi-statement conditionals. Loops are built from %cycle ... %repeat with %while, %until and %for forms, and %exit and %continue leave or restart a cycle. Short forms attach a condition or loop to a single instruction:

1
2
3

A(J) = 0 %for J = 1, 1, 20
READ SYMBOL(S) %until S = NL
SKIP SYMBOL %while NEXT SYMBOL = ' '

For computed jumps there are switch vectors, arrays of labels that can be indexed by expressions, even by character ranges such as %switch LET('A':'Z').

Four kinds of procedure

IMP-77 has four kinds of procedure:

Maps can sit on the left of an assignment, which gives IMP a structured form of the address arithmetic that systems code needs. Predicates are called wherever a condition is expected. Parameters are passed by value or by reference (%name), and procedures can themselves be passed as parameters.

Records and strings

Records are declared from formats and can hold pointers to records of the same format. Elements are selected with an underscore:

1
2
3

%record %format F(%integer X, %record(F) %name LINK)
%record (F) R
! R_X, R_LINK_X, R_LINK_LINK_X ...

Strings have a declared maximum length, as in %string(7). Besides concatenation with ., IMP has string resolution, a pattern-matching assignment written with ->:

1
2

S -> T.(",").U                       ! split S at the first comma
%if WHO -> ("SIR ").WHO %then KNIGHT = 1

A failed resolution used as a statement signals an event. Used as a condition, it is simply false. The <- operator performs a “jammed” assignment that truncates a string to fit its destination instead of faulting.

Events

IMP-77 signals synchronous errors such as a failed resolution or an array-bound fault as numbered events, and blocks can trap them:

1
2
3

%on %event 9 %start
   ! end of input reached
%finish

An event that is not trapped in the current block is propagated outward through the dynamic chain until it is caught or reaches the outermost block, where it is reported as a fault. EVENT, SUB EVENT and EVENT INFO describe the most recent event, and programs raise their own with %signal %event.

A short example

The following program is illustrative. It uses only constructs described in the 1977 manual and has not been compiled for this page:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

%begin
   %integer I, TOTAL
   TOTAL = 0
   %for I = 1, 1, 10 %cycle
      TOTAL = TOTAL + I
   %repeat
   PRINT STRING("Sum of 1 to 10 is ")
   WRITE(TOTAL, 0)
   NEWLINE
%end %of %program

The I-code Compilers

Robertson’s compilers were built in passes. A machine-independent first pass parsed IMP-77 and emitted I-code. A machine-specific second pass turned I-code into code for one processor. A third pass, which the thesis says was added “to simplify the generation of versions of a compiler for different operating systems”, handled object-file formats and system conventions. Robertson notes that “the extra phase could be used for other purposes as well.”

The Edinburgh Computer History Project archive keeps second and third passes for the PDP-11, Interdata 7/32, Perkin-Elmer, ARM and Intel. The thesis shows example code for the Data General Nova, DEC PDP-10, PDP-11 and VAX-11/780, GEC 4080, ICL 2900 and 4/75, Interdata 7/16 and 7/32, and Perkin-Elmer 3200. It describes these as machines “for which code is demonstrated”, which does not necessarily mean each one had a production compiler.

Measuring the optimiser

The thesis measures code size, not speed. Appendix A3 compares optimisations on the Interdata 7/32 and DEC PDP-11/45. In one deliberately trivial example, a program that declares %integer %array A(1:1000) and assigns A(1) = 0 compiles to 30 bytes of 7/32 code with all array optimisations enabled and to 170 bytes without them. Robertson immediately warns that “a reduction of 82% is not to be expected on more typical programs”. He left execution time out of the figures on purpose. On the systems he used, timing could not be measured more accurately than about plus or minus 5%, and longer runs spent much of their time in system I/O routines.

Evolution

• 1977: first edition of the reference manual.
• 1978-1980: code generators for Interdata and Perkin-Elmer 32-bit machines; the third edition of The IMP-77 Language in 1980.
• 1981: IMP80 defines a common subset, with IMP77 as one of its two named implementations.
• 1980s: the VAX/VMS IMP77 compiler and the APM’s 68000 compiler, which follows VAX/VMS IMP77 as defined in the manual’s third edition. The front end’s revision log runs from July 1984, when its size limits were set to match the “V8 production VAX compiler”, to version 9.18 in February 1988, in a copy copyrighted by 3L Limited. An ARM back end by Robertson followed. Its revision log begins in October 1987, it was compiling natively on the Acorn A310 by June 1988, and the archived copy is likewise copyrighted 3L Limited, 1988.
• 2002-2003: Andy Davis’s x86 compiler. Its November 2002 README describes a full IMP-77 compiler for MS-DOS, or a Windows command box, that produced 16-bit OMF objects and needed at least an 80186. It had one major gap: %on %event blocks did not work. Version 1.03 of an Intel 80386 pass 2 followed in October 2003. Its header credits the original to “Copyright 1977-1980 Peter Robertson”. Wikipedia says this revival also covered Linux. The archived README itself mentions only DOS and Windows.

Current Relevance

IMP77 is historical. No institution maintains it, but it is the only form of Edinburgh IMP that still has a native compiler on current hardware. The Edinburgh Computer History Project archive hosts the 1977 manual, Robertson’s thesis, and compiler sources for several targets. Rosetta Code’s language page describes the current Imp77 compiler as “a hobbyist revival”, still partly under development and lacking the library support and run-time diagnostics of the Edinburgh implementations. Rosetta Code lists only a handful of Imp77 solutions. There is no official or community Docker image.

Why It Matters

IMP77 is an early, well-documented case of the retargetable compiler, and a real one: one front end, an intermediate code designed around a real systems language, and separate back ends for very different machines of the late 1970s and 1980s. Robertson’s thesis compares I-code with UNCOL, Janus, BCPL’s OCODE, Pascal’s P-code and Z-code. Unlike most of those codes, which he says were designed to permit interpretation, I-code’s prime aim was compilation into efficient machine code. Its central argument is that “carefully designed machine-independent intermediate codes can be used to generate viable optimising and diagnostic compilers”. Many modern compilers use the same split between front end, intermediate representation and back end.

IMP77 also preserves the Edinburgh view of a systems language. It is verbose on purpose and checked at run time by default. The wider IMP tradition, in Stephens’s words, also allowed “machine coding … at any point in the program” when hardware demanded it. Those choices let a small university community write operating systems, compilers and teaching software in one language across many machines.