Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site redwood.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!zehntel!dual!amdcad!fortune!rhino!redwood!rpw3
From: rpw3@redwood.UUCP (Rob Warnock)
Newsgroups: net.lang.c
Subject: Re: goto's in 'C'
Message-ID: <137@redwood.UUCP>
Date: Tue, 22-Jan-85 21:17:38 EST
Article-I.D.: redwood.137
Posted: Tue Jan 22 21:17:38 1985
Date-Received: Thu, 24-Jan-85 19:39:14 EST
References: <308@harvard.ARPA>
Distribution: net
Organization: [Consultant], Foster City, CA
Lines: 96

+---------------
| >[rpw3] The incidence of the "goto" in C code is so rare anyway, I dare say
| >we could abolish it altogether (replacing it with BLISS's "leave")
| >and not miss the loss. (I certainly never missed it in BLISS.)
| I would miss it. I have never used it for breaking out of loops or
| making loops in the conventional sense. It is extremely useful, though,
| for 'hardcoding' finite state machines. If they contain more than say 3
| or 4 states, the use of structured constructs is awkward...
| 						Thomas.
+---------------

Well, that depends on what "structured construct" you use. The standard
technique (criticized by Wulf in "Global Variable Considered Harmful") is
to use a (global) state variable which is really the "PC" of your state
machine, with assignments to "state" instead of "goto"s:

	state = INITIAL;
	while (state != TERMINATION) switch (state) {
	...
	case ENABLED:	...
			if (...) state = ACTIVE;
			break;
	case ACTIVE:	...
			break;
	...
	}

This can be fairly clean if you never allow "fallthrough" from one state
to another (each case ends in "break"), and to my taste is somewhat
easier to follow than the equivalent mass of "goto"s.

If your machine is of the form INPUT X STATE ==> (OUTPUT, NEXT-STATE)
it is sometimes more useful to have the state variable be a pointer to
the processing routine for the current state, which is called for each
"event" (input). This way, the size of each state "module" can be kept
manageable. This approach was used in a disk driver I know of, with
great success (the controller never told you WHY it was interrupting,
you had to know what you'd asked it do do):

	diskintr(p)			/* called on interrupt from disk */
	register struct DISKDDB *p;	/* any of several controllers */
	{
		while ( (*(p->state))(p) )	/* return 0 to dismiss */
			;
	}

This also works nicely for lexical analysis routines which are driven off
of each character "event".

In any case, however, one must be aware that one is dealing with potentially
explosive complexity on the order of the number of input values times the
number of states (and if next-state depends on things other than the "input",
that can be inputs times number of states squared, or worse). As Dijkstra says
[EWD512, in "Selected Writings..."]:

	"But programming, when stripped of all its circumstantial irrelevancies,
	boils down to no more and no less than very effective thinking so as to
	avoid unmastered complexity, to very rigorous separation of your many
	different concerns... We have to fight chaos, and the most effective
	way of doing that is to prevent its emergence. We have to learn to
	avoid all forms of combinatorial complexity generators that, when
	active, rapidly tax our ability to carry out a case-analysis far beyond
	the limits of our power of reasoning."

When forced into a "state machine" approach, wherever possible we must factor
the problem so that the EVENTS x STATES decisions are not more than we can
individually examine for correctness (hopefully much less than a dozen cases).
There are two useful tools for this: factoring the events and factoring the
states.

Factoring the input events can often be done by noting when we are really only
interested in equivalence classes. For example, in lexical analyzers, when in
the "idle" state we usually only care whether the character is a <number>, a
<letter>, some <space>, or an <operator>. (Of course, once we are in "number"
state, we care about each of the possible values of a <number>.)

Likewise, many state machines can be partitioned into either disjoint or
hierarchically nested sub-machines. This often has the consequent desirable
effect of allowing further reduction in the size of the input space. The
entire state "number" above could be considered (from the "top" level) to
be a sub-machine that is interested only in events of the form <number>
and <not-number>. Likewise, states such as "operator" are only concerned
with handling <operator> and <non-operator> inputs (although internally it
must distinguish among all the individual operators).

Whether we use the "goto", "while/switch", routine dispatch, threaded code,
or any other coding style, state machines can be complicated beasts if we
are not extremely careful.


Rob Warnock
Systems Architecture Consultant

UUCP:	{ihnp4,ucbvax!dual}!fortune!redwood!rpw3
DDD:	(415)572-2607
USPS:	510 Trinidad Lane, Foster City, CA  94404