GOTOphobia considered harmful in C

GOTOphobia considered harmful in C
blog.joren.ga

I've been reading a lot about retro gaming lately, so I'm just thinking in the context of bedroom coders of the 80's that learned to program in BASIC, then moved on to assembly to get more performance, and then later moved on to C and C++ as projects became more complicated. They all seem to have turned out okay.

I suppose what I'm getting at is you can write bad code in any language.

E.g. even an odd problem. Let's use GNU C with local functions:

  #include 

  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);
  }

  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;
  }

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;
    }
  }

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.