IMP(ID:512/imp002)

Extensible dialect of ALGOL-60 

• Country: us
  • languages for us
  • us/1965
• Began: 1965
  • Languages for 1965
  • 1960s languages
  • Third generation
  • Early Cold War
• Published: 1965
  • 1965
• Type:True ALGOL60s
  • True ALGOL60s
• Sammet:MLT
  • MLT
  • MLT/1965
  • MLT/us

Irons, Edgar T. "Experience with an Extensible Language" view details Abstract: An operational extensible language system is described. The system and its base language are appraised with respect to efficiency, flexibility, and utility for different categories of users. DOI Extract: Introduction
A family of extensible languages which have been used for general programming in the IDA-CRD computing center for several years is presented, and aspects of this experience which are of general interest are examined. One of the principal incentives for the language system was to produce a language and compiler which was a "real world" tool: one which was suitable for general programming use (particularly for "system programming" including programming of the compiler) and whose compiler was good enough to compete with standard commercial software.
Other hopes for the project were to use the mechanisms for extensibility to produce an "elegantly bootstrapped" compiler, to find formal systems for specifying the translation processes (particularly code optimizing processes), and yet to maintain a conciseness and simplicity of devices which allow the use of the more interesting properties of the system by users of average sophistication.
The language system, which has come to be called IMP, began in early 1965 as a compiler, written first in machine language and then in its own language, for the Control Data 1604 computer. As plans developed for replacing the 1604 computer with a 6600, the compiler was carried over to the 6600 in two versions, one each for the central processor and peripheral processors, and was used exclusively for the programming of the CRD time-sharing system, which has been in continuous use since late 1967 at CRD.
The IMP language has been in general use on the 6600 since then, suffering somewhat from economies of implementation, but nonetheless a productive tool. The most recent work on the language system has been to consolidate lessons learned from the first implementations by reorganizing and reprogramming the compiler to provide a firm base for further work and a more gentle and sympathetic servant for everyday tasks.
Extract: The IMP Language
The IMP Language
A complete description of the IMP family of languages is not required for this paper, but we shall describe some of the facilities it contains, with details where appropriate to facilitate further discussion. In brief, the language is ALGOL 60 except: without block structure; with completely dynamic storage of arrays; without type-dependent operators; with basic list processing capabilities; with syntactic extensibility; and including recursively callable procedures where the recursive capability is specifically requested.

By way of example, the complete program



is composed entirely of the definition of a subroutine which locates its parameter A in the vector WORDS if it occurs, and otherwise appends A to WORDS. Before the first execution of the subroutine, the vector WORDS is empty.
The constructions which have been used in this program include most of the basic ones and are described briefly here. Following each IMP expression, where applicable, is an equivalent ALGOL 60 construction in parentheses, as well as a brief statement of the meaning of the expression.



In the subroutine APPEND, the vector WORDS is assumed to contain N items. The vector is initially empty and the fact that all variables are initialized to zero is used for N. Each time APPEND is called, the parameter A is compared with each item in WORDS. If A matches an items its index in WORDS is the value of APPEND. If not, A is added to the end of WORDS, N is made one larger and is compared with the currently allocated size of WORDS which by convention is addressed as the rightmost 18 bits of the (-2) item of every vector. In the event that WORDS will be too small, function REALLOT is invoked to make the vector WORDS larger by 100 words.
Extract: Syntactic Extensions
Syntactic Extensions
The grammar for the IMP language is a context-free grammar [3], and the extension mechanism allows specifications in a notation which is isomorphic to such a grammar.
The associated parsing procedure is a refinement of that in [8]. However, considerable attention has been given to both the extension notation and to the structure of the base grammar so that for simple extensions only the essentials of the extension need to be specified and no knowledge of the base grammar is required.
The most general form of a syntactic extension is exemplified by the definition of a right assignment operator:

EXPR :: (A,EXPR) → (B,NAME) :: 'B ← A'


This extension specifies that the syntactic entity EXPR may be formed from three items in sequence:
1. A syntactic entity EXPR (labeled A).
2. The symbol →.
3. A syntactic entity NAME (labeled B).
(The equivalent production given in the notation of the ALGOL 60 report [10] is <EXPR>::=<EXPR> →<NAME>.)
The expression B ← A gives the semantic portion of the extension. It must be an expression from the base language including all extensions up to this one. This expression specifies the effect that an occurrence of the defined construction will have in a program. The effect is that of the expression B ← A, but with A replaced by the NAME (comprising item 3 above) and B replaced by the EXPR (item 1). For example if X + Y → Z is an occurrence of the construction in a program, its effect is that of B ← A with A replaced by X + Y and with B replaced by Z, i.e. Z ← X + Y. Thus A and B are formal parameters of the defining expression A ← B. They are marked as such by their association with the syntactic items in the definition: A in (A, EXPR) and B in (B, NAME ).
An extension such as the one given above is similar to a procedure declaration in ALGOL 60, except that the syntactic form of a call of the procedure is fixed in ALGOL 60, whereas in IMP it is separately specified in each declaration.
Thus the above extension is like the ALGOL 60 declaration procedure ASSIGN(A, B); B := A, except that the syntactic form for a call of the procedure is X → Y instead of ASSIGN(X, Y). In IMP, the parameter passing mechanism is implemented by literally copying the procedure body in place of the call, but replacing formal parameters in the body by actual parameters in the call. Thus the calling mechanism corresponds exactly to the ALGOL 60 call by name. Since this calling form is the most general of those in current use, it allows the FORTRAN "address passing" call or the ALGOL 60 value passing call to be implemented within the existing framework. The call of a definition can be implemented by actual substitution (as usually done for macros in assemblers) or by generating only once a closed-form subroutine which is used for each call (as is generally done for compiler-generated subroutine definitions). Which of these is more efficient is usually determined by the length of the definition.
The ability (or requirement) to specify the syntactic form for a call individually for each subroutine can be a mixed blessing, however. The power of this facility is great enough to allow the whole compiler (including the syntax for syntax) to be specified within its framework. However, many extensions are so simple in form that the requirement to specify syntactic types is too great, especially since most users will not be aware of the syntactic names associated with constructions of the language. Therefore, it is permissible to write an extension leaving out any or all of the syntactic names. The above extension rewritten in this way is:
(A) → (B) :: 'B ← A'
The missing syntactic specifications are filled in automatically. Some care must be taken, however, in the design of the base language to make this automatic filling in of syntactic types produce reasonable results. Since nearly every construction in IMP is of the type EXPR (or expression), the convention is adopted that the syntactic type EXPR will be filled in for all missing specifications, except that, to avoid ambiguities and to select right nesting for unparenthesized expressions, the left-most of the constituent categories will be chosen as PRIMARY (roughly including names and parenthesized expressions).
So the result of presenting the short form of the definition (A) → (B) :: 'B ← A' is the same as having written:
EXPR :: (A, PRIMARY) → (B, EXPR) :: 'B ← A'
For this example the automatic choices are not quite the best, since they will usually require parenthesizing the left side when using this definition (X + Y → Z will be interpreted as X + (Y → Z)). Also we have allowed an expression to be used on the right where we probably would like a name. (What does A → (P + Q) mean?)
Furthermore, a consequence of having the same syntactic
category for all constructions would be that the
operators + and ? occur at the same priority level, so that
A * B + C would mean A * (B + C) and not (A * B) + C,
as would be more natural to the mathematician. To establish a system of operator priorities, a syntactic category is established for each priority, perhaps with such suggestive names as LIKEPLUS and LIKETIMES, so that the syntactic parts of the extensions for + and * are
LIKEPLUS :: (A, LIKEPLUS) + (B, LIKETIMES) :: ...
LIKETIMES :: (A, LIKETIMES) * (B, PRIMARY) :: ...
Then to define A - B at the same priority as A + B one would write
LIKEPLUS :: (A) -- (B) : : . . .
which would be taken as
LIKEPLUS :: (A, LIKEPLUS) -- (B, LIKETIMES) :: ....
The automatic filling in of intuitively correct categories for '(A) → (B)' is more difficult, and no attempt has yet been made in the IMP systems to improve on the method we have discussed. However, we can at least say that many extensions will be satisfactorily filled in this way. Of the 130 extensions defining one of the IMP languages, 76 or about 60 percent were filled in automatically.

      in [ACM] CACM 13(01) (Jan 1970) view details