History and lessons of Algol 68

Algol 68 is the Cronus of programming languages. Cronus is the titan who fathered Zeus, an important character in the myth, but vastly overshadowed by his own progeny. Algol 68 was an important language, and had a fascinating history. This post is a combination history, lesson, and filled with quotes from people who were there.

There is an unofficial and undocumented set of stories and folklore in programming. From kids illegally building the Graphing Calculator for Apple to Mel relentlessly optimizing his code around hardware drums. These stories are our lore.

In 1965 work began on the next generation of the Algol programming language, featuring some of the greatest and angriest programmers of the time. It's an exciting story and should be one of the standard histories that every programmer reads about.

The development of Algol 68

In 1965 the Algol Working Group finished its work on the Algol 60 programming language, and turned towards the future. It wanted to build the next generation of Algol. It would compete with other modern languages that were appearing, like Lisp, COBOL, PL/1, and Simula. The initial committee was a powerhouse that included five future Turing Award recipients (Peter Naur, Edsger Dijkstra, Tony Hoare, John McCarthy, and Niklaus Wirth).

In true large committee fashion, the plan went off track quickly and repeatedly.

W. L. van der Poel, the chairman of the group, remarked that the group was spinning its wheels on small issues, and not taking the broader view.

It seems to me that taking the restricted view is putting the clock backward and we revert to an efficient FORTRAN kind of computer. Even PL/I goes further. We must seriously ask ourselves: what do we want to accomplish? Where are we going? Do we want to compete with PL/I or do we really want to make a breakthrough by providing something more powerful and better defined than before.

After this statement and discussion, the group called for volunteers to submit their own proposals for Algol 68.

Adriaan van Wijngaarden submitted a paper called "Orthogonal design and description of a formal language" to the ALGOL X group. It was an ambitious paper that created a new grammar just to help describe a new language. Bauer later said of it, "You want the committee to accept not only the language you have defined but also the peculiar form of description you have chosen for your definition."

The goal of an orthogonal language was that every feature could operate with every other feature. Every statement was actually an expression that returned a value, and that value could be used by any other statement. It was a powerful concept that let a complex language be defined with a few simple features.

To the surprise of Niklaus Wirth (later known for Pascal) and Tony Hoare (later known for Hoare Logic), van Wijngaarden's paper was chosen over their own, more modest proposal. There's were inspired by the Euler language, and had already gone through a round of comments and revisions. Their ideal was a diagonal language, where only certain statements would combine with certain other statements.

Van Wijngaarden was asked by the committee to go forth and build the next generation Algol from his paper. It took six months, and then another six months, and, well, in the words of C. H. Lindsey:

Throughout the whole project, the WG in general, and van Wijngaarden in particular, consistently underestimated the time it would take by substantial factors.

Making Van Wijngaarden truly the original model for a programmer. :)

Lindsey continues:

Recall that ALGOL 60 was put together in six days, albeit after various preliminary meetings over the previous six months. Naur's draft was written in two months, and the final version was circulated within two months after the meeting. But the art of language design and definition had advanced since 1960 and things could not be done at that pace anymore.

The actual language of Algol68

Cross referencing section 3 of A history of ALGOL 68 with Algol 68 – A Retrospective is an education. The former has the historical reasons behind each feature, and the latter has good demonstrations of how they work.

I'm not well versed on the history of programming language, so I can't say for certain which features were invented by Algol 68. Array slices may have been first seen here, given how delighted the committee was to see them. Overloading was being pushed by James McCarthy (LISP), and Algol 68 may have claim to being the first language to implement it.

How to design a language

I've quoted C. H. Lindsey a few times already. He became interested in Algol 68 in 1968, a time when few people, even its creators, really understood it. Lindsey wrote a paper called, "ALGOL 68 with fewer tears", which demonstrated how the language could actually work. Based on the illuminating strength of that paper, he joined the Working Group, and later wrote the definitive history of the language in chapter 2 of History of Programming Languages Volume 2.

Needless to say, he has some well-earned opinions on the topic of language design.

A small group of people (four or five) must do the actual work ... A large committee is a good place for brainstorming to get initial ideas, but it must recognize its limitations, the most important of which is that it is incapable of attending to detail.

Peter Naur said during this effort, "a committee is a group of people unwilling to work, organised by other people incapable of doing so to do work which is probably useless."

Lindsey gives some great advice on how to write a repor, of any sort.

  • Pragmatic remarks should be copious, but well delineated from the formal text. Their purpose is to educate the reader (in the sense of the Latin educare).
  • Motivation should be given for whythings are as they are. Redundancy is no bad thing, except within the strictly formal parts.
  • Syntax should be fully cross referenced, both forwards and backwards; semantics likewise.
  • Each syntax rule should be accompanied by examples.
  • There should be copious glossaries, indices, and summaries.
  • The Report should not take itself too seriously. With the best will in the world, it is not going to be perfect. Our Report contains some good jokes, many quotations from Shakespeare, Lewis Carroll, A. A. Milne and others, and even a picture of Eeyore. The various translations of it have been made in the same spirit.
  • Above all, the Report should be fun to write.

A fun note: The text of the Algol 68 spec was edited with ed and formatted with fmt. It was printed and typeset with custom machines to handle all the special fonts.

The use of a distinctive font to distinguish the syntax (in addition to italic for program fragments) commenced with [MR 93], using an IBM golf-ball typewriter with much interchanging of golf balls. Each time Van Wijngaarden acquired a new golf ball, he would find some place in the Report where it could be used (spot the APL golf ball in the representations chapter).

Scattered conclusions

Algol 68 generated a strongly worded minority report in 1969, warning against the project, signed by Dijkstra and a few others.

More than ever it will be required from an adequate programming tool that it assists, by structure, the programmer in the most difficult aspects of his job, that is, in the reliable creation of sophisticated programs.

C. H. Lindsey ultimately concludes that he's unsure if the language can be considered a success.

Has it a future? The honest answer must now be "No." The world has moved on. To be accepted now, your language needs modules, exception handling, polymorphism, safe parallelism, and clean interfaces to everything else (not to mention a rich and powerful sponsor). Moreover, you need all these things from the start--this is certainly one place where Ada got it right. ... Was the WG wrong to attempt too much innovation in what was intended as a language for widespread use? Possibly so. It may be that experimental features should be tried out in small experimental languages. Instead, we found ourselves with a large experimental language on our hands. That might have been avoided, but only at the expense of more time.

Was it a success?

"Success" is a weird property.

Back in 2000, Mozilla finally released version 6 of their Netscape browser after a long rewrite. The barely-functional browser, and the long time it took to create, was blasted by Joel Spolsky (Things You Should Never Do, Part I). But Netscape 6 was built with help from open source code, and from that flaming wreckage arose the Firefox browser. Firefox was was undeniably a success, and great event for the internet.

Algol 68 was not widely used. It had partial implementations in university settings, but only received a full implementation years later, and I believe that was only done to prove Dijkstra wrong (who thought it couldn't happen).

But Algol 68 did influence an entire generation of languages. Wirth created Pascal after his own rejected proposal for what Algol could have been. Ada was directly inspired by Algol 68, was also designed by committee, and also featured disdain by Dijkstra. Both Dennis Ritchie and Bjarne Stroustrup has cited Algol as a direct inspiration for C and C++. Algol 68 proved the benefits of strong types, the complexity of coersions, and all language designers still take those lessons to heart.

That's why I call Algol 68 the Cronos of programming languages. It's not still living, but it is responsible for the entire pantheon that is.

Reading

Note: If you can't access any of these resources, let me know and I'll email you a copy. I'm at jm@landedstar.com .

A history of ALGOL 68 by C. H. Lindsey

Most of this blog post is taken from Linsdey's chapter in History of Programming Languages II.

The Emperor’s Old Clothes by C.A.R. Hoare

Hoare talks about his unhappy time on the Algol 68 committee in the middle part of his Turning Award talk.

Some Notes on the History of ALGOL by W. L. van der Poel

Van der Poel was the chairman of the working group for seven years, and witnessed all (and recorded much) of its struggles and hilarity. He recorded it in chapter 7 of the most-boringly-named MC-25 Informatica Symposium.

Comments

żaden.

Add your voice