Goto considered helpful

[T. William Wells]

In article <54281 at sun.uucp>, jamesa%betelgeuse at 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.