Dijkstra's Crisis: The End of Algol and Beginning of Software Engineering (2010) [pdf]
tomandmaria.com
tomandmaria.com
Dijkstra's rebellion against Algol 68 was deeply ironic. While he drafted the minority report condemning Algol 68 as an "obsolete" tool, his goal was not to make programming easier for everyday developers; instead he used the "software crisis" to advocate for replacing vast teams of average, working-class programmers with an elite corps of "mathematical engineers" modeled on himself. While Wirth and Hoare focused on building practical engineering tools, Dijkstra championed a highly theoretical, ivory-tower approach to programming based on strict mathematical principles and structured logic. Interestingly, both Wijngaarden (the primary architect of the highly complex "mathematical" and heavily criticized Algol 68 specification) and Dijkstra were Dutch.
"I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras."
> A number of these phenomena have been bundled under the name "Software Engineering". As economics is known as "The Miserable Science", software engineering should be known as "The Doomed Discipline", doomed because it cannot even approach its goal since its goal is self-contradictory. Software engineering, of course, presents itself as another worthy cause, but that is eyewash: if you carefully read its literature and analyse what its devotees actually do, you will discover that software engineering has accepted as its charter "How to program if you cannot.".
Moreover, even the report about ALGOL 68 was not bad as a tool for a compiler designer who must search through it which is the correct syntax for various language features. The ALGOL 68 report even contained some subtle humor.
However where ALGOL 68 was a complete failure was that Van Wijngaarden and his collaborators did not publish any other document about ALGOL 68, except the Report.
The Report was completely unsuitable as the first document used by someone who wanted to know what ALGOL 68 is and what it does.
The only way in which ALGOL 68 could have succeeded as a language would have been if Van Wijngaarden would have published at least 3 documents to be read before reading the Report: a tutorial presenting programming examples of using ALGOL 68, a rationale for the design choices of the language (like the designers of the Ada language have published at its introduction) and a document explaining how the Report with the formal specification of the language has to be read.
Without these preliminary documents, the Report about ALGOL 68 looked too alien and it required too much effort to reverse engineer how it is supposed to be understood that even people with the experience of Dijkstra did not bother to make the effort to understand it, so they never knew whether there actually is something valuable in the report or not.
Many years ago, when I have seen for the first time the ALGOL 68 Report, my first thought was also that this must be some kind of useless garbage, and I did not read it. Only years later I tried again and that time I read most of it, so I could see that actually many important programming language features were described there for the first time, and some of them were actually better in ALGOL 68 than in later languages.
I really cannot understand what was in the mind of Van Wijngaarden, how could he believe that publishing this report alone, without accompanying it with a set of explanatory documents, would be enough for other people to learn what ALGOL 68 is. His reputation has certainly suffered after the publication of this report, so whichever was his reason to not write and publish more at that time, it was a wrong decision for his career.
In what respects particularly?
A nice feature of ALGOL 68 that was new at that time was the fully bracketed syntax (like later in the Ada language) with different kinds of brackets for different purposes, i.e. not just one "begin" and "end" pair (or "{" and "}" pair). Having different kinds of brackets for loops, conditional statements and blocks greatly improves the readability of a program, while avoiding the verbosity of commenting the brackets to achieve a similar effect, like it would be needed in languages like Pascal or C. In languages with fully bracketed syntax, the number of brackets used in a program is frequently much smaller than the number of parentheses and braces that must be used in C, where the various kinds of statements do not include braces in their definition, but in practice you must almost always use compound statements enclosed in braces, instead of simple statements. This leads to much more parentheses and braces than are needed in languages with more uniform syntax, like ALGOL 68. E.g. ALGOL 68 "if A then B else C fi" vs. C "if (A ) {B;} else {C;}". I find the first much more readable than the second, which is full of superfluous symbols. Pascal was not much better than C, for the same reason of defining the program structures based on simple statements, when in reality almost always compound sentences are needed, which add redundant instruction brackets in comparison with ALGOL 68.
Compared with the languages of Wirth, ALGOL 68 had more methods for creating data types, e.g. it had tagged unions that worked correctly, not like the crippled and buggy variant records of Pascal. Moreover, the various kinds of defining types could be used in an orthogonal way, which was not the case in the Wirth languages. Also, ALGOL 68 did not have defects like that of the array type from Pascal, where the size of the array was a part of the type and there was no way to declare arrays whose sizes are known only at run time.
ALGOL 68 could allocate variables dynamically, either in a stack or in a heap. This feature had appeared for the first time in the language IBM PL/I, but while in PL/I the heap variables had to be managed manually, with allocate and free, the ancestors of C malloc and free, in ALGOL 68 the heap was managed with a garbage collector like in LISP.
ALGOL 68 had a FOR and WHILE loop syntax that was equivalent with that of PL/I, and both of them were significantly improved over the loop syntax of ALGOL 60 and over the loop syntaxes used in ALGOL W or Pascal or any other of the Wirth languages. ALGOL 68 and PL/I can express loops that are more general than those that can be written in Pascal, Modula or any other Wirth language, but this is accomplished without increasing verbosity, because all elements of a loop specification are optional, so they can be omitted when not needed (this is possible because distinct keywords are used as separators, instead of ambiguous symbols like semicolons or parentheses, so whenever a part of the loop specification is omitted that does not confuse the parser). An example of an ALGOL 68 loop: "for I from A by B to C while D do E od", where any of the parameters together with the keyword that precedes it may be omitted when it has the default value. The WHILE and FOR conditions are combined correctly, so such a loop may express e.g. a search, which can be terminated either when the desired value is found or when all the data structure has been scanned.
Later, the C language introduced a syntax for the FOR loop that allows the writing of some very complex actions in the loop header, more complex than those that can be described in the PL/I or ALGOL 68 loop syntax. However, I consider that the C FOR was a mistake. While in rare cases its generality allows a more elegant writing of some unusual loops, for the 99.999% of the loops that are simple the C FOR syntax forces the programmer to write superfluous boilerplate. This can be simplified at writing if you configure your editor to insert complete FOR templates whenever needed, but the verbosity of the C FOR still hinders program reading in comparison with the simpler syntax of ALGOL 68.
This has not existed in ALGOL 68 at the beginning, but a dialect of ALGOL 68 was one of the first languages that has implemented a kind of FOR EACH loop, which is preferable for the large fraction of the loops that can be expressed in this way (the first language with a FOR EACH was LISP, where several kinds of MAP forms were equivalent with a FOR EACH iteration). Nowadays, in C++ one can avoid most classic C FOR loops by replacing them with simpler FOR EACH loops, but their syntax is much less clean than in languages like ALGOL 68.
There are many other features, one would have to write a full-length article to describe them. There are some ALGOL 68 features that have been inherited by the C language, e.g. the operation-and-assignment operators.
not too far from what Tony Hoare said about ALGOL 60 ;)
My own incomplete opionion is that the net effect is that we ended up writing orderd of magnitude more code than necessary to solve the problems at hand. It's the equivalent of doing the computations manually instead of using a calculator. This has led to an industry that has served us well, but strictly speaking it was never necessary and much more could have been achieved with a fraction of the resources.
Why are the abstractions leaky? Are all abstractions leaky? Why - we simply accept the situation without spending any real effort.
"There's no free lunch" - this is representative of the level of argument in software circles entirely. But WTF does that mean? If the lunch is not free, how cheap or expensive can it get and why?
This is why, as engineers, we tend to brush off the Dijkstras as arrogant, while at the same time ignoring both our arrogance and ignorance.
You're simply wrong to claim that we accept the situation without spending any real effort. In reality the more experienced developers who build abstraction layers tend to spend a lot of time trying to prevent leaks, but they can't have perfect foresight to predict what capabilities others will need. Software abstractions often last through multiple major generations of hardware technology with wildly different capabilities: you can't prevent those changes from leaking through to higher levels and it would be foolhardy to even try.
Do you feel like software transcends pyhsics, mathematics and logics? Because that's what the statement translates to.
The only reason it's impossible, is because nobody tries, because trying to do so would interfer with the deliverables of next sprint. The software industry has painted itself into a corner.
No such faith comforts the software engineer. Much of the complexity he must master is arbitrary complexity, forced without rhyme or reason by the many human institutions and systems to which his interfaces must conform. These differ from interface to interface, and from time to time, not because of necessity but only because they were designed by different people, rather than by God."
- Fred Brooks, No Silver Bullet
You cannot have a thing without doing the work to build it. You don't get the better abstraction without implementing it first. Your proof in theory, is just that, until exercised, and the divergence from the ideal to the real world is finally realized. I can teach a programmer all manner of linguistic trickery to allow them to exploit all sorts of mathematical abuse of notation. None of that makes a cotton-picking, salt-licking bit of difference if at the end of the day, if your symbolic proof isn't translateable to a machine code that runs and maps successfully onto the operational space of an implementation of a computing device. If you give a program written in the form of a Shakespearean sonnet (an example of a focus on radical novelty in encoding a program without regard to analogy); say; I still need a bloody compiler that'll turn that into something that is capable of running within the constraints of the machine, and the other primitives to make it work. That's TANSTAAFL. You break from what exists; you still have to reroot and establish a parallel basis of operation that covers the primitive operations you're familiar with. Djikstra might be right. There's something liberating to staying in the realm of the formal and mathematical. His detractor's were also right. He is so damn far above everyone else, that everybody in the room has trouble understanding just what it is he's going on about. At the end of the day, teach what the greatest number of the people there can firmly mentally grip, and pass that on. The geniuses like Djikstra will quickly outgrow it, and excel. They don't need the help. Everyone else on the other hand, does. I wouldn't be opposed, to trying Djikstra's approach myself. Shattering my current understanding of the practice of programming and working more from a formal methods POV. That comes after a career which has been fruitful, and was rooted in the old way which worked quite well for many others educated at the same time I was. I already know I can do it. His method just changes the emphasis. Though I will note with alarm, his reticence to test is disturbing. If he does assume everything is proofable from the get go, then I suppose you don't need tests; but that's hardly the way anything in the world actually bloody works. That's Math in a vacuum, with spherical cows. Not writing code then realizing "Shit, the processor in the machine I'm writing for doesn't support that primitive, or has a glitchy implementation thereof".
Software engineering isn't programming for people who can't; it's a set of practices and know-how to navigate a niche field that are battle hardened, and tested through time to actually guarantee some semblance of a chance of success in a field shaped by such fast development, the logic of 6 months ago seems antiquated. For that time with Moore's Law in full swing, yeah. Radical novelty might have been justifiable; but ultimately didn't push past the test of time. It can be as clever a hack as you can imagine, but if no one else can follow it... You haven't condensed it to a teachable form.
There's an irony about the design of ALGOL 68. It was denounced at the time as being too big a language, with too many experimental features. In fact, the language in the Report is unimplementable, primarily because the lexical syntax is fanciful (there's an actual difference between the roman period and the italic period) and also abstract (so no two implementations actually have the same lexical syntax). I was on the periphery of an ALGOL 68 implementation project that foundered because the goal was to implement every conceivable edge case, include those that could never occur in practice, e.g., x[i] := x[...50 pages of code...] Yet very reasonable subsets (including ALGOL-68R and FLACC) were built. As for the language breadth, arguably C# is much broader, and I haven't heard anyone claim that it is a failure.
As for the Report...there was a time when I understood it cover to cover. But Lindsey and van der Meulen's Informal Introduction presented the whole language at a level understandable to anyone who understood ALGOL 60. van Wijngaarden did the language a terrible disservice when he forced (that is the correct word, I believe) the use of two-level grammars in order to ensure type correctness. Had the Report never existed, the language would have had much more traction.
The irony? Apart from the grossly-overengineered “transput” library—much better adapted to a unit-record and line printer world than our modern world—the one actual experimental feature in the language was the par clause, which provided parallel execution, and relied on semaphores for synchronization. Dijkstra's semaphores.
Excerpts:
What, for Dijkstra, was the crisis? I believe it was the separation of practice from theory in the development of commercial systems software. Recall the background shared by many of the most distinguishing contributors to the Nato conference, such as Dijkstra, Hoare, Perlis, Naur, and Wirth. They were exceptionally gifted men, many with strong scientific backgrounds, who in the early- and mid- 1960s had produced effective, elegant and reliable pieces of systems software with small teams and tiny budgets while working in research environments or for marginal computer firms. They were not by temperament successful corporate managers or project management specialists. So their instinct was to recoil as word spread of out-of-control industrial development efforts in which millions were being spend to produce unreliable, bloated, and incomplete operating systems and compilers ... Instead their faith was that with the application of suitably rigorous and mathematical methods a small team could produce high quality systems software without the need for massive teams of programmers and elaborate bureaucratic controls.
Near the end of his life, Dijkstra wrote that
"The ALGOL implementation was one of my proudest achievements. Its major significance was that it was done in 8 months at the investment of less than 3 man-years. The rumour was that IBM's FORTRAN implementation had taken 300 man-years and thus had been a project in size way beyond what a university could ever hope to undertake. By requiring only 1 % of that labour, our compiler returned language implementation to the academic world, and that was its political significance".
Yet his single biggest complaint, and one underlying many of the others, was against the idea that computer scientists must adjust their expectations to a world in which most programmers are intellectually mediocre and theory-averse. This is why he called himself a “humble programmer” in his Turing award speech, rather than, as his colleagues might, an arrogant (albeit insecure) academic computer scientist. Trained as a physicist he believed that the proper model for programming came from “mathematical engineering,” a concept he claimed was well understood in the Netherlands but which thoroughly confused his American colleagues. By seizing the mantle of programmer, despite his increasingly deep immersion in the world of mathematical theory and formal methods, Dijkstra could insist that he had not left programming behind. If actual programmers failed to grasp the importance of his new work then it was they who were betraying the true essence of programming.
Dijkstra gave a particularly clear statement of this in 1977, in an open letter circulated to fellow members of Working Group 2.3. According to Dijkstra, in the late 1960s it “became abundantly clear that we did not know how to program well enough.” As a result “people concerned with Programming Methodology,” by which he presumably means him and his fellow working group members, discovered that programming was “a tough engineering discipline with a strong mathematical flavor.” However this inarguable conclusion was sometimes ignored, “because of the unattractiveness of its implications, such as,”
(1) good programming is probably beyond the intellectual abilities of today's 'average programmer’
(2) to do, hic et nunc, the job well enough with today's army of practitioners, many of whom have been lured into a profession well beyond their intellectual abilities, is an insoluble problem
(3) our only hope is that, by revealing the intellectual contents of programming, we will make the subject attractive to the type of students it deserves, so that a next generation of better qualified programmers may gradually replace the current one.
According to Dijkstra, only “political or emotional reasons” could explain disagreement with these “technical” observations. He conceded that they were “unattractive” and had “severe” social implications and no quick solutions. Clearly it would not be easy to replace almost the entire programming workforce. But he dreamed of a scientific revolution, in which programming would win recognition as a mathematical discipline and the incompetent hordes currently messing things up would be swept away and replaced by an elite corps of scientists versed in new and more formal methods of software development.
PS: With AI tools becoming the norm in programming today, things are going to become exponentially worse if "the average programmers" do not study and use formal mathematical methods for code generation and verification.