7 ms·

Use of Goto in Systems Code

49 points by adunk 14y ago

bigfrakkinghero 14y ago
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.
- bodyfour 14y ago
  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.
  - praptak 14y ago
    > 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.
    - bodyfour 14y ago
      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.
jacques_chester 14y ago
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_To_Considered_Harmful.html http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...
- ygra 14y ago
  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.
  - jacques_chester 14y ago
    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.
justincormack 14y ago
Lua 5.2 introduced goto, which was interesting, see http://www.inf.puc-rio.br/~roberto/talks/novelties-5.2.pdf http://www.inf.puc-rio.br/~roberto/talks/novelties-5.2.pdf for some explanations as to why.
praptak 14y ago
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.
- huhtenberg 14y ago
  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().
  - reycharles 14y ago
    Java has exactly this. It's called "labelled continue". again: for(...) { ... continue again; .... }
patrickg 14y ago
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 http://abel.math.umu.se/~lars/misc/tex.pdf) is very readable.
primitur 14y ago
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 ..)
- jstanley 14y ago
  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.
  - primitur 14y ago
    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..)
drostie 14y ago
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.
- jacques_chester 14y ago
  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.
- rwmj 14y ago
  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 http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html
- twoodfin 14y ago
  RAII style in C++ handles this kind of resource cleanup well, and it's the main feature I miss when programming in C.
- Garoof 14y ago
  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.
arocks 14y ago
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!"
zvrba 14y ago
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.6084 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103....
- bcoates 14y ago
  Hah, his example 1 looks like a motivating example for Python's for-else.
wglb 14y ago
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.
kvinnako 14y ago
couldn't you just say: if(allocate_memory() != SUCCESS) { free_memory(); return error; } ... The other examples provided make a better use case of GOTO.
- sophacles 14y ago
  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.
- askimto 14y ago
  Generally with that approach you can end up with a lot of duplicate code. It is more error prone.

49 points by adunk 14y ago

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.

bodyfour 14y ago
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.
- praptak 14y ago
  > 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.
  - bodyfour 14y ago
    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.

jacques_chester 14y ago

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_To_Considered_Harmful.html http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T...

ygra 14y ago
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.
- jacques_chester 14y ago
  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.

justincormack 14y ago

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

praptak 14y ago

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.

huhtenberg 14y ago
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().
- reycharles 14y ago
  Java has exactly this. It's called "labelled continue". again: for(...) { ... continue again; .... }

patrickg 14y ago

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 http://abel.math.umu.se/~lars/misc/tex.pdf) is very readable.

primitur 14y ago

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 ..)

jstanley 14y ago
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.
- primitur 14y ago
  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..)

drostie 14y ago

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.

jacques_chester 14y ago
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.
rwmj 14y ago
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 http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html
twoodfin 14y ago
RAII style in C++ handles this kind of resource cleanup well, and it's the main feature I miss when programming in C.
Garoof 14y ago
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.

arocks 14y ago

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!"

zvrba 14y ago

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.6084 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103....

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

wglb 14y ago

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.

kvinnako 14y ago

couldn't you just say: if(allocate_memory() != SUCCESS) { free_memory(); return error; } ... The other examples provided make a better use case of GOTO.

sophacles 14y ago
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.
askimto 14y ago
Generally with that approach you can end up with a lot of duplicate code. It is more error prone.