Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

What Dijkstra said was harmful about goto statements

March 16, 2009

In my last post, I mentioned a Usenet discussion about continue statements and their relation to goto statements, and said that almost none of the responses to that post went beyond the responders' personal opinions.  The comments associated with that post that post mostly repeated the pattern of the Usenet discussion: They did not go much beyond stating the commenters' opinions.

One of the comments did mention Dijkstra's 1968 article Go to Statements Considered Harmful, but aside from that mention, there was much opinion and little fact.

Isn't the claim that goto statements are harmful just an opinion?  No it isn't -- because Dijkstra showed factual properties of goto statements and explained why those properties are harmful.  The sole matter of opinion is how much harm those properties cause--an opinion which can only be contextual.

Dijkstra argued that goto statements were harmful because they complicate two important and related tasks: Proving that a program fragment is correct and describing what a program has done so far.  We'll consider each of these in turn.

Because proving a program correct can be an enormous task, I will concentrate on just one subtask: answering the question What do I know about the state of the program at a given point?

As a simple example, consider a loop:

    while (n != 0) { /* do something */ }

Because this loop has n != 0 as its condition, we know that when the loop terminates normally, n is zero.  Notice that I said "when the loop terminates normally," because if there is a break statement inside the loop, it is possible that n will be nonzero when the loop terminates.  This possibility shows how break statements can make it harder to understand what programs do.

How do we deal with the possibility of break statements in our programs when we analyze them?  In one of two ways: (1) by including whatever conditions apply at the time the break is executed among the conditions that might apply when the loop terminates, or (2) by ensuring that the loop-termination conditions are true when the break is executed.

How do we deal with goto statements when we are trying to understand what a program does?  The question is analogous to the question of how we deal with a break statement: It complicates our understanding of what is happening at the destination.

The destination of a goto is a label.  Accordingly, the complication appears not when we analyze a goto statement, but when we try to figure out what we know about a program when control passes through a label.  In particular, we must inspect every part of the program that might possibly contain a goto statement that refers to this label in order to understand what conditions might hold at those goto statements, and how those conditions affect our understanding of what is happening at the label.

Here is an example to make this complexity concrete.  Suppowe we rewrite our while loop:

    top: if (n == 0) goto bottom;  /* do something */   goto top;  bottom:

On the surface, this loop is no harder to analyze than the earlier version--after all, it behaves in the same way.  However, when we added the label "bottom," we opened the possibility that a goto statement anywhere else in the program might jump there.  So now, instead of merely having to inspect the loop to understand what it does, we must inspect the entire program.

This increase in complexity is a matter of fact, not of opinion; opinion enters only in deciding how important the complexity is.

Dijkstra's second objection to goto statements is not discussed much today, but I think it's still important: With goto statements, it becomes much harder to characterize how far a program has gone in its execution.

His argument was roughly as follows.  If a program has no loops or function calls, you can simply mark the point in the program that execution has reached, and you know everything that has happened so far.  If you add function calls, your marker becomes a stack: When you call a function, you must remember where you were; when the function returns, you can resume from that point.

If the program contains loops, you can use a similar stack, with one entry for each nested loop.  Instead of keeping track of the return point, the stack entry for a loop counts how many times the loop has executed.  Again, when each loop finishes, you can pop the stack.

Once we introduce goto statements, it is no longer possible to keep track of a program's progress with a stack, because control can pass through its labels in any sequence, and in general you cannot know when it is no longer possible for control to return to a given label.  Therefore, adding goto statements to a program means that a stack is no longer sufficient to trace the program's progress.

With these remarks in hand, we can look at continue statements.  What we see is that continue statements are similar to break statements in their effects: A loop with a continue statement must take the conditions at the continue statement into account at the beginning of the loop.  So each continue statement adds one (and only one) more set of conditions to consider when we think about what the loop does.

Similarly, continue statements don't particularly complicate our understanding of how much progress a program has made: Once it has been executed, the surrounding loop starts again just as if it had not been executed.

Therefore, according to Dijkstra's criteria, continue (and break) statements have much less potential for harm than goto statements.  The reason is that goto statements require labels, and each label requires you to examine the entire program to determine what might have happened immediately before the label was executed.  Moreover, the possibility of getting to a label from anywhere implies that it is no longer possible to use a stack to understand how much progress a program has made; instead, it is necessary to use memory that grows without bound.

In short, the reason that break and continue statements are less harmful than goto statements is that each goto statement requires the complexity of figuring out what is happening at a label, and break and continue statements do not add labels to the program.

Again, these claims are matters of fact, not opinion; where opinion enters is only in deciding how much importance to give to the facts.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:



Video