Skip to content

Edsger Dijkstra and Structured Programming

Abstract

In 1968, a Dutch computer scientist sent a short letter to the editor of Communications of the ACM. The letter argued that the GOTO statement (a standard feature of every programming language of the day) was harmful to program clarity and should be abolished. Rebuttals were still being printed twenty years later. Edsger Dijkstra was accustomed to this response. He spent fifty years arguing that programming was a mathematical discipline requiring rigorous proof, not an engineering craft requiring clever tricks. He was right on most counts and difficult about all of them, and his ideas, bitterly contested in his lifetime, became the foundations of how software is taught and written today.

Edsger Dijkstra
Edsger W. Dijkstra, 1994. Image: Andreas F. Borchert, CC BY-SA 4.0, via Wikimedia Commons.

Rotterdam to Göttingen to Amsterdam

Edsger Wybe Dijkstra was born in Rotterdam on May 11, 1930, the son of a chemist father and a mathematician mother. He began studying theoretical physics at Leiden University in 1948. In 1951 his father paid for him to attend a programming course in Cambridge, England, his first trip outside the Netherlands and one of the first such courses anywhere.

Aad van Wijngaarden heard about it and hired him: in March 1952 Dijkstra became the part-time programmer of the Mathematical Centre in Amsterdam, which had no working computer yet. In 1955 he decided that programming was the greater intellectual challenge, finished his physics degree as fast as he could in 1956, and never practised physics. In 1957 he married Maria (Ria) Debets; the marriage register would not accept “programmer” as a profession. He received a PhD from the University of Amsterdam in 1959, but his intellectual identity was shaped by the peculiar demands of early computing: the discipline of an environment where an error in reasoning produced not a red-penciled paper but a machine that silently computed the wrong answer, sometimes for days before anyone noticed.

Dijkstra’s Algorithm: Twenty Minutes at a Café

In 1956 the Mathematical Centre held the festive opening of its new ARMAC computer, and Dijkstra had to provide the demonstration. It needed a problem that people who were not mathematicians could understand, answer included. He chose shortest paths: on a reduced road map of the Netherlands with 64 cities (so that six bits could identify a city), find the shortest route between two of them, say Rotterdam and Groningen.

He designed the algorithm in about twenty minutes, on a café terrace in Amsterdam where he and his fiancée had sat down after a morning’s shopping. He worked it out without pencil and paper, which, he said later, forces you to avoid all avoidable complexities. The algorithm was simple in concept: maintain a set of nodes for which the shortest path from the source is already known, and repeatedly extend that set by adding the node reachable at the minimum additional distance. The correctness argument was immediate: at each step, the chosen node cannot be reached more cheaply, because all edge weights are non-negative.

The algorithm ran on the ARMAC in 1956 and was published in 1959 as “A Note on Two Problems in Connexion with Graphs.” It stayed unpublished for three years because a shortest-path algorithm was hardly considered mathematics; it appeared only when F. L. Bauer asked for a contribution to Numerische Mathematik, together with a minimum spanning tree method Dijkstra had worked out for wiring hardware panels. Link-state routing protocols such as OSPF and IS-IS run it, and route planners use refinements of it such as A*. Its place in the longer story, from Königsberg’s bridges to PageRank, is traced in Graph Algorithms.

The Mathematical Centre then went into business. In June 1956 Electrologica was founded as a subsidiary of the Hague insurer Nillmij, whose director Johannes Engelfriet was a mathematician, and its engineers Bram Loopstra and Carel Scholten designed the X1, one of the first transistorised computers on the European continent: germanium transistors in small aluminium modules, 27-bit words plus a check bit, core memory, an addition in 67 microseconds. Dijkstra wrote its basic software, and the X1 was among the first machines to offer program interrupts; his real-time interrupt handler for it became the core of his 1959 doctoral thesis. The first went to Nillmij in 1958; 35 were built by 1965, eighteen of them ordered from Germany, before Philips bought the company in 1968.

Info

Dijkstra’s algorithm requires non-negative edge weights to guarantee correctness. For graphs with negative weights, the Bellman-Ford algorithm (Ford 1956, Bellman 1958) handles the general case at higher computational cost. The distinction matters in practice: GPS routing uses Dijkstra because road distances are non-negative; certain financial optimization problems require Bellman-Ford because some “costs” can be negative gains.

The THE System and the Architecture of Correctness

In 1962 Dijkstra became professor of mathematics at the Technische Hogeschool Eindhoven (now Eindhoven University of Technology), where he first lectured on numerical analysis. In 1963 and 1964 he designed the channels and interrupts of the Electrologica X8 with Carel Scholten. His interest had shifted from algorithms on paper to systems that actually ran, and specifically to the question of how you could know that a complex running system was correct.

Operating systems were, in the early 1960s, notoriously unreliable. A program running on a batch system could corrupt another program’s memory, leave hardware in inconsistent states, or simply crash in ways that were impossible to reproduce. The prevailing approach was to debug problems as they appeared. Dijkstra thought this was intellectually unserious and practically inadequate.

His response was the THE multiprogramming system for the X8, designed at Eindhoven from 1964 and described in Communications of the ACM in May 1968. THE stood for Technische Hogeschool Eindhoven. The system had two features worth describing.

The first was layered architecture. THE was organized as a stack of abstract machines, each layer providing services to the layer above and relying only on services from layers below. Layer 0 handled processor allocation and interrupts. Layer 1 managed memory. Layer 2 handled the operator console. Layer 3 dealt with I/O. Each layer could be reasoned about in isolation, proved correct against its specification, and replaced without disturbing the others. Layering has been standard in operating system design since.

The second innovation was semaphores, a synchronization primitive named after the mechanical railway semaphore signals that coordinate train traffic. Dijkstra had worked them out in 1962. A semaphore is an integer with two atomic operations: P (from the coinage prolaag, short for the Dutch probeer te verlagen, “try to decrease”: decrement the semaphore, blocking if it would go negative) and V (from verhogen, to increase). Used carefully, semaphores let concurrent processes share resources without race conditions; avoiding deadlock still took design, and Dijkstra’s banker’s algorithm addressed it.

Dijkstra’s 1968 paper claimed that the system had been designed so that “its logical soundness can be proved a priori and that its implementation admits exhaustive testing”: each layer was argued correct from the properties of the layer below, and the layers were small enough to test completely. The only errors that showed up in testing, he reported, were trivial coding errors.

“Go To Considered Harmful”

Dijkstra first explained the problem to Brian Randell and others at the ACM operating systems symposium in Gatlinburg in October 1967, and they urged him to publish it. In March 1968, Communications of the ACM printed it as a letter titled “Go To Statement Considered Harmful.” The section editor, Niklaus Wirth, had turned the submitted article, “A Case Against the GO TO Statement,” into a letter to speed publication and changed the title; “X considered harmful” became a template. The letter ran to under two pages. The arguments it started lasted decades: Frank Rubin’s reply “‘GOTO Considered Harmful’ Considered Harmful” appeared in CACM in 1987.

The argument was precise and, once stated, difficult to refute. The GOTO statement transferred control unconditionally to any labeled point in a program. This meant that the relationship between a program’s text (what you could read) and the program’s execution (what actually happened) was arbitrarily complex. To understand what a program was doing at any given point, you had to reconstruct the entire history of all the GOTOs that might have led there. The go to statement, Dijkstra wrote, “is just too primitive; it is too much an invitation to make a mess of one’s program,” and “the quality of programmers is a decreasing function of the density of go to statements in the programs they produce.”

The alternative was structured programming: organizing every program from three control structures only, sequence (one statement after another), selection (if-then-else), and iteration (while loops). These structures had a clean correspondence between program text and program behavior. A structured program could be read from top to bottom and understood, because the control flow was visible in the syntax.

Dijkstra acknowledged that structured programs might sometimes be longer than equivalent programs using GOTO. He was unmoved. The cost of program length was measured in bytes; the cost of incomprehensibility was measured in weeks of debugging.

Info

The structured programming debate of the late 1960s and 1970s was not merely about GOTO. It was a proxy for a deeper dispute: Was programming an engineering discipline, where experienced practitioners’ intuitions should be respected, or was it a mathematical discipline, where correctness had to be argued formally? Dijkstra’s position was unambiguously the latter. Most working programmers found this position impractical, idealistic, or both. Dijkstra found their position intellectually incoherent and said so.

The EWD Manuscripts

Alongside his published work, Dijkstra maintained a parallel output that was in some ways more revealing. Beginning in the 1960s, he wrote a series of numbered manuscripts (EWD1 through EWD1318) which he typed or wrote by hand, photocopied himself, and distributed to colleagues by mail. The manuscripts covered mathematics, programming theory, philosophy of computing, and extended critiques of the field’s intellectual practices.

The EWDs are remarkable documents. Dijkstra was a gifted prose stylist in Dutch and English, capable of both mathematical precision and withering wit. He criticized specific papers and people by name and was openly hostile to commercial pressure on computing science. In EWD498, “How do we tell truths that might hurt?” (1975), he wrote that “the use of COBOL cripples the mind” and that teaching BASIC mentally mutilates students. He disliked COBOL, FORTRAN, PL/I, and BASIC on the grounds that they encouraged bad habits of thought. He disliked the notion that programming skill was measured by productivity in lines of code. He disliked “management” as a category. He particularly disliked “software engineering” as practised, which he summed up as “How to program if you cannot” (EWD1036, 1988).

Myth: Dijkstra said “computer science is no more about computers than astronomy is about telescopes”

The line appears nowhere in his writings, although it is the remark most often hung on him. The argument goes back to Alan Perlis in 1968; the familiar wording surfaced in print in the mid-1980s and was spread as a slogan by Michael Fellows and Ian Parberry around 1991. See Myths and Misconceptions.

Predicate Transformers and Weakest Preconditions

Beyond structured programming, Dijkstra developed a formal calculus for reasoning about program correctness: predicate transformers and weakest preconditions. Introduced in the 1975 CACM paper “Guarded Commands, Nondeterminacy and Formal Derivation of Programs” and worked out in A Discipline of Programming (1976), this framework allowed a programmer to specify the desired postcondition of a program (what should be true when it finishes) and mechanically derive the weakest precondition (the most general condition under which the program would achieve that postcondition when started).

This was programming-as-theorem-proving in a precise technical sense. A program was correct with respect to a specification if and only if its weakest precondition with respect to the specified postcondition was entailed by the initial condition. You did not test the program; you proved it.

The weakest precondition calculus influenced the development of formal methods (the use of mathematical logic to specify and verify software) and found applications in the design of safety-critical systems. It built on Tony Hoare’s axiomatic semantics of 1969, and the two influenced each other for decades. For the complementary story, see Tony Hoare and the Science of Programming.

Testing Is Not Enough

One of Dijkstra’s most quoted observations, from the 1969 NATO conference in Rome and his “Notes on Structured Programming” (EWD249, 1970): “Program testing can be used to show the presence of bugs, but never to show their absence!” A finite number of tests cannot cover a practically infinite input space. Some readers took this as an argument against testing; Dijkstra’s point was that testing could not replace a correctness argument as the basis for confidence in a program.

This position infuriated practitioners who relied on testing as their primary quality assurance method. Dijkstra acknowledged the frustration and declined to retreat from the argument. He was not, he made clear, interested in what was politically comfortable.

Austin and the Final EWDs

From 1973 he was a Burroughs Research Fellow, working mostly from his home in Nuenen. In 1984 he took the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin, where he spent the rest of his career. He continued writing EWDs (by hand, with a Montblanc fountain pen, on unlined paper) until shortly before his death. He retired in 1999.

He received the ACM Turing Award in 1972, before his most influential theoretical work was complete, a recognition of the practical impact of structured programming and semaphores. In 2002 he received the ACM PODC Influential Paper Award for his 1974 paper on self-stabilizing systems; the award was renamed the Dijkstra Prize after his death.

Dijkstra died in Nuenen, the Netherlands, on August 6, 2002. His papers, about 40 linear feet of manuscripts, diaries and correspondence, are held by the Briscoe Center for American History at the University of Texas, and the university’s E. W. Dijkstra Archive has put more than a thousand of the EWDs online.

Dead End: Programming as Pure Mathematics

Dijkstra’s most ambitious vision: that programming would converge toward theorem-proving, that programs would be derived by formal transformation from specifications rather than written and debugged, was not realized in mainstream practice.

Warning

Formal methods found important niches in safety-critical software: avionics (the static analyser Astrée has been used to prove the absence of run-time errors in safety-critical Airbus software, including the A380’s), medical devices, nuclear plant control, and certain financial systems. In these domains, the cost of verification was justified by the cost of failure. But in commercial software development (web applications, enterprise software, consumer apps) formal methods remained an academic specialty. The reasons were practical: formal specification requires mathematical training that most programmers lack, takes more time than management typically funds, and scales poorly to large codebases developed by changing teams. Dijkstra found this situation deeply unsatisfactory and attributed it to the intellectual failure of the software industry. The industry, in return, largely ignored him and kept writing tests. Both parties were, in their own terms, correct.

The influence of Dijkstra’s structured programming on language design is explored in The Rise of High-Level Languages. His work on concurrent systems connects to The Unix Story.

📚 Sources