Horror! Using goto statement in finite state machines?

[Rui Maciel]

I've been delving into finite state machines and at this time it seems that
the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at the
goto statement, accusing it of being some sort of spawn of satan. So it
seems we have a pickle here.

The thing is, at first thought it seems that there aren't any viable
alternatives which are better suited for this task. Yes, probably the end
result will be an entangled mess but as far as I know a set of nested if
and switch statements will not improve much on the subject.

So, what are your views on this subject? Is the use of goto statements in
this application really the best possible solution to this problem or is it
unjustified and there is some godsend method which I'm missing out on?


Thanks in advance
Rui Maiel

 

[Ben Pfaff]

I've been delving into finite state machines and at this time it seems that
the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at the
goto statement, accusing it of being some sort of spawn of satan. So it
seems we have a pickle here.

How about a switch statement or an array of function pointers?

 

[Richard Heathfield]

Rui Maciel said:

I've been delving into finite state machines and at this time it seems
that the best way to implement them is through an intense use of the
goto statement.

It doesn't surprise me.

Yet, everyone plus their granmother is constantly
cursing at the goto statement, accusing it of being some sort of spawn
of satan. So it seems we have a pickle here.

Don't let them put you off. If you think goto is the best way to go,
then use goto. It's what we call learning the hard way, but at least
you'll learn.

The thing is, at first thought it seems that there aren't any viable
alternatives which are better suited for this task. Yes, probably the
end result will be an entangled mess but as far as I know a set of
nested if and switch statements will not improve much on the subject.

If you think switches won't improve /much/, then you already agree that
they're an improvement on what you have already said is "the best way".

So, what are your views on this subject?

That you contradict yourself.

Is the use of goto statements
in this application really the best possible solution to this problem

No, but don't let us stop you if that's what you want to do.

or is it unjustified and there is some godsend method which I'm
missing out on?

Well, there's always the right way, of course, but don't worry your head
about it.

Thanks in advance
Rui Maiel

I'm not one for spelling flames, but you might want to put a little more
effort into learning how to spell your own name.

 

[Walter Roberson]

I've been delving into finite state machines and at this time it seems that
the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at the
goto statement, accusing it of being some sort of spawn of satan. So it
seems we have a pickle here.

How are you defining "best" in this context? Are you talking
about program execution speed, about how quickly the program
can be written, about how easily the code can be read, about
how easily the code can be modified to add or revise states,
about how easily the code can be debugged while it is running?

Implementation mechanisms vary according to what is being state'd;
it isn't uncommon to use some kind of state description language
that is passed through a processor that dumps out C code that
is then compiled. With that kind of setup, concerns about the
readability of the C code phase become much reduced -- though
concerns about the ability to debug the running state machine
may still be sufficient to push towards generated code that
is relatively readable by humans.

I can't say that I have a "vast" experience with state machines,
but (like most programmers) I've implemented a few, and have been
on a team that worked on a large complex state machine. So far,
none of the state machines I've implemented have required a goto;
some of the lex machines I've done might have generated goto's,
but none of the projects for which I have implemented the state code.

I've gone the while/ switch/ inline code route, and I've gone the
while/ switch/ tables-and-function-pointer route, and I've gone
hybrids; the versions with tables and function pointers have tended
to be the most satisfying, but when the actions to be taken in
the states are too different then that can become too ackward.

 

[Charlton Wilbur]

RM> So, what are your views on this subject? Is the use of goto
RM> statements in this application really the best possible
RM> solution to this problem or is it unjustified and there is
RM> some godsend method which I'm missing out on?

The goto statement is reviled by pedagogues and maintenance
programmers because structured programming languages provide a
multitude of ways to express the logic of the code. In almost all
cases where you think of using a goto, there's a control structure
that makes the *meaning* of what you want to do clear.

Honestly, all of the control structures are just syntactic sugar for
goto, but they're syntactic sugar that conveys the meaning of the
code, and that's something that maintainers really need to know.

For a state machine, a switch/case structure is probably what you
want. But if you're going to be the one maintaining the code, use
whatever you think best.

Charlton

 

[santosh]

RM> So, what are your views on this subject? Is the use of goto
RM> statements in this application really the best possible
RM> solution to this problem or is it unjustified and there is
RM> some godsend method which I'm missing out on?

Honestly, all of the control structures are just syntactic sugar for
goto, but they're syntactic sugar that conveys the meaning of the
code, and that's something that maintainers really need to know.

I don't think so. A goto generates an unconditional jump, but the
structured control flow statements usually generate a conditional jump.

 

[Flash Gordon]

santosh wrote, On 09/02/07 18:19:

I don't think so. A goto generates an unconditional jump, but the
structured control flow statements usually generate a conditional jump.

OK, they are syntactic sugar for condition + goto.

I've done enough programming in assembler implementing loops and the
like to agree with Charlton's point.

 

[Rui Maciel]

How are you defining "best" in this context? Are you talking
about program execution speed, about how quickly the program
can be written, about how easily the code can be read, about
how easily the code can be modified to add or revise states,
about how easily the code can be debugged while it is running?

The main property on which I based my definition of "best way to implement a
finite state machine" was code simplicity to write, read, debug, modify. As
far as I can tell the end result may end up being clearer and simpler to
deal with than a whole bunch of convoluted if/switch nests peppered with
loops.

Implementation mechanisms vary according to what is being state'd;
it isn't uncommon to use some kind of state description language
that is passed through a processor that dumps out C code that
is then compiled. With that kind of setup, concerns about the
readability of the C code phase become much reduced -- though
concerns about the ability to debug the running state machine
may still be sufficient to push towards generated code that
is relatively readable by humans.

I see what you mean. When I started this project first I delved into Ragel
but as I'm mainly interested in the learning experience and I never wrote a
FSM before, I found it best to try to write it by hand.

I can't say that I have a "vast" experience with state machines,
but (like most programmers) I've implemented a few, and have been
on a team that worked on a large complex state machine. So far,
none of the state machines I've implemented have required a goto;
some of the lex machines I've done might have generated goto's,
but none of the projects for which I have implemented the state code.

I've gone the while/ switch/ inline code route, and I've gone the
while/ switch/ tables-and-function-pointer route, and I've gone
hybrids; the versions with tables and function pointers have tended
to be the most satisfying, but when the actions to be taken in
the states are too different then that can become too ackward.

That sounds very interesting. Where can I learn more about those approaches,
specially the one that uses table-and-function-pointers?


Thanks for the help and best regards
Rui Maciel

 

[Rui Maciel]

For a state machine, a switch/case structure is probably what you
want.  But if you're going to be the one maintaining the code, use
whatever you think best.

At the moment my experience writing FSMs is very limited and, due to my lack
of experience, my reasoning regarding this subject may not be strong enough
to provide sound judgement.

So if you were to write a FSM, what method would you choose and why? If the
method isn't exclusively based on goto statements, why did you opted it?


Best regards and thanks in advance
Rui Maciel

 

[Michael]

I've been delving into finite state machines and at this time it seems that
the best way to implement them is through an intense use of the goto
statement. Yet, everyone plus their granmother is constantly cursing at the
goto statement, accusing it of being some sort of spawn of satan. So it
seems we have a pickle here.

Dijkstra's paper about using gotos really was complaining about
arbitrary use of gotos (which can produce spaghetti code).

I would argue that there are certain cases where there is a clean
pattern to using gotos. One example that has been discussed on this
group in the last couple of months is error handling. As another
example, I could imagine that state machines could be implemented in a
way that the goto solution was cleaner than the non-goto solution.
I'm assuming your pattern looks something like this:
STATE_N:
/* do a bunch of stuff. */
goto next_state;
STATE_N_PLUS_1:
/* do a bunch of stuff */
goto next_state;

The basic thing is that you're not using gotos in arbitrary ways
within the state machine, but rather, in a very boilerplate, standard,
almost cookie-cutter way. With an appropriate comment or two at the
beginning explaining the pattern, and appropriate documentation (or
both), I would consider this fine.

Michael

 

[Roberto Waltman]

I don't think so. A goto generates an unconditional jump, but the
structured control flow statements usually generate a conditional jump.

In the general case they generate both types.

This

if (condition)
{
xxx
}
else
{
yyy
}

Is roughly translated as

test condition
if false goto label_1
xxx
goto label2
label_1:
yyy
label_2:


This

while (condition)
{
xxx
}

Is roughly translated as

label_1:
test condition
if false goto label_2
xxx
goto label_1
label_2:

And so on. The comment on "syntactic sugar" is still valid, ignoring
the cases where a processor's instruction set would allow some
construct to be mapped directly into less primitive operations.

Roberto Waltman

[ Please reply to the group,
return address is invalid ]

 

[Rui Maciel]

Don't let them put you off. If you think goto is the best way to go,
then use goto. It's what we call learning the hard way, but at least
you'll learn.

The point of this thread is to avoid "reinventing the wheel". If others are
more experienced and knowledgeable about this subject it is preferred to
learn from them instead of running the risk of needlessly spending time and
effort to end up back in square one.

If you think switches won't improve /much/, then you already agree that
they're an improvement on what you have already said is "the best way".


That you contradict yourself.
Right...



No, but don't let us stop you if that's what you want to do.


Well, there's always the right way, of course, but don't worry your head
about it.
Right...

I'm not one for spelling flames, but you might want to put a little more
effort into learning how to spell your own name.

Sarcasm and bitterness aside, I fail to see the point of your post. Was
there one?


Best regards
Rui Maciel

 

[Rui Maciel]

How about a switch statement or an array of function pointers?

As far as I can tell, to use the switch instead of the goto statement would
end up generating a nested mess inside continuous loops. On the other hand
the use of arrays of function pointers is completely new to me.

In both cases, is it possible to get my hands on information on how to
implement those methods? Even implementations would be great.


Thanks for the help and best regards
Rui Maciel

 

[Ian Collins]

Charlton Wilbur wrote:




At the moment my experience writing FSMs is very limited and, due to my lack
of experience, my reasoning regarding this subject may not be strong enough
to provide sound judgement.

So if you were to write a FSM, what method would you choose and why? If the
method isn't exclusively based on goto statements, why did you opted it?

That depends on the requirements, but I'd prefer either nested switch
statements or an array of function pointers.

 

[Malcolm McLean]

I'm assuming your pattern looks something like this:
STATE_N:
/* do a bunch of stuff. */
goto next_state;
STATE_N_PLUS_1:
/* do a bunch of stuff */
goto next_state;

The basic thing is that you're not using gotos in arbitrary ways
within the state machine, but rather, in a very boilerplate, standard,
almost cookie-cutter way. With an appropriate comment or two at the
beginning explaining the pattern, and appropriate documentation (or
both), I would consider this fine.

You don't have to use structured programming and its derivatives as your
methodology. The ban on goto does not necessarily apply to programs designed
around state machines, for instance.

However if you don't use structured programming you are very much setting
off on your own. You might find something better, more probably you will
invent something worse, and other people will have to learn your methodology
as well as your program. I don't see that

struct machine
{
int state;
}

switch(machine->state)
{
case STATE_N:
dosomething();
machine->state = STATE_NPLUSONE;
break;
case STATE_NPLUSONE:
dosomethingelse();
machine->state = STATE_N;
break;
}

is a huge improvement in any absolute sense, but it is a familiar paradigm.

 

[Christopher Layne]

For a state machine, a switch/case structure is probably what you
want. But if you're going to be the one maintaining the code, use
whatever you think best.

Charlton

And of all of them - switch()/case: is the most thinly veiled goto: factory.

 

[Christopher Layne]

As far as I can tell, to use the switch instead of the goto statement would
end up generating a nested mess inside continuous loops. On the other hand
the use of arrays of function pointers is completely new to me.

In both cases, is it possible to get my hands on information on how to
implement those methods? Even implementations would be great.

You seem to be having trouble.

In your web browser, open this location:

http://groups.google.com

You then apply your fingers to the keys and type:
"FSM function pointers"

 

[Lew Pitcher]

As far as I can tell, to use the switch instead of the goto statement would
end up generating a nested mess inside continuous loops. On the other hand
the use of arrays of function pointers is completely new to me.

I've used the function pointer array idea in several small state
machine projects. Below, I've stripped one such project of it's meat,
to leave the framework intact...

#include <stdio.h>
#include <stdlib.h>


int State1(int datum)
{
/* do some work /*
return 2; /* next is state 2 */
}

int State2(int datum)
{
/* do some work /*
return 3; /* next is state 3 */
}

int State3(int datum)
{
/* do some work /*
return 4; /* next is state 4*/
}

int State4(int datum)
{
/* do some work /*
return 1; /* next is state 1 */
}

int GetChar(void)
{
int datum;

if ((datum = getchar()) != EOF)
datum &= 0x7f;

return datum;
}

int main(void)
{
int (*Process[])(int) = {
NULL, /* no logic for state 0 (EOF) */
State1, /* State1() processes state 1 */
State2, /* State2() processes state 2 */
State3, /* State3() processes state 3 */
State4 /* State4() processes state 4 */
};
int state = 1;

while (state != 0)
state = Process[state](GetChar());

return EXIT_SUCCESS;
}

HTH

 

[Eric Sosman]

Rui Maciel wrote On 02/09/07 14:47,:

Ben Pfaff wrote:

How about a switch statement or an array of function pointers?

As far as I can tell, to use the switch instead of the goto statement would
end up generating a nested mess inside continuous loops. [...]

If there's nothing going on during a state transition except
the transition itself, then switch-in-a-loop has no benefit that
I can see, aside from evading the wrath of the goto police. If
you just change `goto state42' to `state = 42', all you've done
is change the spelling.

However, lots of applications of state machines perform some
additional action at each transition: They consume the next input
character or emit the next output message or something of the
sort. In that setting, switch-in-a-loop is very attractive
because it provides convenient places for the "transitional"
actions, to wit, before and after the big switch block:

for (; {
/* "prefix" actions ... */
switch (state) {
...
}
/* "suffix" actions ... */
}

If both "prefix" and "suffix" are empty, though, there
seems little point to this structure.

 

[Richard Harter]

At the moment my experience writing FSMs is very limited and, due to my lack
of experience, my reasoning regarding this subject may not be strong enough
to provide sound judgement.

So if you were to write a FSM, what method would you choose and why? If the
method isn't exclusively based on goto statements, why did you opted it?

My usual method is to use two tables, a successor table, and an action
table. Each table is two dimensional, one dimension being the state
number and the second being the event number. The successor table
contains the next state for each (state,event) pair; the action table
either contains an action code (if I am using a switch) or a function
pointer (if I am using functions for each action). There two special
states, an init state and a term state.

When using function pointers the execution engine is really simple,
basically

while (state != TERMINAL)
{
action[state][event]();
state = successor[state][event];
event = get_next_event();
}

If you are using a switch the execution engine looks like

while (state != TERMINAL)
{
switch (action[state][event])
{
case 0:
{
/* action code goes here */
break;
}
....
}
state = successor[state][event];
event = get_next_event();
}

HTH HAND