[PDF] SEN. Centrum voor Wiskunde en Informatica. Software Engineering. Software ENgineering

Download SEN. Centrum voor Wiskunde en Informatica. Software Engineering. Software ENgineering...

Centrum voor Wiskunde en Informatica

SEN Software Engineering

Software ENgineering The Dijkstra-Zonneveld ALGOL 60 compiler for the Electrologica X1 historical note SEN, 2 F.E.J. Kruseman Aretz NOTE SEN-N0301 JUNE 30, 2003

CWI is the National Research Institute for Mathematics and Computer Science. It is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a founding member of ERCIM, the European Research Consortium for Informatics and Mathematics. CWI's research has a theme-oriented structure and is grouped into four clusters. Listed below are the names of the clusters and in parentheses their acronyms. Probability, Networks and Algorithms (PNA) Software Engineering (SEN) Modelling, Analysis and Simulation (MAS) Information Systems (INS)

Copyright © 2003, Stichting Centrum voor Wiskunde en Informatica P.O. Box 94079, 1090 GB Amsterdam (NL) Kruislaan 413, 1098 SJ Amsterdam (NL) Telephone +31 20 592 9333 Telefax +31 20 592 4199 ISSN 1386-3711

The Dijkstra–Zonneveld ALGOL 60 compiler for the Electrologica X1 F.E.J. Kruseman Aretz

Abstract In the summer of 1960 Edsger W. Dijkstra and Jaap A. Zonneveld put into operation the very ﬁrst ALGOL 60 compiler in the world. Its code was never documented. This report contains the full assembly text of one of the latest versions of that compiler (from 1964). In order to make that text more accessible, an equivalent version in Pascal is added, together with eight chapters introducing the compiler and explaining its major features.

2000 Mathematical Subject Classification 01-08, 68-03, 68N20

1998 Computer Science Classification K.2, D.3.4

Keywords and Phrases historical, ALGOL 60 compiler, Electrologica X1

iii

Preface The main purpose of this document is to preserve the code of what presumably has been the ﬁrst working ALGOL 60 compiler. It was written for the Electrologica X1 by E.W. Dijkstra and J.A. Zonneveld at the Mathematical Centre in Amsterdam in the years 1959 and 1960. Its code has never been documented before. Somewhere in the period 1962 to 1969, when I was working at the Mathematical Centre and was in charge of the maintenance of that ALGOL system, I started to type the full text of the compiler on a Friden Flexowriter, aiming to document the latest version of the compiler in a Mathematical–Centre report. Due to more urgent work and my departure from the institute it remained unﬁnished. Only after my retirement I was able to take up the project again. Apart from presenting the compiler code in full, including its commentary in Dutch, much attention is paid to make that code accessible. This is done in two diﬀerent ways. First, an equivalent Pascal version of the compiler code was written and is presented as well. Second, in a number of chapters the main components of the compiler are described and many aspects of the compiler are dealt with. I am grateful for the hospitality of Philips Research Laboratories, where most of the work of preparing this document was carried out. I also gratefully used computer facilities at the Eindhoven Technical University. Critical comments of R.R. Hoogerwoord were very helpful to improve the readability of the text. It would have been a pleasure to me to dedicate this work to my friends Edsger Dijkstra and Jaap Zonneveld, from who I learned so much of computing science. Alas, Edsger died shortly. So I can only dedicate it to Jaap and to the memory of Edsger. Eindhoven, september 2002

Contents 1 Introduction

1.1

Some history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

The Electrologica X1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3

Working with the ALGOL system for the X1 . . . . . . . . . . . . . . . . . 11

1.4

Developments of the ALGOL system after 1962 . . . . . . . . . . . . . . . 17

1.5

The Pascal version of the compiler

1.6

The X1–code version of the compiler . . . . . . . . . . . . . . . . . . . . . 19

. . . . . . . . . . . . . . . . . . . . . . 18

2 Overview

3 The lexical scan routines

4 The prescan program

4.1

The art of skipping program text . . . . . . . . . . . . . . . . . . . . . . . 29

4.2

Representation of the prescan list . . . . . . . . . . . . . . . . . . . . . . . 34

4.3

Quantitative aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Main scan

5.1

Structure of the object program . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2

The execution model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2.1

The execution stack

. . . . . . . . . . . . . . . . . . . . . . . . . . 43

CONTENTS

5.2.2

The display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3

The context state

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.4

The name list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.5

The constant list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.6

The future list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.7

The translation of a for statement . . . . . . . . . . . . . . . . . . . . . . . 54

5.8

The compiler stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.9

The transformation of expressions

. . . . . . . . . . . . . . . . . . . . . . 57

5.10 Designational expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.11 The central loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.12 The inner loops of the central loop . . . . . . . . . . . . . . . . . . . . . . 65 5.13 Store management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.14 Some quantitative data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.15 Some problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6 The compiler output

6.1

The ﬁrst version

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.2

The ALD7 system

6.3

The load–and–go version

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7 The library system

8 Program loading

8.1

The original loader program . . . . . . . . . . . . . . . . . . . . . . . . . . 88

8.2

The loader for the ALD7 system . . . . . . . . . . . . . . . . . . . . . . . . 89

8.3

The loading phase of the load–and–go compiler . . . . . . . . . . . . . . . 91

9 The Pascal version of the compiler 10 The X1–code version of the compiler

95 147

CONTENTS

vii

A Compiler and run–time stops

309

B A sample ALGOL 60 program

313

C The OPC table

319

D The compact code

323

References

327

blanko

Chapter 1 Introduction This report documents the ﬁrst ALGOL 60 compiler, written by E.W. Dijkstra and J.A. Zonneveld at the Mathematical Centre in Amsterdam in the period from november 1959 to august 1960. It was written for the Electrologica X1, a machine developed at the Mathematical Centre but built by a Dutch computer factory specially founded for that purpose. Although Dijkstra wrote a few papers on the compiler [4, 6, 7] and although part of the total system was documented in reports of the Mathematical Centre, the compiler code itself never was fully described and documented. This report tries to remedy that situation. Its value is not the possibility to use the documented code on an X1 emulator (which can and has been done); nor will it inﬂuence the state of the art in compiler writing. Its value, if any, is purely historical: it is a report on the result of an undertaking that was new for that time, in spite of the existence of Fortran and Cobol. ALGOL 60 was a tremendous step forward, a milestone in the development of computing as a science, and writing a compiler for a language with such a new and rich structure required the invention of many new techniques. The compiler text shows which solutions were found for the problems encountered. It also reveals the struggle with many problems. One of the most impressive facts is that the compiler had to work in a store of 4K 27–bit words, in which both compiler code and working space had to be embedded. The X1 ALGOL 60 system became operational in august 1960 and was used at the Mathematical Centre until the late sixties. This report presents the compiler text in full. It does so in the (rather primitive) assembly language of the X1, which in its turn is documented in Dijkstra’s PhD thesis

CHAPTER 1. INTRODUCTION

[1]. Since that compiler text is not very accessible even for readers knowing Dutch and X1 assembly language, a more or less equivalent version of it in (standard) Pascal has been added. These compiler codes are preceded by eight chapters explaining the most important aspects of the compiler. In the remaining part of this introduction we deal with some general aspects in more detail.

1.1

Some history

The Mathematical Centre of Amsterdam played an important role in the development of the ‘Algorithmic Language ALGOL’, later (with the publication of the 1960 Report [9]) called ALGOL 60. It was A. van Wijngaarden who took part in the group responsible for the language deﬁnition. This group was the cradle of the IFIP working group WG 2.1. In the annual reports of the Mathematical Centre ALGOL is mentioned for the ﬁrst time in the report on 1959. We cite1 : Prof. Van Wijngaarden attended congresses and conferences on ‘ALGOL’ in Copenhagen, Paris and Mainz, [. . . ]

In the annual report on 1959 we further ﬁnd the following information: Prof. Van Wijngaarden and Dr. E.W. Dijkstra attended a congress on ‘ALGOL’ in Copenhagen. A congress on ‘Information processing processes’ in Paris was attended by Prof. Van Wijngaarden, J.A. Zonneveld, Dr. T.J. Dekker and M.L. Potters. In Mainz Van Wijngaarden gave a presentation on ‘Divergent series’, also attending there the so–called ‘ALGOL’ conference. F.J.M. Barning and Dr. T.J. Dekker took a course on ‘ALGOL’ in Darmstadt, [. . . ] A research project that has the special interest of all staﬀ members of the Computing Department is the one concerning the ‘ALGOL’. In international context a draft is prepared of a universal language: ‘ALGOL’, i.e. ALGO–rithmic Language. This language shall be as close as possible to the standard notations in mathematics and be readable without further explanation. The language shall allow the description of any computational process, using the ﬁxed algorithmic expressions, and it shall be translatable mechanically into machine programs. The deﬁnition of such a language is a big international project. The ‘ALGOL’ is now in ‘statu nascendi’; 1

The annual reports were written in Dutch these years; translation by the author.

1.1. SOME HISTORY

several national working groups are working towards its ﬁnal shape and the international ‘ALGOL’ conferences organised regularly try to arrive at uniformity in notation of ALGOL programs; they do so under supervision of the international ALGOL committee. In this work the Computing Department makes an essential contribution. From about Oktober 1959 a team of ﬁve members of the department (A. van Wijngaarden, J.A. Zonneveld, E.W. Dijkstra, F.J.M. Barning and miss J.M. Feringa) are hard at work on the many problems presenting themselves here. As soon as the ALGOL language is cast in a deﬁnitive shape the construction of a compiler program for the electronic computer X1 can be turned to. This program shall be capable to derive, from a description in ALGOL, a program by which the calculations concerned can be executed on the X1.

Edsger Dijkstra, Bram Loopstra and Ria Debets in front of the Mathematical Centre building, 1954 (photograph G.A. Blaauw)

The 1960 annual report of the Mathematical Centre devotes a long passage to the ALGOL compiler: The large–scale activity of the Computing Department with respect to ALGOL began already in November 1959. Due to the fact that Prof. Van Wijngaarden

CHAPTER 1. INTRODUCTION

participated in the committee that, in January 1960, would decide on the ﬁnal shape of ALGOL, there was ample reason to discuss the various aspects of algorithmic languages. The last two months of 1959 were also used to study the compiling technique as we learned it from Prof.Dr. H.D. Huskey and to subject it to a critical investigation. Thus, when in January 1960 the ﬁnal form of ALGOL – baptized ‘ALGOL 60’ in order to avoid confusion and as an expression of modesty of the composers – was stated, we already had a fair notion of the problems awaiting us. Moreover, we had the ﬁnal data at our disposal at ﬁrst hand, i.e. very rapidly. Largely due to these circumstances the ALGOL 60 compiler of the Mathematical Centre would be one of the ﬁrst in the world, if not the very ﬁrst one, that really did work. Possibly also the fact that precisely at that stage we got our own X1 at our disposal played a role: we were not yet accustomed to apply this machine in a certain manner and could therefore more easily start from scratch. Because the implications of the language permeated to us only gradually we were not confronted with all problems at the same time and in a number of steps a closely ﬁtting system was constructed. Then, in March, we had a three–day discussion in Copenhagen with a number of experts from Regnecentralen, intending to confront our ideas with theirs before starting the detailed elaboration. Our visit to Copenhagen resulted in a very important embellishment which we were able to incorporate in our projects within a couple of weeks. Immediately thereafter detailed elaborations started working in parallel projects. While Dr. E.W. Dijkstra and J.A. Zonneveld were developing the compiler Miss M.J.H. R¨ omgens and Miss S.J. Christen started work on the organisational and arithmetic subroutines which should be at the disposal of the object program during its execution. Where the problems in the construction of the compiler were mainly of a logical nature, the work on the subroutines at the service of the object program were aggravated most by the requirement of maximal eﬃciency. By July the compiler was subject to tests for the ﬁrst time; a few weeks later object programs produced were actually executed for the ﬁrst time. Most of the bugs that were revealed had the character of clerical errors or clear omissions (the latter especially in the compiler), for which the remedy was immediately obvious. Late September we had built up such strong conﬁdence in our realization of ALGOL 60 that time was considered ripe for the organization of a course on ‘Programming in ALGOL 60’. A syllabus was written and in November the ﬁrst four–day course was given. Because of the overwhelming interest this course had to be repeated in December. The great interest for these courses, the enthusiasm of the course–members and especially the good experiences with ALGOL 60 that the Computing Department

1.1. SOME HISTORY

has acquired itself for its own work conﬁrmed us in the conﬁdence that the labour invested in the completion of this project was not wasted. On the contrary!

So far our citation of the annual report 1960. Indeed it was an huge project for a computing department of 11 people. The compiler is about 2000 instructions long, another 2000 instructions support object–program execution. The latter 2000 instructions, constituting the collection of organisational and arithmetic subroutines supporting object–program execution, was baptized ‘the Complex’. All these 4000 instructions were written (and tested) in no more than 9 months, quite a feat for a machine that was only put into use at the Mathematical Centre in March 1960. The annual report of 1961 continues the interesting story of the ALGOL 60 project. We cite: Scientiﬁc activities of the Computing Department during 1961 largely concentrated on the ALGOL compiler that was ﬁnished in 1960. On account of the intensive use a number of further errors came to light (allbeit with decreasing frequency). Some of these were easily repaired, others, however, required quite an amount of brainwork. During the construction of standard procedures in ALGOL 60 it became apparent – after discussions in which eventually every member of the Computing Department would participate – that the formulation of standard processes is possible only in as far as the requirements to be met by the executing arithmetic are known. In concerted eﬀort a number of such requirements were sketched. The arithmetic incorporated in 1960 appeared not to meet these requirements. A long list of small changes in the arithmetic complexes2 proved necessary, changes that were carried through by Miss R¨ omgens and Miss Christen with their usual precision. Once the implementation of these changes was decided upon, it was, for obvious reasons, given high priority. Hence the freshly started construction of an MCP–library (a library of standard procedures that the user can apply without prior declaration) was slowed down. What was, nevertheless, achieved in 1961 in MCPs, mainly by Mrs Goldschmeding–Feringa, concerned the control of the fast tape punch by ALGOL programs3 . Besides the usual diﬃculties occurring while testing interrupt programs we were confronted here at the same time with the defects of the (yet untested) punch and its connection to the X1. It was therefore a great pleasure to see an ALGOL program producing tape one of the last days before Christmas. 2

Originally there were two complexes of subroutines supporting object program execution: ALS, with single length ﬂoating point arithmetic, and ALD, with double–length arithmetic. 3 When I entered the Mathematical Centre in 1962, only a slow tape punch (25 characters/sec) was connected to the X1. A fast one (300 characters/sec) was installed only in 1963.

CHAPTER 1. INTRODUCTION

Edsger Dijkstra and Jaap Zonneveld agreed not shave before the project of writing the ALGOL 60 compiler was done. Which, however, did not imply that they did shave when it was completed as scheduled August 24, 1960, 16:00 h. Zonneveld had a proper shave in March 1961 (picture from his personal archive); Dijkstra always kept his beard since. A few months were spent in writing two internal reports assessing the knowledge sofar available only by oral communication. These reports regard the construction of MCPs and the adaptation of the compiler and the complexes to other X1 installations4 . They were written in order to be able to delegate these activities and to protect the Computing Department from the burden of these (mainly administrative) activities that are no longer of interest to it. [. . . ] With several foreign visitors (both from universities and industry) the problem of implementing ALGOL 60 for their speciﬁc machines was discussed in various degree of detail.

The annual report of 1962 adds: For the ALGOL 60 compiler for the X1, ﬁnished in 1960, the construction of a library of standard procedures (series AP) was started. Several issues have been published in 1962. By these provisions the ALGOL system showed to be a highly serviceable system, not only for testing and theoretical purposes, but also for production. After installment of the system about 20% of machine time of the X1 was allocated for the execution of ALGOL programs. By the middle of 1962 this percentage had 4

The ﬁrst of these reports is presumably [5]; I never saw the other one.

1.2. THE ELECTROLOGICA X1

risen to a good 70%. The programming of procedures in machine code of the AP series (series AP 100) was performed by the staﬀ members Mrs. Goldschmeding– Feringa, Miss R¨ omgens, and Miss Christen under supervision of Mr. Dekker. Thanks to the fast growth of the ALGOL system, the department was able to spend more time on the investigation of numerical methods during 1962. The arithmetic complex with new, improved arithmetic, designed in 1961, was ﬁnished early in the year and put into operation February 1st.

Some 31 machine code procedures (MCP’s) were published that year in the series AP 100 and some 24 procedures in ALGOL 60 in the series AP 200. Moreover, the complexes ALD and ALS were printed as the series P (1)200. Also some manuals were released, in particular for working with ALGOL programs. A year after completing the compiler, the ALGOL 60 system for the X1 was considered complete and no further developments to the compiler or to the complexes were planned. The key players embarked on new endeavours. Dijkstra left the Mathematical Centre in August 1962 for a chair at the Technical University Eindhoven. Zonneveld returned to his specialism, numerical analysis, and was now investigating Runge–Kutta methods for the numerical integration of diﬀerential equations, the subject of his PhD thesis[11] in 1964. When I joined the Mathematical Centre in September 1962 the original crew of the ALGOL 60 project for the X1 was almost dissolved.

1.2

The Electrologica X1

The Mathematical Centre had developed and built several automatic computers (ARRA and ARMAC) before it started the development of the X1. The latter project was soon to be continued by a commercial company founded for that purpose, Electrologica. This was a full subsidiary of a Dutch insurance company, Nillmij. The ﬁrst design of the X1 had been completed by the end of 1956. It was a rather modern design. It was one of the ﬁrst fully transistorized machines, it had an interrupt system, and an index register. Below we give some more details of the X1. A rather good description of its instruction repertoire and of its assembly language can be found in Dijkstra’s PhD thesis[1]. An overview of the X1 is given in [8]. The X1 had a word and instruction length of 27 bits. It had two 27–bit registers called A and S, a 16–bit index register B, and some 1–bit registers, the most important of which was the condition register C. The instruction counter was called the T register.

CHAPTER 1. INTRODUCTION

The machine on which the work was done, the Electrologica X1 computer at the second floor of the Mathematical Centre.

It had integer arithmetic only. The number system was one–complement. It had some double–length instructions, in which registers A and S operated as one double–length register. This was the case in the (integer) multiplication and division instructions and in some of the shift instructions. Integer arithmetic was minus–zero preferent. There was neither ﬂoating–point hardware nor support for a stack: all such operations had to be carried out completely by software. Also support for dynamic (i.e., two–level) addressing was absent. The 27 bits of an instruction were, in general, structured in the following way: 3 3 2 2 2 15

bits bits bits bits bits bits

‘function letter’, indicating mostly the register involved ‘function digit’, specifying the operation ‘A/B/C variant’, giving the addressing mode ‘P/Z/E variant’, specifying condition setting ‘U/Y/N variant’, specifying condition following ‘address part’, mostly specifying an address or a number

1.2. THE ELECTROLOGICA X1

For register A (‘function letter’ 0) the following instructions5 were available: notation 0A n 1A n 2A n 3A n 4A n 5A n 6A n 7A n

meaning A:= A + M[n] A:= A – M[n] A:= M[n] A:= – M[n] M[n]:= M[n] + A M[n]:= M[n] – A M[n]:= A M[n]:= – A

The system here should be clear. Calling the function digit f we have: – for f < 4, the destination of the result is the register (A), otherwise the word of memory (M[n]) involved; – for f < 2 mod 4, the result is formed by addition of register and memory word, otherwise by taking register or memory word; – for odd f , the inverse of the (second) operand is used rather than the operand itself.

Register S (‘function letter’ 1) and B (‘function letter’ 4) had analogous instructions. For register T (’function letter’ 5), the instruction counter, we had: notation 0T n 1T n 2T n 3T n 4T n m 6T n m

meaning condition T:= T + 1 + M[n] T:= T + 1 – M[n] T:= M[n] T:= – M[n] M[m]:= M[m] – 1; T:= n (0 ≤ m ≤ 7) M[m+8]:= T + 1; T:= n (0 ≤ m ≤ 15)

Here 0T and 1T are jump instructions, 2T and 3T (indirect) goto instructions, 4T is a counting (direct) goto, whereas 6T is a subroutine call. The function letters X, D, Y, Z, and P were used for multiplication (X), division (D), and a great number of special instructions. 0P, . . . , 3P denoted register–shift instructions. There were logical instructions too, denoted with the function letter combinations LA and LS. ‘0LA n’ meant bit by bit ‘or’ between A and M[n], ‘2LS n’ bit by bit ‘and’ between S and M[n]; the function digits 1 and 3 implied as usual inversion of the second operand. 5

Strictly speaking, the X1 assembler required, for technical reasons not to be discussed here, a notation ‘0A n X 0’ rather than ‘0A n’

CHAPTER 1. INTRODUCTION

The address part normally indicated a 15–bit store address. In case of the A variant of the addressing mode it indicated a 15–bit natural number. Thus ‘1B 1 A’ had as eﬀect ‘B:= B - 1’ and ‘2T n A’ meant ‘T:= n’, i.e. a (direct) transfer of control to (the instruction at memory cell) n. In case of the B variant the contents of B were added to the address part before executing the instruction. Thus ‘2A n B’ meant ‘A:= M[B+n]’. The addition ‘B+n’ was carried out in 15 bits without end–around carry; ‘B+32767’ had the eﬀect of ‘B-1’. Condition setting was done by means of the P/Z/E variants. The P variant set the condition register C aﬃrmative if the result of the operation was positive, i.e. +0 or larger; the Z variant set C aﬃrmative if the result of the operation was +0 or −0. Thus the instruction ‘3A 0 A P’ had ‘A:= -0; C:= No’ as eﬀect. Condition following was done by the Y/N variants. The Y variant caused the instruction to be executed only if the condition register was aﬃrmative, otherwise it was skipped. The N variant required C to be negative for the instruction to be executed. The following instruction pair could be used to load the absolute value of ‘M[n]’ into A: 2A n P N 3A n The fact that condition following was available to all instructions and not to jump instructions only, lead often to compact code, the more so as the condition setting could have occurred many instructions before. The U(ndisturbed) variant suppressed the assignment of the result of an operation to its ﬁnal destination. It was used for condition setting without disturbing register or store. The instruction ‘U 1A n P’ did not more than ‘C:= (A > M[n])’. The U variant could not be combined with each instruction. The read–and–rewrite cycle of the core store was 32 µsec. Skipping an instruction took 32 µsec, instructions like ‘2A n A’ (without a store operand) 36 µsec, instructions like ‘0A n’ (with a store operand) 64 µsec, whereas multiplication and division took 500 µsec. On the average the X1 executed 20K instructions per second. In the (rather primitive) assembly language addresses were speciﬁed relative to so–called ‘paragraphs’, indicated by two paragraph letters, formed with the 13 letters Z, E, F, H, K, L, R, S, T, W, U, Y, and N. The address ‘n ZE m’ meant ‘(32*m + n) ZE 0’, i.e. 32 ∗ m + n places further than the address assigned to the paragraph–letter combination ‘ZE’. The meaning of the paragraph–letter combinations were deﬁned at the beginning of the X1 program. The letters X, D, and C were used without a second paragraph letter and had a ﬁxed meaning: X = 0, C = 16384, and D = 245766. The text ‘DP RZ 0X7’ deﬁned RZ to mean address 224 (i.e. 7 ∗ 32 + 0).

1.3. WORKING WITH THE ALGOL SYSTEM FOR THE X1

The X1 had no operating system. It had two states, running or stopped. When running it could be stopped by turning a switch (Stop Next Instruction) or by setting a stop address in a number of toggles. It also stopped by executing a stop instruction. When stopped it could be started by pressing a button. Button 1 started the assembler which was present in read–only store (addresses from ‘0 D 0’). At the Mathematical Centre the X1 was installed in 1960 and put into daily use March 8th, 1960. Its (read/write) store was extended from 8K to 12K words in May, 1962. It had no backing store whatsoever (apart from paper tape). Originally it had a console typewriter, a tape reader and a tape punch as sole peripherals; later a fast tape punch and a plotter were connected.

1.3

Working with the ALGOL system for the X1

Nowadays, with backing stores of Gbytes even for the smallest PC, with on–screen editors and cheep laser printers it is hard to imagine how primitive (but exciting) life was these days. It was a major improvement that ALGOL programs could be punched on a (Friden) Flexowriter, which produced, apart from the tape, also a print on paper6 . It could (also new!) be used for text editing, by reading (and thus reprinting and repunching) the tape, inserting the changes at the right places. The ALGOL system was contained in 5 system tapes: the compiler tape, the complex tape, the loader tape, the cross–reference tape and the library tape (the latter 4 tapes existed in two versions, for single–length and double–length arithmetic respectively). During the compilation process the compiler was, at least in principle, not overwritten. During object–program execution the complex was, at least in principle, not overwritten. Therefore it was possible to compile a number of ALGOL 60 programs in sequence after loading the compiler once, and to execute a number of object programs (using the same arithmetic) after loading one of the complexes. In practice this was done only rarely: programs were compiled and immediately executed most of the time. In that case the compilation and execution of a (correct) ALGOL 60 program required the reading (and subsequent rewinding) of the following tapes: 1. the compiler tape, 6

When I entered the institute there were already 4 (sic!) of these.

CHAPTER 1. INTRODUCTION

2. the tape(s) containing the ALGOL 60 program, 3. the tape(s) containing the ALGOL 60 program a second time (during the reading of this tape the object–program tape was punched), 4. the complex tape, 5. the loader tape, 6. the second part of the object–program tape (produced in step 3), 7. the cross–reference tape, 8. the ﬁrst part of the object–program tape (produced in step 3), 9. the library tape, 10. the input–data tape(s). If an ALGOL program did not use any of the library routines the reading of cross reference and library could be skipped; if a program had no input the last step had to be skipped. The reading of each tape had to be started by pushing one of the console buttons. The greatest shortcoming of the system, however, was the almost complete absence of syntax checks and run–time checks. At compile time most checks had to do with the representation of the basic symbols on tape (mistrusting the proper functioning of the Flexowriter punch and the X1 tape reader) and with store management; there was also a check on undeclared identiﬁers. The run–time checks involved the arithmetic (especially integer overﬂow) and again the lexical level of the input tape, but did not cover stack overﬂow or array indices out–of–bound. A complete list of the error–stop numbers is given in Appendix A. In case of a compile–time stop the operator could give as feed back to the programmer only the error number and the list of identiﬁers typed on the console typewriter7 and could mark the position of the source tape in the tape reader at the moment of the stop. Even the error stop for an undeclared identiﬁer did not mention that identiﬁer! Also in case of a run–time stop an error number was returned to the programmer, together with the output produced thusfar. There was no program debugger available. In case of erroneous results the only means of debugging was to recompile and rerun the program 7

During the second reading of the source text the identiﬁers of labels, procedures and switches were typed when processing their declaration started.

1.3. WORKING WITH THE ALGOL SYSTEM FOR THE X1

with more output statements for intermediate results added to the source text. The stepwise execution of an ALGOL object program, using the start and stop buttons of the console, required, apart from a lot of machine time, an enormous knowledge of details of the ALGOL system and was used only in exceptional cases, for otherwise unsolvable problems and in cases where the correct functioning of the ALGOL system itself or of the X1 hardware was in doubt. In 1963 a second ALGOL 60 system, developed by Nederkoorn and Van de Laarschot, became available. Although it was hardly used as complete system the compiler came in use as separate syntax checker (suppressing the punching of an object tape). In later years no (fresh) ALGOL program was run with the Dijkstra/Zonneveld system without a prior syntax check by the Nederkoorn/Van de Laarschot compiler. The following ‘special properties of the MC–Algol–system’ (mostly restrictions) were mentioned in the user manual8 : 1. Comments starting with ‘comment’ and ending by ‘;’ are permitted also at the beginning of the program. Apart from this a program shall have the form of an unlabelled block or an unlabelled compound statement, in other words start with ‘begin’ and end with ‘end’. After the last symbol ‘end’ the compiler does not accept any symbol to be skipped but requires a symbol ‘Carriage Return’. 2. In the series of symbols that are skipped after an ‘end’ symbol (not being the last one of the program) the symbols ‘begin’, ‘comment’, and the stringquotes ‘ ’ | are not permitted. 3. Only the ﬁrst nine symbols of identiﬁers do matter. 4. The following rules apply to numbers occurring in an Algol program: The number zero is interpreted always as being of type integer, even if a decimal point is included or a numeric part = 0 is followed by an exponent. A number that, because the absence of a decimal point and an exponent, is of type integer according to the rules is treated as being of type real as soon as its absolute value exceeds 67108863. The decimal exponent shall not exceed 600 in absolute value. 5. In Algol 60, function procedures can be called not only in expressions but also as a statement by themselves. In that case the function value is of no interest and will 8

taken from the user manual dated December 12th, 1962; translation by the author.

CHAPTER 1. INTRODUCTION

be ignored. For the standard functions mentioned in Sections 3.2.4 and 3.2.5 of the Report and for ‘read’ and ‘XEEN’, however, holds that they may not be called as statement by their own in the MC–Algol–system. 6. The value of the standard function ‘abs’ has the same type as its argument. The standard function ‘entier’ may have an argument of type integer. The standard functions ‘sqrt’ and ‘ln’ operate on the absolute value of the argument. 7. The primaries of an expression are evaluated in left–to–right order. (We mention this in so many words because the Algol–60 report is suggesting it but does not settle it explicitely.) 8. Labels beginning with a digit are not permitted. 9. It is not permitted to embrace a block lexicograﬁcally by more than 30 blocks. Herein do count for–statements, procedure bodies, and actual parameters consisting of more than a single identiﬁer or number also as blocks. 10. In a goto–statement the evaluation of any possible switch designator shall result in a well–deﬁned value (label). If not so then the goto–statement is not equivalent to a dummy statement but undeﬁned. 11. Not only the value of the controled variable – called ‘V’ below –, but also the identity of V (i.e. if it is an subscripted variable) may be changed in the statement following the for–clause. In the expressions occurring in a for–clause (i.e. between for and do), not only in the expressions in the list elements but also in any possible index expression of V, the call of function procedures with side eﬀects should be avoided. Also it should be avoided that the identity of V depends on the value of V (e.g. a controled variable of the form A[A[1]]). In a for list element of the form ‘A step B until C’, where A, B, and C denote arithmetic expressions, one should avoid the value of sign(B) to depend on the value of V. For in the MC–Algol–system the expression B is evaluated only once per cycle and already calculated for the ﬁrst time before the assignment V:= A. 12. Upon a for–clause no conditional statement shall follow. In other words, ‘do if ’ is prohibited. 13. Only a comma symbol is permitted as parameter delimiter.

1.3. WORKING WITH THE ALGOL SYSTEM FOR THE X1

14. Except for the explicit prohibition for certain procedures it is allowed to present an actual parameter of type integer for a formal parameter speciﬁed as real (or vice versa) in a procedure statement or a function designator. 15. Declarations starting a block and speciﬁcations in a procedure declaration shall be given in the following order: 1) scalars ( or own) and strings 2) arrays 3) destinations (label or switch) 4) procedures 16. Procedures in which declarations marked by the symbol ‘own’ occur function not in the oﬃcial manner when used recursively. 17. Only integer numbers, possibly preceded by a sign symbol, are permitted as array bounds in array declarations of the outermost block or those preceded by ‘own’. 18. The MC–Algol–system does not discriminate between ‘real’ and ‘integer’ as the ﬁrst symbol of a function declaration: in each invocation the type of the result is determined by the arithmetic that is carried out this time. 19. The MC–Algol–system requires a speciﬁcation for each formal parameter of a procedure declaration. 20. Procedure bodies starting with a label should be avoided. 21. A formal parameter speciﬁed as label or procedure shall not occur in the value list. 22. Parameters in the value list are evaluated at procedure entry in the order of speciﬁcation. (This is of importance when the evaluation of an actual parameter can inﬂuence the value of another one.) 23. An array in the value list may have at most ﬁve indices. The restrictions contained in these ‘properties’ seldom gave any problem for the use of ALGOL 60 as a programming language. The generality of the implementation, including full block structure, recursive procedures, and name parameters, even Jensen’s device, often lead to compact and nice algorithms.

CHAPTER 1. INTRODUCTION

To give an impression of the excution speed of ALGOL 60 programs on the X1 we collected the execution times of some statements in Figure 1. statement i:= 1 i:= i + 1 A[i]:= 1 y:= sin(x) p q(x) r(x) for i:= 1 step 1 until 1000 do

time 2.0 msec 3.0 msec 5.0 msec 26.5 msec 3.5 msec 8.5 msec 11.8 msec 7650 msec

(in the context of the following declarations: integer i; real x; procedure p; ; procedure q(z); real z; ; procedure r(z); value z; real z; ; ) Figure 1: execution times of some statements The table clearly shows the trade–oﬀ between ease of programming in ALGOL 60 and execution speed. Incrementing an integer variable by one (cf. the second example in Figure 1) could be coded in X1 machine code in two instructions: 2A 1 A 4A n executing in less than 100 µsec. The programmer himself has to locate the variable in memory and to choose what register to use for the operation. In ALGOL 60, on the other hand, he simply writes ‘i:= i + 1’ without bothering about the way of execution. The variable i is located by the compiler and even the use of the variable in a recursive procedure is no problem at all. The price paid for this convenience is a slowing–down of the execution, in case of the X1 from some 100 µsec to about 3000 µsec, by the execution of 7 instructions of the object program and 56 instructions of 4 ‘operators’ coded in ‘the Complex’ of administrative and arithmetic subroutines supporting object–program execution. In general the ease of programming in ALGOL 60 was paid by a loss of execution speed by a factor of 10. Given the fact that within two years more than 70% of machine time of the X1 at the Mathematical Centre was used for the compilation and execution of ALGOL 60 programs, the users were quite willing to pay the price.

1.4. DEVELOPMENTS OF THE ALGOL SYSTEM AFTER 1962

1.4

Developments of the ALGOL system after 1962

The main developments of the ALGOL 60 system for the X1 after 1962 were the introduction of a load–and–go version of the system and the incorporation of a plotter. Moreover the MCP library was extended with some new routines and some checks were added, both at compile time and at run time. The load–and–go version, in operation from autumn 1963, reduced greatly the tape handling. There was only one system tape, ALGOL source programs were read physically once only, and no object tape was punched at all. The development of this system was made possible by the much larger size of the store, 12K words instead of 4K for which the original version was written. (In 1965, also an 8K version of the load–and–go system was made on behalf of the University of Utrecht; then, the system had to be divided over two tapes, the second of which to be loaded after compilation of the ALGOL program.) Since during the loading phase of the compiler, part of the compiler was overwritten by the object program, however, the system tape had to be read for each ALGOL program anew. The new system facilitated a fast service with many small student programs for the Universities of Amsterdam. A Calcomp plotter was connected to the X1 in 1964. A nice package of MCPs for driving it was developed by van Berckel and Mailloux and documented in [12]. For a very simple but eﬀective partial check on the syntactical correctness of source programs counts of yet unpaired round and square brackets were added to the lexical scan routines. In the ﬁrst compiler scan it was then checked whether these counts were both zero at the occurrence of a semicolon or end–symbol. An equally simple, incomplete but rather eﬀective check was added at run time. It was checked that the address of an array element lay within the area reserved for that array (for one–dimensional arrays this meant a complete index–out–of–bound check). This check could be easily added to the indexer routine of the complex without any further change of the system. Many of the ﬁrst ‘victims’ got angry and requested to run their programs with the ‘old’ system! Further improvements were made in the tape–reading routines such that tape reading was accelerated quite a lot. But all these changes had in common that they aﬀected the system only skin–deep: the heart of the system remained untouched. In 1966 the X1 got the Electrologica X8 as competitor. Since the ALGOL 60 system on that machine ran about 100 times faster than the one on the X1, and since it had rather

CHAPTER 1. INTRODUCTION

complete syntax and run–time error checks, the main stream of ALGOL 60 programs was directed to the X8 very soon. The X1 remained in use at the Mathematical Centre, however, until mid 1972.

1.5

The Pascal version of the compiler

The Pascal version of the compiler is written in ISO Standard Pascal. It is reverse– engineered rather close to the machine–code version. It has been tested thoroughly: for a range of ALGOL 60 programs it produces exactly the same object code as the original version in X1 code. Being close to the original, there are, however, from sheer necessity, some diﬀerences. In machine code one can do things that are impossible in any higher level language. First of all, the order of the subroutines is diﬀerent, and much more systematic than in the machine–code version. We also used the structuring that Pascal permits: most of the procedures are local to one of the three main procedures: ‘prescan’, ‘main scan’, and ‘program loader’. In the machine–code version these parts are mixed up criss–cross. In order to facilitate the relation between the two texts we added to most parts of the Pascal text the paragraph letters of the corresponding machine–code part as a comment. Second, in the machine–code version all variables were accomodated in store. Most simple variables had an address of the form ‘n ZE m’ (with m ∈ {0, 1, 2}) or ‘n RE 0’. In the Pascal version these variables are just global or local variables in the program. On the other hand all lists maintained in store are allocated in the Pascal program in an array ‘store’, modelling the store, with bounds 0 and 12287 as in the X1 of the Mathematical Centre. Next, the X1 code contains a number of constant tables in the text, e.g. for the decoding of Flexowriter punch code, for the compact coding and decoding of object instructions, and for the preﬁll of the symbol table. These are partly accomodated in arrays (which then have to be given a value at run time by a piece of program code), and partly implemented by means of a case construct or by program text only: in initializing the symbol table just before invoking procedure main scan instead of copying a table using a loop now the appropriate values are ﬁlled in by linear code. In the X1 code the only means of transfering control is the jump instruction9 . We tried to 9

In many simple cases of conditional constructs also the condition following variants of the X1 were used.

1.6. THE X1–CODE VERSION OF THE COMPILER

make the text slightly more structured by using ‘if . . . then . . . else . . . ’, ‘while . . . do . . . ’, and ‘repeat . . . until . . . ’ whereever simple. Subroutines with multiple entry points also caused some problems. Some could be solved by splitting the subroutine into several separate subroutines. In one case (in the loader) where a subroutine conditionally added 1 or 2 to its link and where the subroutine call was followed by two jump instructions to cater for the normal exit and one of the exceptional cases we eliminated the whole subroutine. But in general we believe that the Pascal version is a faithful and honest representation of the original machine code. It reveals that the style of programming has changed largely in the years since 1960, not the least by the activities of one of the primary authors of the X1 system.

1.6

The X1–code version of the compiler

When I entered the Mathematical Centre in 1962, there were two handwritten manuscripts (in pencil) of the compiler code, one of Dijkstra and the other of Zonneveld. They contained the original version of the compiler. This version diﬀers from the text given in the present report – the load–and–go version of the compiler – in some well–isolated areas. Especially the parts ‘ﬁll result list’ (FRL, paragraph letters ZF), ‘read next symbol’ (RNS, ZY), ‘next ALGOL symbol’ (NSS, HT), and ‘read ﬂexowriter symbol’ (RFS, LK) diﬀer, whereas the routines with paragraph letters LL upto SZ, which have to do with the load–and–go aspects, are totally absent in the original version. Dijkstra’s copy was recently found again and is now available in the archives of CWI. All changes and improvements made from 1962 were written in an exercise book much in the same way as the original version. After completing the load–and–go version of the compiler I felt the need to produce a complete text of the compiler in its new state; so I started to type it – for the very ﬁrst time! – on Flexowriter. That code text was completed just before I left the Mathematical Centre in 1969, but I never had time to extend it to a full documentation. After my retirement I decided to resume that documentation project. I retyped the Flexowriter print, now as a ﬁle in ASCII in my work station, proﬁting of all modern text– editing facilities. In order to have more than a visual check I wrote an X1 emulator, typed in the complex of run–time support routines, and was so able to rerun the X1 ALGOL 60 system. This made it also possible to check the outputs of the X1–code and the Pascal version of the compiler against one another and to carry out a number of measurements.

CHAPTER 1. INTRODUCTION

Those measurements would have been quite a job in the sixties, but with today’s tools they were mere child’s play.

Chapter 2 Overview The ALGOL 60 compiler for de El X1 uses two text scans for producing the translation. Originally, the source text, punched on papertape in Friden Flexowriter code, was physically read twice. The two compiler scans, called prescan and main scan, used the same routines for scanning the text. Those routines constitute the lexical scan part of the compiler. A later version of this lexical scan stored its intermediate results during the prescan and retrieved these from store during the main scan. The output of the main scan was originally punched on paper tape. The output tape consisted of three parts: the object code proper, still in a free locatable format, the constant list, containing all numbers that occurred in the ALGOL text, and the future list, containing the ﬁnal destinations of all forward references. The object code was punched during the main scan itself, the two other parts at the end of the main scan. A special loading program was used to convert the object tape into executable code. In a later load–and–go version the output of the main scan was stored in memory without punching. The loading phase was executed immediately after completion of the main scan. Chapter 3 discusses the lexical scan routines. Chapter 4 presents the prescan program. In Chapter 5 many aspects of the main–scan program are analysed. Chapter 6 gives an overview of three versions of the compiler output. Chapter 7 introduces the library system. Chapter 8 treats three versions of program loading. Finally, in Chapters 9 and 10 the Pascal version and the X1–code version of the compiler are printed in full. The compiler does not use any of today’s parsing methods. In fact, there is hardly any parsing at all, in the sense of checking whether the program text conforms the grammar rules and constructing the parse tree. Almost any text is ‘accepted’ and the inspection 21

CHAPTER 2. OVERVIEW

of the symbols constituting the text is merely done for the immediate production of the translation. There is, however, some resemblance with methods based on precedence grammars.

A page from Dijkstra’s handwritten version of the compiler. See page 173.

Chapter 3 The lexical scan routines After its revision in 1963 the lexical scan consists of four hierarchically linked routines, called read ﬂexowriter symbol (RFS), next ALGOL symbol (NSS), read next symbol (RNS), and read until next delimiter (RND). The lowest level routine in the hierarchy is read ﬂexowriter symbol. The Flexowriter code has two shifts, lower case and upper case, with explicit punchings marking shift changes. Therefore, RFS keeps the most recent shift in the variable rfsb. RFS reads one or more punchings from the input tape, skips blank and erase codes, records shift punchings, checks parity and delivers as function value the next relevant code in internal representation. The next level routine in the hierarchy is next ALGOL symbol. Its main task is to assemble basic symbols that are represented by more than one Flexowriter symbol, such as word delimiters, colonequal, unequal, or string quotes. Moreover it skips – outside strings! – comments introduced by the basic symbol ‘comment’ and closed by a semicolon. Symbols between a basic symbol ‘end’ and the next semicolon, ‘end’, or ‘else’1 are, however, not skipped by NSS and only ignored by the prescan and – once again – by the main scan. The third level routine in the hierarchy – nonexistent originally – is read next symbol. During prescan it calls NSS for the next symbol and assigns it to the variable dl. Moreover it stores that symbol in a symbol store, packing three symbols in one computer word. During the main scan it takes its symbols from the symbol store and assigns them to dl. The upper level of the hierarchy is routine read until next delimiter. It hops over numbers and identiﬁers to the next delimiter, which can be found in variable dl. Whether or not 1

The ALGOL 60 report states that the sequence of symbols ‘ end ’ is equivalent to ‘ end’.

CHAPTER 3. THE LEXICAL SCAN ROUTINES

a number or an identiﬁer was met can be seen from the variable nﬂag: it is set to 1 if a number or an identiﬁer was met, and to 0 otherwise. If nﬂag = 1 the variable kﬂag indicates whether a number (kﬂag = 1) or an identiﬁer (kﬂag = 0) was met. In both cases information indicating what number or identiﬁer was met is given in variable inw and, if more information is necessary, in variable fnw. In the latter case variable dﬂag is set to 1, otherwise to 0. At most 9 letters (or digits) of an identiﬁer are taken into account. Consequently, identiﬁers that diﬀer only after the ﬁrst nine characters are not distinguished. If an identiﬁer consists of less than 5 characters, it can be represented by inw alone. In that case the last three bits of inw are zero. Note that RND assembles numbers and identiﬁers from their constituting characters – and does so during both prescan and main scan –, but does no table look–up: all look–up activities are carried out in the main loop of the main scan. In addition to hopping over identiﬁers and numbers, RND also hops over the basic symbols ‘true’ and ‘false’. These are mapped onto the numbers 0 (for ‘true’) and 1 (for ‘false’), i.e., RND delivers into dl the code for the delimiter following these symbols and sets nﬂag to 1, kﬂag to 1, dﬂag to 0, and inw to 0 or 1. Although RND, the upper level routine of the hierarchy, is the central interface between lexical scan and the compiler scans, there are a few places in both prescan and main scan where the underlying routine RNS is called. In the ﬁrst place the contents of strings are skipped (prescan) or read and transferred to the object code (main scan) by calls of RNS. Secondly, in the main scan, comments after an ‘end’ symbol are skipped using calls of RNS (during the prescan they are skipped by the main loop thereof using calls of RND). There are two more places in the main scan using RNS: to read the type symbol following the symbol ‘own’ in a declaration (for unknown reasons) and to read the symbol following a ‘]’ symbol in a switch designator (for a very speciﬁc, technical reason). Originally, RFS read its characters from an input buﬀer rather than directly from the paper–tape reader. That buﬀer was ﬁlled by an autonomous process running in parallel with the compiler and driven by the paper–tape reader interrupt. That was a good solution when the reader was slow (about 25 characters/second), but absolutely inadequate for the later installed EL1000 which was capable of reading 1000 characters a second. Recall that the EL X1 executed roughly speaking about 20 instructions in a millisecond, whereas the interrupt handling and buﬀer administration took about 125 instructions or 6 millisecond per symbol read and delivered (the input buﬀer being full all the time, retrieving a symbol from the buﬀer implied a restart of the autonomous reading program, the reading and buﬀering of a new symbol, and an inactivation of the reading program; in the mean time the interrupt signal was set and before the symbol retrieved from the

buﬀer could be processed the interrupt handler was activated only to ﬁnd no request for reading). Therefore, we decided to replace the buﬀer mechanism by a direct access from RFS to the tape reader, leading to a drastic accelleration of the prescan process. Moreover, much attention was given to ﬁnd further ways to speed up the execution of RFS, using the code table to encode the simple cases in an easy recognizable manner. As a result, the tape was read during the prescan phase at more than half of its maximal speed. We end this section by a few other remarks on the implementation. The recognition of word delimiters in NSS is carried out in a rather primitive way. The occurrence of a word delimiter is noticed when an underline symbol ‘ ’ is followed by a lower case letter, an ‘A’ or a ‘B’. If that letter happens to be in {a, c, d, g, l, o, p, r, u, v, w, B}, the identity of the word delimeter is established immediately as ‘array’, ‘comment’, ‘do’, ‘goto’, ‘label’, ‘own’, ‘procedure’, ‘real’, ‘until’, ‘value’, ‘while’, or ‘Boolean’, respectively. Otherwise, a second underlined letter is read. If that is a ‘t’, a third (underlined) letter is read in order to discriminate between ‘step’ and ‘string’. Otherwise, if that second letter is in {a, e, f, h, r, w} the choice is, given the fact that the ﬁrst letter was ambiguous, clear: it has to be ‘false’, ‘begin’, ‘if’, ‘then’, ‘true’, or ‘switch’, respectively. Otherwise, the ﬁrst letter is inspected anew, and given the fact that neither the ﬁrst letter nor the second was decisive, the choice between ‘boolean’, ‘end’, ‘for’, and ‘integer’ is made immediately. After recognition the remainder of the underlined word is skipped. A minor detail is that repetitions of underline symbols are skipped (the underline and the vertical bar are non–advancing symbols on a Flexowriter; therefore, repetitions thereof do not change the print on paper). As stated before, this recognition algorithm is rather primitive and unsafe. For example, ‘bagin’ is interpreted as ‘false’ ! It is, however, also rather fast through the use of a table. Identiﬁers are represented by one or two X1 words. If the identiﬁer consists of at most 4 characters, they are stored in inw : the last character at bit positions 26 to 21, the second last (if any) at bit position 20 to 15, the third last (if any) at bit positions 14 to 9, and the fourth last (if available) at bit positions 8 to 3. Note that bit positions 2 to 0, the least signiﬁcant three bits of inw, remain zero. If the identiﬁer has more than 4 characters, the ﬁfth character is stored at inw [21:26], the fourth at inw [15:20], the third at inw [9:14], the second at inw [3:8], and the ﬁrst partly at inw [0:2], partly in three bits of fnw (depending on the number of characters). Since the ﬁrst character of an identiﬁer is always a letter, letters are internally coded by a value from 10 upto and including 62 (value 36 is unused), and inw [0:2] is used for the most signiﬁcant three bits of the code, these bits are not all zero. In this way a single–word representation can be discriminated

CHAPTER 3. THE LEXICAL SCAN ROUTINES

from a two–word representation. This is used in the main scan when a name list has to be searched through. As said before, (unsigned) numbers are assembled by RND. If the number is an integer not exceeding 67108863 (the integer capacity of the El X1), it is represented by one word, inw. Otherwise, it is represented by two words, inw and fnw respectively, as a ﬂoating point number in the so–called P9 representation of de X1. The 40 bits mantissa m is scaled between .5 and 1 (.5 ≤ m < 1). The 26 most signiﬁcant bits of m are stored in fnw, the 14 least signiﬁcant bits of m together with a sign digit 0 in the head of inw. The remaining 12 bits of inw are used for the binary exponent e. That exponent should fulﬁll the requirement −2048 ≤ e ≤ +2047 and the tail of inw contains the number e + 2048. The conversion from decimal ﬂoating to binary ﬂoating is carried out in 52 bits precision, with 12 guarding bits. The result is rounded to 40 bits. The conversion uses multiplications or divisions by powers of 10, preferably 108 , the largest power of 10 represented in the standard X1 system software. In the Pascal version, however, only the ﬁrst power of 10 is used for reasons of simplicity. The transformation of the representation of an ALGOL 60 program punched on paper tape in Flexowriter code to a sequence of delimiters possibly separated by constants or identiﬁers results in an enormous reduction of information. We carried out some measurements on a sample program taken from the PhD thesis of Zonneveld [11]. The text used in these experiments is reproduced in Appendix B. It was typed in ASCII (using ‘ for ∨, ^ for ∧, ~ for ¬, and % for 10 ) and transferred to Flexowriter code by means of a Pascal program. We measured: 9198 heptads, of which 1247 2730 44 2764 320 2092 1

shift punchings, dealt with inside RFS lay–out punchings, skipped by NSS punchings of comments skipped by NSS one–punching basic symbols punchings for 160 two–punching symbols punchings building 276 word delimiters lay–out symbol kept in stock by NSS

3200 basic symbols delivered by NSS and stored for reuse in the main scan 1254 delimiters delivered by RND, separated by 658 identiﬁers, 210 numbers, and 9 logical values The comment punchings count includes the punchings used for the representation of the symbol ‘comment’ itself and of the concluding semicolon. The punching count for word

delimiters is inclusive those for ‘true’ and ‘false’ but exclusive ‘comment’. The count of one–punching basic symbols includes 22 lay–out symbols not skipped by NSS because of their occurrence within a string.

CHAPTER 3. THE LEXICAL SCAN ROUTINES

Chapter 4 The prescan program 4.1

The art of skipping program text

The main task of the prescan is to construct the prescan list PLI. This list contains, for each block in the ALGOL 60 program, two sublists. The ﬁrst sublist contains the switch identiﬁers and the label identiﬁers declared in the block, the second sublist contains the procedure identiﬁers declared in the block. These are precisely those identiﬁers that can be referred to in the block before their declarations. According to the ALGOL 60 report, scalar and array identiﬁers can also have applied occurrences before their deﬁning occurrence. However, the X1 implementation of ALGOL 60 precribes an order for the declarations of a block: ﬁrst the scalar variables, next the arrays, and only thereafter the declarations of procedures and switches, in arbitrary order. In these declarations of procedures and switches, the identiﬁers of all procedures, switches, and labels of the block may be used in applied occurrences. Only the identiﬁers are recorded: no other information whatsoever from the declaration is added. It is in the name list (NLI) that is built and manipulated during the main scan that a descriptor is added to each identiﬁer. Some words must be devoted to what constitutes a block in X1 ALGOL. In the ﬁrst place, each block in the sense of the ALGOL 60 report constitutes an X1–ALGOL block. Also the declaration of a procedure constitutes a block (containing, e.g., the identiﬁers of the formal parameters). In addition to these the controlled statement of a for statement constitutes a block. It is this latter mechanism by which a goto statement outside a for statement cannot refer to a label within the for statement, preventing jumps into a

CHAPTER 4. THE PRESCAN PROGRAM

for statement. However, some care is taken not to introduce unnecessarily many blocks. If the body of a procedure declaration itself is a block, it is combined with the block containing the identiﬁers of the formal parameters. If, however, the controlled statement of a for statement is a block in the sense of the ALGOL 60 report, it is treated as a block diﬀerent from the one that is introduced for the controlled statement itself. We give a short example. Consider the following ALGOL 60 program: begin integer i; procedure p(x); integer x; begin switch s:= aa, bb, cc; aa: x:= x - 1; goto s[sign(x) + 2]; bb: end; procedure q; dd: for i:= 1, 2 do ee:

p(i);

q; cc: for i:= 1 while i > 0 do begin integer i; aa: i:= 0 end end This program generates the following PLI: [[cc], [q, p],[bb, aa, s], ,[dd], ,[ee], ,, ,[aa], ] In the PLI, blocks are sorted in the same order as the occurrence of their ﬁrst symbol in the text. Within each sublist, the identiﬁers occur in retrograde order. By means of the following two operations the prescan program operates upon the PLI: ﬁll prescan list and augment prescan list. The former operation inserts an identiﬁer (stored in inw and, perhaps, fnw) in some existing sublist, the latter one extends PLI at the end with two new and empty sublists. They use two global variables, mbc (for maximum block count) and bc (for block count). In mbc the number of blocks encountered thusfar is recorded, whilst bc gives the number of the current block. Upon block entry mbc is incremented by one, the current value of bc is saved in a stack, and bc is set to mbc. Upon block exit bc is restored from the stack.

4.1. THE ART OF SKIPPING PROGRAM TEXT

The prescan program itself can best be characterized as ‘the art of skipping text’. Its main loop hops, by means of invocations of read until next delimiter, from delimiter to delimiter, only paying some attention to it if it is: -

a stringquote open, in order to skip strings; ‘for’, in order to start a new block in PLI; a colon, in order to add the label identiﬁer to PLI; ‘begin’, in order to see whether it is followed by a declarator (introducing a new block in that case) and to enable a match with the corresponding ‘end’; ‘end’, in order to match it with the corresponding ‘begin’ and to check whether it ends a block construction, or perhaps even the program; a semicolon, in order to check whether it ends a for statement or a procedure body; ‘procedure’, in order to add the procedure identiﬁer to PLI and to start a new block in PLI; ‘switch’, in order to add the switch identiﬁer to the PLI and to skip the switch declaration upto and including its concluding semicolon; or ‘own’, ‘Boolean’, ‘integer’, ‘real’, ‘array’, ‘string’, ‘label’, or ‘value’. For these symbols the remainder of the corresponding declaration or speciﬁcation is skipped in an inner loop upto and including its concluding semicolon.

Note that the prescan program never meets a letter, a digit or the symbols ‘true’ or ‘false’, because these are hopped over by RND (except when occurring within a string). The main loop as described above can, however, be in one of two states. The current state is recorded in a variable bﬂag. The normal state is bﬂag = 0, whilst bﬂag = 1 indicates the possible processing of speciﬁcations. bﬂag is set to 1 whenever the delimiter ‘procedure’ is met in the normal state; it is, with some exceptions, reset in each iteration of the main loop. Exceptions occur, for unknown reason, in the iteration following the treatment of a colon, a stringquote open or a ‘begin’. There are two inner loops. The ﬁrst one is entered upon the detection of a stringquote open. It skips, by means of invocations of read next symbol, the contents of the string upto and including the corresponding closing stringquote. Thereafter the next cycle of the main loop is entered without, however, resetting bﬂag. The other inner loop is used to skip declarations and speciﬁcations. It is entered from the main loop after detection or processing one of the delimiters ‘own’, ‘Boolean’, ‘integer’, ‘real’, ‘array’, ‘switch’, ‘procedure’, ‘string’, ‘label’, or ‘value’. It is exitted at the ﬁrst semicolon, after which the next cycle of the main loop is entered without resetting bﬂag. In this way the parameter list of a procedure, its value list, and its speciﬁcation lists are skipped by an alternation of a cycle of the main loop and a number of cycles

CHAPTER 4. THE PRESCAN PROGRAM

of this inner loop. Inside this inner loop the treatment of the delimiter ‘procedure’ is equal to that inside the main loop. In this way the occurrence of a function declaration (starting with ‘Boolean’, ‘integer’, or ‘real’) is properly reacted upon. The only eﬀect of the state bﬂag = 1 in the main loop is that the delimiters ‘switch’ and ‘procedure’ are interpreted as speciﬁers and not as declarators. Note that array declarations are skipped by an inner loop. In this way the colons that occur in bound pair lists are never taken for a colon marking the occurrence of a label. (In a later stage we added to the prescan program some code that checks, at each occurrence of a semicolon or ‘end’, whether the number of opening parentheses is equal to the number of closing parentheses and whether the number of opening square brackets is the same as the number of closing square brackets met in the text thusfar. In this way a frequently occurring source of troubles could be detected early. The check was carried out during prescan in order to enable the operator to mark the place in the paper tape where the error was detected.) Because we deal with a context free grammar, a push–down list is needed. It is used to match corresponding ‘begin’ and ‘end’ symbols and to cater for the block structure of the ALGOL 60 program. Each ‘begin’ symbol is pushed onto the stack; it is removed at the occurrence of an ‘end’ symbol. If bﬂag = 1, indicating the start of a procedure body, nothing more is added to the stack: it is by this mechanism that a procedure body which is a block by itself does not count as a block in addition to the one that is introduced for the procedure declaration and in which the formal parameters are accomodated. If, on the other hand, bﬂag = 0, and if the ‘begin’ symbol is followed by a declarator symbol, indicating the start of a new block, two other values are pushed onto the stack just below the top–of–stack value (i.e. the ‘begin’ symbol): the current value of bc and the value −1. The latter is used as block marker. The ‘begin’ symbol itself continues to be the top–of–stack value. Also when a ‘for’ symbol is encountered, these two values are pushed to the stack too, this time just on top of the stack: bc and −1. At the occurrence of a semicolon or ‘end’ symbol, pairs of a block marker and a saved bc value on top of the stack are popped repeatedly (thereby terminating for statements, which are treated as blocks) until a ‘begin’ symbol is found as top–of–stack value. In case of an ‘end’ symbol the ‘begin’ is popped as well, in case of a semicolon it is preserved in the stack. Each time that a saved bc value is popped in this process it is used to restore variable bc. For the push operations onto the stack the procedure ﬁll t list is used (both by the prescan

4.1. THE ART OF SKIPPING PROGRAM TEXT

program and the main scan); inspections of the top–of–stack value and pop operations are, however, explicitly coded in the text of the prescan program. One may wonder whether such a primitive program as the prescan program can properly accomplish its task, the construction of the prescan list, for any syntactically correct ALGOL 60 program, and in fact it does not. We found a number of ﬂaws but in practice they hardly mattered: most programmers don’t write grammatically complex programs. I remember only one user problem that we could trace back to a shortcoming of the prescan program, and it was easily circumvented. A ﬁrst mistake, rather unimportant, is the way in which comments between an ‘end’ symbol and the subsequent semicolon, ‘else’ or ‘end’ symbol are dealt with. The comment symbols are skipped by the main cycle of the prescan program and consequently there is a reaction upon the occurrence of those symbols the prescan program is interested in. In the X1 ALGOL 60 user’s manual the occurrence of the symbols ‘begin’, ‘comment’ and of stringquotes are explicitly forbidden, but also symbols like ‘for’ and ‘procedure’ better do not occur in these contexts, as is illustrated by the following example: begin integer i; for i:= 0 do begin AA: end for i, BB: ; CC: end producing: [[CC], ,[AA], ,[BB], ] as prescan list in stead of: [[CC], ,[AA], ] We notice already here that in the main scan program there is a separate loop of only 6 X1 instructions for skipping this kind of comments neatly, and it is incomprehensible why the same solution is not used in the prescan program. Then no exclusion rule would have been necessary in the user manual, and the prescan program and the main scan program would have had the same treatment of comments. The true solution would have been to skip such comments already in the lexical scan part of the compiler: that’s where it belongs! A more serious ﬂaw is caused by the way the block structure is treated. For an ALGOL 60 block ‘begin end’ the block marker −1 in the stack is not removed upon reading of the ‘end’ symbol, but only at the next semicolon or ‘end’

CHAPTER 4. THE PRESCAN PROGRAM

(at the same level). Consequently, for the following ALGOL 60 program: begin if 0 < 1 then AA: begin integer i; BB: end else CC: begin integer i; DD: end end the prescan program generates the following prescan list: [[AA], ,[CC, BB], ,[DD], ] instead of: [[CC, AA], ,[BB], ,[DD], ] The faulty prescan list leads to an endless loop within the main scan.

4.2

Representation of the prescan list

During prescan and main scan the working space of the latest version of the X1 ALGOL 60 compiler ran from store address 1933 (1–28–13)1 upto 6783 (6–19–31). In this space all lists had to be accomodated with the exception of the compiler stack and of the outputbuﬀer for the console typewriter. For the former 128 words were reserved from store address 800 (0–25–0) upto 927 (0–28–31). The execution of the prescan program generates two lists: the prescan list PLI and a coding of the input text as produced by NSS, packed 3 symbols in a word. The text words were stored from address 1941 onwards, PLI was build at the end of the available space; its last word had address 6783. The representation of PLI was just a linked list. The words coding the identiﬁers of a sublist of PLI were written one after another without any separation. Each sublist, however was preceded by a link refering to (the link preceding) the next sublist. All these 1

In the X1–practice it was customary to denote addresses in the number system with base 32: a 15–bit address is then split into three 5–bit parts. For the Mathematical Centre X1 addresses ran from 0–0–0 upto 11–31–31 and, for the read–only part of the store, from 24–0–0 onwards.

4.3. QUANTITATIVE ASPECTS

links were forward references. After the last sublist a backward reference was included as an endmarker. PLI is initialized as: address 6781 6782 6783

contents 6782 6783 6782

representing the two (as yet) empty sublists of the outermost block. The prescan list for the ﬁrst example read: [[cc], [q, p],[bb, aa, s], ,[dd], ,[ee], ,, ,[aa], ]. Its representation is given in Figure 2. A consequence of this representation is that the insertion of an identiﬁer in one of the sublists, or of two new (empty) sublists at the end of PLI is quite a complex operation: shifting part of the list downwards in order to create one or two empty places and updating the links in the lower part of the chain. In order to keep the amount of shifting as small as possible identiﬁers are inserted at the front end of the appropriate sublist. The chosen representation is, on the other hand, quite ﬁt for use during the main scan.

4.3

Quantitative aspects

In order to get an impression of the eﬃciency of the prescan program we carried out some measurements on the sample program of Zonneveld that was also used in the previous chapter. What we could easily measure was the number of instructions executed between two successive read instructions (the count including one of these). The paper–tape reader of the X1 was able to read 1000 punchings a second. The minimal time between two successive reads was therefore 1 millisecond. Taking as average instruction time about 50 microsecond, the X1 was capable of executing some 20 instructions per millisecond. If less than 20 instructions were executed between two read instructions, the X1 had to wait until the next read result was available, whilst the execution of more than 20 instructions between two read instructions lead to an activation of the brakes and a slow–down of the tape reader. From our measurements we calculated the average number of instructions executed between reads, replacing any count less than 20 by 20. The resulting average was 33.8

CHAPTER 4. THE PRESCAN PROGRAM

address 6762 6763 6764 6765 6766 6767 6768 6769 6770 6771 6772 6773 6774 6775 6776 6777 6778 6779 6780 6781 6782 6783

contents comments 6764 25559040 cc 6767 54525952 q 52428800 p 6771 23429120 bb 21299200 aa 58720256 s 6772 ε 6774 27688960 dd 6775 ε 6777 29818880 ee 6778 ε 6779 ε 6780 ε 6782 21299200 aa 6783 ε 6782

Figure 2: store representation of [[cc], [q, p],[bb, aa, s], ,[dd], ,[ee], ,, ,[aa], ] instructions, suggesting that the tape reader would have run at 60% of its maximum speed for this program. A detailed analysis of the available 9198 number–of–instructions–between–successive– reads can be given. We want to relate these ﬁgures to speciﬁc activities in the layers of the lexical scan and in the prescan program itself. Before doing so we tried to eliminate the eﬀects of two diﬀerent sources of a kind of noise. In the ﬁrst place the second level of the lexical routines, NSS, reads at some occasions one Flexowriter symbol in advance, which then is stored in an internal buﬀer. At the next invocation of NSS this symbol is taken from that buﬀer instead of reading it from the tape reader. In the second place, within the third level of the lexical routines, RNS, the symbol obtained from NSS is stored in the text buﬀer. This takes 11 instructions but at one of each three invocations an ad-

4.3. QUANTITATIVE ASPECTS

ditional 7 instructions are executed for starting a new text–buﬀer word (remember that in the text buﬀer 3 symbols are stored per word). A ﬁrst observation is that the 9198 heptades read by the tape reader lead to only 3200 symbols delivered by NSS. This means that 5998 heptades are ‘absorbed’ by RFS and NSS. In 5145 of the cases the number of instructions executed between two successive reads is 20 or less, and in 6007 cases 27 or less. With some exceptions these will correspond to absorbed heptades, and the average number of instructions between reads is for these cases only 20.4, replacing again numbers less than 20 by 20. For a second observation we mention that the PLI produced for this program counts 36 blocks (of which 32 for blocks without any identiﬁer) and 8 short (i.e. one–word) identiﬁers, resulting in a total PLI length of 81 words. The ﬁrst block introduction (for procedure f ) takes 163 instructions, including insertion of its identiﬁer, whilst the insertion of label identiﬁer A requires 114 instructions, the incorporation of the ﬁrst for block 181 instructions, and that of the last for block 744! We see here clearly the eﬀect of the steadily increasing amount of work for adding new sublists at the end of PLI (all numbers mentioned here are the number of instructions between successive reads). Block introduction or name insertion costs, on the average, 413.0 instructions. As a result the tape reader halted noticeably at the occurrence of labels, switch– or procedure identiﬁers and ‘for’ symbols. For the remaining symbols we measured an average number of instructions between successive reads of 54.6. This caters for the activities at all the levels of the lexical scan and at the prescan level itself. The lowest number above 27 that occurs is 34, the biggest one not related to PLI increments is 133. Typical numbers are 36 and 43 for the letters and digits of an identiﬁer and 50 and 57 for the digits of a number (here we should mention that for each digit of a number two multiplications are executed with an execution time of 500 µsec each. Therefore the ﬁgures 50 and 57 could also be read as 68 or 75). The prescan as a whole takes 292 810 instructions, 256 848 (88%) of which are spent in the lexical scan. In more detail, RFS requires the execution of 95 722, NSS of 63 990, RNS of 42 684 and RND of 54 452 instructions.

CHAPTER 4. THE PRESCAN PROGRAM

Chapter 5 Main scan During the main scan the object program is generated. In the original version of the compiler the source text was read from paper tape a second time and the object program was punched, also on paper tape. The latter was a rather time–consuming process as the tape punch ran at a speed of 25 punchings a second. In the latest load–and–go version of the compiler the source text was taken from store and the object program as produced during the main scan was stored in compressed form. After completion of the main scan it was decompressed and stored at its ﬁnal place by the loading phase of the compiler. Inputs to the main scan are the source text (as stored by RNS during prescan) and the prescan list PLI. Outputs are: the list of object instructions RLI (in its compressed form), the list of future references FLI, the list of constants KLI and some numbers: the lengths of RLI, of FLI, and of KLI and GVC, the ﬁrst free address of the execution stack. The structure of the main scan resembles that of the prescan program. There is one central loop and some inner loops (for dealing with special constructs like strings, formal parameter lists etc.). The central loop starts with a call of RND, whereafter there is a case construct on the delimiter just read. In contrast to the prescan program, the main scan has a separate case for almost every delimiter, in which a piece of object program is generated and the appropriate administrative actions are carried out. There is also a state, to control the activities in the central loop, and a push–down list to cater for the context–free character of the ALGOL 60 grammar. The state – in the prescan program just one boolean – is much more extended than during prescan and is used to record the context. Also the stack is used for many more purposes than in the prescan program.

CHAPTER 5. MAIN SCAN

5.1

Structure of the object program

The object program generated by the X1 ALGOL 60 compiler has been documented by Dijkstra [5]. This report is in Dutch and presents a mixture of a description of the object program itself and of its working during execution. The compiled program is in terms of 101 operators that are coded in ‘The Complex’, a complex of run–time subroutines. Many of the operators have parameters, which are transferred to the subroutine in one of the X1 registers. Therefore, the object program is full of instructions to load a parameter value, e.g. the address of a variable, into a register, followed by a call to one of the subroutines of the complex. A full list of the operators is given in Appendix C. The complex had two versions: ALD, using a 54 bits representation for real numbers, and ALS, using 27 bits to represent these. The latter ran slightly faster and used less space for storing real arrays but was hardly used in practice. The object program is transferred by the main scan to its destination (paper tape originally, store later) by means of the procedure ﬁll result list (FRL). FRL has two parameters: - the OPC–value, which is either the number of an operator from the complex (8 ≤ OP C ≤ 109), or has one of the values 0, 1, 2, or 3. - a word w. For an operator from the complex the value of w is irrelevant, otherwise it is an X1 instruction (or in a few cases a constant or a code word), to be incorporated into the object program. The OPC–value then indicates whether in the loading phase following the main scan the instruction should be taken as it is (OPC = 0), the begin address of the object program should be added to it (OPC = 1), the address part of the instruction should be replaced by the corresponding entry in the future list (a list of future references produced by the main scan) (OPC = 2), or the begin address of the constant list should be added to the instruction (OPC = 3). The result list RLI (both its version on paper tape and the one stored in computer store) is just an encoding of these parameters. It is only in the loading phase of the ALGOL 60 system that OPC–values ≥ 8 are replaced by the corresponding subroutine calls of the complex and the meaning of OPC–values ≤ 3 for w–values is taken into account. Apart from parameter–loading instructions, mainly jump instructions occur as explicit instructions, either coded with OPC = 1 (for backward jumps) or with OPC = 2 (for forward jumps). Only 11 instruction types (with diﬀerent opcodes) do occur as explicit instructions. The address of a variable can be either ‘static’ (for variables declared in the outermost

5.1. STRUCTURE OF THE OBJECT PROGRAM

block) or ‘dynamic’ (for variables declared in inner blocks). A dynamic address consists of two parts, a block number n and a displacement d relative to the begin of the block cell in the execution stack. As a parameter to an operator it is coded as 32 ∗ d + n. As an example we present in Figure 3 the piece of object program produced as the compilation of the statement ‘i:= 2 + i * i’, assuming the dynamic address n = 1, d = 7 for i and relative position 29 for constant 2 in the constant list. OPC 0 16 3 34 0 33 0 48 59 85

w explanation 2S 225 A load dynamic address of i in register S TIAD, take integer address dynamic 2B 29 A load static address of 2 in register B TIRS, take integer result static 2S 225 A load dynamic address of i in register S TIRD, take integer result dynamic 2S 225 A load dynamic address of i in register S MUID, multiply integer dynamic ADD, add ST, store

Figure 3: object code for the statement ‘i:= 2 + i * i’ The translation is syntax directed and in polish–reversed form. The load instructions are generated on the basis of the identiﬁer or constant assembled by RND, the operations are formed on the basis of the delimiters and kept in the compiler stack until they can be inserted in the object program. The latter is regulated by the priorities of operator and context. The assignment symbol ‘:=’ is considered an operator with lowest priority. Where possible an operator is combined with a preceding take. MUID is such a combination of TIRD and MUL (multiply). All of the instructions of the example given above are generated inside procedure production of object program. We come back to these points in a separate section. The translation is such that the code corresponding to applied occurrences of identiﬁers is generated during the analysis of the delimiter immediately following it. There is one exception to this rule: the code for a switch identiﬁer in a switch designator is generated after the code for the index expression. In this case the identity of the switch designator has to be saved in the stack (during analysis of ‘[’) and to be popped later (during analysis of ‘]’). As further examples we present in Figure 4 the translation of a procedure statement

CHAPTER 5. MAIN SCAN

OPC 511: 1 2 513: 3 15 0 34 56 13 1 3 3 0 523: 0 9

w explanation 2B 18 A load begin address of SUM in register B 2T 3 jump over translation of parameters 2B 0 A load static address of x in register B TRAS, take real address static 2B 138 A load static address of i in register B TIRS, take integer result static IND, indexer EIS, end of implicit subroutine 0A 513 C codeword for parameter x[i] 0A 5 A codeword for parameter 10 0A 4 A codeword for parameter 1 0A 138 A codeword for parameter i 2A 4 A load number of parameters in register A ETMP, extransmark procedure

Figure 4: object code for the statement ‘SUM(i,1,10,x[i])’ ‘SUM(i,1,10,x[i])’ and in Figure 5 that of a goto statement ‘goto s[i]’. OPC w explanation 0 2B 138 A load static address of i in register B 34 TIRS, take integer result static 29 SSI, store switch index (in location 48) 1 2T 65 A jump to code for declaration of s Figure 5: object code for the statement ‘goto s[i]’ Here we supposed that: - the translation of the procedure statement starts at (relative) address 511 of result list RLI; - the translation of the declaration of SUM starts at (relative) address 18 of result list RLI; - the contents of word 3 of future list FLI contains the (relative) address of the ﬁrst instruction following the translation of the actual parameters, i.e., 523; - the storage function1 of array x is located from word 0 of constant list KLI; 1

The ‘storage function’ of an array is a number of words containing the information nescessary to

5.2. THE EXECUTION MODEL

- the static address of variable i is 138; - constants 10 and 1 are located in words 5 and 4 of constant list KLI; - the (relative) address of the entry point for the code for the (switch) declaration of s is 65. The ﬁrst instruction of the implicit subroutine for parameter x[i] is located at (relative) address 513 in result list RLI; The subroutine ETMP in the complex gets in fact 3 parameters: the address of the code for SUM in register B, the number of actual parameters in register A, and the subroutine link (so that it, a.o., can ﬁnd the code words describing the actual parameters). Note that for simple actual parameters like variables and constants one parameter code word suﬃces to encode them. For each more complex actual parameter a piece of code, called implicit subroutine, is generated preceding the code words. In that case the code word contains, a.o., the (relative) address of that piece of object code.

5.2

The execution model

Although it is not very relevant for the discussion of the main scan of the compiler, we will nevertheless present some information about the execution model.

5.2.1

The execution stack

The main data structure during execution is the execution stack. It is a list of block cells, one for each block in execution, in order of the moment of block entry. Apart from the ﬁrst cell — that for the outermost block — each cell has the same structure: 5 words of link data, the locations of the formal parameters (2 words per parameter), the locations for local scalar variables (1 word for integers and booleans, 2 words for reals), the storage functions of local arrays ((3 + the array dimension) words), the storage functions of value arrays (8 words per array), space for the elements of local and value arrays (again 1 word per element for arrays of type integer or boolean, 2 words per element for real arrays), and the expression stack. The begin address of the block cell is called pp (procedure pointer), the begin address of the expression stack wp (working space pointer), and the address of the ﬁrst location following the expression stack ap (accumulator pointer). There are global variables AP, WP, PP, and BN containing these pointers and the block number of the blockcell currently in execution. compute the address of an array element given the index values.

CHAPTER 5. MAIN SCAN

The link data consist of: - the pp–value of the most recent incarnation of the lexicographically enclosing block (the ‘static’ link), - the wp–value, the pp–value and the block number just before block entrance (the ‘dynamic’ link), and - the return address (the subroutine link proper). These values are written by the complex subroutine ETMP, for a procedure statement of a non–formal procedure, or by ETMR (extransmark result, OPC 8), for a function designator of a non–formal type–procedure. These subroutines also reserve (and prepare the contents of) the locations of the formal parameters on the basis of the code words just preceding the call of ETMP or ETMR. The locations for the formal parameters contain: - for a parameter called by name and for an array parameter called by value: a two– location code word characterizing the corresponding actual parameter, which can be interpreted by OPC 18 (TFA, take formal address) or OPC 35 (TFR, take formal result), - for all other parameters called by value: their value in one (for integer or Boolean values) or two (for real values) words. ETMP and ETMR prepare the locations for all formal parameters as if they are called by name; the transformation of the code words to values for value parameters is carried out by (the object code of) the procedure declaration itself. The locations for all simple local variables together are reserved by three instructions in the code for the procedure declaration, simply incrementing AP and WP by the same amount. These instructions are generated by the compiler procedure reservation of local variables which is called when a type declaration is not followed by another type declaration. In this context it is important that all type declarations of a block are grouped together and precede all other declarations of the block. After the reservation of the locations for all simple local variables the storage functions for the local arrays are constructed, thereby incrementing the values of AP and WP anew by (array dimension + 3) per local array. The complex routines RSF (real arrays storage function frame, OPC 90) and ISF (integer arrays storage function frame, OPC 91) play a role here. Only after completion of the construction of the storage functions for all local arrays the storage functions for the value arrays are constructed using the formal parameter code words build by ETMP or ETMR, and incrementing the values of AP and WP by 8 per value array (this restricts the dimension of arrays called by value to at most

5.2. THE EXECUTION MODEL

5). This work is done in the compex routines RVA (real value array storage function frame, OPC 92) or IVA (integer value array storage function frame, OPC 93). Thereupon the space for the elements of all local and value arrays is reserved using LAP (local array positioning, OPC 94) or VAP (value array positioning, OPC 95). Both LAP and VAP increment AP and WP. VAP is also responsible for making the copy of the elements of the actual parameter array. The amount of space required for the array elements is not known at compile time, and does not play any role in the dynamic address system (the displacement part of which being restricted to at most 1023). RVA, IVA, LAP, and VAP are generated by the compiler procedure reservation of arrays which is called at the occurrence of the ﬁrst delimiter implying that no more declarations of local arrays follow. Here it is important that all array declarations of a block precede the declarations of switches and procedures. The expression stack consists of 4–word cells. The last word of each cells speciﬁes its type ( −1 for real values, −0 for integer values, some value ≥ +0 for addresses). Integer values and addresses are given by the ﬁrst word of a cell, real values use the ﬁrst three cell words (a mantissa of 52 bits + 2 sign bits, a binary exponent of 27 bits). ETMR reserves a 4–word cell on top of the expression stack before constructing the new block cell. Moreover, both ETMP and ETMR ﬁll one word just below the new block cell, ETMP giving it the value −0 and ETMR the address of the 4–word cell for the result. This word is inspected by OPC 87 (STP, store procedure value) to see whether the calling environment of a type procedure needs the result or not, and if so, where it should be stored. The translation of the procedure declaration: real procedure SUM(i,a,b,ti); value b; integer i,a,b; real ti; begin real s; s:= 0; for i:= a step 1 until b do s:= s + ti; SUM:= s end; is given in Figure 6. In Figure 6 we assumed that location 24 of the future list contains the (relative) address of the instruction following the return instruction, that location 8 of the constant list contains constant 0, and that procedure SUM is declared in the outermost block.

CHAPTER 5. MAIN SCAN

OPC 2 0 89 0 16 0 35 85 0 0 0 0 14 3 34 85 ... 0 31 0 87 12

w 2T 24 2B 1 A 2S 41 A 2S 41 A

2A 4A 4A 2S

2A 49 50 45 A

2B 8 A

... 2S 45 A 2B 0 A

explanation jump over procedure declaration load block number in register B SCC, short circuit load dynamic address of b in register S TIAD, take integer address dynamic load dynamic address of b in register S TFR, take formal result ST, store load length local area in register A increment WP increment AP load dynamic address of s in register S TRAD, take real address dynamic load static address of 0 in register B TIRS, take integer result static ST, store translation of the for statement load dynamic address of s in register S TRRD, take real result dynamic load block nr of enclosing block in register B STP, store procedure value RET, return

Figure 6: object code for the declaration of real procedure ‘SUM’

5.2.2

The display

A second data structure that plays an important role in the execution phase of an ALGOL 60 program is the display. It is a list disp of length BN + 1, and its elements are the PP–values of the static chain. More precisely, disp[0] = 0, disp[BN] = PP, whereas for all i, 1 ≤ i < BN, we have disp[i] = the static link from the block cell starting at disp[i + 1]. disp is used for converting dynamic addresses to static addresses: the static address corresponding to the dynamic address 32 ∗ d + n is disp[n] + d. disp is updated during block entrance (by routine SCC, short circuit, OPC 89, from the complex), block exit (by routine RET, return, OPC 12), just before a jump that leads to a label outside the block currently in execution (by GTA, goto adjustment, OPC 28) and

5.3. THE CONTEXT STATE

at the start and at the end of the execution of an implicit subroutine (the translation of a non–trivial actual parameter).

5.3

The context state

As stated before, the structure of the main–scan program is a loop in which a call of RND (read until next delimiter) is followed by a case analysis with respect to the delimiter just read. The interpretation of that delimiter often depends on the context, which is kept in a number of state variables, the context state. The context state can be described by the 6–tuple: (eﬂag, oﬂag, mﬂag, iﬂag, vﬂag, sﬂag) These ﬂags are boolean variables (coded 0 for ‘false’ and 1 for ‘true’), and have the following meaning: ﬂag eﬂag oﬂag mﬂag iﬂag vﬂag sﬂag

the context is an expression the start of an expression an actual parameter list a subscript list a for clause a switch declaration

eﬂag and oﬂag are set after the delimiters ‘if’, ‘do’, ‘:=’, ‘(’, ‘[’, and ‘array’. There are several places where eﬂag is reacted upon, e.g. to determine whether a procedure call is a procedure statement or a function designator. oﬂag is reacted upon at one place only; it determines whether the delimiters ‘+’ and ‘-’ should be interpreted as binary (oﬂag = 0) or unary (oﬂag = 1) operators. It is reset in each call of RND. mﬂag is set after a procedure identiﬁer followed by ‘(’, after pushing its old value to the stack. It is reacted upon in the analysis of the delimiters ‘,’ and ‘)’, interpreting them in case of mﬂag = 1 as actual parameter list separator and actual parameter list closing parenthesis, respectively. Its old value is popped when dealing with the latter (after generating the parameter code words and the ETMP or FTMP instruction). Moreover, mﬂag is reset at the beginning of expressions between parentheses and of subscript lists after pushing its old value, which is popped at the occurrence of the corresponding closing

CHAPTER 5. MAIN SCAN

bracket. (Note: mﬂag does not play any role in procedure declarations, since the procedure heading is analysed in an inner loop of the case ‘procedure’ of the central loop). iﬂag is set after reading the delimiter ‘[’. It is reacted upon in the analysis of the delimiter ‘,’, interpreting that delimiter as a separator in a subscript list or a bound pair list. Its old value is temporarily saved in the stack during the scan of an actual parameter list, a subscript list, and a bound pair list. In the ﬁrst case it is also reset. vﬂag is set after reading the delimiter ‘for’ and reset after reading ‘do’. It is reacted upon in the analysis of the delimiters ‘:=’ and ‘,’, interpreting these as delimiters in a for clause. During the scan of an actual parameter list vﬂag is reset, but its old value is kept in the stack. sﬂag is set after reading the delimiter ‘switch’. It is reacted upon in the analysis of the delimiters ‘:=’ and ‘,’, interpreting these as delimiters in a switch declaration. It is reset at the end of the switch declaration, when meeting a semicolon when sﬂag = 1. In case of the opening of a new context part of the old context state is saved in the stack and retrieved from the stack at return to the old context. This is carried out in an ad hoc fashion: each case only that part of the state is pushed that is relevant after the return from the new context and that (possibly) has an other value in the new context. As an example we mention that vﬂag is saved in the stack in the analysis of the delimiter ‘(’ provided that it is the opening parenthesis of an actual parameter list (this changes the interpretation of commas). There are three more ﬂags: pﬂag, jﬂag, and ﬄag. They play a role in the interpretation of identiﬁers and mainly aﬀect the generation of the object program. They are reset in each call of RND. If RND hopped over an identiﬁer (setting nﬂag = 1 and kﬂag = 0), the code of the central loop following the call of RND will set, according to the data stored in the namelist, pﬂag if the identiﬁer is the name of a procedure, jﬂag if it is the name of a label or switch, and ﬄag if it is the name of a formal parameter. Moreover, jﬂag is set at the begin of a switch declaration. As said, these ﬂags mainly aﬀect the generation of the object program. In some special situations they inﬂuence also the interpretation of a delimiter. An example of the latter is the interpretation of the delimiter ‘(’: if pﬂag = 1 it is interpreted as the opening parenthesis of an actual parameter list. At one occasion jﬂag is even pushed to the stack: at the occurrence of the delimiter ‘[’ its value is saved in the stack and retrieved from it at the occurrence of ‘]’. Also ﬄag is pushed at ‘(’ and ‘[’ and popped at the corresponding closing parentheses. In these cases the information about the identiﬁer concerned is needed at a later stage. Since the values of these three ﬂags are determined anew at each delimiter of the text, we do not consider them part of the context state.

5.4. THE NAME LIST

5.4

The name list

During the main scan the compiler maintains a symbol table called the name list NLI. It contains all identiﬁers that are in scope. There is no block structure visible in this list: the only structure present is the list’s ordering: the identiﬁers of the most recently entered block structure are at the end of the list. Searches scan NLI in backward order: the search for an identiﬁer starts at the end of NLI and continues until the identiﬁer is found or the begin of the list is reached (in which case the compilation is halted with error stop 7: ”undeclared identiﬁer”). In contrast to the prescan list PLI, NLI contains for each identiﬁer a one–word descriptor (immediately following the one– or two–word coding of the identiﬁer). The interpretation of the 27 bits of this descriptor is depicted in Figure 7.2 Note that array identiﬁers are not marked as such in their descriptor. At the begin of a new block in the text the current length of NLI (recorded in the compiler variable nlsc) is saved in the stack. Thereupon the next two sublists of the prescan list PLI are moved to (the end of) NLI, adding to each identiﬁer a descriptor: d17 + d15 + d19 ∗ bn for the label and switch identiﬁers of the ﬁrst sublist, d18+d15+d19∗bn for the procedure identiﬁers of the second sublist, where bn is the block’s blocknumber. In the case of a procedure declaration the formal parameter list is scanned after this augmentation of the name list. The formal parameter identiﬁers are added to the name list with a descriptor containing their dynamic address and the bits d16 + d15. Thereupon the value list is scanned, the identiﬁers are searched for and d26 is added to their descriptors. Next the speciﬁcations are scanned, adding d17 for identiﬁers speciﬁed ‘label’ or ‘switch’, d18 for identiﬁers speciﬁed {} ‘procedure’, and d19 for identiﬁers speciﬁed ‘integer’ or ‘Boolean’ {‘array’}. Moreover, for identiﬁers speciﬁed ‘real’, ‘integer’ or ‘Boolean’ that occurred in the value list (having d26 = 1) d26 is reset and code is generated for evaluating the corresponding actual parameter and storing its value at the location reserved for the actual parameter code word. According to the restrictions for X1 ALGOL 60 programs all formal parameters should be speciﬁed. This plays a role in the code to be generated for a statement like ‘p(s[i])’ where ‘s’ is a formal identiﬁer. For a formal switch identiﬁer this code diﬀers from the code for a formal array identiﬁer. At each applied occurrence of a nonformal label, switch, or procedure identiﬁer the com2

In the X1 tradition the 27 bits of a word were denoted by d26, d25, . . . , d0, d26 being the most signiﬁcant bit.

CHAPTER 5. MAIN SCAN

bits d26 d25, d24 d23 · · · d19 d19

d18 d17 d16 d15

d14 · · · d0

interpretation 1 for a formal value parameter for which not yet its evaluation code has been generated, 0 otherwise OPC–value for a nonformal label, switch or procedure identiﬁer for a nonformal label, switch, or procedure identiﬁer: its block number, otherwise d23 · · · d20 all 0 1 for an integer or Boolean type variable or array or for a formal parameter occurring in the value list and speciﬁed integer or Boolean (array) 1 for a formal or nonformal procedure identiﬁer 1 for a formal or nonformal label or switch identiﬁer 1 for a formal name parameter identiﬁer for a nonformal label, switch, or procedure identiﬁer: 1 before its ﬁrst occurrence in the text, 0 thereafter for a simple variable, an array, or a formal parameter: 1 if it has a dynamic execution–stack address, 0 otherwise object–code address (for a label, switch, or procedure), future–list location (idem), or execution–stack address (for a simple variable, array, or formal parameter)

Figure 7: The 27 bits of a descriptor in the name list piler routine test ﬁrst occurrence is called. If d15 = 1, i.e., if it is its ﬁrst texual occurrence (which therefore precedes its deﬁning occurrence), d15 is reset, d25 is set (giving the identiﬁer an OPC value of 2), a place in the future list is reserved for the as yet unknown object–code address, and the address of that place is ﬁlled in in bits d14 · · · d0 of the descriptor. At the deﬁning occurrence of a label, switch, or procedure identiﬁer the compiler routine label declaration is invocated. If d15 = 1, d15 is reset, d24 is set (giving the identiﬁer an OPC value of 1), and the current length of the object code (recorded in the compiler variable rlsc) is ﬁlled in in bits d14 · · · d0 of the descriptor. If, on the other hand, d15 = 0, the value of rlsc is stored in the future list at the location stored in bits d14 · · · d0 of the descriptor. Note that in that case all applied occurrences of that identiﬁer are addressed

5.4. THE NAME LIST

with an OPC value of 2 and a reference to the future list, also those following its deﬁning occurrence. Another task of label declaration is the output to the console typewriter of the label, switch, or procedure identiﬁer, followed by its (relative) object–code address in 32–ary scale notation. All other deﬁning occurrences of identiﬁers (i.e. of scalar variables and of arrays) lead to the addition of that identiﬁer at the end of the name list. They get static addresses if their declarations occur in the outermost block, otherwise they get dynamic addresses3 . Therefore, they get a descriptor with d14 · · · d0 ﬁlled in, d15 = 1 in case of dynamic addressing, and d19 = 1 in case of an integer or Boolean (array) type. At the end of a block the old length of NLI is retrieved from the stack and stored in nlsc, thereby eﬀectively removing all local identiﬁers of the block from the name list. Identiﬁers are searched for in the name list by the compiler routine look for name. If the identiﬁer is found then its descriptor is copied to the compiler variable id ; the (relative) position of the descriptor within the name list is stored in another compiler variable nid. Note that id and nid potentially change value after each call of read until next delimiter in the main cycle. In general, the old values need not to be saved in the stack. In four cases, however, nid is pushed to the stack: during the scan of the of a , of the of a , of the of an , and of the of a . In the ﬁrst two cases the old value is used afterwards indeed. At the start of the main scan the name list is preﬁlled with a number of identiﬁers. These are the identiﬁers of those procedures and functions that are available without declaration. To these belong the standard functions abs, sign, sqrt, sin, cos, ln, exp, entier, and arctan, some input and output procedures as read, print, TAB, SPACE, PRINTTEXT, FLOT, FIXT, and ABSFIXT, and some frequently used functions. They fall apart in two catagories: - The ﬁrst nlscop words of this preﬁll belong to procedures that are treated as operators. A call of such a procedure is translated by code transferring its parameter values to the stack, followed by an invocation of the corresponding routine from the complex of runtime routines. - The remaining nlsc0 − nlscop words belong to procedures that in the loading phase of the system are selectively added to the code from some library source. For the procedures of the ﬁrst category the discriptor has the value d18 + 12 ∗ 256 + n + o, 3

Own scalar variables and own arrays always get static addresses, as if they were declared in the outermost block.

CHAPTER 5. MAIN SCAN

where o is the OPC–value of the operator and either 76 ≤ o ≤ 84 and n = 57 or 102 ≤ o ≤ 108 and n = 40. It is likely that the latter group is from a historically later period than the ﬁrst group. OPC–value 81 was reserved for the function arctan which later was moved to the library, using a diﬀerent algorithm. For the procedures of the second category the descriptor has the value d18 + d15 + m, where m is the number of the routine in the library. Finally we remark that clearly the name list has been designed to occupy a minimal amount of core store. The identiﬁers of blocks that have been scanned completely do not require store any longer, where as for blocks in the yet unscanned part of the text only the local label, switch, and procedure identiﬁers are kept in the prescan list.

5.5

The constant list

The constant list KLI is built during the main scan and contains all constants that occurred in the program thusfar, including values for the logical values4 ‘true’ and ‘false’. Each constant met by RND in the central loop of the main scan is searched for by the compiler routine look for constant. If the constant is not found it is added to the list. Moreover, look for constant assigns the value d25 + d24 + the (relative) address of the constant in KLI + (if dﬂag = 0 then d19 else 0) to the compiler variable id as a pseudo descriptor. Another contribution to KLI are the storage functions of the arrays declared in the outermost block and of all own arrays (which, in fact, are treated as if they were declared in the outermost block). The storage function consists of (3 + array dimension) numbers which are computed by the compiler and stored in KLI by means of the compiler routine ﬁll constant list. According to the restrictions for X1 ALGOL 60 programs the array bounds for these arrays should be numbers (instead of s). The array bound numbers are read by a separate inner loop of the main scan program and not added to the constant list but processed immediately in the construction of the storage function. 4

ALGOL 60 terminology.

5.6. THE FUTURE LIST

5.6

The future list

In the generation of the object program it occurs frequently that an instruction refers to an address in the object program that is not yet known. This is the case for applied occurrences of label, switch and procedure identiﬁers that precede their deﬁning occurrences, but also for the forward jumps that are used in the code for certain ALGOL program constructs like conditional statements and for statements. In such a case the ﬁrst free location of the future list FLI is reserved for the yet unknown address and the index of that location is used as address in the instruction (marked as such by an OPC value of 2). During the loading phase of the ALGOL system the future list references in the object program are replaced by the contents of the future list. In the case of a forward reference to the declaration of an identiﬁer the index of the reserved location in FLI is stored in the descriptor of that identiﬁer in the name list as described in a previous section. In the case of a forward reference in a program construct the index of the reserved location is saved in the stack or in a global compiler variable and retrieved when the object–code address concerned is deﬁned. Then the latter can be ﬁlled in in the FLI location. As an example of the use of FLI we give the translation of the expression ‘(if x > y then x else y)’ in Figure 8. Suppose that preceding the compilation of that expression the length of the object code rlsc = 182 and the length of the future list ﬂsc = 18. Let, moreover, both x and y be of type real and statically addressed with 138 and 140, respectively. After generating this code, FLI[18] = 192, FLI[19] = 194, ﬂsc = 20 and rlsc = 194. The future list is also used when one of the library routines is used in the program. At the ﬁrst occurrence of its identiﬁer a location is reserved in FLI which is ﬁlled by the descriptor of that identiﬁer. In the name list itself that descriptor is replaced by d18 + d24 + d25 + the index of the reserved location in FLI. These actions are carried out in the compiler procedure test ﬁrst occurrence. The reservation of a location in the future list is done explicitely by reading the value of ﬂsc and incrementing it. The assignment of a value to such a location is always carried out by means of the compiler procedure ﬁll future list, which takes two parameters: the (absolute) store address of the location and the value to be assigned. As we will discuss elsewhere it may be nescessary to enlarge the area reserved for the future list ﬁrst before the assignment can be eﬀectuated, but this is encapsulated totally inside ﬁll future list.

CHAPTER 5. MAIN SCAN

OPC w 182: 0 2B 138 A 32 0 2B 140 A 32 65 30 2 N 2T 18 0 2B 138 A 32 2 2T 19 192: 0 2B 140 A 32 194:

explanation load static address of x in register B TRRS, take real result static load static address of y in register B TRRS, take real result static MOR, more CAC, copy Boolean accumulator into condition if condition = NO, jump to else part load static address of x in register B TRRS, take real result static jump over else part load static address of y in register B TRRS, take real result static

Figure 8: The translation of the expression ‘(if x > y then x else y)’

5.7

The translation of a for statement

The translation of a contains many forward references for which the future list is heavily used again. A scheme for the translation of ‘for := do ’ is presented in Figure 9.

r1 :

FLI[f1 ]:

FLI[f3 ]: FLI[f2 ]:

OPC 2 ··· 20 2 0 2 9 ··· 2 27 19 1 ··· 1

w 2T f1 ··· 2T f2 2A 0 A 2B f3 ··· 2S f4

2T r1 A ··· 2T r1 A

explanation jump over code for code generating the address of the variable on the execution stack FOR1 jump to translation of load 0 in register A load address of FOR0 instruction in register B ETMP, extransmark procedure code for load address of instruction following the into S FOR8 FOR0 jump to code for code for jump to code for

FLI[f4 ]:

Figure 9: The translation of ‘for := do ’

5.7. THE TRANSLATION OF A FOR STATEMENT

In Figure 9, f1 , . . . , f4 are locations in the future list ﬁlled with the appropriate (relative) object–code addresses, whereas r1 is the (relative) object–code address given to the code for generating the address of the controlled variable on the stack (allways the second instruction of the translation of the ). The code for loading the address of a variable to the execution stack depends, of course, on the nature of that variable: - for a formal identiﬁer ‘v’ it is: 0 2S @v A load dynamic address of v in register S 18 TFA, take formal address - for a simple variable ‘v’ it consists of an instruction loading the address of v to register B (static addressing) or S (dynamic addressing), followed by one of the instructions TRAD (OPC 14), take real address dynamic, TRAS (15), take real address static, TIAD (16), take integer address dynamic, or TIAS (17), take integer address static. - for a subscripted variable ‘v[i1 , . . . , in ]’ the code reads: ··· ··· ··· ··· 56

··· ··· ··· ···

code generating the address of v to the execution stack code generating the value of i1 to the execution stack ··· code generating the value of in to the execution stack IND, indexer

The code for the is the concatenation of the codes of its constituent s, which read: - for an arithmetic expression E: the code generating the value of E to the execution stack, followed by FOR2 (OPC 21). - for the ‘while element’ ’E while B’: ··· 22 ··· 23

··· ···

code generating the value of E to the execution stack FOR3 code generating the value of B to the execution stack FOR4

- for the ‘step–until element’ ’E1 step E2 until E3 ’:

CHAPTER 5. MAIN SCAN

··· 24 ··· 25 ··· 26

5.8

··· ··· ···

code generating the value of E1 to the execution stack FOR5 code generating the value of E2 to the execution stack FOR6 code generating the value of E3 to the execution stack FOR7

The compiler stack

Whereas during the prescan the compiler stack is used only to keep track of the block structure of the ALGOL 60 program, during the main scan it is used for many more purposes. In this section we give an overview of the most important applications of the compiler stack. For pushing values on top of the stack the same compiler procedure ﬁll t list is used as in the prescan. For popping a value from the top of the stack to a compiler variable the procedure unload t list element is frequently used. Sometimes, however, it is done explicitely, especially if there is no interest in that value. The inspection of the top of the stack is always by explicit code. The stack is used for the following purposes: - to keep track of the block structure. For each block that has been entered but not yet exited the stack contains three values: a location in the future list (in which the ﬁrst code address after the block has to be ﬁlled in), the length of the name list prior to block entrance, and a block–begin marker (the value 161). These are pushed to the stack, partly by means of a procedure intro new block, when encountering a declaration immediately following a delimiter ‘begin’, and when dealing with the delimiters ‘do’ and ‘procedure’. They are popped from the stack when a delimiter ‘;’ or ‘end’ indicates the end of the block. - as discussed in Section 5.3, at context switches, to save and later restore part of the context state. - to record the begin address of a piece of code which will be referred to at some point(s) in the sequel, in situations where the possibility of recursive constructs prohibits to save it in a global compiler variable. An example of this we met in the previous section, where the address r1 of the code for the controlled variable of a has to be saved for later use. Since the controlled statement can be or contain another for statement, this code address has to be saved in the stack. It is pushed when dealing with ‘for’ and popped in the treatment of ‘;’ and ‘end’

5.9. THE TRANSFORMATION OF EXPRESSIONS

when it is the end of that for statement. - to record locations in the future list in which yet unknown code addresses have to be ﬁlled in. For an example we refer to the previous section again, where location f4 is pushed to the stack (when dealing with ‘do’) and popped at the end of the for statement. Note that neither f1 nor f2 nor f3 need to be saved in the stack: only when dealing with the controlled statement new for constructs can be encountered; f1 is kept in the global compiler variable fora, f2 in forc, and f3 in fora again. - in the transformation of expressions to polish–reversed format. This is discussed in the next section. - to record the code words for the actual parameters of a or a . An example of the translation of a procedure statement is given in Section 5.1. The four code words are constructed during parameter analysis and pushed to the stack when dealing with the parameter separator ‘,’ or the parenthesis concluding the parameter list. They are popped when dealing with that concluding parenthesis. - to record the entry points for the code for the s of a in a . When the concluding semicolon is encountered a piece of object code is generated with a jump instruction to each of these entry points.

5.9

The transformation of expressions

The transformation of expressions to polish–reversed notation is based on a priority scheme. To each operator a priority is assigned according to the following table: ( := ≡ ⇒ ∨ ∧ ¬ , = +,(binary)– (unary)–,∗,/, : ↑

0 2 3 4 5 6 7 8 9 10 11

CHAPTER 5. MAIN SCAN

Note that subtraction gets priority 9 whilst the unary operator for sign inversion gets priority 10. In the transformation the code for loading operands is always generated immediately, the code for operators has possibly to be postponed until the priority of the context is suﬃciently low. In case of postponement the operator is saved in the stack. In fact, pairs are pushed to the stack consisting of the operator itself and its priority (coded as 256 ∗ priority + representation of the operator). An invariant of the algorithm is that the top part of the stack contains some value with priority part 0 and zero or more operators with priority part ≥ 2. While scanning an expression from delimiter to delimiter, for each operator roughly the following actions are carried out: - set the operator height oh equal to the operator’s priority. - if nﬂag = 1 (indicating that the operator was immediately preceded by an identiﬁer or constant) then generate an instruction that loads an address into register B or S using the information found in the compiler variable id. The appropriate load operation for the operand is selected. If the top of stack contains one of the operators +, (binary) –, ∗, /, or : and if its priority part is at least oh, that operator is removed from the stack and integrated with the selected load operation. The resulting operation code is added to the object code. - as long as the top of the stack contains an operator/priority pair with priority part at least oh it is removed from the stack and the corresponding operation instruction is added to the object code. - the current value of dl and its priority are pushed to the stack as a new operator/priority pair. The ﬁrst three of these actions are executed by a call of the compiler procedure production of object program with the operator’s priority as a parameter. At the occurrence of the ﬁrst delimiter not belonging to the expression (i.e., one of the symbols from the follow set of consisting of the symbols ‘)’, ‘]’, ‘;’, ‘end’, ‘then’, ‘else’, ‘do’, ‘while’, ‘step’, ‘until’, ‘,’, and ‘:’) the translation of the expression is ﬁnalized by a call of production of object program with parameter value 1 (in some cases indirectly via a call of the compiler procedure empty t list through thenelse). A delimiter ‘(’ within an expression is pushed to the stack with priority value 0. The expression following it is thereby handled separately; at the occurrence of the corresponding closing parenthesis ﬁrst that expression is ﬁnalized; thereafter the opening parenthesis is popped from the stack again.

5.10. DESIGNATIONAL EXPRESSIONS

The value at the bottom of the operator stack (having priority ﬁeld 0) can be either the representation of some delimiter, like ‘(’, ‘if’, ‘then’, ‘else’, ‘while’, ‘step’, ‘until’, ‘begin’, ‘[’, or the block–begin marker 161, or the switch list separation marker 160.

5.10

Designational expressions

Designational expressions occur in three roles: as element of a in a switch declaration, as element of an in a procedure statement or a function designator, and following the delimiter ‘goto’ in a goto statement. In all three roles a designational expression is translated in the same way: execution of the object code will always lead to the tranfer of control to some label. Consequently, the occurrence of a ‘goto’ symbol can be ignored by the compiler but for the fact that it marks the beginning of a statement and thereby possibly the end of the declarations of a block. The translation of an identiﬁer ‘id ’ occurring in a designational expression (i.e., an identiﬁer having d17 = 1 in its descriptor in the namelist, indicating that it is a label or switch identiﬁer) depends on the delimiter immediately following it. If that diﬀers from ‘[’, id is interpreted as a label identiﬁer and translated in one of the following ways: - if id is a non–formal identiﬁer the translation is a jump instruction. Its precise form depends on two circumstances: - if the label declaration precedes the ﬁrst applied occurence of that label, it reads: ‘2T @id A’ with OPC–value 1, where @id denotes the address part of the descriptor belonging to id. Otherwise it reads: ‘2T fid ’ with OPC–value 2, where fid is the location in the future list reserved for id. - if the goto statement leads to a label outside the current block the jump instruction is preceded by two instructions: - an instruction ‘2B bnid A’ with OPC–value 0, where bnid is the blocknumber of id, and - the instruction GTA (goto adjustment, OPC 28) which caters for the necessary adaptation of execution stack and display. - if id is a formal identiﬁer the translation reads: - the instruction ‘2S @id A’ with OPC–value 0, followed by - the instruction TFR (take formal result, OPC 35). On the basis of the code words for id in the block cell, TFR transfers control to the implicit subroutine for the corresponding actual parameter. This translation of id is completely produced by only one call of the compiler procedure

CHAPTER 5. MAIN SCAN

production of object program. If, on the other hand, id is followed by ‘[’ it is interpreted as a switch identiﬁer. The translation of ‘id [E]’ reads: - the translation of the subscript expression E in the usual way, - the instruction SSI (store switch index, OPC 29), which stores the value of E, incremented by 1, in store location 48 (16 X 1), - the translation of id as if it were a label identiﬁer. This code will, when executed, transfer control to the very last instruction of the translation of the corresponding switch declaration which is the table jump instruction (the jump table just precedes this instruction). The occurrence of a designational expression or a switch identiﬁer as an actual parameter leads always to the production of an implicit subroutine. As all implicit subroutines it ends with the instruction EIS (end of implicit subroutine, OPC 13) which is never executed. As an example consider the following ALGOL 60 program: begin switch s:= AA; procedure p(ss); switch ss; goto if false then ss[1] else BB; AA: p(s); BB: end In Figure 10 we give the complete translation of this program. It produces the following future list FLI: location contents 0 5 1 22 2 22 3 18 4 21 5 31 6 29

5.10. DESIGNATIONAL EXPRESSIONS

2: 4: 5: 6:

18:

21: 22: 24:

29: 31:

OPC w explanation 96 START 2 2T 0 jump over switch declaration to code address 5 2 2T 1 jump to code address 22, i.e. AA (FLI[1] = 22) 1 2T 2 A jump to code address 2 (for index value 1) 0 1T 48 jump backwards over store[48] places 2 2T 2 jump over procedure declaration to code address 22 0 2B 1 A load block number in register B 89 SCC, short circuit 3 2B 0 A load KLI[0], i.e. 1, in register B 34 TIRS, take integer result static 30 CAC, copy Boolean accumulator into condition 2 N 2T 3 jump over then–part to code address 18 3 2B 0 A load KLI[0], i.e. 1, in register B 34 TIRS, take integer result static 29 SSI, store switch index 0 2S 161 A load (dynamic) address of ss in register S 35 TFR, take formal result 2 2T 4 jump over else–part to code address 21 0 2B 0 A load 0 (block number of BB) in register B 28 GTA, goto adjustment 2 2T 5 jump to code address 31, i.e. to BB (FLI[5] = 31) 12 RET, return 1 2B 6 A load code address 6, i.e. of p, in register B 2 2T 6 jump to code address 29 (FLI[6] = 29) 0 2B 0 A load 0 (block number of s) in register B 28 GTA, goto adjustment 1 2T 4 A jump to code address 4, i.e. to s 13 EIS, end of implicit subroutine 1 0A 24 B parameter code word, code address 24 0 2A 1 A load 1 (number of parameters) in register A 9 ETMP, extransmark procedure 97 STOP Figure 10: The translation of a program involving labels and switches

CHAPTER 5. MAIN SCAN

and the following constant list KLI: location contents 0 1 Furthermore the following (relative) code addresses are assigned to the label, switch and procedure identiﬁers: identiﬁer code address s 4 p 6 AA 22 BB 31

5.11

The central loop

The overall structure of the central loop of the main scan is rather simple: it consists of the following components: 1 a call of read until next delimiter ; 2 if nﬂag = 0 a call of either look for constant or look for name; moreover, jﬂag, pﬂag, and ﬄag are redeﬁned as described before; 3 a case statement with a case for each of the possible values of dl, i.e. the delimiter found by RND. There are, however, a few complicating factors. - in a few cases of the case statement there is a need to inspect the next delimiter as a look–ahead symbol. Then, in the next iteration of the central loop, the call to RND has already been carried out and should be suppressed. - at some other occasions also the second step of the main loop is suppressed. At one occasion this is obligatory: when the delimiter ‘]’ is encountered and if after the restoration of the old context jﬂag happens to be 1 indicating that ‘]’ ends a switch designator, id contains (a copy of) the desciptor of the switch identiﬁer, which is still relevant for the generation of a piece of object code. This generation is delegated to the case for the next delimiter which is read with RNS rather than RND. At other occasions the second step of the central loop is suppressed only as a sort of short–cut because no identiﬁer or constant should have preceded the delimiter.

5.11. THE CENTRAL LOOP

- some of the cases share a piece of code. This is implemented by jumps from one case into another (and sometimes back again). A typical example of this is found in the code for delimiter ‘do’, where part of the code for the delimiter ‘,’ is executed in order to generate one of the instructions FOR2 (OPC 21), FOR4 (OPC23) or FOR7 (OPC 26), concluding the translation of the last for–list element, before continuing the code for ‘do’ itself. These factors make it hard to encode the main loop in a structured way. Below we ﬁrst present the cases for the four delimiters ‘∗’, ‘step’, ‘[’, and ‘:’. ‘∗’ two subroutine calls only (cf. Section 5.9): production of object program(10); ﬁll t list with delimiter ‘step’ again two subroutine calls; the ﬁrst one ﬁnalizes the generation of the object code for the expression preceding the delimiter ‘step’ (which might be a conditional expression): empty t list through thenelse; ﬁll result list(24{FOR5},0) ‘[’ we have the following components: - if eﬂag = 0 then reservation of arrays; in a non–expression context the occurrence of ‘[’ implies that the declaration part of the block is over. If the block contains array declarations possibly still some code for these has to be generated. - oﬂag:= 1; oh:= 0; since a new arithmetic expression follows, initial adding operators should be interpreted as unary operators. - save (part of) the current context to the stack: eﬂag, iﬂag, mﬂag, ﬄag, jﬂag, and nid. The stacking of nid is important in the case that jﬂag = 1, implying that the delimiter ‘[’ is part of a switch designator. - eﬂag:= 1; iﬂag:= 1; mﬂag:= 0; redeﬁne the context such that it is that of index expressions and not that of actual parameters. Important for the interpretation of comma’s. - ﬁll t list with delimiter ; save ‘[’ to the stack with oh–component 0. - if jﬂag = 0 then generate address; in case of an array identiﬁer the delimiter ‘[’ is part of a subscripted variable. The compiler has to generate code for loading the address of the storage function

CHAPTER 5. MAIN SCAN

of the array to the execution stack. In correct programs the delimiter ‘[’ is always preceded by an identiﬁer. ‘:’ Here we have two cases, one of which is selected on the basis of the context state. 1. jﬂag = 0: the colon is interpreted as separator in a bound pair list. The generation of the object code for the lower–bound expression is ﬁnalized and the bound pair is counted (in a global variable, no danger of recursion!): ic:= ic + 1; empty t list through thenelse 2. jﬂag = 1: the colon was preceded by an identiﬁer with d17 = 1 in its descriptor, indicating that the identiﬁer was isolated during prescan as label of a statement or as switch identiﬁer in a switch declaration. The colon is interpreted as marking the label of a labeled statement. Since it could mark the begin of the compound tail of a block and, therefore, the end of the declarations of a block head, possibly some object code has to be generated to ﬁnalize array declarations. No further object code is needed, but, of course, the descriptor of the label identiﬁer in the name list should be updated: reservation of arrays; label declaration The most complex case analysis is required for the delimiter ‘,’. The following cases are distinguished: 1. iﬂag = 1 The comma is interpreted as subscript separator in a subscript list. 2. (iﬂag = 0) ∧ (vﬂag = 1) The comma is interpreted as separator between for list elements in a for list. 3. (iﬂag = 0) ∧ (vﬂag = 0) ∧ (mﬂag = 1) The comma is interpreted as separator between actual parameters in the actual parameter list of a procedure statement or a function designator. 4. (iﬂag = 0) ∧ (vﬂag = 0) ∧ (mﬂag = 0) ∧ (sﬂag = 1) The comma is interpreted as separator between designational expressions in the switch list of a switch declaration. 5. Otherwise, the comma is interpreted as separator in the bound pair list of an array declaration. Some cases in the case analysis in the central loop contain inner loops. These are presented in the next section.

5.12. THE INNER LOOPS OF THE CENTRAL LOOP

5.12

The inner loops of the central loop

In some of the cases that are distinguished in the central loop of the main scan we ﬁnd one or more inner loops. They fall apart in two classes. In the ﬁrst place there are inner loops to ﬁnalize the generation of a piece of object code after the detection of the concluding delimiter of a certain construction. Typical examples are: - repeat production of object program(1) until not thenelse; to enforce the completion of the code for all pending conditional constructs. We ﬁnd such a loop in the cases for the delimiters ‘then’, ‘,’, ‘)’, ‘]’, ‘;’, and ‘end’. - the generation of the actual parameter code words (stored in the compiler stack), after the detection of the closing parenthesis of the actual parameter list. - the addressing of the identiﬁers in an array segment of an array declaration, after detection of the closing square bracket. - the generation of the jump table for a switch declaration from the list of begin addresses of the code for the designational expressions (stored in the compiler stack), after the detection of the concluding semicolon. More interesting are the situations in which a piece of the source text is read, analyzed and compiled within one of the cases of the central loop. These are: - after the detection of a string quote the string is read and transferred to the object program in portions of three characters in one word of object code. - after the detection of the delimiter ‘end’ the input string is scanned until the ﬁrst occurrence of one of the delimiters ‘;’, ‘else’, or ‘end’ (with one exception: if the delimiter marks the end of the program). Recall that this kind of comment is, in the prescan program, unjustly skipped by the central loop itself. - after a type symbol (‘real’, ‘integer’, or ‘Boolean’) followed by an identiﬁer the whole type list is scanned; all identiﬁers are added to the name list. Moreover, in the case of an inner block of the program all type declarations following the ﬁrst one are analyzed at once without returning to the main loop. - for an array declaration in the outermost block all array lists are read and analysed. According to the restrictions of X1–ALGOL, all bounds of arrays declared in the outermost block should be numbers. Their values are immediately used to construct the storage functions of these arrays which are added to the constant list. For an array declaration in an inner block of the program only the array identiﬁers of the current array segment are read and added to the name list; the bound pair list is analyzed in the central loop.

CHAPTER 5. MAIN SCAN

- of a procedure declaration the formal parameter part, the value part, and the speciﬁcation part are completely handled after the detection of the delimiter ‘procedure’. It leads to the addition of the formal parameter identiﬁers to the name list and to the construction and alteration of their descriptors. Moreover, code is generated for those formal parameters that occur in the value list and that are speciﬁed as ‘real’, ‘integer’, or ‘Boolean’.

5.13

Store management

During the main scan of the compiler the following data structures have to be represented in store: -

the the the the the

compiler stack TLI; future list FLI; constant list KLI; name list NLI; (remaining part of the) prescan list PLI.

In the latest version of the compiler two additional data structures also had to ﬁnd a place in store: - the (remaining part of the) internal representation of the source text; - the object program RLI in compressed representation. For the compiler stack 128 words were reserved at a ﬁxed location as described in Section 4.2. The remaining working space of the compiler, running from store address 1933 upto 6783, was used to accommodate all other data. The prescan list resides at the end of the available space; its length shrinkes at each block introduction, which, as explained before, transfers two sublists from the prescan list to the name list. The compressed representation of the object code is placed at the beginning of the working space. At the start of the main scan the internal representation of the source text starts only 8 places beyond the (then still empty) object program. Luckily, during the main scan the source text is consumed whilst the object program grows. If, however, the object code is about to overwrite the source text, the latter is, together with FLI, KLI and NLI, shifted upwards over 8 places. The future list immediately follows the source text. The constant list is initially placed 16 places beyond the (then still empty) future list and the name list 16 places beyond

5.14. SOME QUANTITATIVE DATA

the (then still empty) constant list. FLI and KLI are steadily growing during the main scan, whilst NLI grows and shrinks in connection to block structure. If FLI is about to overwrite KLI both KLI and NLI are shifted upwards over 16 places; if KLI would overwrite NLI then NLI is shifted upwards over 16 places. In this way the lists are accomodated as a kind of ﬂoating islands in a linear sea; the fact that in case of a collision the distance is enlarged by more than one place reduces the frequency of the necessary shifts and thereby the total costs of storage management. Maybe this technique was rather new in that time in which ‘heaps’ still had to be invented. Before any list is shifted it is checked that by the shift the remaining part of the prescan list will not be overwritten. If that would be the case the compiler halts with error stop 6, 16, 18, or 25. All assignments to RLI, FLI, KLI, and NLI in the compiler are executed by the invocation of a procedure in which all the necessary checks are carried out and the absolute address of the location is determined. The compiler itself only keeps track of relative positions (with respect to the begin of the lists).

5.14

Some quantitative data

In order to obtain some feeling for the performance of the compiler we collected some data of the translation of a sample program. We took the same program by Zonneveld used before. The output of the main scan for this program can be summarized as follows: total length of object code length of future list length of constant list

2538 192 84

The source program (in our lay–out) takes 185 lines (blank lines inclusive), therefore the object code has on the average 13.7 instructions per line of source text. This is a relative high number. But we should keep in mind that a simple load operation of an integer variable requires two instructions: one for loading the static or dynamic address to a register and a call to one of the routines in the complex of subroutines. This is also reﬂected by the fact that on the average for each delimiter found by RND 2.02 instructions of object code are generated.

CHAPTER 5. MAIN SCAN

From the 2538 object code instructions 1112 were generated with OPC value ≤ 3 and 1426 with OPC value ≥ 8 (i.e., a call to the complex of run–time subroutines). The object words with OPC values ≤ 3 can be subdivided as follows: OPC OPC OPC OPC

= = = =

0 574 words 1 88 words 2 205 words 3 245 words

There are 50 parameter code words, 25 words encoding strings, 189 jump instructions, 839 instructions loading a value in register A, B or S as parameter of a complex subroutine, and 9 instructions to increment the execution stack pointers for 3 procedure declarations. More speciﬁcally, we found as most frequent OPC/instruction combinations: OPC X1–instruction count frequency 0 2S . . . A 454 40.8 3 2B . . . A 220 19.8 2 2T . . . 101 9.1 1 2T . . . A 66 5.9 catering for three quarters of the cases. The 13 most frequently generated contributions to the object program with OPC value ≥ 8 are: OPC 34 33 56 85 14 58 31 9 18 16 59 15 19

name TIRS TIRD IND ST TRAD TAR TRRD ETMP TFA TIAD ADD TRAS FOR0

meaning Take Integer Result Static Take Integer Result Dynamic INDexer STore Take Real Address Dynamic TAke Result Take Real Result Dynamic ExTransMark Procedure Take Formal Address Take Integer Address Dynamic ADD Take Real Address Static FOR0

count frequency accumulated 148 10.58 10.58 129 9.05 19.42 129 9.05 28.47 98 6.87 35.34 92 6.45 41.80 81 5.68 47.48 57 4.00 51.47 52 3.65 55.12 51 3.58 58.70 35 2.45 61.15 35 2.45 63.60 34 2.38 65.99 32 2.24 68.23

5.15. SOME PROBLEMS

which cater for more than two third of the subroutine calls to the complex. Striking is the relative unimportant role of the arithmetic operations in a typical numeric program for the calculations of planetary orbits, at least at the code level. The most frequent arithmetic operation, ADD, occurs only at the 10/11th line in the list, and the total count of arithmetic operations sums up to 178, i.e. 12.48 % of the invocations of a routine in the complex. In compacted form the object code requires only 981 words (+ 9 bits for the code word under construction), that is about 10.5 bits per instruction. We come back to this aspect in the next chapter. It overwrites gradually the input text which originally has a length of 1067 words, but in our experiments it turned out that it was never necessary to shift the yet unconsumed part of the input text upwards (together with FLI, KLI and NLI). We also did some measurements of the number of compiler instructions executed during the main scan. This number is exclusive the instructions for encoding and storing the object string in the store in compact form (by giving ﬁll result list temporarily an empty body) but includes the repetition of (part of) the lexical scan, especially of RND. We found in total the execution of 385 077 instructions, of which 95 058 (25 %) are spent in the lexical scan (41 611 in RNS and 53 447 in RND). This means that for the example program the main scan requires the execution of about 152 instructions per instruction of object code generated, and of about 307 instructions per delimiter analyzed. During the main scan the name list NLI had to be shifted 5 times in order to make place for an addition to the constant list KLI, whereas KLI and NLI together had to be shifted 11 times in order to cater for the growth of the future list FLI. These 16 shifts moved altogether 2960 words (on the average 185 words per shift), which required the execution of 11840 instructions or 3% of the main scan execution time. With a preﬁll of the name list of 51 words as used in our experiments the name list had a maximum length of 177 words. The maximum length of the stack was 43 words.

5.15

Some problems

The most important and inconvenient shortcoming of the X1 ALGOL 60 compiler was the almost total absence of a syntax check. Most of the checks that were carried out had to do with the proper use of the Flexowriter code (parity check, shift deﬁnitions where required). The only check that really had to do with the (context sentitive) grammar rules was the test whether all applied identiﬁers were declared within the context. If not

CHAPTER 5. MAIN SCAN

the compiler stopped without even mentioning what identiﬁer had not been declared. Other grammatical errors lead to one of four possible forms of behaviour: - during the prescan program the tape ran out of the tape reader, often caused by some missing ‘end’ symbol. Another possible cause was the lack of some Flexowriter symbol (preferably a newline) after the last ‘end’ symbol. - the compiler just generated an incorrect object program, which passed on the problem to the execution phase. An example of this behaviour is the ‘expression’ x+∗y which produces the code given in Figure 11, leaving the stackpointer AP during execution eﬀectively unchanged. 0 32 0 47 59

2B 138 A

load static address of x in register B TRRS, take real result static 2B 140 A load static address of y in register B MURS, multiply real static ADD Figure 11: The translation of x + ∗ y

- the compiler stops with an errornumber indicating something unexplicable. An example: consider the text begin real x; then x:= 1 end This lead to error stop 1 in the compiler procedure production of object program that ﬁnds an operator on the stack with a value > 151. This is caused by the fact that when dealing with the delimiter ‘end’ the operator ‘then’ is found on top of the stack which results in removing three words from the stack, including the ‘begin’ symbol and the block–begin marker. The stack is then empty, and the next call of production of object program inspects the word of the store below the stack. Its contents are not set by the compiler, and it depends on the history what value is retrieved. In the case of our X1–code interpreter, which initializes the whole store with the value −0, the values 255 for the operator height and 255 for the operator value are found. In the case of the Pascal version of the compiler the values 0 and 0 are found, respectively, which leads to a continuation of the compilation process beyond the last ‘end’. A lot of ‘symbols’ are retrieved and skipped until the code sequence ‘91 52 112’ (for ‘; P procedure’) is met. This results in error 7: unknown identiﬁer!

5.15. SOME PROBLEMS

- the compiler enters an endless loop. Again an example. begin integer i; procedure 0(n); value n; integer n; print(n ∗ n); o(5) end The loop occurs within the compiler procedure label declaration (called from the code for the delimiter ‘procedure’), which tries to print the ‘identiﬁer’ ‘0’, ﬁnds that the last three bits of its encoding are zero (indicating a one–word identiﬁer encoding) and starts to ﬁnd the ﬁrst non–zero part of that word, which it never will meet. All these problems were caused by an inadequate reaction on faulty source programs, occurring, however, frequently. This does not imply, however, that all correct programs are dealt with appropriately. Apart from the problem already mentioned when dealing with the prescan program, we have also seen a case that was not compiled correctly by the main scan. The problem is demonstrated by the following program5 . begin procedure P(a); value a; integer a; AA: begin integer array A[1:100]; print(a); goto AA end; P(10) end The object code produced is given in Figure 12, (with FLI [0] = 20 and FLI [1] = 23). There are two problems here. - First of all, there is in the code only one block for procedure P, which includes both parameter a and array A. Therefore it is impossible for the code to exit the inner block and abandon A without abandoning a at the same time. In fact, the jump to label AA does not leave any block, and in the repetition (the storage function of) array A is added to the execution stack over and over again without ever removing any of those storage functions. - Secondly, only part of the code for declaring an array is generated: the code for generating the storage function for array A is present but the code for reserving the area for its elements is missing. The missing code (cf. Section 5.2.1) reads: 0 2S 163 A load dynamic address of array A in register S 94 LAP, local array positioning 5

According to the list of restrictions as reproduced in Section 1.3, ‘procedure bodies starting with a label should be avoided’.

CHAPTER 5. MAIN SCAN

0: 2:

20:

23:

OPC 96 2 0 89 0 16 0 35 85 3 34 3 34 0 91 0 33 103 1 12 1 2 3 0 9 97

w 2T 2B

0 1A

2S 161 A 2S 161 A

2S 161 A

2B 2T 0A 2A

2A 1 2A 1A

explanation START jump over procedure declaration (FLI[0] = 20) load 1 into register B SCC, short circuit load dynamic address of ‘a’ in register S TIAD, take integer address dynamic load dynamic address of ‘a’ in register S TFR, take formal result ST, store load static address of constant 1 in register B TIRS, take integer result static load static address of constant 100 in register B TIRS, take integer result static load number of arrays in register S ISF, integer arrays storage function frame load dynamic address of ‘a’ in register S TIRD, take integer result dynamic print jump to label AA RET, return load address of procedure in register B jump over parameter code word (FLI[1] = 23) codeword for parameter ‘100’ load number of parameters in register A ETMP, extransmark procedure STOP

Figure 12: The incorrect translation of a correct program The explanation is more subtle and is a consequence of the way in which the generation of the reservation of store for array elements is postponed until no more array declarations can follow. For that purpose there is a compiler variable vlam. It is set to some value = 0 for each new block encountered. It is inspected at each delimiter that implies that no (further) array declarations of the block can follow. If it is non–zero, it is set to zero and the part of the namelist corresponding to the block is scanned for the presence of value array parameters and local arrays (marked in the namelist by a descriptor with d26 = 1). For these the instructions to reserve the store for the array elements are generated. In the present case, vlam is already set to

5.15. SOME PROBLEMS

zero upon the occurrence of label AA in the text (marking that the statement part of the block is being scanned), at a moment that identiﬁer A is not yet incorporated in the namelist. The declaration of array A is not treated as marking the start of an inner block to the procedure body, due to the presence of a block–begin marker just below the top of the stack. Consequently, vlam is not set to a value = 0 again and no further inspections of the namelist will take place when it is zero.

CHAPTER 5. MAIN SCAN

Chapter 6 The compiler output 6.1

The first version

Originally, the object program generated by the main scan was punched on 5–track paper tape. The paper tape contained1 : -

a piece of about 50 cm of blank tape; an endmarker ‘XCXX’ (in fact, an empty cross–reference list); a piece of about 10 cm of blank tape; the ‘result list’, i.e. the instructions of the object program; the constant list, each word of the constant list given an OPC value of 0; a piece of about 50 cm blank tape; 5 numbers, i.e. the number of object words, the length of the constant list, the length of the future list, the address of the ﬁrst unreserved word of the execution stack, and the begin address of the execution stack (i.e. 138), each given an OPC value of 0; the elements of the future list, with OPC value 1; the number of MCP’s (library routines) called directly from the object program (with an OPC value 0); the places in the future list which contain the identiﬁcation data of those MCP’s (again with OPC value 0); a piece of about 50 cm of blank tape.

Since the original code of the compiler seems to be lost, the information given here is largely reconstructed from the code of the loader program.

CHAPTER 6. THE COMPILER OUTPUT

Each item, consisting of an OPC value and, in case of an OPC value ≤ 3, a 27–bit word, was punched as 2, 5, or 7 pentads in the following way: - for an OPC value ≥ 8: 2 pentads, consisting of a parity bit, a code bit 1, and the OPC value in 8 bits; - for an OPC value ≤ 3 and a w value corresponding to one of 10 diﬀerent instruction types: 5 pentads, consisting of a parity bit, two code bits 0, a value between 1 and 10 indicating the instruction type in 5 bits, the OPC value in 2 bits, and the address part of the instruction in 15 bits; - for an OPC value ≤ 3 and a w value not corresponding to one of the 10 instruction types mentioned above: 7 pentades, consisting of a parity bit, a code bit 0 followed by a code bit 1, three bits 0, the OPC value in 2 bits, and the w value in 27 bits. The 10 instruction types leading to a 5 pentad encoding in the object tape are given by Figure 13. nr 1 2 3 4 5 6 7 8 9 10

instruction type 0A 0 2A 0 A 2S 0 2S 0 A 2B 0 2B 0 A 2T 0 2T 0 A N 2T 0 4A 0

Figure 13: The 10 instruction types leading to a 5 pentad encoding For the example program of Zonneveld we measured: - 1426 two–pentad instructions, - 1050 ﬁve–pentad instructions, and 62 seven–pentad instructions, giving 8536 pentads for the instructions. The constant list required 502 pentads (43 ﬁve– pentads words and 41 seven–pentads words), the future list 970 pentads (187 ﬁve–pentad and 5 seven–pentads words), wereas the six numbers and the ﬁve MCP locations required 55 pentads. Together with the 4 pieces of blank tape (640 pentads 0) and the marker this

6.2. THE ALD7 SYSTEM

gives a total of 10707 pentads requiring 428.3 seconds or about 7 minutes of punch time. The design goal of the successor of this ﬁrst output system was to reduce that punch time by at least a factor of two.

6.2

The ALD7 system

The development of the ALD7 system started in 1962. It was one of my ﬁrst tasks on the institute, and my ﬁrst acquaintance with a compiler. The aim was to reduce the punch time of the Dijkstra/Zonneveld compiler by at least a factor of two by means of two measures: - punching heptads in stead of pentads (the tape punch used seven–track paper tape); this alone could reduce the length of the code on paper tape by roughly a factor 1.4; - using a shorter encoding of the information, applying short code for frequently occurring pieces of information; another length reduction of a factor 1.4 would suﬃce. The hope was that the nescessary modiﬁcations would concentrate at the periphery of the compiler only. The most extreme possibility in this respect was to encode the pentads as produced by the original version: that required the adaptation of the routine that oﬀered the pentads to the tape punch. A measurement on the frequency distribution of pentads in some object tapes showed that a Huﬀmann encoding thereof would not lead to the required length reduction. Therefore we had to go one level deeper into the compiler, to the compiler routine ﬁll result list. Frequency measurements (again on some object tapes) of the occurence of instructions, both for OPC ≤ 3 and OPC ≥ 8, showed that it was possible to attain the required shortening by relatively simple means, allowing a fast encoding and decoding algorithm. We used one bit to discriminate between instructions with OPC ≤ 3 and those with OPC ≥ 8. The latter were encoded in 3, 4, 5, 6 or 9 additional bits, depending on their frequency of occurrence. For the instructions with OPC ≤ 3 the 15 bits of the address parts were split into three portions of 5 bits, each of which was encoded according to its own frequency distribution. The 12 bit function part was encoded together with the OPC value itself: for the 19 most frequently occurring combinations a 2–, 3–, or 6–bit additional value was used, the other combinations were encoded in the same way as an address part together with a special 6–bit escape code. The full details of the encoding can be found in Appendix D.

CHAPTER 6. THE COMPILER OUTPUT

During the design period it was suggested (came the suggestion from L.A.M. Meertens?) that if the tape was punched in such a way that it could (and should) be read and decoded in the backwards direction, the amount of tape handling in the program loading phase could be reduced greatly. This requires some further explanation. The object tape consists essentially of two sections: - the result list and the constant list, and - some numbers and the future list. The problem was that they have to be produced in this order – due to the fact that those numbers and the contents of the future list are known only at the end of the compilation process –, but have to be loaded in the opposite order – a.o. since substitutions of references to the future list (OPC value 2) by the value found there are carried out immediately during reading of the result list –. Moreover, the reading of the so–called Cross–Reference List CRF, containing information about the mutual use of MCP’s library routines (see Chapter 7), had to be inserted in between. By inserting the contents of the CRF in the loader (with the disadvantage that when the contents of the library were updated also a new loader tape had to be produced) and reading the object tape in the backwards direction the latter could be read at one stroke. In the ALD7 version the object tape consisted of: -

a piece of 50 cm blank tape, a punching 124, followed by a punching 30 as end combination, a piece of blank tape of 6.25 cm, a punching 127 as section end, the following bitstring, cut into pieces of 27 bits, to each of which a parity bit (for odd parity) is added and which are punched in 4 heptads: - the result list, - the constant list, each word of it given an OPC value of 0, - the places in the future list which contain the identiﬁcation of the MCP’s called directly from the object program, each encoded as an address, - the number of those MCP’s, encoded as address, - the future list, each word of it given an OPC value 1, - 5 numbers, i.e. the begin address of the execution stack (i.e. 138), the address of the ﬁrst unreserved word of the execution stack, the length of the future list, the length of the constant list, and the number of object words, each encoded as an address, - a bit 1, as marker of the begin of the information, - enough bits 0 to complete the current group of 27 bits,

6.3. THE LOAD–AND–GO VERSION

- a punching 30, indicating the begin of a section, - a piece of 50 cm blank tape. During loading the end combination enforced a machine stop, giving the opportunity to insert the library tape into the tape reader. The changes to the original compiler were relatively small. Routine ﬁll result list had to be rewritten completely and two subroutines for subtasks were added: address coder and bit string maker. The latter had functionally two arguments: n, the number of bits to be added to the bit string, and w, the bits themselves, but for practical purposes these two argument values were packed into one parameter: 1024∗n+w. Quite often this parameter value was taken from a table. All additions to the bitstring used bit string maker and it was inside that routine that a parity bit was added to each 27 bits of the bitstring and that the result was punched in portions of 7 bits. Furthermore the compiler code following the main scan had to be adapted to the new order and lay–out of the output tape. Of course also a new loader had to be written. Moreover programs were written to recode the library tape in the same format as the object tape and to make a table version of the library cross–reference tape. Although developed for shortening the punch time of the compiler, that aim was soon superseded by the arrival of a fast tape punch (Creed 3000). The shorter length of the object tape and the increased ease of tape handling in the loading phase, however, retained their value. Also the library tape in the ALD7 version used the Huﬀmann encoding and heptads (as opposed to pentads in the original system) and was considerably shorter than before. For the example program of Zonneveld we measured a bitstring of in total 33318 bits, punched in 4936 heptads. Together with the additional punchings this leads to 5365 heptads, punched in 214.6 seconds or about 3.5 minutes of punch time (on the old tape punch).

6.3

The load–and–go version

In the fall of 1963 the ALD7 could already be replaced by a load–and–go version of the compiler. The original ALGOL system for the X1 was designed to operate in a 4K word memory machine. The compiler was about 2K words long, and only 2K words remained to be used as working space, for the compiler stack, prescan list, the future list, the constant list, the

CHAPTER 6. THE COMPILER OUTPUT

name list, and the prescan list. The compiler code was positioned at the high end of the store. For program execution it was overwritten by the complex of run–time subroutines (again about 2K long). The loader was positioned at the low end of the store. During program loading the object code (the constant list included) was positioned adjacent to the complex and the library routines (used by the program) in front of that. During execution the loader was overwritten by the execution stack. In the mean time the store size was extended to 12 K. The additional space was used during program execution, but until then hardly for program compilation. The compiler was positioned from 6K to 8K, such that the run–time routines (moved to the area from 10K to 12K) could reside in store during compilation, and substantially longer programs could be compiled. That situation was retained in the ﬁrst version of the ALD7 compiler. The ﬁrst real application at compile time of the increased store size was the storage of the source text during the prescan phase of the compiler, thereby eliminating the need to read the source text twice. It was implemented in the second version of the ALD7 system. After that the idea was born to store also the object code as produced by the compiler (in its compacted form!) in the memory instead of punching it, and to integrate the loader as a third phase of the compiling proces. For its implementation only a suitable memory management had to be devised. The ‘system tape’ now contained the compiler, the loader, the complex, the cross–reference list, and, in a second release, part of the library routines2 . The following store lay–out was used: - after system loading (addresses in the number system with base 32, therefore 01–00– 00 is just 1K): - 00–07–00 / 00–18–26: loader program - 00–19–15 / 00–22–02: cross–reference list - 00–29–00 / 01–13–18: library selection - 06–25–00 / 06–29–10: preﬁll of the name list - 07–04–02 / 09–28–00: compiler program - 09–29–21 / 11–31–00: complex ALD - during prescan and main scan the area from 01–13–18 to 06–20–00 is used for object string, source text, future list, constant list, name list and prescan list, in this order as described earlier. The compiler stack is located from 00–25–00 to 00–29–00. - in the transposition from main scan to loader the constant list is moved to its ﬁnal 2

This system tape consisted of a good 6000 words, punched in 4 heptades a word. Its length was therefore slightly more than 60 m, its reading time (by means of a special fast reading program for binary tapes) about 25 s.

6.3. THE LOAD–AND–GO VERSION

place, adjacent to and in front of the complex3 . Moreover by consultation of the namelist, the future list, and the cross–reference list two lists of 128 places each are constructed indicating the directly and indirectly used library routines and their loading addresses. After that the only relevant parts of the contents of the store are the loader program, the two library lists, the library selection, the objectstring, the future list, the constant list, the complex, and some numbers saved in the working space of the loader. - during program loading: - 00–07–00 / 00–18–26: loader program - 00–19–15 / 00–23–15: list of library use - 00–25–00 / 00–29–00: list of library use - 00–29–00 / 09–29–21: - remainder of library selection and object string at the low end, - loaded part of library selection, object program, and constant list at the high end, - future list somewhere in between. The loading proceeds in backwards order. Whenever the loaded program reaches the future list’s end, the latter is moved downwards against the remainder of the object string. In the coding much proﬁt was taken from the ALD7 compiler. In the main scan part only routine make bit string had to be rewritten in order to store each portion of 27 bits instead of punching them. Of course also some initializations and the code following the main scan had to be rewritten. The existing loaders could be used as blue–print. The load–and–go compiler was put into operation in november 1963.

by a piece of compiler code located from 09–13–20 to 09–13–28, apparantly never overwritten by it.

CHAPTER 6. THE COMPILER OUTPUT

Chapter 7 The library system In the foregoing chapters we refered to the library system already a number of times. Here we give some more detailed information. In the ALGOL 60 system for the X1 a number of procedures and functions were incorporated. Part of them were the standard functions mentioned in the Revised Report: abs, sign, sqrt, sin, cos, arctan, ln, and exp. Other ones were added for input/output (for the console typewriter, the tape punch, and, at a later stage, a plotter). Moreover, some frequently used algorithms were gradually added to the library, for ﬁnding zeros, solving linear equations, computing special functions, etc. All of them could be used in ALGOL programs without declaration or any other way of signalling their usage. All their names were entered in a list (added to the compiler code) which was copied to the name list NLI at the start of the main scan. These procedures and functions were implemented in two diﬀerent ways: - abs, sign, sqrt, sin, cos, ln, exp, entier, read, print, TAB, NLCR, XEEN, and SPACE are included in the complex of run–time subroutines. They have each an OPC number and are treated as operators changing the top of the execution stack. Consequently, they cannot be used as an actual parameter in a procedure statement or function designator, nor can the function identiﬁers among them be used in a procedure statement (since there is no mechanism to remove the function result from the stack). The ﬁrst nlscop words from the preﬁll of the name list belong to these procedures and functions. As all routines in the run–time complex these operators are coded in X1 code. - All other procedures and functions are included in the library proper and called MCPs (for Machine Code Procedures). They are written in some extension of X1 code to 83

CHAPTER 7. THE LIBRARY SYSTEM

be discussed below, and programmed in such a way that there were no restrictions in usage whatsoever: they could be used as if declared in the outermost block of the ALGOL program. Originally they were assembled and punched in object code format on paper tape, the library tape. At the end of program loading this tape was read and the routines that were directly or indirectly used by the program were selectively added to the object program. The routines could refer to one another (even recursively), and therefore the need of a program was the transitive closure (with respect to the use relation) of the routines that were called directly from the source program. Some MCPs were ‘anonymous’. Not having an identiﬁer that could be referred to in an ALGOL 60 program, they could be used only indirectly by other MCPs. The names of the non–anonymous MCPs were collected in the second part of the name–list preﬁll. By means of an example we like to give an impression of the nature of the code of an MCP. We present the text of ‘AP 109’: the MCP RUNOUT. Its task is to punch 81 blank heptades on the output tape. Its code is reproduced in Figure 14. DPZE DPZF

DN DI X0X X89 X0X X0X X0X X3X X1X X12 X

16 20

X0 X0

MCP number of RUNOUT is 16 MCP number of PAS1 is 20

+8 0 ZE 0

2A 6A 2S 6T 4T

80 0 128 0 4

RUNOUT has 8 instructions MCP number of RUNOUT A A

X0 A ZF 0 2 X0 0E

blocknumber = 1 SCC, short circuit number of zeros set counter blank, with punch mark call PAS1, i.e., punch! decrement counter and jump if ≥ 0 RET, return

Figure 14: code of the MCP RUNOUT , AP 109 The ﬁrst two lines of Figure 14 deﬁne the MCP numbers of MCP RUNOUT and of MCP PAS1. The latter is an anonymous MCP (whose name is not in the preﬁll of the name list). Then follows the part that constitutes the MCP itself: ﬁrst two numbers, the MCP

length and its number (the latter encoded as an instruction of which the function part happens to consist of 12 bits zero) and the (in this case) 8 instructions of the MCP. These are either an X1 instruction preceded by an OPC code 0, 1, or 3, or a call to one of the run–time routines of the complex, indicated by its OPC number (≥ 8). The last line contains an end marker for the last instruction. So we see that the body of an MCP is in fact a mixture of X1 code proper and ‘connectors’ to its ALGOL environment. Its starts by the standard two instructions for all procedures, whether declared in the ALGOL program or member of the library, and ends with the standaard return instruction for all procedures. The X1 instructions themselves have an OPC code, indicating whether at load time the address part of the instruction should be kept unchanged (OPC 0), whether the begin address of the MCP itself should be added to it (OPC 1), or (OPC 3) whether it should be replaced by the begin address of some other MCP (the number of which is given by the given address part). OPC value 2 never occurs in MCPs. Anonymous MCPs do not need connector code to the ALGOL environment. The library tape contained all MCPs in object code format (as described in Section 6.1) and was concluded by an end marker (the pseudo MCP length 16383). To it corresponded a separate cross–reference tape CRF with the following contents: - for each MCP: - a punching 31, - the MCP length in 3 pentads (with odd parity), - the MCP number, in 2 pentads (with odd parity), - a list of the numbers of those other MCPS that call this MCP directly or indirectly (each in 2 pentads with parity), - the pseudo MCP number 511 as end marker for the list; - a punching 31, - the pseudo MCP length 16383 as end marker for the CRF tape. The cross–reference table was used during program loading. Details of its use are described in Section 8.1. The program to translate the assembly code of MCPs to object code format had as input the assembly code of one or more MCPs and the most recent version of the cross–reference tape. It produced the extension to the library tape and an updated version of the cross– reference tape. MCPs that called one another recursively should be translated together. For the transition to the ALD7 system (discussed in Section 6.2) two programs were written to recode both the library tape (to the new object tape format) and the CRF tape. Since the latter was to be incorporated in the ALD7 program loader, it was punched

CHAPTER 7. THE LIBRARY SYSTEM

in standard X1 binary tape format. In the load–and–go versions of the compiler it was possible to incorporate some of the most frequently used MCPs directly in the compiler tape, simplifying tape handling for programs with low MCP demands. We come back to this point in the next chapter.

Chapter 8 Program loading The main task of program loading is, of course, loading into store the compiled ALGOL 60 source program and all the library routines it uses directly or indirectly, thus delivering a program ready for execution. In order to fulﬁll that task, it has to do some other tasks. First it has to determine which library routines are needed. It does so from a list of library routines that are called directly from the source program and augments this to a list of all library routines needed with the help of information from the cross–reference list. Secondly, it has to determine where object program and library routines will be placed, by computing the begin addresses of both the object code and of all the library routines used. It does so using the length of the result list RLI, the length of the constant list KLI, and the lengths of the library routines as given by the cross–reference list. Thirdly, while loading the object code and the code of the library routines, it has to deal with the OPC code of each instruction. If that OPC code is at least 8, it deﬁnes the instruction by itself: the instruction should be taken from the OPC table. If that OPC code is 2 (occurring in the object program only), it should replace the address part by an address taken from the future list FLI. In case of an OPC code 3 either the begin address of the constant list should be added (for an instruction in the object program) or the address part should be replaced by the begin address of an MCP. An OPC value of 1 leads to the addition of the begin address of either the object program (for the object code) or the current MCP to the address part of the instruction. Fourthly, some minor adaptations are aplied to the object program. In case of an OPC value of 2, if bit d17 of the instruction is 1 it is set 0, otherwise bit d19 is set 1. Probably these indicate some ‘maintenance’ actions to the original compiler that easiest could be

CHAPTER 8. PROGRAM LOADING

done in the loader (rather than in the compiler). A number of jumps in the compiler, certainly all jumps that refer to a location in the future list, are coded by the compiler as indirect jumps. Maybe it was originally planned to have the future list in store during execution and to lead those jumps via it. The setting of d19 changes the jumps into direct jumps, and the substitution of the location in the future list by its contents then makes the presence of the future list during program execution superﬂuous. The resetting of d17 has, according to a comment in the (revised) loader, to do something with a recoding of actual parameter code words (PORDS), but its meaning is not clear. Finally, at the end of the loading phase, the store is prepared for a reproducible program execution by ﬁlling the whole working space by −0 (this had also the advantage of stopping the machine if, by loosing proper control, it tries to execute an unused word of working space as an instruction).

8.1

The original loader program

In the version that was documented together with the complex of subroutines (since it is referring to ‘the older version’ it probably is the second release of the loader) the object code was loaded in front of the complex (that started at location 10299 = 10 – 01 – 27). First the lengths RLSCE of the result list RLI and KLSCE of the constant list KLI were read from tape, and from it the begin address of the object code RLIB = 10299 – RLSCE – KLSCE (truncated downwards to a multiple of 32) and KLIB = RLIB + RLSCE were computed. Thereafter length FLSCE of the future list and address GVC0 were read. The begin address FLIB of the future list was taken as 608 (= 00 – 19 – 00), and the future list was read and loaded from that point. Note that due to the OPC coding 1 of the future list words each of these was increased by RLIB. Next the use–list MLI, running from location 480 (= 00 – 15 – 00 ) to 607 (00 – 18 – 31) was initialized with 128 zeros. Then the number RNB of directly called MCPs was read, followed by the RNB future list locations were the MCP numbers could be found. For these MCPs the corresponding positions of MLI were ﬁlled with – (FLI location + FLIB), indicating their (direct) use. The begin address MCPE of the last located entity was initialized to RLIB. The X1 stopped in order to load the CRF tape. This tape was read until its end marker (the pseudo MCP length 16383). For each MCP in the library its length was read. Thereafter the list of ‘users’ (starting with the MCP itself) was read and if at least one of them was wanted (the corresponding MLI positions diﬀerent from 0), the MCP itself

8.2. THE LOADER FOR THE ALD7 SYSTEM

was wanted. In that case MCPE was decreased by the MCP length, and its new value was copied to MLI as begin address of the MCP. Moreover, in the case of direct use from the object code (as seen from a negative old value in MLI) that begin address was also ﬁlled in in the corresponding location in the future list. After the processing of the cross–reference tape all the nescessary addresses (of RLI, KLI, and all MCPs that are needed) were known, and the actual loading could start. De X1 stopped for loading the (ﬁrst part of the) object tape. After reading and loading RLI and KLI the begin address of the object program RLIB was typed on the console typewriter in the number system with base 32 (xx xx 00) Also MCPE was typed in the same way. The working space (from 680 to MCPE) was ﬁlled by −0 and the X1 stopped for loading the library tape. From this tape all MCPs were read, but only those that were used (as indicated in MLI) were loaded from the begin address as given by MLI. At the end of the library tape the program was ready for execution and the X1 stopped anew, now giving opportunity to load a potential data tape. In the implementation the main subroutine is LIL (Read List) for reading and placing a list of instructions. LIL uses subroutine RBW (Read Binary Word), which builds the next instruction from 2, 5, or 7 pentades, incorporating its OPC–value. RBW, in turn, uses subroutine RNP (Read Next Pentade). In this (second) version of the loader no use is made of the interrupt system for the tape reader. This suggests that it was written after the arrival of the fast tape reader. It runned reasonably fast. One ineﬃciency still is that during the processing of the library tape the contents of each MCPs is decoded to instructions independent of whether that MCP is actually needed or not. We remediated that in the load–and–go system.

8.2

The loader for the ALD7 system

Apart from a diﬀerent decoding of the object tape and the library tape and the fact that the cross–reference information is taken from store rather than from tape, the diﬀerences are not very big. Again the main subroutine is LIL for reading and placing a list of instructions, in their turn read by subroutine RBW. It is in RBW that the bitstring is decoded, thereby using additional subroutines ML (Read Mask), for decoding the function part of an instruction (with OPC ≤ 3), ADD (Address Decoder), for decoding the address part of an instruction), and RBS (Read Bits), for reading a front portion of the bit string (the length of which speciﬁed in its parameter). It is only in RBS that heptades are read from paper

CHAPTER 8. PROGRAM LOADING

tape and that the parity of each group of 4 heptades is checked to be odd. RBS operated roughly in the following way: It maintained, in one word of its working space, a number of ‘bits in stock’. Those bits, at least 21 (and, of course, at most 27), were positioned at the most signiﬁcant part of the word, the ﬁrst bit at position d26 (that bit was therefore easily inspected by testing the sign of the stock word). Moreover, the number of bits in stock was registered, and as soon as, by a call of RBS, the stock becomes shorter than 21 bits, a heptade is read from tape and added to the low end of the stock word. The logical sum of each group of 4 heptades is formed, and checked for parity when the ﬁrst heptade of the next group is read. In that case only (the most insigniﬁcant) six bits of the new heptade are added to the stock, otherwise all seven bits are added. RBS is initialized by setting the number of bits in stock equal to zero, by skipping blank tape and the ﬁrst non–blank heptade (requiring that it has the value 30), by loading 4 heptades, and by calling RBS (each time for 1 bit) until a bit 1 is obtained. In the main part ﬁrst RLSCE and KLSCE are read (by calls of ADD), RLIB and MCPE are computed, and FLSCE and GVC are read (again by ADD). Next the future list is read by LIL. Then RNB, the number of directly used MCP’s is read (by ADD), and, if diﬀerent from 0, the use–list MLI is initialized, the RNB references to the future list containing their speciﬁction are read (by ADD again) and incorporated in MLI, and the cross–reference list CRF is read from store and processed. For reading CRF a subroutine LC (Read Cross Reference), yielding an MCP length or number, is used. Now the result list RLI and the constant list KLI are read (by a call of LIL). RLIB is typed on the console typewriter. Next the MCPs are loaded in the following way: Each time an end marker (i.e., pseudo MCP length 7680) is found, it is checked whether all MCPs have been read. If so, MCPE is typed, the working store for execution is cleared, and the X1 stops with stop nr 3–7, ready for program execution. If not, the X1 stops with stop nr 3–6, indicating that a (next) MCP tape should be entered in the tape reader. This organization makes it possible both that if no MCPs are used at all the reading of the MCP tape(s) can be skipped, and that, if the user removes the end marker from his object tapes and glues a copy of an MCP tape to it, the loading can proceed without intermediate stop. If an MCP length less than 7680 is found, the MCP number is read, and if it is used, that MCP is loaded by a call of LIL. If, however, MLI indicates that it is not used at all, the MCP is skipped (although still the instructions are decoded by calls of RBW). Allthough the cross–reference list is now build–in in the loader, the user had the possibility

8.3. THE LOADING PHASE OF THE LOAD–AND–GO COMPILER

to load his own version by means of the standard input program of the X1 using directive DW followed by binary encoded tape (as if directive DB had been read). This did, however, not alter the contents of the name list preﬁll, and, to the best of my knowledge, this facility never was used.

8.3

The loading phase of the load–and–go compiler

In a previous section (Section 6.3) much information has already been given about the store management of the load–and–go version. We discuss here the main diﬀerences from the ALD7 loader. The structure of the loading phase is that of the ALD7 loader. The main diﬀerence is in the subroutine RBS (Read Bits), which now is capable to obtain its bits from two sources: from store, for the object program and for part of the library, and from tape, for the part of the library not in store. It is initialized in three diﬀerent ways: - the RBS switch is set to ‘reading from store’, the ‘bits in stock’ word is partly taken from the bits in stock of the make bit string routine of the main scan, and completed from store; - the number of bits in stock is set to zero, the bit stock is completed from store (thus requiring a full word), and RBS is called for the next bit until it delivers a bit 1; - the RBS switch is set to ‘reading from tape’, the number of bits in stock is set to zero, blank tape and a heptade 30 are skipped, the bit stock is completed from tape, and RBS is called for the next bit until it delivers a bit 1. In fact this is almost the initialization of RBS from the ALD7 loader. Again RBS keeps a stock of at least 21 bits. It is supplemented by 6 (1 out of 4 times) or 7 (3 out of 4 times) bits in order to keep this invariant. In case of reading from store they are taken from d26 − d21 , d20 − d14 , d13 − d7 , and d6 − d0 , successively, of a word from store. Another diﬀerence to the ALD7 loader is in the table of MCP use. In stead of one table there are now two of such tables. At the end of the main scan, before switching to the loader program, the table MLI is cleared, and from the initial namelist part (from location nlscop to nlsc0 – 1) the locations in the future list are isolated for used MCP’s (having a descriptor with bit d15 = 0). From those locations in the future list the MCP numbers are isolated and at the corresponding places of MLI the values – (FLIB + relative FLI– address) are ﬁlled in. Then the cross–reference table from store is used to determine the secondary needs and to compute and store the begin addresses of all used MCP’s in MLI

CHAPTER 8. PROGRAM LOADING

and, for primary use, also in the future list. After loading the result list RLI and the constant list KLI (and the typing of RLIB) a copy is made of MLI (it overwrites the area reserved for the cross–reference table, thereby deleting that cross–reference table). During the loading of MCPs the copy is consulted to see whether an MCP is needed, and if so, to ﬁnd the appropriate place. After loading of such a needed MCP, the number of needed MCPs is decremented by one and the entry in the copy of MLI is cleared (indicating that that MCP is no longer needed). It is, however, maintained unaltered in MLI itself, and it is that list that is used in processing an OPC value of 3. By this organization it is possible to have several copies of the same MCP in memory and/or on paper tape, only one of which (the ﬁrst one encountered) is loaded when needed. It also gave users the possibility to load their own version of an MCP (provided it had the length as given by the cross–reference table) by reading a private MCP tape prior to the standard one. It is again unknown to me whether this facility was ever used. In order to accellerate the loading of MCPs, unused MCPs were no longer decoded by RBW (Read Binary Word), but skipped without any processing. In case of reading from store successive words from store were skipped until a ﬁxed end pattern was found (d26 through d21 one, d20 through d0 zero), in case of reading from paper tape by skipping heptades until two successive blanks were encountered. Prior to the processing or skipping of an MCP, RBS was reinitialized in the second or third way as speciﬁed above. Again we give some ﬁgures for the sample ALGOL program of Zonneveld dealt with already many times. It uses 5 MCP’s, all directly invocated by the program: MCP ‘SUM ’, ‘PRINTTEXT ’, ‘FLOT ’, ‘FIXT ’, and ‘ABSFIXT ’. The ﬁgures are measured using a version of the load–and–go compiler in which the part of the library assembled from store contained 8 MCP’s, occupying 408 words of store.

8.3. THE LOADING PHASE OF THE LOAD–AND–GO COMPILER

length of result list RLI 2538 length of constant list KLI 84 number of MCP instructions loaded 305 instructions executed during prescan 292810 instructions executed during main scan 531378 instructions executed during program loading 268641 instructions executed for store clearing 14161 total number of instructions 1106990 estimated execution time for prescan 15.5 s estimated execution time for main scan 26.6 s estimated execution time for program loading 13.4 s estimated time for store clearing 0.7 s total estimated execution time 56.3 s In these times the typing time for the console typewriter is not taken into account; it could have slowed down the compiler, but in view of the limited output to that typewriter for the current program the eﬀect is neglectible. Note that for this program the operator was not able to rewind both the source tape and the system tape during compilation.

CHAPTER 8. PROGRAM LOADING

Chapter 9 The Pascal version of the compiler The Pascal program presented in this chapter is a back–engineering of the X1 code of the load–and–go version of the Dijkstra/Zonneveld ALGOL 60 compiler for the X1. It has been structured in the following way. There are three main procedures, each representing a phase of the compiling process: ‘prescan’, ‘main scan’, and ‘program loader’. All procedures that are called exclusively from one of these main procedures are declared locally to the one that uses it. A procedure that is shared by two or more of these main procedures is declared globally preceding the main procedure that textually contains its ﬁrst applied occurrence. We arrived at the following program lay–out: lines lines lines lines

lines lines lines

60 – 324: the lexical scan routines. Procedure read until next delimiter is called from both procedure prescan and from procedure main scan. 325 – 327: procedure ﬁll t list, storing its parameter on top of the compiler stack. 328 – 436: procedure prescan. 437 – 570: some procedures shared by procedure main scan and the main program, in which, before calling procedure main scan, the block administration for the outermost block is created and the instruction ‘START’ is generated. 571 – 1516: procedure main scan. 1517 – 1818: procedure program loader. 1819 – 1992: the main program.

The program contains some output statements not occurring in the X1 code. Some 95

CHAPTER 9. THE PASCAL VERSION OF THE COMPILER

of these, placed between braces, are now comment but were previously used to inspect intermediate results. The table given in Figure 15 can be used to ﬁnd the declaration of a procedure. procedure name address coder address decoding address to register augment prescan list bit string maker block introduction complete bitstock empty t list through thenelse do in t list ﬁll constant list ﬁll future list ﬁll name list ﬁll output ﬁll prescan list ﬁll result list ﬁll t list ﬁll t list with delimiter generate address intro new block intro new block1 intro new block2 label declaration logical sum look for constant look for name main scan new block by declaration

line 484 1601 705 351 462 355 1533 866 871 590 580 692 606 331 505 325 577 715 459 455 437 622 1522 899 881 571 679

procedure name new block by declaration1 next ALGOL symbol oﬀer character to typewriter prepare read bit string1 prepare read bit string2 prepare read bit string3 prescan procedure statement production of object program production transmark program loader read binary word read bit string read crf item read ﬂexowriter symbol read list read mask read next symbol read until next delimiter reservation of arrays reservation of local variables stop test bit stock test ﬁrst occurrence thenelse typ address unload t list element

line 674 82 618 1581 1587 1592 328 767 781 778 1517 1661 1571 1723 60 1707 1630 178 211 726 698 54 1700 664 856 1703 603

Figure 15: location of the procedure declarations of the Pascal version In the X1–code version of the compiler as given in the next chapter each component (subroutine, table, set of global variables, constant list) has its own address, characterized by two ‘paragraph letters’. For example, the subroutine ‘read ﬂexowriter symbol’, given in the Pascal version by lines 60 through 81, has in the X1–code version addresses 0 LK 0 through 31 LK 4. In order to link the two versions of the compiler together we give

for each component in the Pascal text systematically the two paragraph letters of the corresponding part in the X1–code version by means of a comment. See e.g. line 60 of the Pascal version, mentioning paragraph LK in the comment ‘{LK}’.

CHAPTER 9. THE PASCAL VERSION OF THE COMPILER

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

program X1_ALGOL_60_compiler(input,output,lib_tape); const d2 d3 d4 d5 d6 d7 d8 d10 d12 d13 d15 d16 d17 d18 d19 d20 d21 d22 d23 d24 d25 d26 mz

= 4; = 8; = 16; = 32; = 64; = 128; = 256; = 1024; = 4096; = 8192; = 32768; = 65536; = 131072; = 262144; = 524288; = 1048576; = 2097152; = 4194304; = 8388608; = 16777216; = 33554432; = 67108864; = 134217727;

gvc0 = tlib = plie = bim = nlscop = nlsc0 = mlib = klie = crfb = mcpb =

138; 800; 6783; 930; 31; 48; 800; 10165; 623; 928;

{0-04-10} {0-25-00} {6-19-31} {0-29-02}

{0-25-00} {9-29-21} {0-19-15} {0-29-00}

var tlsc,plib,flib,klib,nlib, rht,vht,qc,scan,rfsb,rnsa,rnsb,rnsc,rnsd, dl,inw,fnw,dflag,bflag,oflag, nflag,kflag, iflag,mflag,vflag,aflag,sflag,eflag,jflag,pflag,fflag, bn,vlam,pnlv,gvc,lvc,oh,id,nid,ibd, inba,fora,forc,psta,pstb,spe, arra,arrb,arrc,arrd,ic,aic,rlaa,rlab,qa,qb,

43 44 45 46 47 48 49 50

rlsc,flsc,klsc,nlsc: integer; bitcount,bitstock: integer; store: array[0..12287] of integer; rns_state: (ps,ms,virginal); rfs_case,nas_stock,pos: integer; word_del_table: array[10..38] of integer; flex_table: array[0..127] of integer; opc_table: array[0..112] of integer;

rlib,mcpe: integer;

lib_tape: text;

ii: integer;

54 55 56 57 58 59

procedure stop(n: integer); {emulation of a machine instruction} begin writeln(output); writeln(output,’*** stop ’,n div d5:1,’-’,n mod d5:2,’ ***’); halt end {stop};

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

function read_flexowriter_symbol: integer; {LK} label 1,2; var s,fts: integer; begin 1: read(input,s); if rfsb = 0 then if (s = 62 {tab}) or (s = 16 {space}) or (s = 26 {crlf}) then goto 2 else if (s = 122 {lc}) or (s = 124 {uc}) or (s = 0 {blank}) then begin rfsb:= s {new flexowriter shift}; goto 1 end else if s = 127 {erase} then goto 1 else stop(19) {flexowriter shift undefined}; 2: fts:= flex_table[s]; if fts > 0 then if rfsb = 124 then {uppercase} read_flexowriter_symbol:= fts div d8 else {lowercase} read_flexowriter_symbol:= fts mod d8 else if fts = -0 then stop(20) {wrong parity} else if fts = -1 then stop(21) {undefined punching} else if s = 127 {erase} then goto 1 else begin rfsb:= s {new flexowriter shift}; goto 1 end end {read_flexowriter_symbol};

100

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

CHAPTER 9. THE PASCAL VERSION OF THE COMPILER

function next_ALGOL_symbol: integer; {HT} label 1; var sym,wdt1,wdt2: integer; begin sym:= - nas_stock; if sym >= 0 {symbol in stock} then nas_stock:= sym + 1{stock empty now} else sym:= read_flexowriter_symbol; 1: if sym > 101 {analysis required} then begin if sym = 123 {space symbol} then sym:= 93; if sym 9) and (sym = 63 then sym:= wdt1 else if wdt1 = 0 then stop(13) else if wdt1 = 1 {sym = c} then if qc = 0 {outside string} then begin {skip comment} repeat sym:= read_flexowriter_symbol until sym = 91 {;};

101

127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171

else else else else else

sym:= read_flexowriter_symbol; goto 1 end else sym:= 97 {comment} else begin sym:= read_flexowriter_symbol; if sym = 163 {_} then begin repeat sym:= read_flexowriter_symbol until sym 163; if (sym > 9) and (sym =} if sym = 72 {=} then sym:= 80 {eqv} if sym = 74 { 11 29 12 13 14 15 16 17 18 19 20 21 22 18 => 23 24 25 26 27 28 29 13 => 30 31

Y Y U Y Y U Y Y U Y U U N U Y Y U Y U Y N U Y Y U N

DA 0 H 2S 75 2T 5 H 0LS 74 2S 102 2T 5 H 0LS 70 2S 103 2T 5 H 0LS 162 2T 26 H 7Y 11 1S 9 1S 38 2T 30 H 1S 70 2S 71 2T 5 H 1S 76 2T 23 H 0LS 72 2S 80 0LS 3 2T 5 H 0LS 124 2S 68 2T 5 H 0LS 163 7Y 13 6T 0 L 2T 11 H 4P 2S 13 H DC D0

T 1 T 0

T 0

T 0 T 0 C 0

T 1

T 0 T 1

T 0

DI A A A Z A A A Z A A A Z A A A A A A A A A A A A A A A A A

C 0 K 0 14 T 1 A SB T 3 B

-> ->

P E -> Z -> E -> Z

=> Z -> Z =) =>

zo ja, dan interne representatie gaan afleveren volgsymbool een

[PDF] SEN. Centrum voor Wiskunde en Informatica. Software Engineering. Software ENgineering - Free Download PDF (2025)