Edsger W. Dijkstra

(Redirected from Dijkstra)

Edsger Wybe Dijkstra was a pioneering computer scientist particularly interested in using mathematical proof to produce correct programs. In programming language design he is noted for early advocacy against the GOTO statement (like APL's branch) in his 1968 paper "A Case against the GO TO Statement", later retitled "Go To Statement Considered Harmful"[1]. He is known in array programming for his consistent complaints against the APL language and community.

Relationship with APL

There is no evidence that Dijkstra was ever a user of APL, and several of his remarks suggest he would refuse any opportunity to use or learn it. His familiarity with the language comes from attending presentations by Ken Iverson and others, and friendship with Alan Perlis, a fan of the language.

Dijkstra attended a 1963 lecture on Iverson notation by Ken Iverson, and even asked a question of Iverson:[2]

Dijkstra: How would you represent a more complex operation, for example, the sum of all elements of a matrix M which are equal to the sum of the corresponding row and column indices?

Iverson: ${\displaystyle ++/(M=\iota ^{1}{\begin{smallmatrix}\circ \\+\end{smallmatrix}}\iota ^{1})//M}$ [the initial ${\displaystyle +}$ is likely a transcription error]

In 2001, Dijkstra cited Alan Perlis as the main source for his exposure to APL.[3]

Commentary on APL

Dijkstra didn't hate APL specifically: he hated every language other than ALGOL 60. However, APL has been the target of specific criticism in a number of his correspondences (which are called EWDs, after Dijkstra's initials):

• EWD295: Iverson was walgelijk, dit was een “slick commercial” over APL. Het weerzinwekkendst vond ik zijn grofheid jegens zijn publiek. Als het zijn bedoeling is geweest om APL te verkopen, dan is hij hierdoor niet geslaagd: het publiek accepteerde hem niet. Ik kan het ontwerp geen consistentie ontzeggen (zal dat ook niet doen), wat op het eerste gezicht alleen maar ad-hoccery lijkt, blijkt meestal op een of andere manier overwogen. Het heeft mijn indruk bevestigd dat de invloed van APL op zijn gebruikers funest is: it is a giant bag of tricks! En inplaats van dat het de neiging programmeren te zien als puzzlen bestrijdt, moedigt het gereedschap deze opvatting aan. Ik dacht —en geloof dit nog— dat programmeren in de eerste plaats een conceptuele uitdaging is en zie niet, hoe APL in dit opzicht een stap vooruit is. Het treft mij zelfs als een stap achteruit.
Translated with deepl, with edits:
Iverson was disgusting. This was a "slick commercial" about APL. The most disgusting thing I found was his rudeness towards his audience. If his intention was to sell APL, he didn't succeed: the public wouldn't accept him. I can't deny (or won't deny) the design consistency, which at first glance seems only ad-hoccery, and is usually considered in some way. It has confirmed my impression that the impact of APL on its users is disastrous: it's a giant bag of tricks! And instead of fighting against seeing programming as a puzzle, the tool encourages this view. I thought —and still believe this— that programming is first and foremost a conceptual challenge, and I don't see how APL is a step forward in this respect. It even strikes me as a step backwards.
• EWD340 In the case of a well-known conversational programming language I have been told from various sides that as soon as a programming community is equipped with a terminal for it, a specific phenomenon occurs that even has a well-established name: it is called “the one-liners”. It takes one of two different forms: one programmer places a one-line program on the desk of another and either he proudly tells what it does and adds the question “Can you code this in less symbols?” —as if this were of any conceptual relevance!— or he just asks “Guess what it does!”. From this observation we must conclude that this language as a tool is an open invitation for clever tricks; and while exactly this may be the explanation for some of its appeal, viz. to those who like to show how clever they are, I am sorry, but I must regard this as one of the most damning things that can be said about a programming language. Another lesson we should have learned from the recent past is that the development of “richer” or “more powerful” programming languages was a mistake in the sense that these baroque monstrosities, these conglomerations of idiosyncrasies, are really unmanageable, both mechanically and mentally.
• EWD385: I am afraid that the result is a disaster, at least for German Computing Science. German Computing Science is in danger of being taken over either by the mathematicians or by APL; in both cases the result will be very much the same, viz. the end of German Computing Science! [See also APL-Germany]
• EWD406: Morris showed me some of his efforts to design a higher programming language that would control that machine: it was a valiant effort, but too much APL'ish to inspire me.
• EWD456: Two years ago I pondered about the design of an intellectually well-manageable programming language, the implementation of which would allow a potentially very high degree of concurrency without imposing it (nor, of course, requiring the amount of temporary storage that would be needed to simulate the concurrency.) One can try to reach such a goal by the introduction of multi-component datatypes like in APL, but then the price to be paid seems to be a very elaborate repertoire of operations, and, having seen where that leads to, I obviously did not want to go down "that slippery road of reasoning".
• EWD498: APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums.
• EWD633: I thought "On the Power of Applicative Languages" by R.Lipton and L.Snyder one of the worst [conference talks]: its actual topic, believe me or not, was a study of the space/time complexity of ... APL-one-liners! [See also Co-dfns]
• EWD638: None of the many papers about program verification and derivation that I have written or seen uses APL as a programming vehicle. This could be an accident, it could also be a consequence of the rich expression structure of APL. (They refer to proofs as "...substitutions to be checked with the aid of simple algebraic identities" which, in the case of APL-expressions are perhaps not so simple...) If the latter conjecture is correct, it would explain why APL-addicts might feel unhappy about (or threatened by) modern achievements in proving the correctness of (non-APL) programs. Does it help the understanding of this paper and its venom to know of the heavy involvement with APL of its authors? We can only guess and have our private opinions.
• EWD952: Whereas computing science made great strides towards a vigorous, rigorous discipline, computing practice showed mainly stagnation. I am not exaggerating: the physicists still think that FORTRAN is the last word in computing, the chemists continue with BASIC, and what APL is for the electronic engineer, COBOL is for the MBA.

APL is far from unique in this respect: complaints about COBOL, FORTRAN, PL/I, LISP, PASCAL, and Ada each outnumber complaints about APL in EWDs, and praise for any of these languages is entirely absent, with the exception of LISP, about which Dijkstra remarks "I must confess that I was very slow on appreciating LISP’s merits"[4].

Additionally, Dijkstra gives some reasoning for his dislike of APL in a personal correspondence reproduced by the Vector journal.

• A typical characteristic of the APL devotee is, for instance, his closeness to an implementation of it. I know of a visiting professor at an American University [sic] who, trying to teach APL, bitterly complained about the absence of APL terminals. He was clearly unable to teach it without them. And you, too, write to me that you would like to meet me in your part of the world, so that you can “demonstrate APL” to me. This is in sharp contrast to people who prefer programming languages that can be adadequately [sic] “demonstrated”—i.e. shown, taught and discussed—with pencil and paper.

A further comment is recorded by Alan Perlis[5]:

What [Fritz Bauer] saw or heard was Ken’s remark that APL is an extremely appropriate language for teaching algebra, and he muttered under his breath to me, in words I will never forget, “As long as I am alive, APL will never be used in Munich.” And Dijkstra, who was sitting on my other side, leaned toward Bauer and said, “Nor in Holland.” The three of us were listening to the same lecture, but we obviously heard different things.

"A mistake, carried through to perfection"

By far the most widely reproduced comment made by Dijkstra about APL is the one in EWD498, titled "How do we tell truths that might hurt?":

APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums.

This remark is the last of a list of comments denigrating FORTRAN, PL/I, BASIC, and COBOL, and is followed by a series of negative remarks about the users and developers of programming languages: businesses, IBM, the Department of Defense, soft scientists, and physicists.

Although Dijkstra does not describe in EWD498 the reasons why he believes APL to be a "mistake" (this section of EWD498 is presented as a list of "truths" which Dijkstra assumes the reader mostly agrees with), we can reach some understanding based on the quotes reproduced above as well as the first of his list of truths:

Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.

Dijkstra believed that the most important task for a programmer was to produce provably correct programs. Many of his works emphasize the use of handwritten mathematical proofs produced alongside programs, although he also contributed to the development of automated theorem proving systems. The most important factor in his judgment of programming languages was its amenability to and encouragement of formal proofs, and he saw APL as a failure in this regard. Dijkstra held that the ease of use of early APL sessions relative to other programming systems was actually an anti-feature: the ability for programmers—even those without a strong grasp of computer science or mathematics—to interactively develop programs led to a failure to develop proper programming technique and poorer programs.

It's also possible that the reference to "the programming techniques of the past" refers to the use of branch for control flow. This criticism is now irrelevant: modern APL programming uses control structures like all mainstream languages. Indeed, APL's use of reductions and the Each and Outer Product operators can be seen as a step beyond structured programming in moving from imperative to functional structure. This technique has become common in the 2010s, but APLs use of these operators in the 1980s and 90s was well ahead of its time.

Dijkstra elaborates further on his reasoning for the quote in a 2001 interview published by the ACM[3].

I thought that programmers should not be puzzle-minded, which was one of the criteria on which IBM selected programmers. We would be much better served by clean, systematic minds, with a sense of elegance. And APL, with its one-liners, went in the other direction. I have been exposed to more APL than I'd like because Alan Perlis had an APL period. I think he outgrew it before his death, but for many years APL was "it."

APL by Dijkstra's criteria

While Dijkstra believed that APL failed as a language for the development and communication of mathematical ideas, many APLers have disputed this idea and expressed confusion as to how he arrived at this viewpoint.[6] Array programmers have argued that APL, designed as a mathematical notation, is one of the best embodiments of Dijkstra's goals for programming languages, and some have attributed his dislike for the language to a lack of familiarity or understanding. In particular, examples of the use of APL and J in proofs include:

Dijkstra laments the inability of APL programmers to live without an APL session: an odd criticism, as the first APL session, APL\360, was released years after the publication of A Programming Language, and created at a time when Iverson Notation had already been used to teach mathematics and design IBM hardware. In fact it is common for APLers to communicate verbally, on a blackboard, or on paper without using an APL session; Aaron Hsu is known for combining his use of APL with a love of calligraphy and fountain pens in order to fill notebooks[7]. Among mathematically inclined APLers, the session is often considered an aid in constructing a correct proof rather than a goal in itself. As an "executable mathematical notation" APL is both suited for expressing the final result and for verifying with examples that the steps of the proof are correct.

One specific complaint that Dijkstra levels at APL is its use of an expanded set of operations relative to the typical set used in computer science research. It's true that APL dedicates much of its functionality to working with arrays, but this shouldn't be taken as a theoretical weakness. In fact, APLs array operators are much like structured programming, which eliminates a single construct, Go to, in favor of several branching and looping constructs like if and while. Moving from scalar processing to array processing requires new operations in exchange for, not at the expense of, improved theoretical properties. Nonetheless, language designers such as Arthur Whitney put considerable effort into reducing the number of symbols needed in the language in order to express ideas. Indeed, Fred Brooks praised Iverson for a "fierce determination not to invent any new constructs, until you have to."[8]

Dijkstra pointed out that APL is not used in practice for theoretical computer science applications. This is likely to be cultural: because of the requirement that published papers be readable by most practicing theorists, computer scientists tend to use languages or pseudocode which is kept deliberately simple and uses only the well-known programming features. Nonetheless there are array languages or languages with array influence aimed at theoretical work, such as FP, Nial, and Futhark. APL concepts such as the Scan operator have also been adopted in the study of parallel programming.[9] Aaron Hsu has made heavy use of APL in studying parallel algorithms in Co-dfns, and emphasizes its transparent performance characteristics: time and space complexity can usually be obtained directly from an APL expression with little effort.

Dijkstra claims that APL is a "bag of tricks" which encourages the programmer to think of problems as merely puzzles which require them to find the correct trick rather than to approach them by trying to express their ideas elegantly. An APLer would probably conclude that he has fallen into the trap of thinking of APL as a domain-specific language which just happens to have the right solution for the particular problem under consideration. Iverson thought instead that APLs tricks are carefully selected tools which guide programmers to more elegant solutions, and elegance is a primary concern for APL programmers today. This comment may also reflect a lack of introspection by Dijkstra into his own working methods and those of other mathematicians: mathematicians work by applying high-level concepts, techniques, or tricks, and write proofs by translating these tricks into mathematical language. APL aids a mathematician's thinking by supplying a well-considered set of techniques, and eases reading by making the "tricks" explicit rather than forcing the reader to extract them from a low-level notation.

Influence

Dijkstra's paper "Go To Statement Considered Harmful" was an important factor in the introduction of structured programming, which in APL has led to the addition of control structures and encouraging their use in favor of the branch command. Papers on APLGOL and SAPL, two experiments in bringing structured programming to APL in the 1970s, both reference Dijkstra's work.

Marshall Lochbaum cites EWD1300, "The notational conventions I adopted, and why", and in particular the notion of spacing to represent precedence, as an influence on the design of I.[10]