Loops are gotos

Loops are gotos

Rate This
  • Comments 58

Here's an interesting question I got the other day:

We are writing code to translate old mainframe business report generation code written in a BASIC-like language to C#. The original language allows "goto" branching from outside of a loop to the interior of a loop, but C# only allows branching the other way, from the interior to the exterior. How can we branch to the inside of a loop in C#?

I can think of a number of ways to do that.

First, don't do it. Write your translator so that it detects such situations and brings them to the attention of a human who can analyze the meaning of the code and figure out what was meant by the author of this bad programming practice. Branching into the interior of a loop is illegal in C# because doing so would skip all of the code that is necessary to ensure the correct behaviour of the loop. Odds are good that this pattern indicates a bug or at least some bad smelling code that should be looked at by an expert.

Second, this pattern is not legal in C# or VB.NET, but perhaps it is legal in another useful modern language. You could write your translator to translate to some other language instead of C#.

Third, if you want to do this automatically and you need to use C#, the trick is to change how you generate your loops. Remember, loops are nothing more than a more pleasant way to write a "goto". Suppose your original code looks something like this pseudo-basic fragment:

10   J = 2
20   IF FOO THEN GOTO 50
30   FOR J = 1 TO 10
40     PRINT J
50     PRINT "---"
60   NEXT
70   PRINT "DONE"

The "obvious" way to translate this program fragment into C# doesn't work:

     int J = 2;
     if (FOO) goto L50;
     for(J = 1 ; J <= 10; J = J + 1)
     {
       PRINT (J);
L50:   PRINT ("---");
     }
     PRINT ("Done");

because there's a branch into a block. But you can eliminate the block by recognizing that a "for" loop is just a sugar for "goto". If you translate the loop as:

     int J = 2;
     if (FOO) goto L50;
     J = 1;
L30: if (!(J <= 10)) goto L70;
       PRINT (j);
L50:   PRINT ("---");
     J = J + 1;
     goto L30;
L70: PRINT ("done");

and now, no problem. There's no block to branch into, so there's no problem with the goto. This code is hard to read so you probably want to detect the situation of branching into a loop and only do the "unsugared" loop when you need to.

It is difficult to do a similar process that allows arbitrary branching in a world with try-finally and other advanced control flow structures, but hopefully you do not need to. Old mainframe languages seldom have complex control flow structures like "try-finally".

  • > Branching into the interior of a loop is illegal in C# because doing so would skip all of the code that is necessary to ensure the correct behaviour of the loop.

    Can you elaborate? Do you mean the loop condition for while-loops, and also the initializer for for-loops (in which case goto silently breaks the semantics of the loop - but this seemingly doesn't apply to do-while), or some other code that the compiler generates undercover?

    It's more general than loops. In C# it is illegal to branch into the middle of any block from outside the block. With loops, one wants to be able to reason about the invariants of a loop without having to understand how control could have entered the loop. More generally, one should be able to reason about the control flow within a given block solely by looking at that block. You should not have to look at the whole method to understand how a given block in it could be used.

    Another way to look at this is to think of the name of the label as being scoped to the block, just like the name of a local declared in the block is scoped to the block. Just as you cannot refer to a local by name outside of its scope, you cannot refer to a label by name outside of its scope. 

     -- Eric

  • In a previous life, I had to do just such a beast and wound up doing exactly what you suggested.  However I could do some static analysis and only write the IF/GOTO loop if there were a /targeted/ label inside of the original FOR loop.  Otherwise, I'd write the more natural corresponding FOR loop.

    If I did have to write the IF/GOTO loop I would insert a comment block that indicated what it read originally (FOR) and where the reference to the inner label came from.  This facilitated hand-massaging the code later into something more manageable.

    Thank goodness there were no COME FROM constructs!  :)

  • You can't do Duff's Device in C#?! Jeez.

    Gotos are fun. I wrote a (lexer) state machine once with no loop. It just bounced around with gotos until it bounced into an endpoint.

    It's weird, but good, that we've reached a point when gotos are an exotic construct that you never think about.

  • Simple suggestion, unroll the part of the loop that is being jumped to, outside of the loop, and insert that part at the jump location ... This could get a little complicated if the jump traverses many branches of code, but otherwise I think it could be an option ...

  • When you say this is legal in VB, you mean VB6, right - not VB.Net?

    Bizarre. The customer who asked me about this issue said that it worked in VB.Net, but I have just checked the documentation and clearly it does not. Thanks for noticing that. -- Eric

     

  • So how would you translate this into oh, FORTH, or Python, for example, neither of which has labels.. You need to figure out what the program REALLY needs to do and do it without spaghetti (even flying spaghetti monster) code.

  • Personally if I was going to manually refactor that code then I'd ditch the GOTOs altogether and just do something like:

    IF (FOO) THEN

     PRINT "---"

     FOR J = 3 TO 10

       PRINT J

       PRINT "---"

     NEXT

    ELSE

     FOR J = 1 TO 10

       PRINT J

       PRINT "---"

     NEXT

    ENDIF

    PRINT "DONE"

    Sure it's a lot more verbose, but I find it a lot easier to read than the translated block with the looping GOTOs in it.

  • When people realize today's if-else are also gotos, there's gonna be rioting in the streets! ;)

  • Cleaner would be:

    INTEGER JBASE

    IF (FOO) THEN

        PRINT "---"

        JBASE = 3

    ELSE

        JBASE = 1

    END IF

    FOR J = JBASE TO 10

        PRINT J

        PRINT "---"

    NEXT

    PRINT "DONE"

  • Suppose you have something like this:

    int i = 0;

    if( j < 5 ) goto inside;

    for( ; i < 10 ; ++i )

    {

      do_something( );

    inside:

     do_more( );

    }

    Then why can't you translate it like this?

    int i = 0;

    if( j < 5 ) do_something( );

    for( ++i ; i < 10 ; ++i )

    {

      do_something( );

    inside:

     do_more( );

    }

    This is exactly what Pop Catalin suggested. It will vary on case by case basis, but it is easier to do and more easier to understand.

  • @Malcolm Fitzsimmons:

    Agreed. I would probably pick between that style or my style depending on a few factors, such as how big the actual loop body was, how big the body of the FOO clause was and how often I expected FOO to be true.

  • Read "Structured Programming with go to Statements".  That goto breaks invariant reasoning techniques was established to be wrong.

  • <Quote> Remember, loops are nothing more than a more pleasant way to write a "goto". </Quote>

    Your momma's a "goto."

  • On Error Goto Hell

    Hell:

       MsgBox "Before advanced control flow structures like try-finally, there were gotos."

  • My favorite "goto loop" pattern:

     do { // you think that's a loop? ha!

       ...

       if (something) break; // look, no goto!

       ...

     } while (false); // look, no label either!

    Yeah, I worked with a guy who really liked that one.

Page 1 of 4 (58 items) 1234