Goto (2007)

> "Dijkstra later abandoned the search for program provability and turned instead to the study of techniques for correct program derivation"

It's odd how even today very few people in the "formal verification" world understand this distinction. Naturally verifying a derived program is trivial, since it's literally a proof by construction. I've attempted many times to explain this distinction, and they inevitably just start babbling about the limitations of the tooling they use. A sad case of man with a hammer syndrome and probably an illustration of my own failure to achieve clarity I guess.

> "However, to some extent Dijkstra's principle has not been fully realized when we observe the complexity that must be dealt with by real-world programming tasks, such as multitasking, multithreading, interrupt handling"

Dijkstra designed the first proven correct interrupt handler for a multitasking OS two years before the Goto Letter[1][2] so I think we can rest assured that he was aware of these issues.

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

[2] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/E...

This is a good balanced article.

What is often missing from these goto discussions is the dialog between Knuth and Dijkstra on this topic.

There is another discussion between the two of them about a problem requiring no less than four stacks to understand.

Think of everythin which in java you would put in the catch and finally blocks. Those are nearly always most cleanly handled in C code by doing a goto to the cleanup/return section at the end of the function.

You could work around this via tons of deeply nested blocks, but that makes the code very unreadable. The goto cleanup pattern makes the code intuitive and very readable.

I still have a printout somewhere of an application from the 80s, maybe a dozen pages in small font, every few lines it jumps via goto to somewhere else, depending on state (global variables, of course). It was a serious nightmare to figure out where the code is going. That was the historical context of "goto considered harmful". It sure was! Code like that doesn't exist today, the lessons have been learned. It had nothing to do with clean jump to a cleanup section (which is what a finally{} block is, after all).

It's a very common pattern for C memory allocation checking. A public example I know off the top of my head can be seen here: https://github.com/zedshaw/learn-c-the-hard-way-lectures/blo... (the implementation of the CHECK macro). That's in a C tutorial but I've implemented a version of that macro frequently.

Let's say you need to dynamically allocate two buffers in a function and want to make sure they are freed at the end of your call. You can use this macro like so:

  int two_bufs(int n, int m) {
    int *buf_1 = NULL;
    int *buf_2 = NULL;
    buf_1 = calloc(n, sizeof(int));
    CHECK(buf_1);
    buf_2 = calloc(m, sizeof(int));
    CHECK(buf_2);
 
    // ... lots of cool things with buf_1 and buf_2

  error:
    free(buf_1);
    free(buf_2); // Safe if null

  }

It's good for a simplified version of exception handling for C (granted C does have setjmp/longjmp but that's more like the complicated version of exception handling)

If you hit an error condition in deeply nested logic and need to go to common error handling code or go to a recovery point, then goto makes sense.

Often times in these scenarios simplifying the logic is also an option, but that isn't always the case, especially when dealing with external interfaces that have a lot of potential error conditions that cannot be dealt with easily from the immediate caller (I'm thinking primarily of system interfaces, but also potentially library interfaces).

From what I've seen this is the only really good scenario for goto and I think the examples in the article more or less fall into this category of escaping from deeply nested error cases.

Another example not covered on the article is tail call optimisation. GCC is not very good at it and manually adding it using goto can sometimes speed code up by ~20%. Very useful when writing down a complex recursive algorithm that you can't easily express as a loop.

If you have a dispatcher or an infinite state machine, say an emulator. Or even just anything in general with cleanup, you use goto to "goto ERRORCLEANUP". So you have one exit condition to clean up. This is recommended in CERT c.

There's a good real world example of goto for progressive cleanup here: https://github.com/square/pam_krb5_ccache/blob/master/pam_kr...

The Linux kernel has 28 million lines of C code, and 180 thousand goto statements.

1 every 160 lines is a goto, and that's just a naive count so includes all header and preprocessor gunk, whitespace, some generated C code, comments, etc.

If you're talking about more pure lines if C, it would probably be close to 1% of statements are goto.

It might not be everyone's cup of tea as the pinnacle of C programming, but it's a real highly used medium-large project that has coped well with a pretty high rate of change from a very wide spectrum of contributors. So it is a good real world example of open C code you can look at that is maintainable while making a lot of use of goto.

There are a few decent examples given by the Linus kernel devs on a LKML thread where an unfortunate soul wandered in and suggested that they refactor to get rid of GOTOs: https://lkml.org/lkml/2003/1/12/126

> "I will prefer to hide one or more of the inner loops inside of a function call."

That risks the additional unnecessary overhead of a function call, which can be expensive in a loop, and not all compilers are as good at optimizing as they should be.

What's wrong with the examples in the article?

> deeply nested loops. [...] I will prefer to hide one or more of the inner loops inside of a function call.

And I would too... but sometimes there are too many local variables involved to do that cleanly. And, ultimately, if you are making your code less clean to avoid using a goto then you avoided unwisely.

> Can you give an example of where you've used goto in C or a C-like language?

Well there have been several fairly normal examples cited by others. Let me set out my stall and present a more controversial one.

Suppose I have a switch() block (which is sorta a glorified goto already!) and I have two cases that have the same epilogue. For example:

  switch (get_next_thing_to_do()) {
  case ACTION_A:
      do_action_a();
      goto common_post_action_cleanup;

  case ACTION_B:
      do_action_b();
    common_post_action_cleanup:
      cleanup_something();
      z = nullptr;
      x = x->next;
      // yadda yadda
      break;

   case ACTION_C:
      do_action_c();
      // NOTE: we don't need to do the "cleanup" here
      break;
   }

Another option is to just suck it up, repeat the code twice, and then just trust that the compiler will clean it up. First, that won't be as attractive if you have to do it 10 times instead of twice. Second, you're now violating the DRY principal which to me is sacrosanct. Experience has taught me that if someone updates the cleanup code for ACTION_A they will forget to update ACTION_B at the same time. If you care that the two cases always end with the same epilogue you need to have a single copy of the code.

You can try to get back into compliance with DRY by using something like a C macro, but now you're not winning the war against ugly code.

Finally you could just put the cleanup code after the switch(), either by retesting the enum value (requiring it to be stored in a temporary variable) or by adding some other new cleanup_needed boolean flag. But now we're adding control flow that wasn't there before. I personally believe that doesn't help readability or maintainability. You're now just adding more variables to understand and probably getting worse generated assembly to boot.

While many programmers will look at this and feel vaguely icky about the presence of a "goto" if you really stop and look at the block of code it's actually quite readable...at least as long as the label and the goto are near each other. It is immediately apparent that two "states" are sharing some code and why.

This little example is obviously made up. However I've spent a lot of my career writing things like hand-crafted state machines and situations exactly like this (where two "states" are different but share the same epilogue) comes up all the time. State machine code like this is famously hard to read but often sharing code via goto like this is the least-bad option for expressing non-hierarchical control flow.

For a rough estimation, you can use my bc at [1] which uses goto extensively for safe and effective use of setjmp() and longjmp(), while having no memory leaks (to my knowledge).

When going through the code, though, be aware that some goto's are in #define's to make it easier to work with setjmp().

If you're lazy, it's about 10k loc with about 100-200 uses of goto.

[1]: https://git.yzena.com/gavin/bc

The times I found I used the goto statements are retrials.

For example, if a file is locked for writing, I want to wait for 5, then 10, then 15 seconds, retrying each time, before giving up.

In such case I do not want the retrials loop to be my main control structure.

Instead, I jump from inside the IO exception catch block to the ReTry label, restarting the whole operation.

This makes the flow fairly clean.

https://github.com/codr7/ampl/blob/main/src/ampl/eval.cpp

Few programmers use goto, because they have been indoctrinated against it and they have no understanding about when goto is bad and when goto is good, but there are many cases where using goto is better (i.e. more clear and/or faster) than what most programmers write now in such occasions.

In some of those cases there are alternatives that could be better than goto, but they cannot be used because they need features that are missing from the programming languages popular now.

One example is state machines. Many programmers when having to implement a state machine use a state variable, e.g. an enumeration and a big "switch" or "case" structure, depending on the language, with a branch for each state.

This kind of implementation follows the method taught now to avoid goto's by adding unnecessary variables that are used to store some state when some condition is detected with the purpose to make a jump later with an extra if or switch instead of doing a jump with a goto immediately when the condition has been detected.

This method of eliminating goto's is pretty stupid, because it not only adds useless variables but it also doubles the number of conditional branches, because each

if (condition) goto label;

is replaced by:

if (condition) variable = value;

...

if (variable == value) {...} or switch (variable) {...}

Besides the accesses to non-cached memory, the conditional branches are the main causes of low performance, so doubling the number of conditional branches can result in much worse performance.

When the second conditional branch is a "switch", that is even worse, because it is typically implemented as an indexed jump, which will be frequently mispredicted.

Instead of using a state variable and a "switch" with branches for states, the right implementation is to have sequences of statements for the states, with the first statement in each sequence labeled with the name of the state.

During each state, when the condition for the transition to another state is detected, a goto is executed, with the name of the next state.

Anyone who believes that this is less clear or more difficult to read than the variant with state variables is delusional, because in the variant with goto's you see immediately the effect of a transition condition, while in the variant with state variables you just see some value being stored and you do not know its purpose until possibly much later when you discover that it is tested for a second conditional branch. Even after you see this use, you are not certain that this is the only place where the variable is used, it might also have other uses and you might need extra time until you are certain about what the program really does.

A more elegant solution for state machines is possible only in languages where tail call optimization is guaranteed.

In such languages each state may be implemented as a separate function and the goto's may be replaced with function invocations in final positions, which are transformed by the compiler into jumps.

While not so many programmers need to write state machines, there are much more frequent uses where goto is superior, e.g. for error management in cases where exceptions are inappropriate, but describing when, why and how would be long.

In general all the problems for which goto was considered harmful are not solved by eliminating goto but by restricting its behavior.

There was a series of research articles by various authors, published between 1970 and 1975, whose conclusion was that the right kind of goto should be allowed to make only forward jumps and that the labels must have a scope restricted to the block in which they are declared. Therefore a goto should be able only to exit from a block but not to enter a block.

An example of a programming language that had this restricted form of goto was the language Mesa, from Xerox.

In C however, it would not be possible to restrict goto only to forward jumps without simultaneously adding guaranteed tail call optimization.

state machines a la finite automata, which (for examples) are generated by compiler parser generators like yacc ?

I could refactor a self-contained 50 label goto graph into a network of tail recursing functions pretty quickly; as little as an hour, in the absence of nasty confounding factors.

If the goto graph implements a calculation with no side effects like I/O, my network will be all pure functions, too.

Completely beyond the reproach of any CS academic. :)

There is a mechanical way to do this.

1. We turn all of the function's local variables into function arguments. Each of our tail recursive functions will take these arguments.

2. Every labeled node becomes a function.

3. Every goto becomes a function call invoking the function that its target label was turned into, passing in each of its own argument to the corresponding parameter of that function. The function's return value is immediately returned.

4. Every variable assignment before a goto is turned into an argument expression in the function call which passes the new value to the corresponding argument. E.g. instead

     a++; d *= 2;
     goto foo;

     return foo(a + 1, b, c, d * 2, e, ...);

     int foo(int a, int b, int c, ..., int z)
     {
        return a + c;
     }

     int foo(int a, int c)
     {
        return a + c;
     }

You maybe the right person to ask… Aren’t function / functioncallers a form of goto?

That must have been so satisfying once it was done.

Sometimes a little bit of poison can make a great medicine.

Goes both ways though.

But there's a reason we come up with sanctioned, constrained concepts built atop more powerful lower-level ones. Constraints in code benefit maintainability, correctness, and sometimes even performance.

"Yeah to those still adamant about it, if you've ever used statically-typed code, you've used untyped assembly under the hood. I hope you can live with yourself, you monster :)"

You put a smiley so I suppose it's possible you know better, but this kind of shallow, thoughtless critique is just painful to read, especially when following such a well-presented, historically accurate description of the debate surrounding goto. This is especially true given that Dijkstra himself refutes your argument, such as it is, in the opening paragraph of his seminal paper.

> You've used a GOTO under the hood.

That it's under the hood is the point of using constrained control-flow control. It's significantly easier to reason about `if` and `while` and `for` than about `goto`. That is basically the same reason functional programming have more HoFs than `fold`. You can do everything with `fold` and that's a problem because it creates way more cognitive overhead for the reader, they can't know what the code is trying to achieve until they get all the details, nor is the compiler able to check anything.

Likewise goto.

What's even worse is that, at the machine language level, condition and unconditional jumps are all that there are; we've all been using GOTOs constantly without even knowing it. :)

The real hidden gotos are:

- state machines - early return of a function

a case statement is the one where the GOTO peeks out the most, imo.

I teach high school CS and have eventually come to the same insight, and found that novice programmers do indeed understand primitive BASIC much more easily than Python. Python seems simple to us, but there is so much abstraction even in its base-level syntax. I am gradually redeveloping my course materials to use BASIC (via replit.com) in the early stages.

Subtract and branch if negative is more or less that:

https://en.wikipedia.org/wiki/One-instruction_set_computer#S...

I would disagree with defer being better than goto. Some people prefer it, but I think in a lot of ways it makes your control flow harder to see than just a few cleanup blocks at the end plus goto.

One thing a C-like goto has over exceptions is that you can only jump around within a single lexical scope. That restriction is a big win for readability.

Exceptions use a dynamic scope to decide where to jump to, so, in the general case, it's a lot harder to understand how they will affect program behavior by simply reading the code. That's a major reason why using exceptions for non-exceptional control flow is widely considered to be evil.

> There is no need to use GOTO when a language has functions/procedures and exceptions.

There is no need for exceptions either. Everything can be done with error code.

Just because there are redundant mechanisms to achieve same result does not mean one of them must be abolished.

> There is no need to use GOTO when a language has functions/procedures and exceptions.

The usual example of when goto saves more trouble than it causes is breaking out of a nested loop early. You can avoid goto in that scenario with a sufficient number of flags, but flag-heavy code tends to be harder to read than a couple apposite gotos. Even better is Perl-style named blocks, though.

> There is no need to use GOTO when a language has functions/procedures and exceptions.

... and defer

Right. He was criticizing the version where one subroutine might jump into the middle of another subroutine.

That sort of thing can make safely modifying the second subroutine require knowing if any of its labels are used elsewhere in the program.

It is basically impossible to reason locally when developing like that, unless you first verify that the only uses are local. (Or have applied strict coding standards such that only labels specifically identified can be used as non-local goto targets, etc.)

That sort of thing was extremely normal in say early assembly programming where your code size was so restricted, you needed to reuse code whenever possible. And many early languages brought that sort of capability along with it.

I'd expect Dijkstra's feeling on C's goto would probably be like: Probably a good idea to avoid it when the other control structures work well, but barring silliness like trying to code a large program in a single function, using C's goto for cases not well handled by the other control structures is fine, since it is constrained to local use only.

Indeed, which is why C++ forbids (and the compiler checks) such jumps.

>also omitting the letter 'e'. Absolutely mindblowing talent.

Unreal! I'm going to have to go read a passage or few. Thanks for mentioning it.

Also Gadsby by Ernest Wright

Avoiding jmp in assembly is a sensible thing to do. jmp may stall the pipeline if the branch predictor is wrong. Better to use cmov when you can.

And if we're being silly, you only really need mov[1].

[1]: https://github.com/xoreaxeaxeax/movfuscator

I agree with you; and I keep a printed copy of the MISRA C document on my nightstand for serene reading before sleep (together with the JPL C rules). Yet this point 15.1 does not forbid at all to use goto, just to use goto in an unconstrained way. Thus it is more a warning than a rule.

In the same spirit, you can also enjoy Knuth's "structured programming with goto statements" for a clean programming style whose control flow is based on goto.

> For instance, MISRA C rule 15.1 that states that goto should not be used explains: "Unconstrained use of goto can lead to programs that are unstructured and extremely difficult to understand"

Sure, but constrained uses are fine, right? So why blanket-ban it?

Well, in C you very rarely need it, but in assembler (particularly the 8-bit Z80 and 6502 that I've written raft-loads of code for) you definitely do. Of course, something like a CALL is better, if you can manage it.

I kind-of agree with parent, but I would define it "subjective" instead of "arbitrary".

Isn't the key word in that statement "unconstrained"? Goto is a tool like any other that can be abused.

And jumps relative to cs or ip, which serve both. PIC idea is not related to goto.

Should've used setjmp/longjmp to do the same thing. Make it even harder to reason about.

> People who give blanket rules such as never to use `goto` clearly do not understand where this idea comes from or why it should not be used.

The idea comes from Dijkstra and he sure as hell did consider it a blanket rule: "I became convinced that the go to statement should be abolished from all 'higher level' programming languages (i.e. everything except, perhaps, machine code)."

On modern Intel/AMD and ARM CPUs, which have SHA-1 instructions, SHA-1 is very fast, faster than many apparently simpler hashes.

There are no other so fast hashes with an output of at least 128 bits that you can find in available libraries and use immediately in your code.

The only alternative that is faster and long enough is to use an 128-bit polynomial hash like Poly1305 or the one used inside AES-GCM. Such polynomial hashes are available in various cryptographic libraries, but they are not packaged in a way that would allow them to be used directly in a hashing application, so you might have to extract the code from the library and add an interface to it, to make it usable.

Another alternative that has appeared recently is BLAKE3. BLAKE3 can be much faster than SHA-1, but only when it is computed in parallel with a large number of cores. If you do not want your hashing task to entirely take over your computer, SHA-1 remains faster.

There are many applications that need long hashes to make negligible the likelihood of a collision, e.g. for file deduplication. For such applications using SHA-1 is by far the least effort choice and there is no disadvantage in using it.

I'm not going to contradict you. This was just one random example, based on the git/SHA-1 story. To stay in this example: If someone is claiming SHA-1 is faster for them, I'd expect to document what other algorithms they tested, what the numbers were, why better things were unavailable. A future maintainer can check if the decision still makes sense based on the comment. Hence the huge comment from the post above.

The problem is, I have a few examples that make a lot more sense, but they can't be published here. They depend on local corporate circumstances and pretty obscure knowledge, and would be undecipherable for the HN crowd.

This is where languages that permit nested functions come in handy. You can locally factor out new functions while preserving access to variables in the lexical scope without needing to pass them in as parameters or lift them into a higher level scope (object, class, global, file, etc.).

I tend to find that to be itself a code smell. But it happens. When it does, I like using local functions that just close over the same state.

This is much more confusing to me than just using a goto. From your example, it's not immediately clear at all to me if you're breaking out of outer, or if you're breaking TO outer. You can figure it out with this simple example, but it's way more confusing than it needs to be. And importantly: way more confusing than just using goto.

Given that break and continue are just gussied up gotos anyway, just put the label where you wanna go and goto it. I think it's one of the few perfectly valid uses goto.

Isn't it interesting that all of the examples in the original article can be replaced with a labeled break of arbitrary blocks? Even replacing the continue statement. Solving the problems of goto and keeping the behaviour. Not sure why more languages don't have this

I don't see how that is better. Every one of your "state = N" assignment is just a goto in disguise, which requires the machinery to go back to the top and then jump somewhere again.

Someone looking at "state = 1" has to understand that state is a variable which controls the outer switch, and that 1 is refers to "case 1:" of that outer switch.

You have a proliferation of "case 1:" repetitions, so the reader has to follow the indentation carefully.

The goto is not a simple goto, either. When we assign "state = 1" it doesn't just mean to branch to the "case 1" node, but to go through the "key = getkey()" initialization.

The whole thing is less efficient than goto.

Specifically to C, you have more lines of code now. You remembered your break statements in the outer switch, but in the inner switches, you carelessly changed the gotos to assignments without adding the required break statements, so you have a bug in every inner switch. When you fix those, you will have some seven more lines of code.

Note how my original code has no variables at all, and neither does the transliteration into tail calls. You have two variables: key and state, plus you still have the same underlying goto graph structure.

The only saving grace of this arrangement is that it factors out the common action of calling getkey() into one place which is only important if we can't turn that common action into a tiny function call with just two or three arguments.

The property in my graph that getkey() is called in multiple places is a key property; it helps to farm off each block directly into a corresponding tail calling function in the mechanical transformation to the tail call graph.

I used to write all state machines this way, with labeled states, and a loop around a switch and input processing in one place at the top.

Quite recently, I did some ad hoc comaparative studies which convinced me I won't be doing that any more; I will be using disciplined goto graphs.

longjmp() is the C-language version of going-to labels in other functions.

Its basic "use" is not having to unwind the stack; but moreover, it lets you avoid cleanup and resource de-allocation. Usually it doesn't make sense to do that (you get memory leaks), but if, say, your memory allocations happen in some kind of arena - you can just leave it in any junk state and then proceed to clear it altogether after your setjmp() instruction.