State Machines, The Ultimate Goto

[Herman Rubin]

In article <27568 at cca.CCA.COM>, g-rh at cca.CCA.COM (Richard Harter) writes:
	 
		.......

> >This is almost a finite-state machine, and state machine programming is an
> >accepted idiom. Generalise it as follows:

> State machines are all very well in their way -- I use them myself --
> but state machine logic is quintessential goto logic.  The essence of
> state machine logic is that it doesn't matter where you came from;  all
> that matters are the appropriate actions for this state and the appropriate
> state to transfer to next.
> 
> From a flow control viewpoint, entering a state machine is like falling into
> a pin ball machine.  You bang around here and there and (if there is a 
> guaranteed halting condition) you eventually get out.
> 
> Goto logic says leave and don't come back.  Heirarchical logic says leave
> and come back.  The prescription against goto's really means -- don't mix
> the two types of structure.

Sometimes what is needed is to leave with the idea of coming back, and
sometimes what is needed to to leave without the idea of coming back.  I
have written many Fortran programs (expressed in the C idiom) using the
following control structure:

	for(...; ....; ...)
		{  ....;
		   if(....)goto abc;		/* normal exit */
		   .....;}
	....;					/* abnormal exit */
abc:

Writing this without the goto yields code which is no easier to understand
and which will have more machine gotos.

Another example is the control structure of which I submitted a part with
the challenge to come up with a goto-less version with comparable efficiency.
I do not believe my posted reply made the net--I have not seen it.

A goto-less version of the control structure of the original full code is:

	b=q;	m=0;
	if(w=3)
		{i=3; g4=1;}
	else if (w even)
		{if (B) i=3; g4 = w/2;
		else i=4; g4= w/2 - 1;}
	else if (w=5) ABORT;
	else 
		{g16 = (w-3)/4;
		if (w&2) i=5;
		else ....		/* I now leave out further details */

	switch(i){
		case 4: ....
			if(...)
				{.....; i=2; break;}
			else{
				....;
				if (...){i=1; break;}
		case 3: ....;
		case 2: ....;
		case 1: ....; break;
		case 6: ....; i=...; break;   	/* elaborate code omitted */
		case 5: b >>= g16; m |= b; 
			if (....)
				{u = *(--geom);
				if EVEN(u) i=1;
				else i=2; break;}
			else {u = *(--geom);
				g4 = (u+1)/2;
				if EVEN(u) i=4;
				else i=3; break;}
		case 7:....; i=....; break;	/* code omitted */
		default:	....; i=...; break;  /* code omitted */}

Now what I did, and it obviously produces more efficient code, which I claim is
not harder to understand, was to eliminate storing i unless i > 7, which is
rare.  Instead, the value of i is kept in the current case, which eliminates
99.99% of the storages of i and all transfers to the switch statement.
			
I cannot see how an optimizing compiler, unless it did what I did internally,
can do as well.  And no flames about how complicated the code is; this is part
of a program which is extremely efficient in the use of random bits; all of the
variables except the initial values of b and m are current values of random
variables.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin at l.cc.purdue.edu (ARPA or UUCP) or hrubin at purccvm.bitnet