We use the ALGOL family of programming languages to trace one path through the history of computing.
In this episode I'm going to trace out the main history of the ALGOL family of programming languages. ALGOL isn't a name we hear much anymore. That's not so much because it was abandoned as that its approach became so ubiquitous in our field that the name faded away.
We start in 1958. It's important to take a moment and remember what computers were at that time.
Digital computers were no longer new. ENIAC had started calculations in 1945, over a decade earlier. Dozens, even a few hundred computers had been built since then. Note, not different models of computer. Dozens of individual computers, each enormous, most unique. A few had multiple instances of the same model like the Univac I and the Ferranti Mk I.
These computers mostly used vacuum tubes for their logic elements, though transistor based computers had appeared in research labs in the mid 1950's. Their memory was built from delay lines or cathode ray tubes. In a delay line, bits proceed slowly down a line and circuits replay them when they emerge back at the beginning. You read a bit by waiting for it to come through the line, and write a bit by changing what is fed back in at that spot. Memory could hold hundreds of numbers and the computers could perform thousands of operations per second.
There were a few programming languages that could work on different machines, notably FORTRAN, COBOL, and early variants of LISP. There were many more languages that were unique to specific machines and institutions, and even more programmers who were writing assembly directly. In FORTRAN and COBOL there were basic loops over sequences of integers and conditional were handled by an if expression followed by goto. LISP had what we would recognize as modern if/else statements.
Most of the algorithms we thing of as basic today were being invented, such as the various kinds of sorting. When these were published it was in some combination of flow charts, English description, or some dialect of assembly language.
In this setting, a group of researchers decided they wanted to formulate a common language they could publish algorithms in and that they could implement on a variety of machines to run those algorithms. They gathered at the ETH in Zurich, and the result was a specification called ALGOL 58.
[INSERT:
ALGOL is short for ALGORithmic Language. The gathering was the International Algorithmic Language conference, and they originally planned to call the language IAL after the conference, but they decided that was unpronounceable and pretentious. ALGOL was chosen instead.
]
ALGOL 58 was a creature of its time. It had DO loops like FORTRAN where it would iterate over a sequence of integers. If statements followed a previous statement that they controlled, and control flow was done with GOTO. And it didn't last long, because the same group pretty much immediately got to work on ALGOL 60.
ALGOL 60 was very much not a creature of its time. A lot happened, both during it specification and when various groups implemented compilers for it.
Backus-Naur format, which we take for granted today as the way of specifying grammars for programming languages, was invented for ALGOL 58, and revised into basically today's form for ALGOL 60.
The if/then/else statement was brought in from LISP instead of labeling lines with numbers and doing a conditional goto.
To have if/then/else make sense without having to refer to line numbers, code blocks were added and delimited by writing BEGIN before the block and END after it.
Recursive descent parsing was invented by Dijkstra when writing his ALGOL 60 compiler.
ALGOL 60 also forced the stack into existence.
This was a big deal. The common approach to compiler construction at the time came from an academic group based in Zurich, Munich, and Darmstadt. They endorsed allocating every variable in every function in memory when the program was started. This was by far the most efficient way to run the program.
However, that meant that a function could not be called, and then called again before the first call completed or they would collide. This didn't seem like a big deal to the researchers. Remember, on these early machines there was no time sharing. One program ran on the whole computer at a time. There was no question of another thread calling the same function because there were no threads. What could call the same function again was the function itself if it was recursive.
If you allow a function to be called recursively, you have to allocate a new hunk of memory to hold the variables for each call of the function. Variables no longer corresponded to fixed places in memory, and on early machines the time to push and pop these frames onto the stack for each function call was significant.
John McCarthy, the inventor of LISP, had explicitly asked the ALGOL committee to include recursive procedures. Due to how the proposal got voted on in the committee, it might have been rejected, or maybe just the proposed syntax was rejected, depending on who you asked.
On the other side, the compiler researchers at Zurich, Munich, and Darmstadt regarded the efficiency cost of recursive functions as too high. Remember, this is a time when there were still programmers who regarded languages more abstract than assembly as a fool's errand.
Another much smaller group, including Dijkstra in Amsterdam, convinced Peter Naur, the report's editor, to make a small change in the ALGOL 60 specification that would implicitly allow recursive calls. Naur said,
"I got charmed with the boldness and simplicity of this suggestion and decided to follow it in spite of the risk of subsequent trouble over the question."
There was indeed trouble over it. The Zurich, Munich, Darmstadt group was scandalized and they and their students spent the next few years working on subsets of ALGOL 60 that eliminated recursive functions, though in practice plugging all the holes that could allow a recursive called turned out to be very difficult.
The next major iteration was ALGOL 68. And between 1960 and 1968, computing had changed drastically.
First, the computers themselves. The transistor based computers had left the research lab and entirely supplanted vacuum tubes. In place of huge racks of tubes you had circuit boards with many transistors clustered on them. Delay line memory was gone and basically every machine used magnetic core memory that was pioneered in the mid-1950's by the engineering group at MIT that built the Whirlwind computer. Magnetic core consists of a mesh of wires with a small magnet looped into each node of the mesh. Reading a bit consists of activating the wired that connect to it, measuring the resulting current (influenced by the state of the magnet), and then setting the state of the magnet again since reading reset it. The Whirlwind went into service in 1951, but, as Forrester who headed the team and also spent a lot of stolen time at a workbench basically inventing magnetic core memory, said,
"It took us about seven years to convince the industry that random-access magnetic-core memory was the solution to a missing link in computer technology. Then we spent the following seven years in the patent courts convincing them that they had not all thought of it first."
So while ALGOL 60 had been designed in a world of slow, awkward memory, ALGOL 68 was designed in a world where a computer was transistors and magnetic core memory. ALGOL 60's computers held hundreds of numbers and did thousands of operations per second. ALGOL 68's computers held thousands of numbers and did hundreds of thousands of operations per second.
What was on the computers had changed even more. Time sharing had been invented so that a computer could handle work from multiple people at once, and an operating system provided each person with the illusion of being alone on the machine. Computers had interactive terminals instead of feeding in a batch of punch cards or tape and waiting for an output batch of punch cards or tape. It was no longer assumed that most programmers wrote assembly. Some machines, like the Burroughs large machine, only exposed a dialect of ALGOL or other languages to those programming it.
In 1968, the same years that the next major iteration of ALGOL appeared, Doug Engelbert demonstrated networked graphical workstations with video chat and collaborative editing. This wasn't something you could go buy off the shelf—indeed the next fifty years of computing can be seen as making his work widely available—but it was now in what people thought possible.
Structured programming was a brand new idea. It was not widely accepted outside of very mathematical, academic circles. The idea that you could program without goto, and might want to, wasn't generally accepted until well into the 1970's. People had added records (later called structs) to their languages since ALGOL 60, though proper abstract data types would have to wait for Liskov's work, also in the 1970's.
So, this was the world in which ALGOL 68 was designed. The committee working on it split, this time much more severely than had the ALGOL 60 committee over recursion. On one side you had people like Niklaus Wirth—I mention him by name because he will figure prominently as we go along—who wanted a revision to ALGOL 60 while keeping its simplicity. On the other side you had a group that wanted all the things they could do with their new understanding of compilers. The only thing both sides agreed on was keeping the basic syntax from ALGOL 60 and the need to add standard input/output capabilities now that everyone had a machine that could read and write text.
The group that wanted a large language won. By today's standards ALGOL 68 is a very modest language. It defined input/output procedures, and also added some concurrency control, user defined types and records (or structs as they were later called in C) and static type checking, including some fairly sophisticated ways of restricting values that you could assign to a variable. ALGOL 68 didn't have the same wide use that ALGOL 60 did, but it set the tone for the next generation of languages.
At Bell Labs, C took the lineage of BCPL, which was designed to be easy to write a compiler for, and B, which was BCPL stripped down to be even easier to write a compiler for, and added enough of the type checking and structures from ALGOL 68 to make Ken Thompson, its designer, happy.
The United States Department of Defense decided they needed a common language for their software. The result was Ada, a variation on ALGOL 68 with even more static checking and concurrency control.
Funnily, my first mentor in computing had written an ALGOL 68 interpreter. He said that it had one significant user: the Moroccan air force.
And this is the last language named ALGOL that we'll hear about. Unlike FORTRAN, where the language changes drastically while the name never changes, the ALGOL family lost the name and it never returned.
The group that did not like the large language that was ALGOL 68 and wanted to preserve the simplicity of ALGOL 60 went in different directions, and had been for a while. The lineage more or less continued in the hands of Niklaus Wirth and his students, which will be the topic of the rest of this episode.
But first I want to digress to one of the many languages that branched off of ALGOL 60: Simula. Simula is interesting for two reasons. First, it was a beautiful example of a language being adapted to its domain. They began with more or less ALGOL 60, and augmented it to make it better suited to writing simulations. They took records and extended them to be able to declare classes of entities in their simulation. They added coroutines to thread through the parallel actions of entities on each other.
Second, Simula is generally accepted as one of the major influences on Smalltalk and object oriented programming.
Meanwhile, in the time leading up to ALGOL 68, Wirth had his own proposal for a successor to ALGOL 60, which he called ALGOL W. It added various things that had been developed, but remained a very spare language. After the large language was adopted as ALGOL 68, he went his own way.
One very important thing to know about Nicklaus Wirth is that he is a professor of computer science at the ETH in Zurich, where the original ALGOL conferences took place, and Wirth was always very serious about teaching. So when he was supposed to teach a class on compilers he took his language, ALGOL W, kept the new material like records and type checking, and stripped out the parts that made the compiler complicated, like dynamically sized arrays. Then he wrote a virtual machine and bytecode for the compiler to target, and a book teaching how to compile this language, which he named Pascal.
Pascal appeared at the time when minicomputers were taking off. Minicomputers were a step down in speed and storage, but also in size and especially in cost. This has been an ongoing theme in computing: as the underlying technology advanced, it was used to build a computer that wasn't more powerful, but smaller and cheaper and so affordable for smaller groups of people.
We went from ENIAC and Colossus, affordable only to a country, to the Institute for Advanced Study machine and Whirlwind and the Univac, affordable to a large university or company, to machines affordable to a department or medium sized company in the mid 1960's, to minicomputers—which were still the size of a refrigerator—that were affordable by a single laboratory or group, to, at the end of the 1970's, microcomputers, that were affordable by a family or individual, to, in the late 1990's, PDAs and smart phones, which we carried around in our pockets.
Pascal appeared around the same time as minicomputers started becoming common. The minicomputers were less powerful, so their users were looking for smaller languages, not big ones like ALGOL 68. It was designed to be straightforward to write a compiler for. Students had to be able to do it in a few months. And there was a book that taught you how to write a compiler for. Plus it had structured programming and records and static type checking of user defined types and the other new features in programming language design.
Its popularity jumped again with microcomputers for the same reasons. Apple implemented the Macintosh's operating system in a mix of assembly and Pascal. And the release of Turbo Pascal in the early 1980's meant that you could pay $50 and get an integrated development environment noted for its speed of compilation.
Anders Hejlsberg, who wrote Turbo Pascal, went on to lead the creation of Delphi. Delphi was the preeminent example of the Rapid Application Development (or RAD) tools of the 1990's that integrated compiler, development environment, graphical interface builder, and libraries for common tasks like database access into a single tool. Delphi was also based on Pascal, now with object oriented extensions. Delphi still exists, and there is an open source clone called Lazarus.
Hejlsberg later went on to Microsoft to lead the development of C# and now TypeScript.
After Pascal, Wirth's next language was Modula, in the mid 1970's. Again, let's set the stage for what the computers he was targeting were. In this case they were very specific: Wirth's group at ETHZ built their own workstations which the department used, first the Lilith workstations and later the Oberon workstations. These machines began after Wirth had spent a sabbatical at Xerox PARC and spent time with their Alto workstations, which were the step between Doug Engelbert's mother of all demos and the graphical microcomputers like the Apple Macintosh.
Wirth couldn't get an Alto to bring back to Europe, so he decided to build his own, and part of that was writing a successor to Pascal to program it.
Meanwhile, there were three big changes in programming languages that Modula represents.
The first was the idea of abstract data types from Barbara Liskov. This is one of those ideas that became so pervasive that we forgot it was invented. Before this, you could define record types that grouped values together and functions that operated on them, but you always thought in terms of the actual fields on the type.
Liskov pioneered treating the new type as a black box, usable only via a set of functions that defined its interface. This both reduced the mental load on the programmer and let the implementer depend on invariants being maintained. It was a leap even larger than the one from "a variable is a fixed place in memory" to "a variable is a reference to a value, but who knows where on the machine."
Barbara Liskov is one of those researchers where, as a young programmer you say, "I don't get what the big deal is," but as you gain experience you realize that's because her inventions define much of your world.
The second idea continues from the first: modules. It was a new research direction to try to construct programs from distinct modules that could be compiled separately and replaced by any other module implementing the same interface.
The third idea was integrating the concurrency that had been the domain of special purpose languages like Simula into a general purpose language. Graphical interfaces made this concurrency a day to day concern for handling user interaction. So Modula, like Simula, had coroutines.
Wirth revised Simula slightly a couple of times, then went on sabbatical to Xerox PARC again in the 1980's, where he worked on their latest generation of workstations. Again, he couldn't bring one back, and again he wanted what he found. But unlike at PARC where they had a full engineering staff working on these machines, Wirth had himself (minus time on duties as a professor) and a colleague (who also had other obligations).
So Wirth stripped out any complexity he could without drastically worsening the user experience. The Oberon workstations only had cooperative multitasking, not preemptive. Windows couldn't overlap on the screen. He did the same thing to Modula. He added subclassing and dynamic dispatch so he could do object oriented programming. And then he stripped out everything he didn't absolutely need. For example, Modula had more than one kind of loop, equivalent to for and while. Wirth decided this was unnecessary and stripped it down to only one.
Wirth also had a very interesting criterion to decide whether a new optimization to the compiler should be added: does it reduce the time for the compiler to compiler itself? Optimizations add code to the compiler and complexity to the compiler's work. Does the speedup from the optimization exceed the time added to compile the additional code?
Before we continue with Oberon's story, I want to quickly talk about the other development from the ALGOL lineage in the 1980's: SPARK. Recall that the Department of Defense had sponsored the development of the Ada language for their purposes. Ada was already a language designed to let the programmer build strictly maintained structures. When Stepanov introduced generic programming (which most people know to day in C++'s standard template library), the only language at the time that could handle it was Ada until Stroustrup browbeat the C++ committee into adding all the things that C++ needed to do so.
SPARK took Ada a step further and restricted and modified the language so that you could specify contracts on components of programs and verify them both statically and dynamically. As Ada has been revised, so has SPARK.
Anyway, back to Oberon. In the 1990's, desktop environments were all working on the notion of generic document models, so you could embed spreadsheets in your word processor documents or your presentation. Microsoft did this via OLE on top of COM. Linux had two implementations, one in GNOME and one in KDE. Oberon again stripped this idea down to its simplest form and implemented it.
Wirth revised it again and ported it to FPGAs. Since then people have ported it to, the Linux kernel, the web browser and a variety of other places. It is probably the only full workstation environment today that you can pick up a book (written by Wirth!) and learn how it works from the ground up and how to implement it.
The latest branch off this ALGOL lineage is the Go programming language, which heavily credits Oberon in its design while adding a lightweight threads system and C-like syntax.
We've traced this a long way. ALGOL-the-name has vanished. Its direct lineages that survive—Delphi, Ada and SPARK, and Oberon—have become small communities. Everything else that remains is ALGOL's history as a vehicle for carrying ideas through time and communities into the many other lineages of language we deal with today.