Structured programming: sequence, selection, iteration
In October 1968, about fifty software researchers gathered at a hotel in Garmisch-Partenkirchen — a Bavarian ski resort the NATO Science Committee had recruited for the occasion — to talk about what they were already calling a crisis. The conference report coined the term “software engineering” and used “software crisis” enough times that it stuck. Programs were arriving late, over budget, and riddled with errors. Among those present was Edsger Dijkstra, whose letter abolishing the goto had just gone to press. He left Bavaria with a question: abolishing the goto was the diagnosis. What was the cure?
The following August, back in Eindhoven, he typed his answer. EWD249 — Dijkstra numbered every document he produced, and archivists have since catalogued more than 1,300 of them — argued that a well-structured program is one a programmer can reason about mathematically at every level, from the single statement to the whole system. The central claim was that any computable function needs only three control structures: sequence (statements run in order), selection (if/then/else), and iteration (loops). No goto required. Corrado Böhm and Giuseppe Jacopini had proved this theoretically in 1966, in Communications of the ACM; Dijkstra made it actionable for working programmers.
“Thanks to the ubiquitous Xerox machine,” he later wrote, “my typewritten text could spread like wildfire.” It did. Companies launched internal training programs based on EWD249 before Academic Press had finished typesetting a proper book.
Structured Programming, published in 1972, gathered three essays into 220 pages. Dijkstra’s notes led. Tony Hoare, then at Queen’s University Belfast, contributed an essay on data structures — arguing that a type and its permitted operations belonged together, a claim that would harden a decade later into object-oriented design. Ole-Johan Dahl, co-inventor of Simula at the Norwegian Computing Centre in Oslo, collaborated with Hoare on a closing chapter about hierarchical program structures that introduced something that looked very much like a class. It was, by one contemporary assessment, “certainly one of the earliest books” to discuss classes and objects in print, all in a volume priced at £4.20.
Donald Knuth reviewed it in June 1973, called it “thoroughly stimulating from cover to cover,” and predicted a “profound influence.” IBM, meanwhile, had already stamped “Structured Programming” on an internal initiative that amounted to little more than ban the goto — which was precisely the flattening Dijkstra had been trying to prevent. When a good idea wins broadly enough, the sloganeers arrive before the theorists have finished their coffee.
Fifty years on, every programmer learns sequence, selection, and iteration on the first day of any course. They just don’t call it structured programming anymore. They call it programming.
Sources
- Structured programming — Wikipedia — historical context, the software crisis, and the movement’s arc from Dijkstra to widespread adoption.
- Structured program theorem — Wikipedia — the 1966 Böhm-Jacopini proof that any computable function needs only sequence, selection, and iteration.
- EWD249: Notes on Structured Programming — Dijkstra’s original 1969 manuscript; the source of the book’s first and longest essay.
- EWD1308: What led to Notes on Structured Programming — Dijkstra’s own account of the 1968 NATO conference, the Xerox machine, and the IBM reduction.
- Structured Programming — Internet Archive — the 1972 Academic Press volume, scanned in full.
- Classic Book Review — scenarioplus.org.uk — analysis of each author’s contribution and the book’s lasting significance.
- Knuth review — Stanford CS Technical Report CS-TR-73-371 — Donald Knuth’s June 1973 assessment.