Go to Statement Considered Harmful (1968) [pdf]

https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf

by tosh • 7 years ago

55 49 7 years ago

homepages.cwi.nl

rbinv• 7 years ago

Ahh yes, the origin of this phrase. I still cringe every time I see it used.

wyldfire• 7 years ago

Interestingly [1]:

The original title of the letter, as submitted to CACM, was "A Case Against the Goto Statement", but CACM editor Niklaus Wirth changed the title to "Go To Statement Considered Harmful"

...

Frank Rubin published a criticism of Dijkstra's letter in the March 1987 CACM where it appeared under the title "'GOTO Considered Harmful' Considered Harmful". The May 1987 CACM printed further replies, both for and against, under the title "'"GOTO Considered Harmful" Considered Harmful' Considered Harmful?". Dijkstra's own response to this controversy was titled "On a Somewhat Disappointing Correspondence."

[1] https://en.wikipedia.org/wiki/Considered_harmful

kazinator2• 7 years ago

Interestingly, "A Case Against ..." is also a bit of hackneyed title pattern.

stabbles• 7 years ago

Well, sometimes they are useful when a break statement is not enough to get you out of a nested loop.

    while (...) {
      while (...) {
        // ...
        if (...)
          goto stop_it;
        // ...
      }
      // ...
    }
    stop_it:

amitport• 7 years ago

this use case is specifically addressed by "labeled statements" (e.g., https://docs.oracle.com/javase/specs/jls/se12/html/jls-14.ht...)

mFixman• 7 years ago

Double-breaking is a good sign that you need to refactor your code and put any of the while statements inside its own function.

pjc502• 7 years ago

That generally makes it harder to follow and harder to optimise?

kyllo• 7 years ago

In a high level language, yes, you should probably refactor code that looks like that. In C, no--just write the nested loop that iterates the pointers over the array, and use break or goto.

burfog• 7 years ago

Well then you'll need double-returning, which isn't generally available. One could use longjmp I suppose.

chrisbrandow• 7 years ago

I don’t know if it’s a semantic difference or not but some languages, like swift now have labeled loops so the break statement can reference the specific loop, allowing control flow to jump out of the nest.

kevin_thibedeau• 7 years ago

Nothing new there. Labeled loop exits are a feature of Ada.

pjc502• 7 years ago

The "labelled goto" of the modern world is very far from the GOTO of pre-Dijkstra, which would allow you to jump into the middle of loops or functions.

Someone• 7 years ago

Also: “everything in moderation”. If over half your control flow statements are GOTOs, things get hairy fairly soon.

For an example, look up ancient Fortran code.

AnimalMuppet2• 7 years ago

Yeah. Structured programming was a huge improvement over the... let's call it "unstructured" programming that preceded it. Essentially, you take any flowchart you can possibly draw, and you can implement it with GOTOs. The result wasn't easy to understand, debug, or maintain, though.

One question, though: Of the current languages that have a GOTO, won't some of them still allow you to jump into the middle of a loop? That is, is it the languages that force us not to do that any more? Or is it just that we've learned not to do that, because it's a horrible idea?

ncmncm2• 7 years ago

If you want to see the poster child for this problem, consult the sources for procmail.

In the really-not-very-distant past, a clear majority of e-mail went through procmail.

Gibbon1• 7 years ago

This is the thing I keep pointing out. Goto statements of that era had the same semantics as an assembly language jmp instruction. You have to be of a certain age to have seen this shit in practice[1]. There were reasons for that though computers then had very little memory and reusing fragments of code was the only way to get the program to fit.

The scoped goto in modern languages bears no relation.

[1] Consider setting a global variable to X, then jmp to a code fragment which when done then tests the variable and jmp's somewhere if var == x or somewhere else if not. Edit: I think of this type of stuff as a type of 'compression'. Done right there isn't anything 'wrong' with the program. But it's brittle, hard to reason about, and small mistakes results in bizarre wormholes.

btilly2• 7 years ago

And some languages did even stranger things.

For example COBOL's ALTER statement allowed you to modify the target of a given GO TO. The result is that any given GO TO could theoretically transfer control anywhere in the program, based on a statement that could have appeared anywhere else in the program.

Yes, this was used in production. In code that handled real financial transactions.

Vaskivo• 7 years ago

Yes.

Lua doesn't have continue or break in loops. But it has goto. That's one of the uses of it.

It also has, IMO, a sane goto. You cannot jump to any label outside of the function you are running from.

https://www.lua.org/manual/5.3/manual.html#3.3.4

earenndil• 7 years ago

C goto can't jump to another function either (except for longjmp, but that's a whole other story).

Isamu• 7 years ago

The classic. See also another viewpoint in that conversation:

Donald Knuth: Structured programming with go to statements (1974)

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103....

[edit] Of the 102 (!) entries in the bibliography of this paper, Knuth cites 9 of Dijkstra's papers (including the goto paper) and 3 personal communications.

mcguire2• 7 years ago

Somebody needs to ask Tony Hoare about his axiomization of GOTO described in that...

kstenerud• 7 years ago

Try as I might, I just don't see why it's important to maintain an independent index into the process progress of a running program. So you can know the exact point in the process progress where n equals the number of people in the room minus 1... What is the usefulness of it? What problem does it help solve to have this kind of process coordinate in time?

I can understand that unbridled use of GOTO tends to lead to a mess, but Dijkstra's argument seems to be more about the purity of the process, for... some purpose I can't fathom.

Still, I imagine he'd have a field day trashing dependency injection and dynamic dispatch!

AnimalMuppet2• 7 years ago

If you've ever had to deal with the previous mess in all its unbridled impurity, you'd know why Dijkstra cares about the purity of the process. The answer wasn't to use GOTO a little bit less, or a little more carefully. That wasn't going to work. The answer was to eliminate it, root and branch.

mcguire2• 7 years ago

Ok, I'm not sure I understand your question, but I'll try...

Think of his "index" as a virtual program counter, while you are trying to write the code or understand what someone else has written. At some point, the process is going to be in a state where someone has entered the room (i.e. n = #people - 1), and at a later point you have incremented n (so that n = #people again).

One of the key features of Dijkstra's thinking about how to understand and write programs is that you should be thinking about the text of the program, not its dynamic behavior. You should not be "pretending to be the computer"---when you mentally "execute" the program, you have to keep a finger pointed at the current statement (and procedures, recursion, loops, etc., make that pretty difficult).

However, I don't know if he'd fully developed that idea in 1968; this article reads like he was still trying to understand programs by playing out their behavior. So, if you were counting people going into a room, at some point you will have seen someone go in, but not have incremented the counter while after the next statement you have seen someone and have incremented the counter.

Without a lot of discipline, GOTO has the power to completely throw away whatever understanding of the program you have; you could GOTO that point where you are going to increment the count but without seeing anyone go into the room.

harrygallagher4• 7 years ago

(note: everything I'm about to say is just my take on early CS stuff, I don't know Dijkstra or how he thought, these are just conclusions I've personally drawn from reading about the history of computing)

I think it's hard to imagine because it comes from the mindset of those who pioneered programming, like Dijkstra. You're right that he seemed to be concerned about the 'purity' of the process. It's clear from reading the original article that he (and others) thought about programming in a much more 'mathematical' way than modern people. Dijkstra wanted a program to be clearly defined and computable all the way through, but when you're jumping around the code arbitrarily that's... difficult. All of this comes from the fact that computing was birthed from mathematics, and the people involved in it back then were more likely to have a base in math.

ncmncm2• 7 years ago

Edsger, that is.

gregfjohnson• 7 years ago

Dijkstra used the concept of program statements as "predicate transformers". The idea is that a program has a series of predicates (think "assert()" on steroids).

A predicate is a formula (usually in first order predicate logic) that characterizes the allowable states of the program at the point where the predicate appears in the program text. I.e., "N == A * k + B".

Unlike assert statements, a predicate may not be executable, but rather serves as an aid to reasoning about your code.

A statement (i.e., "if", "assign", "case" etc.) modifies the allowable states of the program. Hence the phrase "predicate transformer".

The initial state when the program starts has a predicate that characterizes any required assumptions about the inputs. The final state has a predicate that characterizes the required output of the program upon completion.

Dijkstra, Gries, Hoare, and others created formal rules of inference describing exactly how a given statement modifies the predicates.

This approach worked brilliantly for the normal "structured" statements ("if", "do", etc.)

(To me, the most helpful idea from their system was the idea of invariants for iterative statements.)

However, their approach was impossible to do for arbitrary "goto" statements.

I believe Dijkstra was of the opinion that localized, static reasoning about program correctness was (is) the best way to get code correct and error-free.

The fact that arbitrary "goto" statements destroyed the ability to reason about programs in this manner was why he forcefully advocated against them.

(An alternative framework, denotational semantics, includes the idea of continuations, which among other things provides a mathematically rigorous characterization of arbitrary "goto" statements.)

FWIW, as a programmer I have found over the years that the predicate/"invariant" approach of Hoare-Gries-Dijkstra gives me a useful handle on reasoning through my code and getting it right.

threatofrain• 7 years ago

What you’re describing sounds like TLA+, among other modeling languages.

User232• 7 years ago

Lamport, Dijkstra, Scholten, Hoare, and Knuth, to name just a few, are giants in the field who routinely read each other’s work. I’m positive TLA+ is directly influenced by predicate transformer program semantics.

User232• 7 years ago

Dijkstra’s A Disciple of Programming is a relatively gentle introduction to this programming style using examples. Predicate Calculus and Program Semantics is a much more rigorous formal treatment of the same subject, but arguably a harder read.

Sharlin• 7 years ago

The very related concept of design by contract, pioneered in Eiffel by Bertrand Meyer, is something I've found absolutely essential for writing robust code. Every programmer should be taught to reason about preconditions, postconditions, and logical invariants, and properly document those when writing interfaces. Not bothering to think about edge cases is a major reason for software fragility.

nwhatt• 7 years ago

"I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras."

- Alan Kay

With Alan Kay putting it into context here: https://news.ycombinator.com/item?id=11796926

simonbyrne• 7 years ago

It's difficult to examine his comments without historical context: I haven't dealt with any code from that era, but there is still plenty of Fortran 77 code from ~20 years later where the use of gotos makes it difficult to understand control flow, e.g.: https://github.com/JuliaMath/openspecfun/blob/master/amos/zb...

That said, gotos are still occasionally very useful: jumping out of nested loops and implementing finite-state machines are both made much easier and clearer via gotos than trying to force them into more standard control flow statements.

The linux kernel also makes judicious use of gotos for cleaning up error handling: https://koblents.com/Ches/Links/Month-Mar-2013/20-Using-Goto...

busfahrer• 7 years ago

One thing I've seen a lot in C code is a goto to a single exit point out of a function for common cleanup code

btilly2• 7 years ago

The use of goto to jump out of nested loops is available in many languages as the ability to break out of a labeled loop. Regular structured programming plus this single extension allows any algorithm that can be written with goto to be written without, with no loss of efficiency.

I have seen multiple ways to implement finite state machines. Autogenerated code with goto is indeed a clean option. However I strongly prefer it if the state machine has a relatively clean definition that does not involve goto.

gizmo686• 7 years ago

The linux kernel also makes judicious use of gotos for cleaning up error handling.

Isn't that standard c style? I can't imagine programming c without goto end.

bighi• 7 years ago

A good (although often misundertood) paper.

munificent3• 7 years ago

Coincidentally, I put up a new chapter in my in-progress book last night that contains a long aside with my thoughts on this paper:

http://craftinginterpreters.com/jumping-back-and-forth.html#...

Overall, I find it pretty disappointing. It lacks the rigor that Dijkstra himself argued so strongly for and may have stifled actual useful language research.

svat2• 7 years ago

Thanks for sharing this. I had the same reaction. I have another point to add: many people think of “goto considered harmful” as saying something like: you can use all the other control structures that (say) C provides, but the “goto” statement should not appear in your program. At least that's what I thought, but in Knuth's encyclopedic response to the article, after giving some examples where eliminating goto (mechanically or otherwise) doesn't give great results, there's a section [1] where he discusses some proposed alternative control structures to goto — and among them is “break”! And on rereading Dijkstra's article and looking at the responses to it and some languages from the time, it dawned on me that what Dijkstra was advocating was that the only control structures be conditionals, loops, and subroutines — no “break” or “continue”, no early “return” in a function — and for example this (plus a discouraged goto) is in fact how things work in the original Pascal language (where you return from a function by assigning to a pseudo-variable and waiting for control flow to reach the end). Most programmers who echo “goto considered harmful” have not actually tried the discipline of giving up all of those and seeing how happy they are. Languages have realized that the barebones proposed by Dijkstra were inadequate and have added “break”, “continue” and “return” and even more control-flow structures, like exceptions.

The weak version of the thesis is that too much ad-hoc control flow can be confusing and is best avoided. But most programmers agreed with this anyway (there wouldn't have been much of a debate if this was all it was), and in this version there's no reason the limited set of control-flow structures cannot involve some use of the “goto” keyword (like the “goto end” / “goto cleanup” pattern in C code). The strong version of the thesis, as mentioned in the previous paragraph, is something no one really wants to live with (and I haven't seen the “coordinates” in practice either way). So what people seem to have settled on is an in-between version that abandons the actual content of Dijkstra's article, while retaining the word “goto” as a marker of sin.

[1] http://www.kohala.com/start/papers.others/knuth.dec74.html#c...

munificent3• 7 years ago

And on rereading Dijkstra's article and looking at the responses to it and some languages from the time, it dawned on me that what Dijkstra was advocating was that the only control structures be conditionals, loops, and subroutines

I'm actually not sure if that's what he's advocating. In fact, one of my main complaints with the letter is that he's really not very clear about what he's saying at all. Some of that may be just context that he could assume people had when he wrote it that has been lost since, but I think some of the blame rests on him.

He does say:

One can regard and appreciate the clauses considered as bridling its use. I do not claim that the clauses mentioned are exhaustive in the sense that they will satisfy all needs, but whatever clauses are suggested (e.g. abortion clauses) they should satisfy the requirement that a programmer independent coordinate system can be maintained to describe the process in a helpful and manageable way.

Which I interpret to mean that some goto-ish statements are fine if they are restricted in a way that doesn't make them hard to reason about. I think he would probably consider break, continue, and early returns acceptable in that way since he specifically mentions "abortion clauses", which sounds similar to those to me.

But he never really defines what he considers an acceptable "briding", so we're still left in the dark.

_lwad• 7 years ago

Soon in hacker news: "Go 2 considered harmful"

Go to Statement Considered Harmful (1968) [pdf]

Related Stories