Use of Goto in Systems Code | Hacker News Reader

Use of Goto in Systems Code

blog.regehr.org

49 pointsadunk55 comments

The page linked has a good rule of thumb for the gotos: don't use backward ones. All the "escape" uses of goto - breaking out of loops, jumping to the appropriate part of the cleanup code, emulating exceptions behavior are forward jumps.

Back in the day hand coded assembly had jumps into the middle of functions' bodies which was a space-saving idiom for things like default initialization - the beginning of the function had some initialization code but you could jump into the function body (and skip this initialization block), provided that you did your own init and set the proper registers yourself.

There is however one valid case for using backward gotos - it's the loop restart.

  again:
     for ( ..container.. )
     {
         ...
         if ( ... )
         {
             touch(container);

             /*
              *   If touch() changes container in a contrived
              *   way, then restarting the loop is sometimes 
              *   the cleanest option.
              */
             goto again;
         }
     }

This obviously requires caution to not enter an infinite loop, but that's usually easier to guarantee than to reconcile the consequences of touch().

Java has exactly this. It's called "labelled continue".

    again:
    for(...) {
       ...
       continue again;
       ....
     }

What almost all modern programmers, fortunately, are not exposed to are the goto-infested programs common during the time preceding this technical note. For one example, Fortran II was quite common at the time. IF statements were made up of a numerical test, and three branches: less, equal, greater. This made even simple programs quite difficult to understand.

Dijkstra, as noted in another comment by 'arocks, was a little alarmed at some taking the principle to the extreme. I am afraid that I was one of them for a while.

But the structured programming movement that followed and resulted in a great improvement in readability and in program reliability.

It still seems like there would be an opportunity for a smarter language here. Like, the reason that `goto` appears here is because the language does not know how to clean up the mess that it's making, thus the code requires humans to jump back and forth between the top and bottom making sure that each cleanup section properly cleans up the corresponding mess above. This is true of both the `if` and `goto` code; and we could do this much more easily if those pieces of code were side-by-side.

You might be interested in looking at the Common Lisp "Conditions" system, which allows code outside of the stack to provide error-handling logic.

In general, though, I think it's more about presentation than the language per se. I've often felt that an IDE or editor that could selectively highlight or hide the different pathways through the code would be a very useful tool.

GCC and LLVM offer a "cleanup in this scope" attribute, so you can write:

    __attribute__((cleanup(free_indirect))) char *foo = strdup ("bar");

where free_indirect is a simple wrapper around free. It's used in the systemd code (making it GCC/LLVM-specific of course).

http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html

RAII style in C++ handles this kind of resource cleanup well, and it's the main feature I miss when programming in C.

So, on a "some other language does like so" note, in D you might write it kind of like this:

    allocate_memory();
    scope(failure) free_memory();
    setup_interrupts();
    scope(failure) teardown_interrupts();
    setup_registers();

The scope keyword is for saying that if you get to this point, then do such and such at end of scope. scope(failure)/scope(success)/scope(exit), for exitting scope by exception/return/either. Is kind of nice.

Dijkstra himself later clarified: "Please don't fall into the trap of believing that I am terribly dogmatical about [the go to statement]. I have the uncomfortable feeling that others are making a religion out of it, as if the conceptual problems of programming could be solved by a single trick, by a simple form of coding discipline!"

One thing about replacing goto with if's: CODE COVERAGE, specifically: BRANCH COVERAGE.

In situations where you have to prove 100% testing of all code, with full branch coverage and absolutely no dead code, the goto is preferred. This is simply because it is a faster instruction that does not depend on any other values being "valid" in order to function.

Why is that important? Bit-rot, folks. Like it or not, but we still have to ensure that the bit that is 1 is a 1 and not a 0, in this day and age - especially for safety-critical/life-dependent systems. The goto gives both full coverage capabilities (good for testing/certification) as well as providing one less path for radiation to be rotting bits.

(And before we get into the NAND/ECC discussion, remember: this is for software certification requirements.. it doesn't matter how hard your hardware is, what matters is how hard your software is ..)

Firstly, I really don't follow your argument about code coverage. If you need to ensure that some unit of code is executed, why can't you make it a function and call it?

Secondly, you have misunderstood what bit-rot is. Bit-rot is not cosmic rays flipping bits, it is a humorous term to describe what happens when code that used to work and has not been touched no longer works.

EDIT: It seems Wikipedia disagrees with me on the second point. My apologies.

Just FYI, I've been working in the safety-critical industry for decades. If I've misunderstood bit-rot, by now some of my colleagues would have .. corrected .. me. ;)

Code Coverage means that you have demonstrated, beyond a doubt, that every single path in your code has been tested as functional and per-spec.

An if statement requires (minimally) two things to happen (sometimes three, depending on the compiler/architecture): a compare of some values, then a branch. A goto requires one thing: jump.

This then, reduces the cyclomatic complexity of your code path, and for coverage purposes is ideal because you're testing a simple jump, not a load, compare, branch. The use of if, in the example given, makes the testing complexity a lot higher - what if the if is broken somehow? (bit-rot: it still happens) In safety-critical, you have to test for that case, or else you don't get full coverage...

(edit: s/cycolmetric/cyclomatic/ .. its a european thing..)

Question: are you talking about code written in assembly language, or are we talking about higher level languages?

I'm talking about C code. For every if-branch, a test must be written to exercise the extreme case - the if failing, for some reason (bit-rot, radiation or heat or hardware-failure derived).

In SIL4, its not enough to say:

    if (SAFE == something) {}; //dosomething..

.. and then just test the SAFE condition. You also have to test the condition where the constant SAFE gets bitrot, where the var something gets bitrot, &etc. Adding a test case for every potential bit-rotted branch of the conditional.

So you prefer gotos to reduce the number of tests you have to write by artificially pushing down the number of countable code paths?

I guess I see the reason. It seems to be connected to your development economics -- SLOCS required to reach a certified state.

I'm glad that works for you. It still scares me.

As someone who has also done safety-critical software for a while allow me to interject this, your wrong.

That is by far one of the _worse_ excuses for goto's I have ever seen. If anything they make full branch analysis more difficult then using conditionals. I have never sat down at a gap analysis and had someone say I don't know if this branch is tested because it uses an if statement instead of a naked goto. I have had people say does control ever get to this point since its at a label and we need to trace the code to find where the goto for the label is and then check the conditions for reaching the goto then check the validity of those conditionals at some non syntax designated point in the code.

Also bit rot as you describe it is not a common occurrence and is something almost no one has to deal with. In fact most safety critical systems I deal with are designed to be replaced before we would ever need to worry about that. The more common use of bit rot is the second definition given in this[0] wikipedia article. Unused code which goto's can be a real headache for.

0. http://en.wikipedia.org/wiki/Bit_rot

You've misunderstood my point in order to make your argument, I think. I didn't say that someone won't "know if this branch is tested because it uses an if" - obviously, they won't get certification if they don't know.

But the point is, they will have to write MORE tests to prove this knowledge. In other words, BREAK the conditions of the if statement in order to test - so simulate a full bitrot scenario on the conditional-branch. We've actually had to write tests to do this, but then been able to rewrite the code to use goto, effectively and without any of the disadvantages you mention - in fact, reducing the cyclomatic complexity of the entire system. This is a good thing.

Bit rot, not common? Well, if you're really safety-critical trained, you would simply never say that, in my opinion.

FYI, my software is running the trains in 38 countries around the world, track-side in thousands of locations. Replace the hardware? Forget it: that hardware will be there, in torturous environments, for years upon years and therefore: must be SIL4 rated. There is no exchange of hardware after a crash.

All hardware gets replaced. If your not establishing a planned maintenance schedule for your hardware then your asking for failures. That's why companies give MTBF. The PLC's I have worked with have shelf life's of 30+ years , but we still have planned maintenance periods where we examine and replace and worn components and we have a tech refresh period designed to prevent anything from ever reaching a point of failure.

In addition every type of media I know of to store computer programs will physically degrade before suffering "bit rot". Most of the industrial controllers I have used ( everything aside from the most basic of uControllers ) have refresh cycles for their programs preventing this supposed bit rot by refreshing the signal on the media on a very regular basis.

FYI trains stations aren't torturous at all. I have put stuff on weather decks of naval warships now thats torturous.

Regardless of whether an if statement or a goto is better, why is a goto preferable to a function call?

1) putting pure cleanup code into different functions is unwieldy. It doesn't make code readability, thus maintainability, better in any way, so why use it?

2) speed. sometimes, when it comes to optimizing hot loops, there is a point where one needs to manually inline code, in order to avoid potentially unnecessary scope cleanups. Ever looked at assembler? Seen how many instructions a typical function call causes?

Of course, (1) is usually only relevant in systems programming and (2) is only relevant in HPC, where going that extra mile can actually save more than a few 100k$. Nothing the average programmer needs to worry about - however that's also one huge problem of that field: Lack of people with said know how.

I accept both of those points. I was asking in the context of safety-critical systems. I see no advantages of goto over a function call.

A function call necessitates setting up the stack for the call, and returning from the call by popping values of the stack. To get 100% coverage, you'll have to test the call, test the broken call, test the stack being corrupted, and so on. This adds to the cyclomatic complexity of the TESTING required to certify that your software doesn't have/take any unknown paths during its lifetime while installed in highly hostile environments (heat, radiation, water, desert conditions, Antarctica, etc.)

I would prefer to rely on languages which can provably ensure all cases are handled than to rely on gotos to artificially improve a complexity metric. Really.

Congratulations. You've just disqualified yourself from working on SIL-4 safety-critical software. There are no such languages that can provably ensure all cases are handled: there are only testing processes.

Aversion to a technology is not the same as mastery of that technology. goto has its time, and place. Certifiably, so.

I'm pretty sure we're on different pages here. Some languages can detect that there are unhandled cases in a selection statement (case, if etc). Those languages can enforce the handling of all cases, which to me at least renders the concept of a dangling case moot.

I didn't say that you'd leave the cases untested. I'm just saying that in some languages the compiler is more of an ally than in others.

I'll write to Galois and Praxis to tell them that they're disqualified from writing SIL-4 software.

There certainly are languages that can provably ensure all cases are handled.

Have a look at ATS.

Structured programming with goto statements by Knuth is a nice paper on the topic.

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

Hah, his example 1 looks like a motivating example for Python's for-else.

I found it enlightening to learn about the context in which the GOTO was first "considered harmful" by Dijkstra in 1968[1].

This is a period of time when the concept of higher level languages with specialist if-then, loops and return statements were still relatively new.

Most programmers in the world had cut their teeth on assembly language. In that model the natural way to think of programs is as a sequential series of addresses in memory that contain instructions.

Since all control structures are merely jumps to a new address, so why were all those grumpy ivory tower idiots so keen on abolishing goto?

Probably the biggest blow to the pro-goto camp in those days was the discovery of the "Structured Program Theorem" in 1966. It was proved that any computable algorithm can expressed in any higher level language that has sequencing of instructions, ability to select an execution path and iteration. The ability to jump is not required. For the times it was an critical discovery because it meant higher level language designers could proceed with the confidence that any HLL they designed with those three properties would be usable for any algorithm in theory.

Finally, Dijkstra (and the other European greats like Hoare and Wirth) had in mind a particular vision of what programming ought to be. He didn't see it so much as an engineering activity. He wanted to treat programs as mathematical objects. Controlling the scope of languages can make this more or less tractable. So for example the "one return from a function" rule goes back to this vision, but has since gone on to live a care-free life of its own.

[1] http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...

I think Hoare said it in a talk I once heard, that control structures essentially give a higher-level meaning to the ordinary GOTO. In that sense I always understood the “considered harmful” paper as advice to replace GOTO by appropriate control structures where applicable.

Right. That was part of the confusion, because as I said above, lots of programmers of the day didn't see the point in inventing a bunch of special cases when a simple general case existed.

It's also important to realize that the "go to" Dijkstra is complaining about isn't seen in modern languages. It's the goto of unstructured Basic and early Fortran where you're doing an unconstrained jump to some other part of the program source by line number. It has no real counterpart in C. Unless your entire program is one long main() function, forward and even backwards C goto within a function is a tamed HLL version that can be reasoned about.

It is possible to reason about the effects of a goto into the middle of a for loop (or switch case), of course, but doing so is likely to make you angry. :)

I believe those are reason enough to avoid doing those particular things, even if the global jumping of assembly of course is even worse.

Of course, this is the part where someone mentions Duff's Device, which uses a do..while spanning multiple switch labels. This is possible because switch works a lot like goto.

http://en.wikipedia.org/wiki/Duffs_device

I agree in the general case but there are many cases where a goto statement is actually more readable than the alternatives in C. Especially if you choose descriptive labels.

Labelled goto statements were around as early as ALGOL-60.

However, an unconstrained goto in C can be realized via the setjmp() longjump() library functions.

Interesting insight, thanks. The way that "goto considered harmful" has been taken out of context and then gone viral reminds me of how Simonyi's original Hungarian prefix scheme was similarly misunderstood and then misapplied, to the detriment of many C and C++ codebases.

A good discussion of what tragomaskhalos is talking about here: http://www.joelonsoftware.com/articles/Wrong.html

I found it enlightening at why GOTO is considered harmful by programming in BASIC as a kid.

Oh-oh spaghetti-oh!

Not that you should waste your time programming in a GOTO dependant language, but it becomes pretty obvious after a couple of days why GOTO sucks.

The opening article is pretty vacuous imo. That's not really a legitimate use, it's just that C++ doesn't support finally.

The language is C, not C++, and it is in no way GOTO dependant.

The examples given are ones of considered and deliberate use of GOTO by choice in a systems programming context.

John Regehr knows his stuff and generally expects the same of his readers. Given his background as a harsh but fair critic of the ragged edges of the C Language standard the part of interest here is that he lets these examples go under the umbrella of "fine by me"

That you found the article vacuous in your opinion is no surprise, at a guess I'd ascribe that to general ignorance on your part as born out by the comment you made. Never mind, you can rectify that with a bit of applied effort.

I'm sorry, perhaps you can share what profound take away you gained from this article which boils down to 'my language doesn't have feature x. So shitty feature y is really meaningful'?

Perhaps you could write an article about the usefulness of Option Explicit in vbscript to really underline the take away here.

I'd love to see you defend the claim that [goto] has a number of legitimate uses in well-structured code including an idiom seen in systems code

Defend that odd statement and you might have a claim on the superiority you're fatuously exuding.

Personally I haven't seen a goto in live code apart from C for about 8 years. But perhaps I'm too durr hurr stupid to notice in the hundreds of different programs I've read.

> this article which boils down to 'my language doesn't have feature x. So shitty feature y is really meaningful'?

Actually that's not what this article is about at all, it's a small part of a much larger arc about C, C semantics, and LLVM. As I pointed out, you're ignorant of this.

> Perhaps you could write an article about the usefulness of Option Explicit in vbscript to really underline the take away here.

Irrelevant and unconnected.

> I'd love to see you defend the claim that [goto] has a number of legitimate uses in well-structured code including an idiom seen in systems code

No need, it's an argument that's been covered already, probably before you were born. As others have pointed out even Dijkstra conceded it's (appropriate) usefulness, he simply wished to promote structured code and the (at the time) endemic bad use of GOTO.

> a claim on the superiority you're fatuously exuding.

Just experience, and seemingly more than yours.

> But perhaps I'm too durr hurr stupid to notice in the hundreds of different programs I've read.

While I originally inferred ignorance and not stupidity on your part I concede that you are making a strong case for the latter.

> probably before you were born.

"Goto Considered Harmful" was published by the ACM in 1968.

I'd love to see accurate numbers for ages of HN reader and HN posters.

Just make a post about BBC micros, VIC-20's, tape drives, punch cards, Commodore-64's, PDP-11's et al and watch the old farts crawl out of the woodwork ... :)

I started out with a breadboard jury rigged Commodore PET and progressed to optimising symbolic math routines for group theory calculations on a Cyber-205 .. it got better after that.

The GOTO debate raged hot until at least the early 80's and seems to have remained on simmer ever since.

If (for whatever reason) you have to write code with support for exception handling compiled out, goto statements are incredibly useful. While not quite as syntactically nice as a try/catch/finally paradigm, the combined use of error checking macros and a "cleanup" label can rather elegantly emulate the control flow of exception handling where appropriate.

They're really a closer cousin to the RAII pattern common in C++ than exceptions. Exceptions usually imply action across functions, but here they're just trying to enforce end-of-scope invariants. So if you're writing C++ code with "exception handling compiled out" (such as with Embedded C++, if anyone still uses that) you can still leverage RAII to do a lot of that type of cleanup.

That said, "goto" gets a bad rap in my opinion. Anyone can parrot Dijkstra's "considered harmful" line, but few know the context that it came from. If you've seen large FORTRAN programs from that era, where "GO TO" was the main control flow choice and labels had to be integers you know how even simple algorithms could be made unreadable. Effectively Dijkstra was extolling ALGOL programers not to code as if they were writing FORTRTAN -- in a structured language "goto" is the control structure you need to use least.

Still, there are places where "goto" is the cleanest way to accomplish what you want to do, and you shouldn't fear using it. (Please pick a good name for the label though!) I've seen programmers write crazy twisty code with all sorts of strange temporary variables simply to avoid the use of the forbidden "goto" keyword. Clarity should be your aim, not religious purity.

Also remember that "break;" (except at the end of a switch case) "continue;" and even early "return;" are morally equivalent to the dreaded "goto;" when you think about it. They don't get the same bad press for some reason.

> Also remember that "break;" (except at the end of a switch case) "continue;" and even early "return;" are morally equivalent to the dreaded "goto;" when you think about it.

To a degree - they can't go backwards and what's more important they can't jump into the middle of other control structures. The second case was what's really made it hard to reason about code with gotos.

OK, I'll give you that. A goto into with a tricky destination is a particularly bad case, worse than most uses of "break;" I was just trying to point out that they're all violations of the LISPy ideal where all control flow forms a hierarchy.

OTOH, with nested loops its easy to misinterpret where a "break;" or "continue;" will actually go. This is something that's bitten me many times over the years, especially when reading code with poor or inconsistent indentation. At least a goto is visually unambiguous and maybe even has a helpfully descriptive label.

Also: "continue;" goes 'backwards' for a "while" or "for" loop but "forwards" in a do-while. It's probably the most confusing of the bunch.

Lua 5.2 introduced goto, which was interesting, see http://www.inf.puc-rio.br/~roberto/talks/novelties-5.2.pdf for some explanations as to why.

TeX is more or less one big pascal function with lots of gotos. While this makes it very hard to port to a more modular (and non-pascal) system, the source code (in typeset format: http://abel.math.umu.se/~lars/misc/tex.pdf) is very readable.

couldn't you just say:

if(allocate_memory() != SUCCESS) { free_memory(); return error; } ...

The other examples provided make a better use case of GOTO.

Well, for starters the semantics of allocate_memory are (in general) such that a SUCCESS == false condition mean that no memory was allocated. So freeing the memory would be an error itself. This is me being a bit pedantic, but it is important to note that the error condition for resource allocation is generally "there is nothing from this step to deallocate". This can turn into an "off by one" error in cleanup if you aren't careful.

Second, say your allocate_memory is successful... your next n steps look like:

   if (allocate_memory() != OK) { return error;}
   if (allocate_resource1() !=OK { free_mem(); return error;}
   if (allocate_resource2() !=OK { free_r1(); free_mem();}
   ....
   if (allocate_resourceN() !=OK { free_N-1();...;free_r2(); free_r1(); free_mem(); return error;}
   // .... CODE
   free_N();
   free_N-1();
   ...
   free_r2();
   free_r1();
   free_mem();
   return success;

There are two things to note here. First of all, the if lines get very long when you have to do all that unwinding at the loop. This is ugly and annoying, but itself not a problem. Second, and this is a code smell, you've gone and seriously repeated yourself. Now every time you add a resource allocation, you have to update the unwinding in several places. There is more room for error, more chance of subtle issues in order creeping in. etc. This pattern is a way to avoid it.

The author addresses doing the whole chain in nested ifs in the original article.

Generally with that approach you can end up with a lot of duplicate code. It is more error prone.

Reply on news.ycombinator.com