Русский | English   search rss

Algol 68 – 25 Years in the USSR

Home → Articles → Algol 68 – 25 Years in the USSR

Mikhail A. Bulyonkov, Alexandre F. Rar, Andrey N. Terekhov

The first information on Algol – then 67 – was brought to our country by Dr. Ershov in 1966. There arouse then in Russia three focuses, in which current work of van Wijngaarden's team was attentively observed. These were Dr. Ershov's group in Novosibirsk, Dr. Lavrov in Podlipki, Moscow Region, Dr. Levinson in Moscow. In these places people began to send numerous remarks on the language and to consider its Russian terminology. The process of translating the report on Algol 68 into Russian followed the process of its up-to-dating in English so closely that both the Report and its Russian translation [1] were issued in the same year of 1969.

Even before that, in February 1968 first lectures on the new language were held in Bakuriani, Georgia, at the special Winter School on Algol 68.

Later on, the expansion of the language in the USSR was noticeable, but restricted. Groups of ardent adherents of Algol 68 appeared in Kiev, Kharkov (Ukraine), Izhevsk, Kazan, Tomsk, Berdsk and other Russian cities. The most strong and most fruitful of these groups was that of the Leningrad State University. For many years the Algol 68 was the principal programming language studied in the course of Computer Science in the Leningrad University. The Leningrad implementations of Algol 68 will be discussed later. But all these Algol islands were rare in the ocean of Fortran and, later, in the seas of Pascal, Modula, Ada.

Starting from 1976 the official national organization on Algol 68 began to act, under whose observation were the translation of the Revised Report, publishing of literature, testing and adopting of compilers. Up to 1982 this body was called "The Scientific-Technical Commission'' and was headed by A. P. Ershov. Lately it became a "Working Group'' with G. S. Tseytin as its head. The last session of the Group took place in 1988, in which the national Standard of Algol 68 has been adopted. No attempt was made since then to call a new session of the Group.

Our first publication of the Report, mentioned before, was bilingual. It contained the whole text of the Report with all pragmatic remarks and pictures from Winnie-the-Pooh. The work on the Russian translation and especially the sophisticated job of transforming the syntactic and metasyntactic rules into the Russian form gave rise to considerations of how to formalize the rules for creating national variants of Algol 68. Methods of designing syntactical and metasyntactical charts of Algol 68 were also considered, and properly designed charts accompanied the publication. Both these problems became topics of the report presented at the Working conference "Algol 68 Implementation'' which IFIP held in Munich in July 1970 [2]. The considerations on constructing national variants have been taken into account by the authors of the Revised Report and corresponding proposals have been partly included into that Report.

The translation of the Revised Report was not performed as quickly as in the case of the previous Report. It was being produced steadily and thoroughly, by a single author rather than by four of them, but under the vigilant surveillance of the national Algol 68 Commission, and the final result had been published only in 1980 [3].

There were not many publications on Algol 68 afterwards in our country. We can mention the translations of the "Informal Introduction'' by C. H. Lindsey and S. G. van der Meulen [4] and of "A Practical Guide'' by F. G. Pagan [5]. As for the original books on the language, there can be mentioned short descriptions by A. N. Maslov [6], by V. A. Vasilyev [7] and also the "Introduction to Algol 68'' by A. N. Terekhov. The latter forms a part of the book describing the Leningrad compiler [8].

As it has been said before, the national Standard of Algol 68 has been adopted in 1988. The text of this Standard was that of the Russian translation of the Revised Report with some minor variations in form but not in substance. At the same time another national Standard has been adopted, namely "The Standard of the Extended Algol 68''. This document made use of the IFIP proposals on modules and separate compilation and also of G. S. Tseytin's proposals on exception handling.

The complexity of Algol 68, intrinsic to it, has contributed to the fact that the language was nested primarily in the academic and university environment and did not find a large support in the industry. There was a danger that Algol 68 could have become an object of purely mathematical investigations with all closeness proper to them. The members of the Working Group did realize clearly this problem and paid considerable attention to practical implementation of Algol 68 as the main way of its propagation. No session of the Group took place where problems of the language implementation were omitted.

There were several attempts to implement Algol 68 in the USSR. For some reasons, which will be shortly mentioned below, only one of them, namely that of Leningrad, survived, but it really became widely spread.

One of the first implementations of Algol 68 was done in a Kiev computer-producing factory in the end of seventies for Siemens computers. Its authors are S. I. Shtitelman, M. G. Shteinbukh, L. A. Makogon. The implementation was oriented to an information management system called "START'', for which Algol 68 was the only language it used. The authors of the project were interested in Algol 68 primarily as in a source of a data base language. The Kiev implementation anticipated many features of modern languages of that sort: persistent objects, an elaborated system of types, orthogonal design, a large share of interpretativity, and so on. The system of types and orthogonality were in fact due to the Algol 68 itself but the persistence feature urged for some corrections of the language. Namely an "everlasting block'' has been introduced, meant to preserve between the executions of the program those objects that could be used by different programs. In fact it was a data base. Some other variations were also done without any regards to the standardization efforts for Algol 68: all arrays were considered to be flexible, a control variable of a loop was long int rather than int, complex values were absent and so on. Accepted by the Working Group in 1979 this system exists no more because of replacement of hardware in the factory.

At the same time Algol 68 was being implemented on the base of the DEC architecture. This implementation was being performed under guidance of Dr. M. Levinson. Though uncompleted it brought some original ideas into the implementation technique. The main distinction of this implementation was in the scope checking: the life-time of any object was not restricted by the execution time of the block, in which the object was declared.

An implementation of Algol 68 compiler for "Elbrus'' computer complex had been designed by V. V. Brol, V. M. Gushchin, V. B. Yakovlev (Moscow). Its source language is the full Algol 68 defined by the Revised Report and extended by some facilities of module handling. The compiler provides a good quality of the object code, a rather complete error diagnostic. It makes a good use of similarity between main concepts of Algol 68 and those of "Elbrus'' architecture and operating system. The compiler has been accepted by the national Working Group in 1985. The Leningrad group participated actively in testing of that compiler. About ten large application packages developed in Leningrad University were ported almost without a problem to the "Elbrus''. But the tragedy of the "Elbrus'' compiler was that these were practically the only real-life programs that were processed by it.

The promising "BETA project'' in Novosibirsk primarily designed by Dr. A. P. Ershov, M. Shvartsman, A. A. Baehrs was intended to produce compilers from language descriptions almost automatically, and it had Algol 68, PL/I and Simula 67 as its first objectives [9]. The system has really been created, but not in the form initially thought of, and the languages it now encompasses are Simula 67, Pascal (these languages being implemented by G. G. Stepanov and S. B. Pokrovsky), Modula 2 (L. A. Zakharov), a subset of Ada (S. V. Ten), but not Algol 68 or PL/I [10]. Nevertheless, the concepts of Algol 68 were used in the BETA system for creating both its universal compiling scheme and its internal language.

Mostly developed were the works on Algol 68 implementation in the Leningrad University, in the group headed by Dr. G. S. Tseytin and Dr. A. N. Terekhov. Primarily these works were coordinated with the work on BETA system in the frame of a strategy elaborated by the Working Group. It was supposed that the Leningrad group would construct a debugging compiler, a sort of an avant-garde, meant to win new application areas for main forces, namely basic compiler to be constructed in Novosibirsk. A natural presumption was that any application program, debugged by the Leningrad compiler should run on the Novosibirsk compiler without a need to be modified.

As it has been just said, the Leningrad project was originally oriented for practical uses and that fact determined both its principal decisions and its history.

The first version of the Leningrad compiler has been completed to the year 1976. Its analyzing part was written in Algol 60 and run on the ODRA 1204 computer. Its generating part was written in the Macroassembler and worked on IBM mainframe.

After that the whole compiler has been rewritten in Algol 68 and extended: every procedure of the compiler (more than 1000 of them) has been translated on ODRA from Algol 68 to an intermediate language (IL), the punch tape obtained has been input to the IBM computer and translated from IL to the IBM object code. The translation of an average procedure took 10 minutes on ODRA and 20 minutes on IBM. Since debugging of these procedures urged remodifying and recompiling them, time consumed was even greater. The result of this bootstrapping process was the residential compiler which compiled every procedure for 2--3 minutes.

In 1978 the first bootstrapping has been done and the resulting compiler has been yielded to many users in different fields (mathematical physics, radar techniques, simulation). Immediately afterwards the second bootstrapping began. At that moment the designers realized necessity of library preludes and separate compilation of procedures. Therefore a new construct has been added to Algol 68, which appeared to be rather like nest not yet known to the authors.

Great efforts were needed to optimize procedure calls. The code size has been reduced from 16 to 6 bytes per call. For comparison, PL/I-F compiler takes 150 commands per call and the optimizing PL/I takes 30 commands. Ten years later there arouse an idea to reverse the direction of the stack, which provided a considerable reduction of code for procedure calls.

The second bootstrapping has been completed to the year 1979 and this version lasted over 10 ten years with minimal modifications. In that time the designers were busy primarily with the programming technology, for there appeared that Algol 68 is too complicated to be a language for simple tasks, but as for big tasks (real time, for instance) language facilities only do not suffice. But compilation problems were not forgotten: a dozen of cross-compilers for different specialized computers were compiled, an optimization techniques has been improved, the compiler was being integrated with other technical facilities.

At that moment it became clear that it was highly improbable that the basic compiler would ever appear. So a new pass was incorporated in the Leningrad compiler, namely an optimization pass. In contrast to that that was planned in the BETA project, the Leningrad compiler exploited only local optimizations, because an introduction of global optimization would have required a significant revision of compiler structure. Statistics showed later that even among all local optimization only two of them are the most effective – those for parameter passing and for array indexing.

In a sense, implementation of Algol 68 undermined the social basis of global optimization: in most cases the results of global optimization can be expressed in the same language.

In 1980 the Leningard group was addressed by the scientific-industrial union "Krasnaja Zarja'' (which is the major telephone production company in the USSR) with proposal for cooperation in programming of a large class of control and communication task and, in particular, for design of functional software for telephone stations controlled by specialized computers. It took several years to get inside the specifics of the new field, to develop prototype implementations, and to settle organizational issues. The people from Leningrad group were convinced by their previous experience that it was absolutely necessary to use high-level programming languages. However they had to start with raising the programming culture of the applied programmers. This was caused by the reason that traditionally in the area of embedded real-time software development computers with non-standard architecture oriented to an application domain are used. (In fact, it is not evident, what this orientation should be. For example, if a specialized computer perform nicely some special operations, but works badly on branching and procedure calls which occurs thousand times as often as specialized operation, then could one consider it to be orientated to that application domain?). Non-standard architecture and small number of specialized computers lead to the absence of sufficiently developed operating systems, compilers, debuggers, and other common programming tools. So the group had to deal with punchcards and switchboards.

In a short period of time new cross-assembler and interpreter were developed, which together with documentation system and some service programs constituted the basis of the first industrial technological system based on Algol 68 and which was intensively used by hundreds of applied programmers. Naturally, the technology was quite restricted but still popular due to the following objective reasons:

Currently Leningrad group has a wide experience of using Algol 68 in various application areas. The compiler A68LGU which is used as the implementation tool has quite satisfactory characteristics of reliability, compilation time and object code quality. However, recently the authors of Algol 68 proposed new interesting extensions of the language concerning modularity, separate compilation and exception handling. On the other hand, it turned out that the A68LGU compiler does not fit well for incorporating of new technological tools, that were not foreseen from the design point, e.g. debugging in terms of source text. In the course of long exploitation of the compiler some other minor drawbacks were discovered (too narrow range of integer, for example) as well as more serious errors such as incorrect memory allocation in some cases. This lead to the decision to design a new programming system, which was called WBC.

The distinguishing features of the new programming system are integrity and interactive style of work. It has special means for configuration control and large project development support. Yet another specific of the WBC system is its simultaneous orientation on several computers (IBM mainframe, DEC architecture, CAMCOH, PS 1001, PC compatibles, and some specialized computer). Several cross-compilers were realized on the basis of the A68LGU compiler. There was an experience of porting the compiler to different computers. The very fact that the greater part of the compiler is written in Algol 68 provokes an idea of its portability. However, the real porting turned out to be much more complicated. It was necessary to reorganize the whole structure of the compiler and its dynamic environment, to specify precisely parts which depend on hardware or on operation system, to unify the mechanisms of communications. The interface with compiler tables was specified so that various units implementing the interface were possible even on one and the same computer depending on the objectives of a particular compiler.

All compilers of the WBC systems have the following common components and features:

Such unification makes the system open for extension to other computers, and the progress on the way from IBM mainframe to DEC architecture, to CAMCOH, to IBM PC, etc., can be a justification for that.

References

  1. Report on the Algorithmic Language Algol 68, Russian translation by A. A. Baehrs, A. P. Ershov, A. F. Rar and L. L. Zmievskaya. "Kibernetika'', Kiev, Part 6 of 1969 and Part 1 of 1970.
  2. A. A. Baers, A. P. Ershov, A. F. Rar. On Description of Syntax of Algol 68 and its National Variants. In: "Algol 68 Implementation'', edited by J. E. L. Peck, N. H. Publ. Co., Amsterdam-London, 1971.
  3. Revised Report on the Algorithmic Language Algol 68. A. van Wijngaarden, B. J. Mailloux, J. E. L. Peck, C. H. A. Koster, M. Sintsoff, C. H. Lindsey, L. G. L. T. Meertens and R. G. Fiskers (Eds.). Russian translation by A. A. Baehrs, "MIR'' Publishers, Moscow, 1980.
  4. C. H. Lindsey and S. G. van der Meulen. Informal Introduction to Algol 68. Russian translation by L. Leifman, "MIR'' Publishers, Moscow, 1977.
  5. F. G. Pagan. A Practical Guide to Algol 68. Russian translation by A. F. Rar, "MIR'' Publishers, Moscow, 1979.
  6. A. N. Maslov. Algol 68. Structure of Programs, Moscow State University Publishers, 1978 (In Russian).
  7. V. A. Vasilyev. The Language Algol 68. Basic Concepts. "Nauka'' Publishers, Moscow, 1972 (In Russian).
  8. G. Deykalo, A. N. Terekhov et al. New Programming Instruments for ES EVM. "Finansy i Statistika'' Publishers, Moscow, 1984 (In Russian).
  9. A. P. Ershov. A Multilanguage Programming System Oriented to Language Description and Universal Optimization Algorithms. In: "Algol 68 Implementation''.
  10. L. A. Zakharov, S. B. Pokrovsky, G. G. Stepanov, S. V. Ten. A Multilanguage Compiling System. Computing Center of the Siberian Division of the USSR Academy of Sciences, Novosibirsk, 1987 (In Russian).

Alexandre F. Rar — Novosibirsk, Institute for System Informatics;
Andrey N. Terekhov — St.-Petersburg State University

Started by Eduard Proydakov in 1997
© Russian Virtual Computer Museum, 1997-2024