ALGOL 68


ALGOL 68 is an imperative programming language member of the ALGOL family that was conceived as a successor to the ALGOL 60 language, designed with the goal of a much wider scope of application and more rigorously defined syntax and semantics.
The complexity of the language's definition, which runs to several hundred pages filled with non-standard terminology, made compiler implementation difficult and it was said it had "no implementations and no users". This was only partly true; ALGOL 68 did find use in several niche markets, notably in the United Kingdom where it was popular on International Computers Limited machines, and in teaching roles. Outside these fields, use was relatively limited.
Nevertheless, the contributions of ALGOL 68 to the field of computer science have been deep, wide-ranging and enduring, although many of these contributions were only publicly identified when they had reappeared in subsequently developed programming languages. Many languages were developed specifically as a response to the perceived complexity of the language, the most notable being Pascal, or were reimplementations for specific roles, like Ada.
Many languages of the 1970s trace their design specifically to ALGOL 68, selecting some features while abandoning others that were considered too complex or out-of-scope for given roles. Most modern languages trace at least some of their syntax to either C or Pascal, and thus directly or indirectly to ALGOL 68.

Overview

ALGOL 68 features include expression-based syntax, user-declared types and structures/tagged-unions, a reference model of variables and reference parameters, string, array and matrix slicing, and concurrency.
ALGOL 68 was designed by the International Federation for Information Processing IFIP Working Group 2.1 on Algorithmic Languages and Calculi. On 20 December 1968, the language was formally adopted by the group, and then approved for publication by the General Assembly of IFIP.
ALGOL 68 was defined using a formalism, a two-level formal grammar, invented by Adriaan van Wijngaarden. Van Wijngaarden grammars use a context-free grammar to generate an infinite set of productions that will recognize a particular ALGOL 68 program; notably, they are able to express the kind of requirements that in many other programming language technical standards are labelled semantics, and must be expressed in ambiguity-prone natural language prose, and then implemented in compilers as ad hoc code attached to the formal language parser.
The main aims and principles of design of ALGOL 68 are:
  1. Completeness and clarity of description
  2. Orthogonality of design
  3. Security
  4. Efficiency:
  5. * Static mode checking
  6. * Mode-independent parsing
  7. * Independent compiling
  8. * Loop optimizing
  9. * Representations – in minimal & larger character sets
ALGOL 68 has been criticized, most prominently by some members of its design committee such as C. A. R. Hoare and Edsger Dijkstra, for abandoning the simplicity of ALGOL 60, becoming a vehicle for complex or overly general ideas, and doing little to make the compiler writer's task easier, in contrast to deliberately simple contemporaries such as C, S-algol and Pascal.
In 1970, ALGOL 68-R became the first working compiler for ALGOL 68.
In the 1973 revision, certain features — such as proceduring, gommas and formal bounds — were omitted. Cf. The language of the unrevised report.r0
Though European defence agencies promoted the use of ALGOL 68 for its expected security advantages, the American side of the NATO alliance decided to develop a different project, the language Ada, making its use obligatory for US defense contracts.
ALGOL 68 also had a notable influence in the Soviet Union, details of which can be found in Andrey Terekhov's 2014 paper: "ALGOL 68 and Its Impact on the USSR and Russian Programming", and "Алгол 68 и его влияние на программирование в СССР и России".
Steve Bourne, who was on the ALGOL 68 revision committee, took some of its ideas to his Bourne shell and to C.
The complete history of the project can be found in C. H. Lindsey's "A History of ALGOL 68".
For a full-length treatment of the language, see "Programming ALGOL 68 Made Easy" by Dr. Sian Mountbatten, or "Learning ALGOL 68 Genie" by Marcel van der Veer which includes the Revised Report.

History

Origins

ALGOL 68, as the name implies, is a follow-on to the ALGOL language that was first formalized in 1960. That same year the International Federation for Information Processing formed and started the Working Group on ALGOL, or WG2.1. This group released an updated ALGOL 60 specification in Rome in April 1962. At a follow-up meeting in March 1964, it was agreed that the group should begin work on two follow-on standards, ALGOL X, which would be a redefinition of the language with some additions, and ALGOL Y, which would have the ability to modify its own programs in the style of the language LISP.

Definition process

The first meeting of the ALGOL X group was held in Princeton University in May 1965. A report of the meeting noted two broadly supported themes, the introduction of strong typing and interest in Euler's concepts of 'trees' or 'lists' for handling collections. Although intended as a "short-term solution to existing difficulties", ALGOL X got as far as having a compiler made for it. This compiler was written by Douglas T. Ross of the Massachusetts Institute of Technology with the Automated Engineering Design system, also termed ALGOL Extended for Design.
At the second meeting in October in France, three formal proposals were presented, Niklaus Wirth's ALGOL W along with comments about record structures by C.A.R. Hoare, a similar language by Gerhard Seegmüller, and a paper by Adriaan van Wijngaarden on "Orthogonal design and description of a formal language". The latter, written in almost indecipherable "W-Grammar", proved to be a decisive shift in the evolution of the language. The meeting closed with an agreement that van Wijngaarden would re-write the Wirth/Hoare submission using his W-Grammar.
This seemingly simple task ultimately proved more difficult than expected, and the follow-up meeting had to be delayed six months. When it met in April 1966 in Kootwijk, van Wijngaarden's draft remained incomplete and Wirth and Hoare presented a version using more traditional descriptions. It was generally agreed that their paper was "the right language in the wrong formalism". As these approaches were explored, it became clear there was a difference in the way parameters were described that would have real-world effects, and while Wirth and Hoare protested that further delays might become endless, the committee decided to wait for van Wijngaarden's version. Wirth then implemented their current definition as ALGOL W.
At the next meeting in Warsaw in October 1966, there was an initial report from the I/O Subcommittee who had met at the Oak Ridge National Laboratory and the University of Illinois but had not yet made much progress. The two proposals from the previous meeting were again explored, and this time a new debate emerged about the use of pointers; ALGOL W used them only to refer to records, while van Wijngaarden's version could point to any object. To add confusion, John McCarthy presented a new proposal for operator overloading and the ability to string together and and or constructs, and Klaus Samelson wanted to allow anonymous functions. In the resulting confusion, there was some discussion of abandoning the entire effort. The confusion continued through what was supposed to be the ALGOL Y meeting in Zandvoort in May 1967.

Publication

A draft report was finally published in February 1968. This was met by "shock, horror and dissent", mostly due to the hundreds of pages of unreadable grammar and odd terminology. Charles H. Lindsey attempted to figure out what "language was hidden inside of it", a process that took six man-weeks of effort. The resulting paper, "ALGOL 68 with fewer tears", was widely circulated. At a wider information processing meeting in Zürich in May 1968, attendees complained that the language was being forced upon them and that IFIP was "the true villain of this unreasonable situation" as the meetings were mostly closed and there was no formal feedback mechanism. Wirth and Peter Naur formally resigned their authorship positions in WG2.1 at that time.
The next WG2.1 meeting took place in Tirrenia in June 1968. It was supposed to discuss the release of compilers and other issues, but instead devolved into a discussion on the language. van Wijngaarden responded by saying that he would release only one more version of the report. By this point Naur, Hoare, and Wirth had left the effort, and several more were threatening to do so. Several more meetings followed, North Berwick in August 1968, Munich in December which produced the release of the official Report in January 1969 but also resulted in a contentious Minority Report being written. Finally, at Banff, Alberta in September 1969, the project was generally considered complete and the discussion was primarily on errata and a greatly expanded Introduction to the Report.
The effort took five years, burned out many of the greatest names in computer science, and on several occasions became deadlocked over issues both in the definition and the group as a whole. Hoare released a "Critique of ALGOL 68" almost immediately, which has been widely referenced in many works. Wirth went on to further develop the ALGOL W concept and released this as Pascal in 1970.

Implementations

ALGOL 68-R

The first implementation of the standard, based on the late-1968 draft Report, was introduced by the Royal Radar Establishment in the UK as ALGOL 68-R in July 1970. This was, however, a subset of the full language, and Barry Mailloux, the final editor of the Report, joked that "It is a question of morality. We have a Bible and you are sinning!" This version nevertheless became very popular on the ICL machines, and became a widely used language in military coding, especially in the UK.
Among the changes in 68-R was the requirement for all variables to be declared before their first use. This had a significant advantage that it allowed the compiler to be one-pass, as space for the variables in the activation record was set aside before it was used. However, this change also had the side-effect of demanding the PROCs be declared twice, once as a declaration of the types, and then again as the body of code. Another change was to eliminate the assumed VOID mode, an expression that returns no value and demanding the word VOID be added where it would have been assumed. Further, 68-R eliminated the explicit parallel processing commands based on PAR.