State Machines, The Ultimate Goto

[Richard Harter]

In article <767 at l.cc.purdue.edu> cik at l.cc.purdue.edu (Herman Rubin) writes:
>In article <27568 at cca.CCA.COM>, g-rh at cca.CCA.COM (Richard Harter) writes:

	... sundry material that doesn't need to be posted twice
	... with the final lines


>> 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.

	Perhaps I expressed this unclearly.  In heirarchical logic each block
has associated with it a statement which is to be executed after the block is
completed.  In inline code this is the statement immediately following the
block; in procedures it is the statement after the procedure invocation.
The fundamental rule of heirarchical logic is that you may only escape up
the stack of successor statements.

	In state machine logic each state has associated with it an assertion
statement that specifies the state.  There is no stack of successor statements.
Each state processor must determine the state of the machine after it has
completed processing and transfer to that successor state.

>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.

	Actually, this is not a good example of "leaving without the idea
of coming back".  The loop exit escapes the loop and control goes to the
successor code of the loop.  What your example really expresses is

	LOOP
	   if (failure) abnormal loop escape
	   ...
	   if (...) normal loop escape
	   ...
	   END LOOP
	if (abnormal loop escape) ....;

I am not terribly impressed with the argument that your cited code will
use fewer machine goto's -- the gain in efficiency in any real example is
nominal.  More to the point is your argument that the code using goto's
is as easy or easier to understand than code which avoids gotos.  I am not
so sure that I agree.  I would probably code your example as

	abend = true;	/* Default exit is abnormal */
	for (...;...;...) {
	   ....;
	   if (...) { abend = false; break}
	   ....;
	   }
	if (abend) ...;

This involves setting a flag and testing on it afterwards (a minor loss of
efficiency) but I am not bothered by flags per se, and this one tells me the
status of the result of computation and makes it explicit that the conditional
code is executed only if there is an abnormal exit.  I would rate it as clearer
code, irrespective of the religious status of gotos's.

>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.

	I didn't go through your example in detail -- it looked equally
messy regardless of whether it was expressed with or without goto's!  This
is not a criticism of the code, which I assume represented the actual situation
to be dealt with reasonably well.  As far as I can see, this is, indeed, a
good example of state machine logic.  Purists may shake their heads, but
it is perfectly reasonable to implement state machines with goto's.  The
only reason for not doing so is that the goto is too weak!!  Quite often
you need code that runs

	i = result of some calculation;
	goto case[i];

As a paranthetical note, if you are going to implement state machine logic
I would avoid depending on fallthrough and use goto's to transfer to the
next state, even if it immediately follows (any reasonable compiler will
optimize it out), e.g

	state_1:
	   ....;
	   goto state_2;
	state_2:
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.