Is it possible to always eliminate goto's?

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


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.


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