#IMP Language and Compiler The first published article on [http://history.dcs.ed.ac.uk/archive/docs/EMAS_IMP/document.html the IMP language and Compiler] by PeterStephens, extracts of which are quoted below, appeared in [http://history.dcs.ed.ac.uk/archive/docs/EMAS_IMP/document.html The Computer Journal, Vol 17 Issue 3 pp 216-223]. ([wiki:Self:Imp80 There is also a much more extensive document on Imp80.]) === Extracts from "The IMP language and compiler" by Peter Stephens === The development of IMP was an integral part of the EMAS project (Whitfield and Wight, 1973) to write a multi-access operating system for the ICL 4-75 computer. The language was to be based on Atlas Autocode (Brooker, Rohl and Clark, 1966) with sufficient additions to allow all the software to be written in it without resorting to assembly language. The long term intention was to enable large parts of the EMAS system to be transported to future ranges of hardware simply by recompilation. Atlas Autocode (AA) often seems, to those not familiar with this delightful and little known language, a curious starting point. "Autocode" suggests, incorrectly, a low level language, while "Atlas" implies an equally misleading machine dependence. In 1966 AA was widely used in Edinburgh University and a compiler (Bratley, Rees, Schofield and Whitfield, 1965) had been written for the University KDF9. This compiler, which was in advance of its time in that it was written entirely in Atlas Autocode, confirmed that AA was free from implementation trouble spots and reasonably suitable for system programming. Further, EMAPS was committed to supporting AA on the multi-access system, so it seemed sensible to economise in compiler writing effort by developing AA as the system programming language. It was the intention to follow the traditions of AA as far as possible and in particular to ensure 1. That keywords continued to be self-explanatory rather than cryptic. 2. That the language remained free of implementation trouble spots. 3. That facilities requiring extensive run time support were not included. 4. That the possibility of mechanical translation of IMP to PL/I should not be excluded. This last intention was designed (in 1966) to ensure that IMP programs and packages could be run at other installations throughout the world This laudable aim has been invalidated by the limited availability of PL/I compilers particularly on British machines. In spite of being designed for system programming, IMP has been used extensively in Edinburgh for applications and general purpose programming. === The IMP language === ==== Alphabet ==== The IS0 (7-BIT) character set is used: [[pre]] A . . . Z a . . . z 0 . . . 9 + - #* / < ( ) = > , . : ; ! ? % @ - & # ! | - [[/pre]] ==== Names ==== These consist of a letter, optionally followed by more letters and/or digits in any order. ==== Keywords ==== These are underlined as in ALGOL (in this publication bold face type is used), e.g. '''''real'''''. ==== Blocks ==== An ALGOL-like block structure is used. Blocks may be nested to any depth. They may be entered only via begin and left only via end. A program is a block starting with begin and terminating with endofprogram. ==== Types ==== The principal types are '''''real''''', '''''integer''''' and '''''string''''' with declarations and scope as in ALGOL. Types '''''real''''' and '''''integer''''' can be further defined by '''''byte''''', '''''short''''' and '''''long''''', subject to hardware limitations. The length of '''''string''''' variables may vary, subject to a maximum length specified at declaration. This compromise gives most of the advantages of variable length strings without introducing the inefficiency of "heap" storage. Space for variables is normally obtained from the stack at block entry. If, however, the variables are declared with the prefix '''''own''''', they are placed in a special area constructed at compile time and allocated at program load time. Initialisation of '''''own''''' variables is permitted. ==== Arithmetic expressions ==== Expressions consist of '''''real''''' and '''''integer''''' variables and constants with the operators + - * / ** () in the usual way. For example: given '''''integer''''' ''i, j''; '''''real array''''' ''a(1:n)''; '''''real''''' ''x, y'', then ''2*x*y**2 + i*(j - 1) + a(i - 1)/3.14'' is an expression. The ALGOL integer division operator is available, represented by '//'. ==== Logical expressions ==== These consist of integer variables and constants and the operators: representing \ logical not ! or !! exclusive or & and << left shift >> right shift For example: given '''''integer''''' ''i, j, k'', then ''(i << 16) ! (j << 8) ! (k & 255)'' is a valid logical expression. Logical operations have proved very valuable in writing system software. ==== String expressions ==== A string expression consists of string variables and constants concatenated together using ''.'' (period) as the concatenation operator. A string constant consists of any combination of characters within quotes except that quote itself is represented by two quotes. e.g. ''name . "has not been declared"'' A contextual string resolution is provided: e.g. given '''''string''''' ''(25) p, q, r'' ''p -> q.(S).r'' The string expression S is evaluated and located within p. The portion of p before the first occurrence of S is transferred to q, and the portion after S is transferred to r. An error condition occurs if S cannot be located within p. (See also conditional instructions.) ==== Assignments ==== Assignments take the form ''u = E'' where ''v'' denotes any variable and ''E'' an expression. If ''v'' is an integer variable, then ''E'' must evaluate to an integer expression (henceforth denoted by ''I''). No implicit rounding takes place; if required, it must be explicitly requested using the built-in function provided. If ''v'' denotes a string variable, ''E'' must be a string expression (denoted by ''S''). In the case of assignments to strings or to byte and short integers, a check is made that no truncation takes place on assignment. An alternative form of assignment ''v <- E'' suppresses the check although any resulting truncation is naturally machine dependent. ==== Conditional instructions ==== These take the form: '''''if''''' [condition] '''''then''''' [unconditional instrn] '''''else''''' [unconditional instrn] where the else clause may be omitted. A simple condition has the form: '''E1''' [cond] '''E2''', where '''El''' and '''E2''' are arithmetic, logical or string expressions. String resolution (see also above) can be used as a simple condition. The condition is regarded as true if the resolution can be completed. e.g. '''''if''''' s->p.(q).r '''''and''''' z > 0 '''''then''''' ... A compound condition consists of a number of simple conditions linked by '''''and''''' or '''''or'''''. There is no implied precedence between '''''and''''' and '''''or''''', so that brackets are required to prevent ambiguity when both operators are present. Compound conditions are evaluated from left to right but only as far as is necessary for an overall verdict of true or false to be obtained. e.g. x = 1 '''''and''''' y = 0 '''''and''''' z < 0 (x>l '''''and''''' y=O ) '''''or''''' z=O. Unconditional instructions include : assignments routine calls routine exits jumps A compound statement can be constructed after a condition using start and finish (not begin and end) as brackets: e.g. '''''if''''' ''x > 0'' '''''then start''''' ''[list of statements]'' '''''finish''''' ==== Cycles ==== The Atlas Autocode form of cycle is maintained: '''''cycle''''' ''i = I1,I2,I3'' ''[list of statements]'' '''''repeat''''' where ''i'' is an integer variable and ''I1,12, I3'' are integer expressions such that ''I2 # 0'' and ''(I3 - I1)/I2'' is an integer > = 0. The integer expressions are evaluated prior to entering the cycle and remain unaltered. Two new forms of loop control have been recently introduced. Their definitions were greatly influenced by the writings of Dijkstra (1970). The new forms of cycle are: a. '''''while''''' ''(condition)'' '''''cycle''''' ''[list of statements]'' '''''repeat''''' b. '''''until''''' ''(condition)'' '''''cycle''''' ''[list of statements]'' '''''repeat''''' Cycling continues while (until) the condition is true. Note that until implies testing the condition after the body has been traversed whereas while implies testing before a traverse is made. Thus the body of an until cycle is always executed at least once, whereas the body of a while cycle may not be executed at all. Cycles may be nested to any depth. ==== Labels and jumps ==== The conditions and cycles already described are designed to allow system programs to be written without requiring jumps or labels. The following facilities are provided to give compatibility with Atlas Autocode. Labels take the form: ''name:'' ''N:'' ''a(N):'' where ''N'' denotes an integer constant. They can only be referenced from within the block in which they are set and not within any sub-blocks. Simple labels require no declarations but vector labels require a declaration of the form '''''switch''''' ''a(N1:N2)''. Jumps take the form: In the case of ''-> a(I)'', I must be an integer expression and a run-time check is made that the corresponding label exists. ==== Structured data objects ==== A limited form of structured object has been introduced to facilitate the manipulation of tables within the language. The structure of such an object is described by a non-executable record format statement of the form: '''''record format name''''' ''([declaration list])'' e.g. '''''record format''''' ''f ('' '''''integer''''' ''i, j, k,'' '''''string''''' ''(5)s)'' All declarations (including record) are accepted within a record format, but arrays must have constant bounds. Space is allocated by a record declaration which may reference any previously declared format treated as an address from which a variable is fetched, or to which a variable is stored, according to the context of the call. Mapping functions thus enable symbolic names to be given to areas of storage outside the normal stack area allocated to the program. The pre-declared mapping functions : ''integer(I); real(I); string(I);'' ''shortinteger(I); longreal(I); record(I)'' ''byteinteger(I)'' are used to access a variable of the corresponding type whose address is given by the integer expression I. These functions are often used in conjunction with pointer variables. e.g. On the ICL 4-75 the word whose address is 72 is the Channel Address Word. To access this it is necessary to code: '''''integername''''' ''caw'' ''caw == integer(72)'' Hereafter, any reference to caw accesses the Channel Address Word. The function: ''addr (v)'' can be used to obtain the address of an IMP variable and the special mapping function: ''array'' can be used to map arrays on to data files. The mapping of arrays and records is a powerful and widely used facility which is very similar in effect to PL/I's "BASED STRUCTURE". ==== Machine code ==== It is possible to write assembly code at any point within an IMP program although, naturally, this is strongly discouraged. All the instructions are available and IMP variables and labels may be used. This seemed preferable to providing special functions to permit Supervisor to use the privileged instructions. The presence of assembly code served also to reassure those who are certain that a high level language is too "inefficient" for a supervisor program. ==== Punching conventions ==== To facilitate punching on terminals or on cards, % character is reserved as a shift character to indicate that the following word is underlined. Statements are terminated by a semi-colon or by a newline. Consequently, if a statement is to occupy more than one line, all lines except the last are terminated by the continuation symbol c. Spaces and superfluous terminating characters are ignored (except within string constants). The " (double quotes) character is not used within the language and is used by EMAS Director (Rees, 1973) as a delete character when accepting input from a terminal. Comments may be inserted by means of: '''''comment''''' ''[text]'' or '''''!''''' ''[text]'' The Atlas Autocode fault statement: '''''fault''''' ''[list of error conditions]'' ''-> label'' has been retained. Its effect is to intercept non-catastrophic errors and to restart the program from the specified label. If a fault occurs which has not been trapped, execution of the program ceases and a stack post mortem is output. An example of such a termination is given in Appendix 1. The unconditional instruction monitor can be placed at any point in the program. Its effect is to obtain a post mortem print without otherwise disturbing execution of the program. ==== IMP - A brief critique ==== The following remarks are proffered in the full knowledge that originators are often totally blind to the defects of their brain children. It seems to us that IMP has struck a reasonable balance between what is desirable and what is possible to implement efficiently. It may err a little on the side of verbosity but it remains easy to read. Its most successful features seem to be the logical operations, strings and diagnostic facilities. Real arithmetic and routine parameters have been almost completely ignored by system programmers although both features are used by applications packages. Arguments continue whether or not the IMP structure with its three types of bracketing (begin ... end, start ... finish, cycle ... repeat) produces more or less readable programs than ALGOL. Its principal failure lies in the area of contingency handling. The fault statement is insufficiently flexible for system programmers who tend to call Director's Signal mechanism directly (Rees, 1973). A system programming language requires some form of on condition that permits the resumption of the interrupted program. Purists have criticised IMP for not having a variable of type logical, and it is true that allowing bit operations on integer variables presumes a conversion between integers and bit representation. Nevertheless, IMP programs have been transferred between the ones-complement Univac 1108 and the twos-complement 4-75 without raising any problems in this particular area. A more serious obstacle to machine independent software is the use of mapping functions which can assume an addressing structure. However, mapping functions have proved too valuable for abolition or amendment to be possible. The choice of the term byte integer was unfortunate as it causes an emotional reaction, particularly among those who dislike IBM System 360 and its architecture. A neutral term such as character would have been preferable. It remains the implementer's conviction that the language would have aroused wider interest if it had been christened Implementation ALGOL or ALGOL(I) rather than IMP. ==== Bootstrapping ==== Compilers have been produced which implement substantial subsets of IMP on PDP8, PDP9, PDP11, PDP15, Modular 1 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 inputloutput 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. ==== On system programming in IMP ==== The EMAS general purpose time sharing system is notable for being coded entirely in IMP, a high level language, which was developed from Manchester University"s Atlas Autocode specifically for system programming. This paper describes the main features of the language and the implementation used for EMAS. 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"! === The IMP Compiler === ==== Compiler restrictions ==== The current EMAS compiler imposes two restrictions on the language described. a. The static depth of nested blocks must not exceed eleven levels of which not more than five may be routine ... end groupings. b. Own arrays, switches, and arrays within record formats are restricted to one dimension only. ==== Compiler diagnostic facilities ==== The compiler can operate in checking or optimising mode, the former being the default. In checking mode, additional instructions are planted to ensure that: a. No variable is used before a value has been assigned to it. b. All references to array elements are within the declared bounds. c. No truncation takes place when assigning to variables of type byte integer, short integer or string. d. Overflow is tested at every stage of every arithmetic operation. e. Any cycle of the form cycle i = p, q, r will terminate. f. Every switch label is set. g. The source line which corresponds to the object code currently being executed is known. h. Pointers are maintained to ensure a useful post-mortem can be produced in source language terms. Naturally, a program compiled with checks is very much larger and less efficient than the corresponding optimised programa factor of 3 is common. Nevertheless, the checking and diagnostic facilities greatly ease the problems of debugging large programs and have proved to be one of the most valuable features of IMP. ==== Language facilities withdrawn ==== It may be of interest to comment on three features of the original IMP specification which have been discontinued 1. Arrays of pointer variables; e.g. '''''integer name array''''' ''nu(1 : 50)''. Name arrays hold the addresses of variables assigned using the address assignment operator ''==''. These inoffensive variables proved of little use and were dropped. 2. Routine variables; These were provided in an attempt to extend the routine parameter mechanism. Declarations took the form '''''routine name''''' ''r''; '''''routine name array''''' ''ra(1 : m)''; Routines could be assigned to routine variables, e.g. ''ra(1) == select input''; ''ra(2) == select output''; and finally a statement of the form ''ra(i)(k)'' calls the routine that was last assigned to ra(i) passing k as a parameter. To enable the call to be compiled, it was necessary to restrict the routines assigned to routine variables to ones having the same parameter structure. It was further necessary to ensure that all routines assigned were global to the routine variable declarations-otherwise calls could be made on routines when their global variables were not present on the stack. These restrictions emasculated what appeared to be an interesting facility. 3. Dynamic formats; The early IMP compilers allowed arrays in record formats to have dynamic bounds. This meant that format statements had run time significance and that a dope-vector was required with each format. The price in execution time was judged to be too high for the advantages provided. === 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 [http://history.dcs.ed.ac.uk/archive/languages/atlas-autocode/imp9.imp.txt the Atlas Autocode compiler for KDF9]. H. Dewar wrote the [http://history.dcs.ed.ac.uk/archive/languages/imp-pdp15/hdcomp.txt 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 [http://history.dcs.ed.ac.uk/archive/languages/skimp/keithsimp_dec6imp11s.html PDP11] respectively. The SKIMP/[http://history.dcs.ed.ac.uk/archive/languages/hal/interdata/hal70.i15 HAL] bootstrapping method was developed from [http://history.dcs.ed.ac.uk/archive/languages/skimp/skimps.imp.html 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.