4 ms·

The problem with goto is that it is an unbelievably primitive operator. It can be used to implement any logic at all, and therefore it does not express any logi

The problem with goto is that it is an unbelievably primitive operator. It can be used to implement any logic at all, and therefore it does not express any logic very clearly. It's a bad way to express intent in code. Aside from the exceptions discussed in the article, there is always a better, clearer way to express logic than to use goto statements. The same is true of while loops. Aside from a few cases where they are required, they are always better rewritten with a less primitive operator (for, etc). The arguments that programmers today make in defense of while are quite similar to the arguments programmers used to make in defense of goto.

kazinator 4y ago
This is false. Tail recursion is clearer and easier to reason about than loops, and tail recursion can be rewritten into gotos. I mean rewritten in a direct way, where the shape of the logic is the same. E.g. even an odd problem. Let's use GNU C with local functions: #include <stdbool.h> bool even(int x) { auto bool odd(int x); bool even(int x) { if (x == 0) return true; else return odd(x - 1); } bool odd(int x) { if (x == 0) return false; else return even(x - 1); } return even(x); } Using goto: achieved by a mechanical transformation involving just some local edits: bool even(int x) { goto start; even: { if (x == 0) return true; else { x = x - 1; goto odd; } } odd: { if (x == 0) return false; else { x = x - 1; goto even; } } start: goto even; } Every tail-called local function just becomes a block headed by a goto label. The tail call is replaced by assigning a new value to every argument variable and performing a goto. Someone who is briefed on the approach here can easily see the original tail recursion and maintain the code in such a way that the tail recursion could always be recovered from it. There was a discussion several years ago in comp.lang.c where a problem was proposed: using whatever approach you see fit, write a C program which strips comments from C code, but preserves everything, including preprocesor directives. Something like that. The person who proposed the problem refrained from posting his solution for several days. He used tail recursion for the entire state machine of the thing (even avoiding if statements; all the cases in the tail functions were handled by the ternary ?: operator). Others used structured programming: nested loops and such. My solution used goto. I argued that the goto solution had all the good properties of the superior tail calling solution. I then supported my argument by writing a text filter which converted that person's tail call program into one with a big function containing goto blocks (compiling and producing the same result and all). A reverse filter would be possible also. I believe that we can take any mess of a goto graph, divide it into the labeled nodes, round up the variable and everything being done to them and express it as tail recursion. Ironically, the one thing that will make it a bit harder is structured control flow constructs like while, for, switch and what not, where we may have to rewrite those to explicit goto first! E.g. if we look at a while loop, it's like a tail call, but one which is invisible. The end of the while loop body invisibly tail calls to the start, which is bad for understanding. The thing that will detract from the ability to understand the tail call graph is excessive parameters. In the worst case, every tail function will have to take all of the state variablews as parameters, and pass them all to the next tail function (except for altering some of them). There is a pass that can be done over that to reduce some of these. Like if some tail function foo(a, b, c, d, e, f) doesn't do anything wiht c d e f other than pass it to children and none of those children do anything with those variables (transitively), we can cull those parameters from foo and all the children. This is the hard thing to understand in goto graphs: which of the numerous state variables are relevant to where the goto is going? Some state vars can be replicated and localized. E.g. in our even() example, we can do this: bool even(int x) { // params of even: int x0; // params of odd int x1; goto start; even: { if (x0 == 0) return true; else { x1 = x0 - 1; goto odd; } } odd: { if (x1 == 0) return false; else { x0 = x1 - 1; goto even; } } start: { x0 = x; goto even; } } Now we no longer have the same variable on both sides of an assignment. Each block works with its private parameter variable. The other block only every assigns to that variable when simulating parameter passing: e.g. the odd block assigns to even's x0 just before goto even. We can start with a goto graph and make incremental improvements like this and recover a tail call graph. We can then try to understand what the tail functions mean in terms of recursion and document that.
- preseinger 4y ago
  > Tail recursion is clearer and easier to reason about than loops tail recursion is a complex and subtle expression of control flow that requires substantial background knowledge to be able to even understand, much less reason about based on code on a page for loops are immediately intuitive to anyone, even without any programming training no idea how you can come to this conclusion. just ain't so
  - kazinator 4y ago
    > tail recursion is a complex and subtle expression of control flow That is simply nonsense; it's just function application, ideally without having to think about state (or as little state as possible). > for loops are immediately intuitive to anyone, for loops are immediately intuitive to anyone That's just hand-waving without some sort of psychological data. Even if it were true, it would not be relevant because you can't just hand over software maintenance to just "anyone" pulled off the street who finds some language feature intuitive. (In my anecdotal experience, on the contrary, non-programmers have a very poor intuition for the idea of changing variables by assignment and what that means when a backwards jump takes place.) A solution expressed recursively is demonstrably, quantifiably easier to reason about informally or prove correct than loops and state variables. Of course, not to "anyone" with no programming background just pulled off the street, but to people who have the understanding and skills. There is simply less proof material. An entire body of proof techniques that are required with imperative loops are absent. You just use straightforward inductive reasoning instead of pre and post conditions over stateful variables, and loop invariants and whatnot. Anyway the idea that for loops are somehow easier than recursion is definitely not from mainstream CS; just some fringe view fr
    - l33t233372 4y ago
      > the idea that for loops are somehow easier than recursion is definitely not from mainstream CS I have never in my life heard a programmer say they think recursion is easier than loops.
      - 4y ago
erik_seaberg 4y ago
This has been called the https://en.wikipedia.org/wiki/Rule_of_least_power https://en.wikipedia.org/wiki/Rule_of_least_power, and it’s a good way to make legible what you’re doing and especially to exclude what you aren’t doing.
- edflsafoiewq 4y ago
  The problem with this is it requires introducing a vast zoo of features distributed across the spectrum of power, and it is not at clear that it is actually easier to learn this whole zoo so you can select precisely the least powerful point on it, than it is to understand the use of a single (or small number of) all-powerful constructs within its context.
  - erik_seaberg 4y ago
    My goal is “most reliable and concise for experts,” because we should spend most of our careers as experts, and “easy to learn” requires bad tradeoffs too often. Learning common names and reusing tested implementations pays off over rolling my own on the spot and forcing everyone else to re-read it.

kazinator 4y ago

This is false. Tail recursion is clearer and easier to reason about than loops, and tail recursion can be rewritten into gotos. I mean rewritten in a direct way, where the shape of the logic is the same. E.g. even an odd problem. Let's use GNU C with local functions: #include <stdbool.h> bool even(int x) { auto bool odd(int x); bool even(int x) { if (x == 0) return true; else return odd(x - 1); } bool odd(int x) { if (x == 0) return false; else return even(x - 1); } return even(x); } Using goto: achieved by a mechanical transformation involving just some local edits: bool even(int x) { goto start; even: { if (x == 0) return true; else { x = x - 1; goto odd; } } odd: { if (x == 0) return false; else { x = x - 1; goto even; } } start: goto even; } Every tail-called local function just becomes a block headed by a goto label. The tail call is replaced by assigning a new value to every argument variable and performing a goto. Someone who is briefed on the approach here can easily see the original tail recursion and maintain the code in such a way that the tail recursion could always be recovered from it. There was a discussion several years ago in comp.lang.c where a problem was proposed: using whatever approach you see fit, write a C program which strips comments from C code, but preserves everything, including preprocesor directives. Something like that. The person who proposed the problem refrained from posting his solution for several days. He used tail recursion for the entire state machine of the thing (even avoiding if statements; all the cases in the tail functions were handled by the ternary ?: operator). Others used structured programming: nested loops and such. My solution used goto. I argued that the goto solution had all the good properties of the superior tail calling solution. I then supported my argument by writing a text filter which converted that person's tail call program into one with a big function containing goto blocks (compiling and producing the same result and all). A reverse filter would be possible also. I believe that we can take any mess of a goto graph, divide it into the labeled nodes, round up the variable and everything being done to them and express it as tail recursion. Ironically, the one thing that will make it a bit harder is structured control flow constructs like while, for, switch and what not, where we may have to rewrite those to explicit goto first! E.g. if we look at a while loop, it's like a tail call, but one which is invisible. The end of the while loop body invisibly tail calls to the start, which is bad for understanding. The thing that will detract from the ability to understand the tail call graph is excessive parameters. In the worst case, every tail function will have to take all of the state variablews as parameters, and pass them all to the next tail function (except for altering some of them). There is a pass that can be done over that to reduce some of these. Like if some tail function foo(a, b, c, d, e, f) doesn't do anything wiht c d e f other than pass it to children and none of those children do anything with those variables (transitively), we can cull those parameters from foo and all the children. This is the hard thing to understand in goto graphs: which of the numerous state variables are relevant to where the goto is going? Some state vars can be replicated and localized. E.g. in our even() example, we can do this: bool even(int x) { // params of even: int x0; // params of odd int x1; goto start; even: { if (x0 == 0) return true; else { x1 = x0 - 1; goto odd; } } odd: { if (x1 == 0) return false; else { x0 = x1 - 1; goto even; } } start: { x0 = x; goto even; } } Now we no longer have the same variable on both sides of an assignment. Each block works with its private parameter variable. The other block only every assigns to that variable when simulating parameter passing: e.g. the odd block assigns to even's x0 just before goto even. We can start with a goto graph and make incremental improvements like this and recover a tail call graph. We can then try to understand what the tail functions mean in terms of recursion and document that.

preseinger 4y ago
> Tail recursion is clearer and easier to reason about than loops tail recursion is a complex and subtle expression of control flow that requires substantial background knowledge to be able to even understand, much less reason about based on code on a page for loops are immediately intuitive to anyone, even without any programming training no idea how you can come to this conclusion. just ain't so
- kazinator 4y ago
  > tail recursion is a complex and subtle expression of control flow That is simply nonsense; it's just function application, ideally without having to think about state (or as little state as possible). > for loops are immediately intuitive to anyone, for loops are immediately intuitive to anyone That's just hand-waving without some sort of psychological data. Even if it were true, it would not be relevant because you can't just hand over software maintenance to just "anyone" pulled off the street who finds some language feature intuitive. (In my anecdotal experience, on the contrary, non-programmers have a very poor intuition for the idea of changing variables by assignment and what that means when a backwards jump takes place.) A solution expressed recursively is demonstrably, quantifiably easier to reason about informally or prove correct than loops and state variables. Of course, not to "anyone" with no programming background just pulled off the street, but to people who have the understanding and skills. There is simply less proof material. An entire body of proof techniques that are required with imperative loops are absent. You just use straightforward inductive reasoning instead of pre and post conditions over stateful variables, and loop invariants and whatnot. Anyway the idea that for loops are somehow easier than recursion is definitely not from mainstream CS; just some fringe view fr
  - l33t233372 4y ago
    > the idea that for loops are somehow easier than recursion is definitely not from mainstream CS I have never in my life heard a programmer say they think recursion is easier than loops.
    - 4y ago

erik_seaberg 4y ago

This has been called the https://en.wikipedia.org/wiki/Rule_of_least_power https://en.wikipedia.org/wiki/Rule_of_least_power, and it’s a good way to make legible what you’re doing and especially to exclude what you aren’t doing.

edflsafoiewq 4y ago
The problem with this is it requires introducing a vast zoo of features distributed across the spectrum of power, and it is not at clear that it is actually easier to learn this whole zoo so you can select precisely the least powerful point on it, than it is to understand the use of a single (or small number of) all-powerful constructs within its context.
- erik_seaberg 4y ago
  My goal is “most reliable and concise for experts,” because we should spend most of our careers as experts, and “easy to learn” requires bad tradeoffs too often. Learning common names and reusing tested implementations pays off over rolling my own on the spot and forcing everyone else to re-read it.