A perspective of Algol 68
March 2023
The
development of Algol
played an important role in establishing computer science as an academic discipline. The former Mathematisch Centrum Amsterdam, now
CWI, Centrum voor Wiskunde & Informatica
was a leading institute in the design of Algol 68, as it was in later years in the development of Python.
To better understand the position of Algol 68 among today’s plethora of programming languages, we should consider their development. First I will give a chronological overview discussing the period 1950-1960 in which a number of programming languages evolved, then the period 1980-1990 that saw consolidation of imperative languages and later the recombination and maturation of existing ideas in the 1990’s, and finally current trends. After that, the particular history of Algol 68 is discussed, and its current position. You will of course be aware that this post is an Algol 68 implementer's perspective.
In the period 1950-1960 a number of programming languages evolved, the descendants of which are still widely used. The most notable are Fortran by Backus et al., Lisp by McCarthy et al., Cobol by Hopper et al. and Algol 60 by a committee of European and American academics including Backus. Algol 60 was particularly influential in the design of later languages since it introduced nested block structure, lexical scope, and a syntax in Backus-Naur form (BNF). Nearly all subsequent programming languages have used a variant of BNF to describe context-free syntax.
At the time of the development of Algol 68, programming languages were required to serve two purposes. They should provide concepts and statements allowing a precise formal description of computing processes and facilitate communication between programmers, and they should provide a tool to solve small to medium-sized problems without specialist help. The context of Algol 68’s development is perhaps adequately illustrated by a quote [1] from Edsger Dijkstra: The intrinsic difficulty of the programming task has never been refuted … I vividly remember from the late 60’s the tendency to blame the programming languages in use and to believe in all naivety that, once the proper way of communicating with the machines had been found, all programming ills would have been cured.
The early procedural programming languages served above purposes required for them. However, the evolving need to build complex interactive systems asked for decomposition of a problem into "natural" components, resulting in object oriented programming languages starting as early as the 1960’s. The object oriented and procedural paradigms each have strengths and weaknesses and it is not always clear which paradigm is best suited to certain problems. In numerical and scientific computing for instance, the benefit of object oriented languages over procedural languages is controversial since in heavy number crunching, efficiency is a top priority.
The latter is a likely reason that software packages coded in
Fortran
are operational today, despite the rise of for instance Python in this field.
The period 1960 to 1980 produced most of the major language paradigms now in use. Algol 68 was conceived as a successor to Algol 60. Its syntax and semantics became even more orthogonal and were defined by a Van Wijngaarden grammar, a formalism designed specifically for this purpose. Simula by Nygaard and Dahl was a superset of Algol 60 supporting object oriented programming, while Smalltalk by Kay, Ingalls and Kaehler, was a newly designed object oriented language. C, the Unix system programming language, was developed by Ritchie and Thompson at Bell Laboratories between 1969 and 1973. Prolog by Colmerauer, Roussel, and Kowalski was the first logic programming language. ML by Milner built a polymorphic type system on top of Lisp, pioneering statically typed functional programming languages. Each of these languages spawned a family of descendants, and most modern languages count at least one of them in their ancestry. Other important languages that were developed in this period include Pascal, Forth, Scheme and SQL.
During the 1980's imperative languages consolidated. Although major new paradigms for imperative languages did not appear, many researchers elaborated on existing ideas from the 1970’s, for example object oriented programming, and adapting them to new contexts, for example to distributed systems. C++ combined object oriented programming and system programming. The United States government standardised Ada as a system programming language for defense contractors. Mainly in Japan major efforts were spent investigating so-called fifth-generation programming languages that incorporated logic programming constructs. The functional languages community standardised ML and Lisp. Research in Miranda, a functional language with lazy evaluation, began in this decade. An important trend in 1980’s language design was increased focus on programming large-scale systems through the use of modules, reflected in the development of Modula, Ada and ML. Some other notable languages from the 1980’s are Objective C and Perl.
In the 1990’s recombination and maturation of existing ideas continued. An important motivation in this period was productivity. Many rapid application development (RAD) languages emerged, which usually were descendants of older, typically object oriented, languages that were equipped with an IDE and garbage collection. These languages included Object Pascal, Visual Basic, and Java. Java in particular received much attention. More radical and innovative were new scripting languages. These did not directly descend from other languages and featured new syntax and liberal incorporation of features. Many consider these scripting languages as more productive than RAD languages, though others will forward that scripting languages may make small programs simpler but large programs are more difficult to write and maintain. Nevertheless, scripting languages came to be the most prominent ones used in connection with the internet. Some important languages that were developed in the 1990’s are Haskell, Python and PHP.
Some current trends in programming languages are mechanisms for security and reliability verification, alternative mechanisms for modularity, component-oriented software development, constructs to support concurrent and distributed programming, metaprogramming, and integration with databases. This century has so far seen the introduction of for example C#, Visual Basic.NET and Go.
Algol, ALGOrithmic Language, is a family of imperative computer programming languages which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost three decades. The two specifications relevant to this publication are Algol 60, revised in 1963, and Algol 68, revised in 1976. Algol 58, originally known as IAL (International Algebraic Language), was an early member of the Algol family soon superseded by Algol 60. Algol 58 introduced a compound statement which was restricted to flow of control only and did not relate to lexical scope as do Algol 60’s blocks.
Ideally, a programming language supports systematic expression of algorithms by offering appropriate control structures and data structures, and a precise, consistent formal definition to avoid surprises and portability issues resulting from details that are implementation dependent. Members of the Algol family (Algol 60 and Algol 68, Simula, Pascal and also Ada, …) are considered reasonable approximations of such "ideal" languages, although all of them have strong points as well as disadvantages. Algol 68 offers appropriate means of abstraction and exemplary control structures that lead to a good understanding of structured programming. Its orthogonality results in economic use of language constructs making it a beautiful tool for programming.
The design of Algol was firmly rooted in the computing community, at the time a term for the small but growing group of computer professionals and scientists. It formed an international platform for discussing programming languages, compiler construction, program construction, et cetera, and thus Algol had an important part in establishing computer science as an academic discipline in its own right. Algol 60 was designed by and for numerical mathematicians; in its day it was the Lingua Franca of computer science. The language introduced block structure with lexical scope and a concise BNF definition that were appreciated by people with a background in mathematics, but it lacked compilers and industrial support which gave the advantage to languages as Fortran and Cobol. To promote Algol, its application range had to be extended. IFIP [2] Working Group 2.1 Algorithmic Languages and Calculi (WG 2.1), that to this day has continuing responsibility for Algol 60 and Algol 68, assumed the task of developing a successor to Algol 60.
In the early 1960’s WG 2.1 discussed this successor and in 1965 descriptions of a language Algol X based on these discussions were invited. This resulted in various language proposals by Wirth, Seegmüller and Van Wijngaarden [3] and other significant contributions by Hoare and Naur. Van Wijngaarden’s paper Orthogonal design and description of a formal language [4] featured a new technique for language design and definition and formed the basis for what would develop into Algol 68. Many features found in Algol 68 were first proposed in Algol Bulletin by the original authors of Algol 60 like Peter Naur, by new members of WG 2.1 like Tony Hoare and Niklaus Wirth, and by many others from the world-wide computing community.
Reference [5] gives a first hand account of the events leading to Algol 68. Algol 68 has had a large influence on the development of programming languages since it addressed many issues; for example orthogonality, a strong type system, procedures as types, memory management, treatment of arrays, a rigorous description of syntax, and parallel processing, but also ideas that caused debate over the years such as context-sensitive coercions and quite complicated input-output formatting.
After various, apparently lively, meetings WG 2.1 had not reached unanimous consent.
Eventually, Algol 68 was produced by those members wanting a new milestone in language design.
Dijkstra, Hoare, Seegmüller and others wrote a brief "Minority Report", more a letter than a report actually, outlining their view on what Algol 60's successor should have been; many years later it was commented that no programming language developed since, would have satisfied that vision.
Yet others, for example Wirth and Hoare, opted to shorten the development cycle by improving Algol 60, which eventually produced Algol W and later Pascal.
Algol 60 syntax is in BNF form whereas Algol 68 syntax is described by a two-level W-grammar (W for Van Wijngaarden) that can define a context-sensitive grammar.
Simply put, in a W-grammar a high-level grammar produces a low-level grammar for all correct particular programs.
The concept of context-sensitive grammar was introduced by Chomsky in the 1950’s to describe the syntax of natural language where a word may or may not be appropriate in a certain position, depending on context. Analogously, Algol 68 syntax defines syntactic restrictions; for example demanding that applied-identifiers or operators be declared (but not necessarily before they are applied), or demanding that modes result in finite objects that require finite coercion, et cetera. To reject incorrect programs, a context-free syntax must be complemented with extra rules formulated in natural language. The rigorous Algol 68 specification had a few loose ends, while the C specification had a few hundred.
Probably because of the formal character of the Revised Report, which takes some study to comprehend, the misconception got hold that Algol 68 is a complex language. In fact it is rather lean, and the alleged obscurity of description is toned down by most who studied it [5]. Since it is argued that the specification of many contemporary languages, including that of modern C, is more complex than that of Algol 68 [6], one can ask whether the latter just looked complex at the time, fifty years ago.
Algol 68 was defined in a formal document, first published in January 1969, and later published in Acta Informatica and also printed in Sigplan Notices. A Revised Report was issued in 1976 [7]. Algol 68 was the first major language for which a full formal definition was made before it was implemented. Though known to be terse, the Revised Report does contain humour solis sacerdotibus — to quote Koster from [5]: The strict and sober syntax permits itself small puns, as well as a liberal use of portmanteau words. Transput is input or output. ’Stowed’ is the word for structured or rowed. Hipping is the coercion for the hop, skip and jump. MOID is MODE or void. All metanotions ending on ETY have an empty production. Just reading aloud certain lines of the syntax, slightly raising the voice for capitalized words, conveys a feeling of heroic and pagan fun (…) Such lines cannot be read or written with a straight face.
Algol 68 was designed for programmers, not for compiler writers, in a time when the field of compiler construction was not as advanced as it is today. Implementation efforts based on formal methods generally failed; Algol 68’s context-sensitive grammar required some invention to parse [8]. At the time compilers usually were made available on mainframes by computing centres, which may explain why Algol 68 was popular in locations rather than areas, for instance Amsterdam, Berlin or Cambridge. It was relatively popular in the United Kingdom, where the ALGOL68R , ALGOL68RS and ALGOL68C compilers were developed. Commercial initiatives were relatively unsuccessful; for instance the FLACC compiler sold just twenty-two copies [9].
Industry did not adopt Algol 68, with a few exceptions.
There may be as many opinions on this as there are experts you might ask.
IBM would not support it (though CDC did, on demand of academia), it was not as fast as Fortran (but might have been), there was no community outside academia, implementations were lagging …
All too often, the timing must be right, the environment must be open to acceptance and adequate marketing should be in place, for an innovation to have a chance.
But this is my two cents.
Once university mainframes were phased out, the compilers on them were decommissioned.
For scientific work, many migrated in the 1990's from mainframes to workstations that did not have Algol 68.
In fact, me leaving academia in 1991 led me to write
my own Algol 68 implementation so I could continue programming in it.
Algol 68 apparently influenced many who were exposed to it, and it may still do so.
A few individuals wonder, even today, whether it would have a future.
In my opinion, the world has moved on.
Although the language was innovative in its days, development stopped so it reflects the era it was developed in.
Probably there is a newer language like Python that better suits your modern application on modern infrastructure, and has a large community.
Algol 68 will not catch up anymore and further development would probably convert it into an anachronism.
On the other hand, Algol 68 appears very familiar to young people, which is a testament to the influence it had on how we think about programming languages.
Therefore the Algol 68 Genie project preserves Algol 68 out of educational as well as scientific-historical interest. Those interested in the language may study it and actually use it to understand the language and the influence it had, and experience what computer science and computing was like in its pioneering years, half a century ago.
Considering the reactions to the project, I think it is fair to say that it succeeds in this purpose.
Of course, people also use it for programming, for instance in numerical mathematics as I like to do.
Despite its age, even today Algol 68 is a beautiful means for writing algorithms.
Notes
[1] Transcript from keynote delivered at the ACM 1984 South Central Regional Conference. Source: E. W. Dijkstra Archive-the manuscripts of Edsger W. Dijkstra.
[2] IFIP, the International Federation for Information Processing is an umbrella organisation for national information processing organisations. It was established in 1960 under the auspices of UNESCO.
[3] Adriaan van Wijngaarden (1916-1987) is considered by many to be the founding father of computer science in the Netherlands. He was co-founder of IFIP and one of the designers of Algol 60 and later Algol 68. As leader of the Algol 68 committee, he made a profound contribution to the field of programming language design, definition and description.
[4] A. van Wijngaarden, Orthogonal design and description of a formal language.
Available online from CWI.
[5] Proceedings, Conference on the history of Algol 68 [1993]. Available online from CWI.
[6] K. Henney. Procedural Programming: It’s Back? It Never Went Away. Available for viewing on YouTube.
[7] A. van Wijngaarden et al., Revised report on the algorithmic language Algol 68 [1976]. Available online from CWI,
or in HTML as a previous
blog post,
or as part of
Learning Algol 68 Genie
.
[8] B. Mailloux, On the implementation of Algol 68 [1968]. Available online from
CWI.
Algol 68 Genie employs a multi-pass scheme to parse Algol 68. Extracting declarations before parsing as proposed by Mailloux, renders the W-grammar LALR.
[9] Source: Chris Thomson, formerly with Chion Corporation, on comp.lang.misc [1988].
|
© 2002-2024 J.M. van der Veer (jmvdveer@xs4all.nl)
|
