SI413 Class 21: Gotos considered interesting

Reading

Go to Reference 2 of this Wikipedia entry, which is Dijkstra's original paper. Really read it!

Also check out this xkcd comic, which really demonstrates how dangerous the use of gotos can be. (Thanks to Midn Kursawe for pointing it out to me.)

Homework

Write your own piece of "spaghetti code" using gotos in C/C++. The program needs to actaully do something reasonable, but be hard to follow on account of the gotos bouncing around, like my example below. Rules:

1. You must include a comment in the top with your name and what your program does (not how it works, but what it does), .e.g. "prints the first 20 fibanocci numbers".
2. Your code must use at least two gotos.
3. Your code must confuse me. You guys ought to have no problems with this last rule.

Please submit a printout of code, plus a screenshot showing the code compiling and running.

Also, find (and tell me about) a typo, misspelling or grammar error in Dijkstra's article. Ha - now you have to read it!

Programming Old-School with gotos

Back in the day, programmers didn't have these fancy while loops, and for loops, and do-while loops, and switches, and all those other fancy things we're used to. They had "if" and they had "goto". Of course many of you may not even know what a goto is. Why? Why did the goto disappear like the dodo, or bell bottoms? First let's make sure we understand what gotos are. We'll use C as our example. In C you can define a label in between statements in a function body. You also have the "goto" statement which is the word "goto" followed by the name of a label. When a "goto" is reached, control jumps to the statement following the label. Pretty simple idea. The following example simply prints the numbers 1,2,...,10, one per line.

int i = 1;
slp:
printf("%d\n",i);
++i;
if (i <= 10)
  goto slp;

Gotos considered harmful

In 1968, Edsger Dijkstra published a letter in the Communications of the ACM entitled "Go-to statement considered harmful". (See this, which links to the manuscript.) This led to the "structured programming revolution" that has pretty much rid the world of gotos.

Gotos can be nice: jumping into a loop

Gotos can be useful. Sometimes, for instance, we want to jump into the middle of a loop to start things off. For example, consider the following code which prints out a comma separated list of 1x, 2x's, ..., 10x's. NOTE that it's flawed!

  int i = 1,j;
  while(i <= 10)
  {
    printf(",");
    for(j = 0; j < i; ++j)
      printf("x");
    ++i;
  }
  printf("\n");

This is really clear, but it doesn't really work, because it sticks a comma before the first x. It's easy to fix this with a goto:

  int i = 1,j;
  goto ac;
  while(i <= 10)
  {
    printf(",");
  ac:
    for(j = 0; j < i; ++j)
      printf("x");
    ++i;
  }
  printf("\n");

Now, there are other ways, of course. But this is nice because it keeps the same structure as our original, and adds no new tests to the code. In fact, the first "i <= 0" test is even avoided.

Gotos can be nice: jumping out of nested loops

Another situation in which gotos are handy is when you want to break completely out of a group of nested loops. Consider the following chunk of code which searches for two integers i and j, i ≠ j, in the range 0..99 whose sin's differ by at least 1.99. Silly problem, but it illustrates the point nicely.

  int i, j;
  for(i =0; i < 100; ++i)
    for(j = i+1; j < 100; ++j)
      if (fabs(sin(i) - sin(j)) >= 1.99) goto found;

 found:
  /* code for doing whatever you wanted i and j for! */

Once again, there are other ways to do this, but none of them is as straightforward ... nor as efficient.

NOTE: Java offers "labeled break" statements, which are essentially like our use of gotos here, and labeled continue statements as well. You stick a label (just like C labels) in front of a loop, and "break foo;" breaks out of the loop labeled foo.

What's so bad about gotos?

You can find acres of print on the pro/con debate on gotos. The web is full of stuff. To summarize, the main argument is that gotos encourage hard to follow "spaghetti" code. From your own opinion. Here's an example of a bad, bad program using gotos:

/******************************************************
 * This is a horrible program that reads a line of text,
 * expecting a number in binary.  The text can only be
 * ' '*(0|1)+' '*'\n' or it prints an error message. So 
 * "101" or "  101" or "101  " or " 101 " are all good. 
 * "  " and "101k" are bad. If the input is good, the
 * program prints the decimal value of the binary number.
 ******************************************************/
#include <stdio.h>

int main()
{
  int x = 0;
  char c;
  goto rs;
 fns:
  if (c != '1' && c != '0') goto er;
  goto ns;
 rd:
  c = getchar();
 ns:
  if (c == '1') { x = x*2 + 1; goto rd; }
  if (c == '0') { x = x*2; goto rd; }
 es:
  if (c == ' ')
  {
    c = getchar();
    goto es;
  }
  if (c == '\n') goto done;
 er:
  printf("Error!\n");
  return 1;
 rs:
  c=getchar();
  if (c == ' ') goto rs;
  else goto fns;
 done:
  printf("%i\n",x);
  return 0;
}

Admittedly, bad programs can be written without the aid of gotos, so the fact that this is bad doesn't imply gotos are bad. However, maybe the way in which this is bad will be suggestive of the way that gotos can be hard to understand.

Goto's and scope

Gotos can cause some scoping problems. Consider the following chunk of code:

  int x;
  scanf("%i",&x);
  if (x > 0)
    goto foo;
  int y = -x;
 foo:
  printf("%i\n",y);

Lexical scoping rules say that y should be visible in the printf statement, but what happens if the x read in from the user is positive? Then we jump over the definition and initialization of y. How should that be handled?

Dijkstra's actual argument

Dijkstra's paper (which I really do want you to read) doesn't just say "gotos lead to hard-to-follow programs". He gives an argument for why code with gotos are often hard to follow, while code using functions and structured loops (i.e. for, while, do-while, etc) are not as hard to follow. His basic point is this: as a program executes we need to think about "where we are" in the computation. In general, as he argues and we discussed in class, a line number in the program is not sufficient to describe "where we are". Dijkstra describes a straightforward, meaningful way to describe "where we are" in a computation when functions and structured loops are used, then argues that it is not possible, in general, to do the same thing when gotos are used systematically. It's an interesting concept, and one that is much meatier than simply saying "programs with gotos are hard to follow".