Edsger Dijkstra and Structured Programming

Zusammenfassung

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. It generated more hostile correspondence than any letter the journal had previously published. 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.

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 grew up in a household where precision was not merely valued but expected — his mother, he later said, could solve quadratic equations in her head — and he absorbed this habit of mind thoroughly. He began studying physics at Leiden University in 1948, intending a career in science. But in 1951 he attended a three-week course on programming at Cambridge, one of the first such courses in Europe, and returned convinced that computing was the more interesting problem.

He took a part-time programming job at the Mathematical Centre in Amsterdam in 1952 while continuing his physics degree, and eventually abandoned physics entirely. In 1957 he married Maria Debets, who shared his precision and patience. His formal credentials were in mathematics — 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, while working on the ARMAC computer at the Mathematical Centre, Dijkstra was asked to demonstrate the machine’s capabilities at a trade show. He needed a problem that a computer could solve visibly and impressively. He chose shortest paths: given a map of cities connected by roads with known distances, find the shortest route between two cities.

He designed the algorithm in approximately twenty minutes, sitting at a café in Amsterdam with his fiancée. He did not have paper with him; he worked it out mentally. 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 appeared almost as a footnote, described briefly and without extended analysis. It is now one of the most cited algorithms in computer science. Every GPS navigation system uses a variant of it. Every routing protocol for networks with non-negative costs — OSPF, IS-IS, Dijkstra-based pathfinding in video games — runs on the same principle. The twenty-minute insight has navigated a trillion journeys.

Info

Dijkstra’s algorithm requires non-negative edge weights to guarantee correctness. For graphs with negative weights, the Bellman-Ford algorithm (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

By the early 1960s, Dijkstra had moved to Eindhoven University of Technology, where he would spend two decades building one of the strongest computer science programs in Europe. 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, designed and built at Eindhoven between 1963 and 1967. THE stood for Technische Hogeschool Eindhoven — a Dutch abbreviation that also, Dijkstra noted drily, produced an article that fit naturally in English sentences (“the THE system”). The system had two innovations that were far ahead of their time.

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. This hierarchical decomposition — now universal in operating system design — was radical in 1968 when Dijkstra published it.

The second innovation was semaphores — a synchronization primitive named after the mechanical railway semaphore signals that coordinate train traffic. A semaphore is an integer with two atomic operations: P (from the Dutch proberen, to try — decrement the semaphore, blocking if it would go negative) and V (from verhogen, to increment). By careful use of semaphores, concurrent processes could coordinate access to shared resources without deadlock or race conditions.

Dijkstra proved the THE system correct by construction — each layer’s correctness was argued formally from the properties of the layer below. This was not testing; it was proof. The system worked on first demonstration, which was unusual for software of its complexity in that era.

“Go To Considered Harmful”

In March 1968, Communications of the ACM published a letter from Dijkstra under the title “Go To Statement Considered Harmful.” The title was supplied by the editor Niklaus Wirth; Dijkstra’s original submission was headed “A Case Against the Go To Statement,” which he considered more precise. The letter was two pages long. It generated more hostile correspondence than any letter the journal had previously published.

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. Programs using GOTO freely were, in Dijkstra’s phrase, “quite unpleasant to think about.” The quality of programmers, he argued, could be measured inversely by the density of GOTO statements in their code.

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 by name, described specific programming practices as “absurd” or “criminal,” and expressed contempt for what he called “the industrial and commercial pressure that is corrupting computer science.” 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 the phrase “software engineering,” which he thought implied that software was the kind of thing you could build by following procedures rather than thinking carefully.

His most frequently quoted remark — “Computer science is no more about computers than astronomy is about telescopes” — appears in an EWD and captures his conviction that the discipline’s proper subject was formal reasoning about computation, not the operation of machines.

Predicate Transformers and Weakest Preconditions

Beyond structured programming, Dijkstra developed a formal calculus for reasoning about program correctness: predicate transformers and weakest preconditions. Published 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. The connection to Tony Hoare’s axiomatic semantics (which Hoare was developing in parallel) was close; Dijkstra and Hoare acknowledged mutual influence. For the complementary story, see Tony Hoare and the Science of Programming.

Testing Is Not Enough

One of Dijkstra’s most quoted and most contested observations: “Program testing can be used to show the presence of bugs, but never to show their absence.” This is logically correct — a finite number of tests cannot cover an infinite input space — and was interpreted by some readers as an argument against testing entirely. Dijkstra’s actual position was subtler: testing was useful as a development tool for finding bugs, but it could not substitute for formal proof as a basis for confidence in a program’s correctness. An untested but proved program was more reliable than a tested but unproved one.

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

In 1984, Dijkstra accepted a position 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. He received the ACM PODC Influential Paper Award in 2002 for his work on self-stabilizing systems, a paper he had written in 1974 that anticipated fault-tolerant distributed computing by two decades.

Dijkstra died in Nuenen, the Netherlands, on August 6, 2002. He had specified that his estate should donate his papers to the University of Texas, where they form the Dijkstra Archive — all 1,318 EWDs are available online, a record of fifty years of one of the most disciplined and combative minds in the history of the discipline.

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.

Warnung

Formal methods found important niches in safety-critical software: avionics (the A380 flight management system was partially verified using formal methods), 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.