This is the fourth edition of Code Reads, a weekly discussion of some of the central essays, documents and texts in the history of software. You can go straight to the comments and post something if you like. Here’s the full Code Reads archive.
The art of programming is the art of organizing complexity, of mastering multitude and avoiding its bastard chaos as effectively as possible.”
— Edsger Dijkstra, “Notes on Structured Programming”
“Notes on Structured Programming” (1970) is the third and, for now, final Edsger Dijkstra work this series will look at. The paper fills out the terse observations in “Go To Statement Considered Harmful” and the historical overview of “The Humble Programmer” — and offers some detailed examples of the disciplined sort of approach to programming Dijkstra was advocating at the time.
In his 2001 “What led to ‘Notes on Structured Programming'” Dijkstra recalled that he wrote the original “Notes” while emerging from a depression; he felt that his previous work on ALGOL and other systems had “only been agility exercises” and he now faced tackling “the real problem of How to Do Difficult Things.”
At the outset “Notes” declares that its concern is “the composition of large programs” — which may be “say, of the same size as the whole text of this booklet.” (The essay is about 80 pages long, or about 2000 lines of text, which is certainly not small, but might well be dwarfed by latter-day codebase sizes.) Dijkstra takes pains to argue that techniques that work on small programs simply do not scale up: quantity transforms quality; “Any two things that differ in some respect by a factor of already a hundred or more, are utterly incomparable.” “Enumerative reasoning” — by which my mathematically-limited brain understands Dijkstra to mean “attempting to prove a program’s correctness by walking through its steps, line by line” — breaks down as program size grows. Therefore, he argues, “We should appreciate abstraction as our main mental technique to reduce the demands made upon enumerative reasoning.”
In the section “On Understanding Programs,” Dijkstra revisits his “Go To Statement” argument, stressing the need for mechanisms that provide a “co-ordinate system in terms of which the discrete points of computation progress can be identified.” Then, in the section “A first example of step-wise program construction,” he walks us through his method of decomposition — breaking a problem down into smaller and smaller parts so that it can be better understood and solved — using the example of a program to print the first thousand prime numbers.
It’s a fascinating exercise: The first thing he points out is that, if you had an “instruction from the well-understood repertoire” that could make sense of the statment “print first thousand prime numbers,” you were basically done. Since you didn’t have such an instruction, you could begin by breaking the problem in two: “fill table p wiith first thousand prime numbers” and “print table p.” Then each of those two statements needs to be broken down further.
Dijkstra works his way down the levels of the problem until he arrives at “primitive”-level instructions that verifiably achieve the program’s aim. Along the way, he observes: “I think that the behavior of the efficient programmer can be described as trying to take the easiest decision first, that is the decision that requires the minimum amount of investigation (trial and error, iterative mutual adjustment, etc.) for the maximum justification of the hope that he will not regret it.”
At the conclusion of this lengthy exercise, Dijkstra wanly observes that “our treatment of a very simple program has become very long, too long indeed to my taste and wishes.” But he is encouraged that “we succeeded to a large extent in building up this program one decision at a time.”
At the heart of “Notes on Structured Programming” lies Dijkstra’s advocacy of a particular approach to a program’s layered structure: “Each program layer is to be understood all by itself, under the assumption of a suitable machine to execute it, while the function of each layer is to simulate the machine that is assumed to be available on the level immediately above it.”
This “imaginary hardware” vision of abstraction may be foreign to the contemporary programming mindset; Dijkstra explains (in “What Led to ‘Notes…'”) that he’d come to this way of thinking from his experiences early in his career of writing software for hardware that was still being built and couldn’t yet run the programs. He worked that way so the code would be ready in time to ship with the new machines.
With a second detailed example illustrating this approach, Dijkstra arrives at his conclusion — a vision of program structure as “a necklace, strung from individual pearls… Changing a program will be treated as replacing one or more pearls of the original necklace by one or more other pearls.”
“Necklace strung from individual pearls” is probably Dijkstra’s best known phrase (after “Go To Statement Considered Harmful,” which, as we learned, he didn’t even write). It suggests beauty and fine handiwork; oddly, though, it also suggests circularity, which I don’t think is part of the idea. (Perhaps the structured necklace is to be envisioned unclasped.)
In the end, according to “What Led to ‘Notes’,” Dijkstra felt that his notion of “Structured Programming” was hijacked: “Apparently, IBM did not like the popularity of my text; it stole the term ‘Structured Programming’ and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of he goto statement.”
Reading Dijkstra’s description today, I’m left with a sense of a common thread that runs through so many different visions of an improved programming universe. The theme is always, “Why can’t we build programs using easily exchangeable parts?” Dijkstra chose a more elegant metaphor than the common Lego blocks — but isn’t the vision the same? Or are there fundamental differences between his “pearls” and the objects and classes that would later come to dominate programming work?
[tags]code reads, dreaming in code, edsger dijkstra, structured programming, software development[/tags]
Post Revisions:
There are no revisions for this post.