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

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.