Is it possible to always eliminate goto's?

Question

While making everthing with goto's is easy (as evidenced by f.ex. IL), I was wondering if it is also possible to eliminate all goto statements with higher level expressions and statements - say - using everything that's supported in Java.

Or if you like: what I'm looking for is 'rewrite rules' that will always work, regardless of the way the goto is created.

It's mostly intended as a theoretical question, purely as interest; not as a good/bad practices.

The obvious solution that I've thought about is to use something like this:

while (true)
{
    switch (state) {
       case [label]: // here's where all your goto's will be
          state = [label];
          continue;
       default:
          // here's the rest of the program.
    }
}

While this will probably work and does fits my 'formal' question, I don't like my solution a single bit. For one, it's dead ugly and for two, it basically wraps the goto into a switch that does exactly the same as a goto would do.

So, is there a better solution?

---

Update 1

Since a lot of people seem to think the question is 'too broad', I'm going to elaborate a bit more... the reason I mentioned Java is because Java doesn't have a 'goto' statement. As one of my hobby projects, I was attempting to transform C# code into Java, which is proving to be quite challenging (partly because of this limitation in Java).

That got me thinking. If you have f.ex. the implementation of the 'remove' method in Open addressing (see: http://en.wikipedia.org/wiki/Open_addressing - note 1), it's quite convenient to have the 'goto' in the exceptional case, although in this particular case you could rewrite it by introducing a 'state' variable. Note that this is just one example, I've implemented code generators for continuations, which produce tons and tons of goto's when you're attempting to decompile them.

I'm also not sure if rewriting in this matter will always eliminate the 'goto' statement and if it is allowed in every case. While I'm not looking for a formal 'proof', some evidence that elimination is possible in this matter would be great.

So about the 'broadness', I challenge all the people that think there are 'too many answers' or 'many ways to rewrite a goto' to provide an algorithm or an approach to rewriting the general case please, since the only answer I found so far is the one I've posted.

Answer 1

This 1994 paper: Taming Control Flow: A Structured Approach to Eliminating Goto Statements proposes an algorithm to eradicate all goto statements in a C program. The method is applicable to any program written in C# or any language that uses common constructs like if/switch/loop/break/continue (AFAIK, but I don't see why it wouldn't).

It begins with the two simplest transformations:

• Case 1

  Stuff1();
  if (cond) goto Label;
  Stuff2();
  
  Label:
  Stuff3();
  

  becomes:

  Stuff1();
  if (!cond)
  {
    Stuff2();
  }
  Stuff3();
  

• Case 2

  Stuff1();
  Label:
  Stuff2();
  Stuff3();
  if (cond) goto Label;
  

  becomes:

  Stuff1();
  do
  {
    Stuff2();
    Stuff3();
  } while (cond);
  

and builds on that to examine each complex case and apply iterative transformations that lead to those trivial cases. It then rounds off with the ultimate gotos/labels eradication algorithm.

This is a very interesting read.

UPDATE: Some other interesting papers on the subject (not easy to get your hands on, so I copy direct links here for reference):

A Formal Basis for Removing Goto Statements

A Goto-Elimination Method And Its Implementation For The McCat C Compiler

Answer 2

A situation where a goto can be avoided, but I think it is better to use it:

When I need to exit a inner loop and the loop:

for(int i = 0; i < list.Count; i++)
{
    // some code that initializes inner
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code.
       if (condition) goto Finished;
    }
}
Finished:
// Some more code.

To avoid the goto you should do something like this:

for(int i = 0; i < list.Count; i++)
{
    // some code that initializes inner
    bool conditon = false;
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code that might change condition
       if (condition) break;
    }
    if (condition) break;
}
// Some more code.

I think it looks much nicer with the goto statement.

The second situation is okay if the inner loop was in a different method.

void OuterLoop(list)
{
    for(int i = 0; i < list.Count; i++)
    {
        // some code that initializes inner
        if (InnerLoop(inner)) break;
    }
}
bool InnerLoop(inner)
{
    for(int j = 0; j < inner.Count; j++)
    {
       // Some code that might change condition
       if (condition) return true;
    }
    return false;
}

Answer 3

I have some practical experience of attempting to take an unstructured program (in COBOL, no less) and render it as structured by removing every instance of GOTO. The original programmer was a reformed Assembly programmer, and though he may have known about the PERFORM statement, he didn't use it. It was GOTO GOTO GOTO. And it was serious spaghetti code -- several hundred lines worth of spaghetti code. I spent a couple of weeks worth of spare time trying to rewrite this monstrous construct, and eventually I had to give up. It was a huge steaming pile of insanity. It worked, though! Its job was to parse user instructions sent in to the mainframe in a textual format, and it did it well.

So, NO, it is not always to possible to completely eliminate GOTO -- if you are using manual methods. This is an edge case, however -- existing code that was written by a man with an apparently twisted programming mind. In modern times, there are tools available which can solve formerly intractable structural problems.

Since that day I have coded in Modula-2, C, Revelation Basic, three flavors of VB, and C# and have never found a situation that required or even suggested GOTO as a solution. For the original BASIC, however, GOTO was unavoidable.

Answer 4

Since you said it's a theoretical question, here is the theoretical answer.

Java is Turing complete so of course, yes. You can express any C# program in Java. You can also express it in Minecraft Redstone or Minesweeper. Compared to these alternatives expressing it in Java should be easy.

An obviously more practical answer though, namely an intelligible algorithm to do the transformation, has been given by Patrice.

Answer 5

I don't like my solution a single bit. For one, it's dead ugly and for two, it basically wraps the goto into a switch that does exactly the same as a goto would do.

That's what you're always going to get when looking for a general pattern which can replace any use of goto, something which does exactly the same as a goto would do. What else could it be? Different uses of goto should be replaced with best matching language construct. That's why constructs as switch statements and for loops exist in the first place, to make it easier and less error prone to create such a program flow. The compiler will still generate goto's (or jumps), but it will do so consistently where we will screw up. On top of that we don't have to read what the compiler generates, but we get to read (and write) something that's easier to understand.

You'll find that most compiler constructs exist to generalize a specific use of goto, those constructs where create based on the common patterns of goto usage which existed before it. The paper Patrice Gahide mentions sort of shows that process in reverse. If you are finding goto's in your code you are either looking at one of those patterns, in which case you should replace it with the matching language construct. Or you are looking at essentially unstructured code in which case you should actually structure the code (or leave it alone). Changing it to something unstructured but without goto can only make matters worse. (The same generalization process is still going on by the way, consider how foreach is being added to compilers to generalize a very common usage of for...)