The IBM OS/360 ALGOL 60-Compiler
by
Hans-Jürgen Hoffmann
1964/1965 chief designer, IBM OS/360 ALGOL 60-Compiler, IBM Böblingen Laboratories,
now Darmstadt University of Technology
– EXTENDED ABSTRACT WITHOUT FIGURES/TABLES –

Introduction
In the sixties, beginning fall 1964, there was a development undertaken by IBM laboratories first in Böblingen, Germany, later in Lidingö, Sweden, to design and implement a F-level ALGOL 60 compiler for OS/360. The compiler when it was completed in 1967 has been successfully used for some time by a number of OS/360 installations in Europe and world-wide, [van Wingen 1970]. Besides IBM manuals not much is known about this early development in the open literature (see, e.g., [Endres 2001]).
Being the project leader and chief designer/programmer of the Böblingen team this paper identifies some intentions of the initial design group and highlights some still interesting solutions realised. Problems and achievements are reflected from the viewpoint of early compiler design techniques. Personal reflections are mentioned.

General specifications
Design and implementation of the compiler followed some basic, general specifications:
–	Despite the concentration of IBM in 1964 towards PL/I it was decided not to provide only a pre-translator from ALGOL 60 to PL/I (however see [IBM LCP 1968], an independent, later work).
–	The official definition of ALGOL 60 was considered to be too general. The so-called remaining trouble spots [Knuth 1965] prove a still preliminary status of the language definition then available. IBM wanted to follow an industry-wide standardisation [ECMA 1963]. The ECMA standard supplemented by recursive definition and use of procedures was decided to be the language level for design and implementation [IBM ALGOL 1967].
–	The official language constructs for input and output ([IFIP/WG 2.1 1964], [Knuth 1964]) didn’t support characteristics of IBM equipment (punched cards, line printers, magnetic tapes) and functions needed to control operations under IBM OS/360 in a way considered to be required to the then IBM customers. An extension had to be defined (see section on Input/Output below).
–	An efficient implementation of loop control and access to subscripted variables was considered to be paramount in the application domain of ALGOL 60 programs. 
–	Memory limitations demanded a multiple phase compilation scheme.

Compiler phases
–	Five scanning passes (four of them pair-wise connected) through ALGOL 60 text and operator/operand token stream, resp., from left to right.
–	Generating IBM/360 machine language file as input to OS/360 Linkage Editor. Separate compilation of ALOGL 60 programs, procedures and functions.
–	Five compiler phases overlaid in 44 kBytes (F level) paged OS/360 memory.
–	Scan I/II (connected)
	Scanning ALGOL 60 text (by TR instructions, card-by-card/record-by-record) to get unified internal representation from the two possible external codes, 46-character BCD as on 80 columns punched cards [ISO/DIN 1965] and 53-character EBCDIC. Letters and digits mapped into internally coded bytes 1xxx xxxx, all other characters into bytes 0xxx xxxx, x e {0,1} – Scan I –.
Tokenising internal character stream (with ALGOL 60 keywords in apostrophes) into a stream of 1-byte keyword/operator-tokens and 6-byte operand tokens. Conversion of <numbers> to internal data format for integers and floating point values, resp. Occurrence of tokens e {<declarators>, procedure, function, begin, end} allowed to detect declarations, parameter specifications and scopes; for each identifier token in a declaration/specification instantiation of an identifier table entry (symbol table entry) obeying scope rules in the tables; finite-state transition technique. In case of an array declaration analysis of dimension and bounds specification postponed. Procedure/function entries and blocks (i.e., unnamed, parameter-free inline procedures) additionally caused an entry in a program block table PBT. Labels (i.e., identifiers before a :-token) caused an entry in the label address table LAT, scope-controlled. Furthermore a data set table  DST was build up. Printing of ALGOL 60 text – Scan II –.
–	Identifier table manipulation
Completion of internal naming; checks for declaration duplicates. Storage allocation, procedure-wise/function-wise/block-wise (data control sections in OS/360 terminology, maximal 4 kBytes per section); preparation of runtime section display by section numbers. 11 byte entries in the identifier table (6 bytes for possibly shortened/filled up external names, 5 bytes typing infor-mation, section identification and offset therein, internal names). Printing of identifier table.
–	Scan III
Replacement of identifiers in program/procedure/function/block-bodies by completed, 5 byte internal operand tokens. Constant processing. Inspection of for-loops and subscript expressions to prepare for more efficient for-loop code and address increments in access to subscripted variables. for-loop inspection was (essentially) based upon
–	Assignment to any identifier in the for-list? A list of critical identifiers (CRIDTAB) and transient  modification of the respective identifier entry in the symbol table by a flag served to control this condition.
–	Array element in the for-list?
–	Real-typed operand in the for-list?
–	Call to a procedure or function in the loop body? A name-parameter in the body?
–	goto and/or switch out of loop body?
Subscript inspection was performed by a finite state automaton (FSA) accepting only subscript expressions belonging to the equivalence class of [ <F> * V  <T>] where V is a scalar variable, integer typed, and <F> and <T>, resp., are expressions build up of only integer variables (not listed in CRIDTAB) and/or constants, the so-called linear subscript expressions. 
In both topics a worst case assumption was followed as long as contrary is not proven. More details are given below in sections on Subscript Handling and Optimisation.
–	Subscript Handling 
Linear subscript expressions are rearranged and separated into an initialisation part and a linear increment added/subtracted in each loop cycle. Registers are identified (as far as possible) to hold addresses of arrays indexed by linear subscript expressions. They are updated by simple register adds/subtracts. More details below in section on Optimisation.
–	Syntactic analysis and machine language generation, SCAN IV/V (connected)
Left-to-right sequential analysis (i) controlled by three decision matrices supported by an operator-token stack – Scan IV – and (ii) combined type checking and generation of machine code – Scan V – by calling transformation/generation procedures which take operand tokens from an operand-token stack as parameters (see figure 1). The three matrices handle the syntactic units <program>, <statement> and <expression>, resp. Semantic analysis/type checking is done operation-wise by the aforementioned procedures. By global simulation of registers for accessing data sections with their intermediate data (run-time stack) controlled by an internal register use table. Entries to the label address table LAT resolved by the linkage editor for labels occurring following the goto-token.
Figure 2 (taken from the Program Logic manual in the [IBM ALGOL 1967]-set, figure 1 there) gives more details including all internal data flow in main memory and origin of compiler listings.

Optimisation
We present the results of the optimisation provisions for loops and access to subscripted variables looking to the construct for <V> .= <A> step <B> until <C> do <S>. In general up to three recalculations of <V> (may be subscripted!) , <B>, and <C> in every loop cycle are required. for-loop and subscript inspection allows to identify three loop types (see figure 3, again taken from the Program Logic manual in the [IBM ALGOL 1967]-set, page 80, with full details).
–	Counting loop: <V> is V, an integer variable; <S> does not use V (except in linear subscript expressions); no assignments to variables in <B> and/or <C>, integer typed; no procedure/function calls; no goto out of the loop body. V has not to be maintained in memory, can be mapped into a predetermined integral interval, e.g., {(val<C> - val<A>)/val<B> + 1, 1} (val<C>  val<A> assumed, i.e., val<B> positive), and loop control can be realised by a BCTR instruction (branch on count register), V maintained in a register.
–	Elementary loop: <S> may use V in general, no typing restrictions and restrictions on goto, resp. There are no assignments to variables in <B> and/or <C>; there may be  non-linear subscript expressions (and some more conditions, internal table overflow and the like). V has to be maintained in memory and individually incremented; however no recalculation is required.
–	Normal loop: no restrictions whatsoever. Recalculation provided. 
The initial access value for a linear subscript expression is calculated before entering the loop body referring to the reference value 0 for the subscript and to the respective initial value of the expression with the initial value of the controlling variable V; a register is used to hold the initial access value (if a register is free for this purpose) In the loop this register is incremented/decremented according to a predetermined val<B>. 
Figures 4 through 8 (also taken from the Program Logic Manual in the [IBM ALGOL 1967]-set, there figures 68 through 72), demonstrate the results (for those still able to understand IBM/360 assembly language, sorry), showing for-lists with more than one element (note how these are realised!) and a linear subscript expression in the loop body.

Input / Output
Originally ALGOL 60 was defined without any specification how to input data and how to output them, resp. In 1964 the IFIP/WG 2.2 officially responsible for all topics related to ALGOL [IFIP/WG 2.1 1964] published the so-called Primitive IFIP input/output procedures. IBM internal review and discussions showed impracticability for the then available wide range of I/O devices supported by OS/360. The Subcommittee on ALGOL of the ACM Programming Languages Committee made a more appropriate proposal [Knuth 1964]; based on [Bekic 1964a]  Dr. Bekic published very critical comments [Bekic 1964b]; again no acceptance of the socalled Knuth  proposal was achieved. [Garwick 1965] is interesting to read considering the topic of I/O.
In continuing co-operation with IBM Vienna Laboratory the Böblingen group elaborated and published [Hoffmann 1965] another proposal based on Fortran I/O. From an easy implementation viewpoint the idea was to use subroutines from the Fortran library implementation (reuse in 1965!). Presentations to external ALGOL experts demonstrated strong refusal; one comment was “if IBM realizes the proposal it would not be acceptable to call the product an ALGOL 60 system”, a k.o. criterion.
So we returned for IBM OS/360 ALGOL Compiler to the IFIP primitive I/O procedures adding only some optional (!) extensions and so-called SYSACT procedures for some controlling actions for punched card devices, line printers, and magnetic tapes (Table 1).
    
OS/360 integration  /Library
The compiler and its compiled programs had to be components under OS/360. There was no discussion to use OS/360 supervisor calls for all operating services, e.g., memory management, program interruption. Memory layout followed the /360 addressing scheme by base address in a register modified by an address displacement, up to 4096 bytes. The standard OS/360 register assignment for base address, return address, and parameter access for subroutine linkage was only partially obeyed; rules for adaptation from/to assembly language programs were available.
It was not difficult to provide separate compilation of ALGOL programs, ALGOL procedures, and ALGOL functions, resp., as well as linking to code originally written in assembly language (a requirement to have very efficient code parts) and/or any other supported (high-level) language. Especially linking with (and from) Fortran subroutines was considered (with some problems as memory management was not compatible); mathematical standard functions were not implemented separately, but also taken from the OS/360 F-level Fortran library.
Output of the compiler was in form of an OS/360 Linkage Editor file consisting (besides controls) of constant pool, code segment, LAT, PBT, and DST (see figure 9 taken from the Programmers Guide in the [IBM ALGOL 1967]-set, there figure 25). This allowed some address resolution to be postponed and resolved by address constants handled by the Linkage Editor.
--------------------------------------------------
Special acknowledgements have to be given to former group members, first to Prof. Dr. Klaus Alber, now Braunschweig, and Mr. Rachel, liaison to the OS/360 development centres in the US. Ms. Grünstein, Ms. Hübner, Ms. Müller, Mr. Sinz, and Mr. Schrattenholzer formed the additional staff of the Böblingen group, all - who is wondering - at this time absolute newcomers to compiler design and implementation. Horst Remus, now Los Altos, and  Dr. Hans. O. Gerstmann, now Munich, were first and second level management always strongly supporting our work. To mention are also Dr. Michael deV Roberts and Mr. Peter Sheridan, both formerly IBM USA, as well as Dr. Ernst Schwarz and Mr. Rainer Kogon from IBM Germany. Dr. Francois Genuys, at that time with IBM France, was a very influential advisor. The late Dr. Bekic and Prof. Peter Lucas, now Univ. Graz, working with the IBM Vienna Laboratories in the sixties, were always interested and helpful partners. One should not forget the Lidingö group from the IBM Swedish Laboratories completing the implementation and documentation [IBM ALGOL 1967] following our specifications after transfer of the project to them due to IBM internal manpower reassignments. 

References
[Alber 1965] Klaus Alber: The design of the OS/360 ALGOL compiler; presentation in IBM internal conference, Skytop, Pa, USA, Nov. 24, 1965 - private communication -.
[Bekic 1964a] Hans Bekic: An input-output proposal for ALGOL based on Fortrtan IV input-output; 1964, IBM Laboratory Vienna, LR 25.3.005.
[Bekic 1964b] Hans Bekic: Some comments on the ACM Committee proposal on I/O conventions for ALGOL 60 by D. E. Knuth; 1964, ALGOL Bulletin AB 18.3.6, 16 - 19.
[ECMA 1963] European Computer Manufactures Association: ECMA Subset of ALGOL 60; 1963, Comm. ACM 6 (1963) 10, 595 - 596.
[Endres 2001] Albert Endres: Forschung und Entwicklung in der IBM Deutschland ― 2. Die IBM Laboratorien Böblingen: System-Software-Entwicklung ―; ISBN 3-920799-22-4, 2001, p. 22
[Garwick 1965] Jan V. Garwick: The question of I/O procedures; 1965, Algol Bulletin AB 19.3.8, 39 - 41.
[Hoffmann 1965] Hans-Jürgen Hoffmann: A proposal for input-output handling in ALGOL 60; 1965, ALGOL Bulletin AB 20.3.5, 31 - 45.
[Hoffmann 1966] Hans-Jürgen Hoffmann: Design of a subscript optimising compiler for ALGOL 60; 1966, IBM Laboratories Böblingen, GTR 05-099.
[IBM ALGOL 1967]
IBM Systems Reference Library, IBM System/360 Operating System ALGOL Language; 1967, IBM Form C28-6615.
IBM Systems Reference Library, IBM System/360 Operating System ALGOL Programmer´s Guide; 1967, IBM Form C33-4000.
IBM Program Logic, IBM System/360 Operating System ALGOL (F) Compiler Program Logic Manual; 1967, IBM Form Y33-8000.
[IBM LCP 1968] IBM Systems Reference Library, IBM System/360 Conversion Aids: Algol-to PL/I Language Conversion Program for IBM System/360 Operating System; 1968, IBM Form C33-2000.
[IFIP/WG 2.1 1964] NN: Report on Input/Output Procedures for ALGOL60; 1964, ALGOL Bulletin AB 16.3.1.2, 9 - 13 (also Comm. ACM 7 (1964) 10, 628 - 630).
[ISO/DIN 1965] NN: Appendix 1, German proposal for representation of ALGOL symbols; 1965.
In: ISO Draft proposal on the algorithmic language ALGOL; ISO/TC 97/SC 5 (Secr-24) 102, March 1, 1965.
[Knuth 1964] Donald Knuth (Committee Chairman): A proposal for input-output conventions in ALGOL 60; Comm. ACM 7 (1964) 5, 273 -283.
[Knuth 1965] Donald Knuth: A list of the remaining trouble spots in ALGOL60; 1965, ALGOL Bulletin AB 19.3.7, 29 - 38.
[Naur 1963] Peter Naur (Ed.): Revised Report on the Algorithmic Language ALGOL60; Comm. ACM 6 (1963) 1, 1 - 17 (and elsewhere).
[van Wingen 1970] J. W. van Wingen: Current status of ALGOL60; 1970, Paper read at the XV Meeting, Sept. 1970, München Germany of the SHARE's European Association (SEAS)
– private communication –.

Address of author 	Univ. Prof. Dr.-Ing. Hans-Jürgen Hoffmann
	Darmstadt University of Technology, Dept. of Computer Science
	Chair on Programming Languages & Compilers
	D-64283 Darmstadt Germany, Alexanderstr. 10
	Phone intl+49+6151+163410
	E-mail hjhoffmann@acm.org / hjhoffmann@computer.org