This chapter is from the book
This chapter is from the book
This chapter is from the book
Structured Programming: 1968
In 1967, after all the successes he had enjoyed, the MC disbanded Dijkstra’s group because they saw no future in computer science. Dijkstra, for that reason among others, descended into a six-month severe depression for which he was hospitalized.
Upon recovery, Dijkstra started to really stir things up.
In an ironic twist, it was Dijkstra’s dream of mathematics that led him to what is perhaps his most valuable contribution to computer science and the software craft: structured programming. In hindsight, we appreciate that value, but at the time, it stirred up quite a controversy.
In 1967 Dijkstra gave a talk at the ACM Conference on Operating System Principles in Gatlinburg, TN. He had lunch with some of the attendees, and the discussion turned to Dijkstra’s view on the GOTO statement. Dijkstra explained to them why GOTO introduced complexity into programs. The group was so impressed by this discussion that they encouraged him to write an article for The Communications of the ACM on the topic.
So Dijkstra wrote a short article describing his views. He titled it “A Case Against the Go To Statement.” He submitted it the editor, Niklaus Wirth,31 who was so excited to publish it that in March of 1968 he rushed it through as a letter to the editor rather than a fully reviewed article. Wirth also changed the title to “Go To Statement Considered Harmful.”
That title has echoed down through the decades.
The title also raised the ire of an entire cohort of programmers, who were horrified at the very idea. It’s not clear to me whether those programmers actually read the article before declaring their angst. Whatever the case may be, the programming journals lit up like a Christmas tree.
I was a very young programmer at the time, and I remember quite well the fracas that ensued. There was no Facebook or Twitter (X) at the time, so the flame wars were conducted in letters to the editors all around the industry.
It took five to ten years or so for things to settle down. In the end, Dijkstra won that war. As a rule, we programmers do not use GOTO.
Dijkstra’s Argument
In 1966 Corrado Böhm and Giuseppe Jacopini wrote a paper titled “Flow Diagrams, Turing Machines, and Language with Only Two Formation Rules.” In this paper, they proved that “every Turing machine is reducible to, or in a determined sense is equivalent to, a program written in a language which admits as formation rules only composition and iteration.” In other words, every program can be reduced to statements in sequence or statements in loops. Period.
This was a remarkable finding. It was generally ignored because it was deeply academic. But Dijkstra took it very seriously, and the argument he laid down in his article is hard to refute.
In short, if you want to understand a program—if you want to prove the program correct—you need to be able to visualize and examine the execution of that program. That means you need to turn the program into a sequence of events in time. These events need to be identifiable with some kind of label32 that ties them back to the source code.
In the case of simple sequential statements, that label is nothing more than the line number of the source code statement. In the case of loops, that label is the line number adorned with the state of the loop; for example, the nth execution of line l. For function calls, it is the stack of line numbers that represent the calling sequence. But how do you construct a reasonable label if any statement can jump to any other statement using a GOTO?
Yes, it’s possible to construct those labels, but they would have to consist of a long list of line numbers, each adorned with the state of the system.
Constructing proofs using such unmanageable labels is simply unreasonable. It’s too much to ask.
So Dijkstra recommended maintaining provability by eliminating unconstrained GOTOs and replacing them with the three structures we’ve come to know and love: sequence, selection, and iteration. Each of those structures is a black box with a single entry and a single exit, and each is likely composed of the same structures in a recursive descent.
As a simple example, consider this payroll algorithm:
)
Nassi–Shneiderman diagrams like this constrain the algorithm to the three structures. You can see the iteration around the outside, the selection as the first element of the iteration, and the four sequences along the Y path of the selection. Each of those four sequences are subsequences that are themselves composed of sequences, selections, and iterations.
Why, if we are not going to follow Dijkstra’s dream of creating proofs, is this strategy valuable? Because even though we don’t write proofs for our code, we want our code to be provable. Provable code is code that we can analyze and reason about. Indeed, if we keep our functions small, simple, and provable, then we needn’t even create Dijkstra’s labels.
In any case, Dijkstra won the argument rather decisively; the GOTO statement has been all but completely driven out of our modern menagerie of languages.
It would be a mistake, however, to think that Dijkstra’s view of structured programming was simply the absence of GOTO. That’s the part that most of us remember, but his intention was far more involved than that. It went as far as layers of architecture and the directions of dependencies. But I’ll leave you, gentle reader, to discover this for yourself within his wonderful writings.
