- Country: uk
- Began: 1964
- Type:True ALGOL60s
Implementation of Algol 60 at EEL Whetstone by Randell and Russell, 1964
Also referred to (by them) as WAlgol and Walgol
Much studied implementation
- KDF9 English Electric-Leo-Marconi
- Kilner, Daphne "Automatic Programming Languages for Business and Science" view detailsAbstract: A Conference under this title was held on 17-18 April 1962 by the Mathematics Department of the Northampton College of Advanced Technology in co-operation with the British Computer Society. The following is a summary report on the Proceedings which will be published in full in the Computer JournalExtract: Aims
What do we want from these Automatic Programming Languages? This is a more difficult question to answer than appears on the surface as more than one participant in the recent Conference of this title made clear. Two aims are paramount: to make the writing of computer programs easier and to bring about compatibility of use between the computers themselves. Towards the close of the Proceedings one speaker ventured that we were nowhere near achieving the second nor, indeed, if COBOL were to be extended any further, to achieving the first.
These aims can be amplified. Easier writing of programs implies that they will be written in less, perhaps in much less, time, that people unskilled in the use of machine language will still be able to write programs for computers after a minimum of training, that programs will be written in a language more easily read and followed, even by those completely unversed in the computer art, such as business administrators, that even the skilled in this field will be relieved of the tedium of writing involved machine language programs, time-consuming and prone to error as this process is. Compatibility of use will permit a ready exchange of programs and applications between installations and even of programmers themselves (if this is an advantage!), for the preparation of programs will tend to be more standardised as well as simplified. Ultimately, to be complete, this compatibility implies one universal language which can be implemented for all digital computers.
Extract: Two English Electric Algol 60s
English Electric Algol 60
English Electric set out with the aim of implementing the full ALGOL 60 report. At the Kidsgrove service bureau they expected to have a wide range of users and of problems and therefore they needed a language which could be universally understood and implemented, as well as eventual fast and efficient object programs. In fact, they have developed two compilers, one at Whetstone, a fast compiler of 3,000 instructions operating on the one-pass load-and-go principle but with no special attempt at efficiency, and the other at Kids-grove, a larger affair of some 20,000-30,000 instructions, designed to be more efficient with exceptionally good procedures but involving several machine passes. Both are expected to be ready for full use by the end of 1962. The Whetstone compiler is suitable for one-off programs but that at Kidsgrove is designed for production programs which require a greater efficiency.
These two compilers have certain properties in common. They accept almost identical versions of ALGOL, and that almost the whole of ALGOL and certainly nothing but ALGOL. For both there is an available library of procedures in ALGOL, and in both one can communicate with the machine only in ALGOL. But the Kidsgrove compiler has greater facilities for checking and amending the source program, and also for the final printing out of programs. Finally, English Electric endorsed the opinion that ALGOL was not difficult to learn: their experience was that, including recursive procedures and side effects, a course would not last even the Amsterdam time of four days to an audience of experienced programmers.
in The Computer Bulletin September 1962 view details
- Randell, B. and Russell, L. J. Single Scan Techniques for
Translation of Arithmetic Expressions in ALGOL 60. (To be published, 1963)
- Randell, B., Duncan, F. G. and Huxtable, D. H. R. KDF9 ALGOL Note 1. Data Processing and Control Systems Division, The English Electric Company Ltd., Kidsgrove, Staffordshire 1963 view details
- Randell, B. "The Whetstone KDF9 ALGOL Translator" view detailsExtract: Introduction
Past experience with computers and translation schemes at the Atomic Power Division has shown that users" requirements of an automatic programming scheme are to some extent conflicting. On the one hand the price paid for ease of writing and testing in a convenient language must be small, and particularly for large or frequently used programs, the final running efficiency must be high. The first objective requires extremely fast translation - the second requires a large sophisticated translator with consequent increase in translation time. Possible solutions to this problem are, firstly, to have compromise scheme, perhaps capable of varying degrees of sophistication or secondly to satisfy the two requirements with two translators.
The second solution has much to recommend it, and has indeed been chosen A team at the Data Processing Division is working on a multi-pass optimizing translator, with the aim of producing as efficient a running program as possible. In parallel a smaller translator is being developed at Whetstone, due to be ready as quickly as possible after completion of the prototype KDF9 in which great stress has been laid on speed of translation, and on ease of communication between object program and programmer. This separation of translators enables each scheme to pursue its own objectives to the full, and allows the writers of the large scheme more time to pursue their goal of runtime efficiency.
Naturally the two schemes are to have complete compatibility, and enable a user to test a new program quickly and efficiently, and then recompile it to get an efficient running program. Both schemes win accept full ALGOL 60, with only the following restrictions: 1. no dynamic own arrays; 2. no integer labels; 3. obligatory specifications for all parameters.
The Whetstone translator takes advantage of the fact that due to the high speed of operation of the KDF9 computer, there is probable scope for utilizing the time spent during input of a program. This leads naturally to the development of a scheme for strict one-pass translation of an ALGOL program, so that the object program is complete, ready to be obeyed, almost immediately after the reading of the ALGOL ceases.
Extract: The Object Program
The Object Program
At an early stage in the project, the author and a colleague, Mr L. J. Russell, met Dr Dijkstra, of the Mathematical Centre, Amsterdam, who, with Mr Zonneveld, was joint author of the extremely successful ALGOL translator for Centre"s XI computer. Later, at the invitation of Dr Dijkstra, a most
pleasant week was spent at the Mathematical Centre discussing translation chniques (Randell and Russell, 1962).
The object program generated by the Whetstone translator is a developLent of that of the Xl translator. Thus the object program consists of a set of operations, with parameters where necessary, which use the remaining core storage as a stack (Dijkstra, 1960) containing all the currently available block structure of ALGOL and of the fact that recursive calls can be made on procedures. The object program is obeyed interpretively at run time by a control routine, which performs the normal arithmetic and logical opertions, dynamic storage allocation of arrays, and all the necessary stack manipulation operations.
The requirements of parallel declarations and one-pass translation have their effect on the design of the object program, which must be capable of being partially generated as the ALGOL is read in, and then completed when ny previously missing declarations are found. Extract: Communication between ALGOL Program and Programmer
Communication between ALGOL Program and Programmer
An important feature of the Whetstone ALGOL translator is the stress placed on ease of communication between ALGOL program and programmer. Thus it should be possible to check-out and test an ALGOL program with no knowledge of the generated object program.
The first problem is that of indicating to a programmer the point at which error in his ALGOL program has become apparent to the translator. This is done by printing out the next 100 characters, or two lines, of the ALGOL (counting only non-trivial information). The line number, and the last label and last procedure identifier declared will also aid identification of the offending ALGOL. This information will be accompanied by a message describing the error (or rather, inconsistency).
It will be possible to continue, and search for further errors, only on the basis of making some reasonable estimate as to the cause of the inconsistency.
Error print-outs at run time will arise from two causes. Firstly, further checks on the validity of the ALGOL which are not easily checked at translation time are performed at run time (for example compatibility of formal and actual parameters). Secondly, actual errors in the program can result in numbers becoming invalid, subscript bounds being exceeded, etc. Error print-outs are formed using a "failure tape" which has been set up at translation time. As any section of the name list is collapsed (see Section 4) a copy of the section is made on magnetic tape. This will include details of the block being collapsed (type of block, level number, line number at start of block, etc.) and information about every identifier in the block. The failure tape also includes, for each block, a table giving details of line number against object program counter. Thus using this failure tape, error print-outs can be made giving a description of the failure, the position where it occurred, and details of the current block. This tape could also be used for trace routines, post-mortems, etc. Extract: Acknowledgements
A large measure of any credit for the Whetstone ALGOL Translator must go to Mr L. J. Russell, who with the author, is jointly responsible for the design and implementation of the translator, and who has assisted in the preparation. The author"s indebtedness to Dr E. W. Dijkstra, and also Professor A. Wijngaarden, and Mr J. A. Zonneveld, will be obvious to anyone familiar with the ALGOL Translator for the Xl computer at the Mathematical Centre, Amsterdam.
The author also wishes to thank The English Electric Company Limited for permission to publish this paper.
in Wegner, Peter (ed.) "An Introduction to Systems Programming" proceedings of a Symposium held at the LSE 1962 (APIC Series No 2) view details
- Randell, B., and Russell, L. J. "Algol 60 Implementation" Academic Press, London 1964 view detailsExtract: Preface
Our main intention in writing this book has been to present a full description of an ALGOL 60 Compiler, originally developed for the English Electric KDF9 Computer. In fact the information contained in this book has already been used in order to produce similar compilers for three other computers, a Ferranti PEGASUS, ACE at the National Physical Laboratory, and an English Electric DEUCE.
We have attempted in the description of the compiler to give the reasons for choosing the particular techniques that we have used, and in certain cases to describe possible alternative techniques; furthermore, in order to place our compiler in a proper perspective, we have included a short survey of the various published descriptions of other ALGOL Compilers and translation techniques. By these means it is hoped that a reader who wishes to implement ALGOL on a computer will be able to evaluate the various possible techniques, and perhaps to take and develop any of the techniques that he might consider to be suited to his own requirements.
It is further hoped that the book will be of use to readers with a more general interest in computers and automatic programming systems - in particular that our attempt at a description of the problems of implementing a language such as ALGOL on present-day computers will be of interest to the designers both of programming languages and computers.
The writing of this book has been a very enjoyable though somewhat exhausting experience. When we originally undertook to write a complete description of our ALGOL Compiler, we had little idea of the magnitude of the task ahead of us. That we have managed to complete this task is largely due to the help and encouragement we have had from many friends and colleagues.
First and foremost it is a pleasure to acknowledge our indebtedness to Professor E. W. Dijkstra, now at Eindhoven University-indeed, without his great assistance in describing to us his pioneering work with Mr J. A. Zonneveld, on the ALGOL Compiler for the Xl Computer at the Mathematical Centre, Amsterdam, our own ALGOL Compiler would have been a very inadequate and inelegant affair, and this book would never have been contemplated. It is also a pleasure to acknowledge the invaluable assistance we have had from Mr M. Woodger of the National Physical Laboratory, from the first days when we were considering whether to attempt this task, right up to the final stages of proof reading.
Our thanks are also due to Mr F. G. Duncan, of the Data Processing and Control Systems Division of the English Electric Company, without whom KDF9 ALGOL would soon have degenerated into mere dialect of ALGOL, and to Mr M. A. Batty, of the Atomic Power Division, whose painstaking checking of the drafts, coupled with an unerring eye for a vague or inaccurate description, caused much re-writing. Equally, we are indebted to Mrs M. French, who has typed and re-typed the drafts of this book with patience and accuracy. However, it must be emphasized that all remaining errors and inaccuracy. However, it must be emphasized that all remaining errors and inadequacies in this book are solely the responsibility of the authors.
This book is published by kind permission of the English Electric Company Limited, to whom we wish to express our thanks, in particular for allowing us to include the complete logical flow diagrams of our compiler. Extract: Foreword by Edsger W. Dijkstra
I am very happy that the authors of this book have been so kind as to ask me to write a foreword to it, because the presence of their manuscript on my desk relieves my somewhat guilty conscience in more than one way.
Accidental circumstances made me play some role in the initial stages of hat part of their work to which they refer as "the Whetstone Compiler", a fact vhich I should regret forever if their acquaintance with our solutions would have withheld them from looking for better ones themselves. The manuscript of this book, however, has convinced me that there is no reason for such regret. On the contrary: both the structure of the object program and the structure of the translator are of such an illuminating perspicuity that one can only be grateful when one"s earlier work has been allowed to act as source of inspiration.
The second reason for my guilty conscience is related to the book itself. When they were urged to write it they were so imprudent as to ask my advice, whether I thought that they could write such a book, whether there was a point in trying it, etc. Impressed by the clarity of their previous writings I answered in a most encouraging and confirmative way, all the time aware of the fact that the preparation of a manuscript like this would be a tremendous task. The production of a piece of mathematical writing is always a considerable task which puts great demands on one"s accuracy and ability to be concise but not obscure. Algorithmic translators, however, are hardly a standard subject of scientific publications, and the authors, who had to create a considerable portion of their "metalanguage" to describe their subject, must have suffered greatly from this lack of a tradition. But the high degree of readability of their product, I am happy to say, removes one more burden from my conscience.
I am very glad that this manuscript has been finished and that it will be published in book form. As far as the latter is concerned I should like to add "and the sooner the better", because I think its publication to be very important. In the Preface the authors express their hope that their "attempt at a description of the problems of implementing a language such as ALGOL on present-day computers will be of interest to the designers both of programming languages and computers." I should like to use my present privileges to point out that I think this hope - all appreciation for understatements included - too modest. Of course I hope that it "will be of interest" but I hope much more. For most of the difficulties met during translation can be traced down to a single source, viz. either an awkward feature of the language or an awkward feature of the machine. Now I hope that we all agree that there is no point in imposing unnecessary burdens on the translator or its composers.
On the contrary they make translators unnecessarily expensive to construct, unnecessarily expensive to run and, worst of all, they tend to affect the reliability and trustworthiness of the whole system. If we agree on this, the art of language designing becomes the art of designing a powerful systematic language primarily from those elements which can be processed elegantly by a translator - and this book shows that this set is certainly not empty - and the art of machine designing becomes the art of building-in such Control Routine described in this book shows some of these features. Many of the signposts along the road to improvement in the computer field are set by the experiences gained by the implementors. And as this improvement is very dear to my heart I can only end by wishing this book a wide circulation and an intelligent audience that will not fail to hear its message.
Edsger W. Dijkstra
- Evershed, DG and Rippon, GE "High level languages for low level users"
view detailsAbstract: Despite the presence of "high level" languages, a communication barrier still exists between the majority of people and computers. This paper suggests how some present computer languages may be improved, and attempts to justify the application of increased effort to this subject.
in The Computer Journal 14(1) 1971 view details
- Wells, M., Holdsworth, D. and McCann, A. P., "The Eldon 2 operating system for KDF9." pp21 - 24. view detailsExtract: Compilers for KDF9
The compilers available were for Usercode and ALGOL.
Usercode is an assembly language with good mnemonics
for operations, but very limited addressing techniques. For
ALGOL two compatible compilers were available. The
"Whetstone" system (Randell and Russell, 1964) offers
excellent diagnostic facilities; compilation is extremely fast,
but the subsequent interpretation is slow. The "Kidsgrove"
system (Hawkins and Huxtable, 1963) is an optimising
compiler, with long compilation times, and rather limited
diagnostics, but producing a fairly efficient object code.
No compiler allowed library insertion at compile time;
instead each text file contained a copy of any library
material, inserted when the file was created.
in The Computer Journal 14(1) 1971 view details