[comp.lang.c] Goto considered helpful

jamesa%betelgeuse@Sun.COM (James D. Allen) (05/24/88)

	The `goto' flames seem to be dying out; I'd like to add some
gasoline.  While others have been defending relatively `structured' goto's
(eg, "break 2", common code coalescing) my favorite goto is really horrendous:
a jump from one inner loop to a different inner loop.  I am sincerely curious
if there is a "better way."
	Following is edited but fairly faithful pseudocode for a contract
bridge endgame analysis program.  Since performance is an issue I mention that
the pseudostatements each compile to very terse machine code.

	initialize;
	for (tricknum = 0; outcome still undecided; tricknum++) {
		for (player = winner of prev trick; other players; player++) {
			determine legal plays;
			remove redundancies;	/* A == K , etc. */
			select most likely play;
		    BACKTRACK:
			play the card;
			push set of legal plays;
			if (player == winner of previous trick)
				restrict others to suit_led;
		}
		determine winner of trick;
	}
	while (--tricknum >= 0) {
		for (player = last_to_play; other players; player--) {
			pop set of legal plays;
			undo played_card and delete from legal plays;
			if (player is on losing side && other play available)
				goto BACKTRACK;
		}
	}
	print solution;


	Here are some alternate coding methods with my objections.

1) Do a recursive function call for each played card.  Clumsy (you either
	have to pass a lot of arguments or maintain the data as globals).
	Execution time increases significantly.
2) Do a recursive function call for each trick.  Reasonable, but doesn't
	completely sidestep the problem since backtracking occurs *within*
	a trick.
3) Rewrite in Prolog.  Plausible but pedantic.
4) Stuff the forward loop into the middle of the backtrack loop, or
	vice versa (left as an exercise).  Requires clumsy boolean flags
	(my code uses none).  Less readable because intuitively the forward
	and backtrack loops are separate.

	I don't claim that this is a general solution for backtracking.
Simpler problems can be handled nicely with nested `while's; harder problems
will require a more general method.  But for this program, depicting the
backtracking with a single powerful "goto" expresses the paradigm more
clearly (and certainly more efficiently) than the alternatives.

bill@proxftl.UUCP (T. William Wells) (06/12/88)

In article <54281@sun.uucp>, jamesa%betelgeuse@Sun.COM (James D. Allen) writes:
>       Following is edited but fairly faithful pseudocode for a contract
> bridge endgame analysis program.  Since performance is an issue I mention that
> the pseudostatements each compile to very terse machine code.
>
>       initialize;
>       for (tricknum = 0; outcome still undecided; tricknum++) {
>               for (player = winner of prev trick; other players; player++) {
>                       determine legal plays;
>                       remove redundancies;    /* A == K , etc. */
>                       select most likely play;
>                   BACKTRACK:
>                       play the card;
>                       push set of legal plays;
>                       if (player == winner of previous trick)
>                               restrict others to suit_led;
>               }
>               determine winner of trick;
>       }
>       while (--tricknum >= 0) {
>               for (player = last_to_play; other players; player--) {
>                       pop set of legal plays;
>                       undo played_card and delete from legal plays;
>                       if (player is on losing side && other play available)
>                               goto BACKTRACK;
>               }
>       }
>       print solution;

One alternate is to first recast this as a state machine.  Here
is how: The first thing to do is to put IN all the gotos.  (Well,
almost all; some are obviously irrelevant to determining the
global control structure, do not bother with those.) Eliminate
labels immediately before gotos (by changing the gotos to that
label).  Then, add a goto just before each label that is not
preceded by a goto.  Next, recast this as a state machine and
clean some of it up.  Among other things, get rid of each state
with only one reference to it.

Then, after it is a state machine, one can then determine the
flow of control and rewrite the code with non-goto control
structures.  The result looks something like this: (assuming I
did everything right; if not, do not bother to grouse, just do it
yourself and tell us how it really should be done.)

initialize;
tricknum = 0;
player = winner of prev trick;
while (1) {
	/* Moving forward ...  this player has not yet had moves
	   generated for him.  Generate those moves.  */

	determine legal plays;
	remove redundancies;    /* A == K , etc. */
	while (1) {
		/* Note that in the original code, the BACKTRACK
		   label should have been one statement eariler;
		   were this code to duplicate the function of
		   the other code, the `select' would have been
		   outside this loop and no selection would have
		   occured after backtracking.  */

		/* We get here either after moving forward or
		   after backtracking.  In either case, we must
		   select a play to make.  */

		select most likely play;
		play the card;
		push set of legal plays;
		if (player == winner of previous trick) {
			restrict others to suit_led;
		}
		/* If all players have not had their turn,
		   advance to the next player.  */

		if (there are more players for this trick) {
			++player;
			break;
		}
		/* The trick is done.  Should there be more
		   tricks to play, advance to the next trick,
		   making the winner of this trick the current
		   player.  */

		determine winner of trick;
		if (outcome still undecided) {
			++tricknum;
			player = winner of prev trick;
			break;
		}
		/* Time to back up; ascend the game tree till
		   someone has a move to make.  Also, do not stop
		   ascending if the player who could move would
		   win.  After all, why explore OTHER ways of
		   winning?  */

		player = last_to_play;
		while (1) {
			pop set of legal plays;
			undo played_card and delete from legal plays;
			if (player is on losing side && other play available) {
				break;
			}
			if (this is the first player for the trick) {
				if (--tricknum < 0) {
					print solution;
					return;
				}
				player = last_to_play;
			} else {
				--player;
			}
		}
	}
}

> 4) Stuff the forward loop into the middle of the backtrack loop, or
>       vice versa (left as an exercise).  Requires clumsy boolean flags
>       (my code uses none).  Less readable because intuitively the forward
>       and backtrack loops are separate.

Well, as you can see, my code effectively does this.  However,
you will notice that there are no additional variables.  Also,
this code, while it appears to be much larger, actually has only
one more statement than the original:

	player = last_to_play;

And this additional statement may be optimized out by some of the
better compilers.

While I am on the subject of optimizers, note also that the
goto-less version is likely to be better optimized than the
original, as many optimizers choke when confronted with a goto.