A microprogrammed implementation of EULER on IBM System/360 Model 301
Summary An experimental processing system for the algorithmic language EULER has been implemented in microprogramming on an IBM System/360 Model 30 using a second Read-Only Storage unit. The system consists of a microprogrammed compiler and a microprogrammed String Language Interpreter, and of an I/O control program written in 360 machine language.
The system is described and results are given in terms of microprogram and main storage space required and compiler and interpreter performance obtained. The role of microprogramming is stressed, which opens a new dimension in the processing of interpretive code. The structure and content of a higher level language can be matched by an appropriate interpretive language which can be executed efficiently by microprograms on existing computer hardware.
Programs written in a procedure-oriented language are usually processed in two steps. They are first translated into an equivalent form which is more efficiently interpretable; then the translated text is interpreted ("executed") by an interpretation mechanism. The translation process is a data-invariant and flow-invariant operation. It consists of two parts-an analytical part, which analyzes the higher level language text, and a generative part, which builds up a string of instructions that can be directly interpreted by a machine. The analytical part of the translator depends on the higher level language; the generative part depends on a set of instructions interpretable by a machine. Historically there was only one set of instructions which could be interpreted efficiently by a machine, its "machine language." Figure 1 outlines this scheme.
Some of the processors of the IBM System/360 family are microprogrammed machines. On them the "360 machine language" is interpreted not by wired-in logic but by an interpretive microprogram, stored in control storage, which in turn is interpreted by wired-in logic. Therefore, in a certain sense the 360 language is not the "machine language" of these processors but the (efficiently interpretable) language in which the processors of the System/360 family are compatible. The true "machine language" of these processors is their microprogram language. This language is on a lower level than the "360 language"; it contains the elementary operations of the machine as operators and the elements of the data flow and storage as operands.
Now it is conceivable to compile a program written in a higher level language into a microprogram language string. This string would undoubtedly contain substrings which occur over and over in the same sequence. We could call these substrings procedures and move them out of the main string, replacing their occurrence by a procedure call symbol, followed by a parameter designator pointing to the particular procedure. Our object program then takes on the appearance of a sequence of call statements. From here it is only a final step to eliminate the call symbols and furnish an interpreting mechanism which interprets the remaining sequence of "procedure designators."
The process just described will result in the definition of a string language and the development of a microprogrammed interpretation system to interpret texts in this string language. The situation is similar to the System/360 case: the string language corresponds to the 360 language. Programs written in a higher level language are compiled into string language text to be stored in main storage. The string language interpreter corresponds to the microprogram
Fig. 1. Processing programs written in higher level languages via translation to machine language.
1Comm. ACM, vol. 10, no. 9, pp. 549-558, September, 1967.