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
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
67  7277 
Rui Maciel <ru********@gmail.comwrites:
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?
--
Ben Pfaff bl*@cs.stanford.edu http://benpfaff.org
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.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain, - www.
In article <45**********************@news.telepac.pt>,
Rui Maciel <ru********@gmail.comwrote:
>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.
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
>>>>"RM" == Rui Maciel <ru********@gmail.comwrites:
RMSo, what are your views on this subject? Is the use of goto
RMstatements in this application really the best possible
RMsolution to this problem or is it unjustified and there is
RMsome 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
--
Charlton Wilbur cw*****@chromatico.net
Charlton Wilbur wrote:
>>>"RM" == Rui Maciel <ru********@gmail.comwrites:
RMSo, what are your views on this subject? Is the use of goto
RMstatements in this application really the best possible
RMsolution to this problem or is it unjustified and there is
RMsome godsend method which I'm missing out on?
<snip>
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.
On Feb 9, 8:14 am, Rui Maciel <rui.mac...@gmail.comwrote:
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
"santosh" wrote:
>Charlton Wilbur wrote:
>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.
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 ]
Walter Roberson wrote:
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
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
Charlton Wilbur wrote:
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
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
santosh wrote, On 09/02/07 18:19:
Charlton Wilbur wrote:
>>>>>>"RM" == Rui Maciel <ru********@gmail.comwrites:
RMSo, what are your views on this subject? Is the use of goto
RMstatements in this application really the best possible
RMsolution to this problem or is it unjustified and there is
RMsome godsend method which I'm missing out on?
<snip>
>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.
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.
--
Flash Gordon
Rui Maciel wrote:
Charlton Wilbur wrote:
>>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?
That depends on the requirements, but I'd prefer either nested switch
statements or an array of function pointers.
--
Ian Collins.
Richard Heathfield wrote:
>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 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.
>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.
Right...
>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.
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
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
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. 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
--
Running Kubuntu 6.10 with KDE 3.5.6 and proud of it.
jabber:ru********@jabber.org
"Michael" <mc******@aol.comwrote in
>
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.
Charlton Wilbur wrote:
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.
Rui Maciel wrote:
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. 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"
On Feb 9, 2:47 pm, Rui Maciel <rui.mac...@gmail.comwrote:
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. 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
--
Lew
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.
-- Er*********@sun.com
On Fri, 09 Feb 2007 19:26:52 +0000, Rui Maciel <ru********@gmail.com>
wrote:
>Charlton Wilbur wrote:
>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?
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
Richard Harter wrote:
On Fri, 09 Feb 2007 19:26:52 +0000, Rui Maciel <ru********@gmail.com>
wrote:
>>
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();
}
Along with simplicity, this approach also has the advantage of
separating the engine from the state logic, giving a more generic solution.
--
Ian Collins.
Rui Maciel wrote:
>... Stuff about FSMs deleted.
>That sounds very interesting. Where can I learn more about those approaches,
specially the one that uses table-and-function-pointers?
For some reason I have never seen FSMs as anything other than tables
(with or without function pointers,) and felt that straight code,
switch statements, etc. are the wrong/unnatural way of implementing
them. Seems to be the other way around for most people.
A simple implementation follows. It is easily extended with default
actions, default transitions for given events, timeouts, etc.
Please note that:
(a) The linear search approach will be inefficient for large FSMs
(b) I verified it compiles without errors, but I have not really used
it. There may be dragons^H^H^H^H^H^H^H bugs.
/*-----------------------------------------------
* tiny_fsm.c
* Trivial implementation of
* a table-driven FSM in C
*
* Put in the public domain
* Roberto Waltman - 9-Feb-2007
*/
#include <stdio.h>
/* Valid states */
enum state_tag
{
NO_STATE,
ST_A,
ST_B,
ST_C,
ST_D /* etc. ...*/
};
typedef enum state_tag state_e;
#define INITIAL_STATE ST_C
/* Valid events triggering
* state transitions */
enum event_tag
{
NO_EVENT,
THING_UP,
THING_DOWN,
STUFF_OPEN
/* etc. ...*/
};
typedef enum event_tag event_e;
typedef struct transition transition_s;
/* Slot in transition table:
*
* current: current state.
* next: next state to
* transition to, if
* event: this event happens.
* action: function to call when
* transitioning from
* current to next.
*/
struct transition
{
state_e current;
event_e event;
state_e next;
void (*action)(transition_s *slot);
};
/* Actions to be invoked
* when changing state */
void f1(transition_s *slot);
void f2(transition_s *slot);
void f3(transition_s *slot);
/* etc. ... */
/* Transition table. There should be an
* entry for each valid transition (arch)
* in the FSM diagram. */
transition_s transition_table[] =
{
/* If current state is ST_A and event
* STUFF_OPEN happens, call f2() and
* move to state ST_C */
{ST_A, STUFF_OPEN, ST_C, f2},
/* If current state is ST_A and event
* THING_UP happens, call f1() and
* stay in same state. */
{ST_A, THING_UP, ST_A, f1},
/* If current state is ST_D and event
* THING_DOWN happens, move to ST_B.
* No action invoked. */
{ST_D, THING_DOWN, ST_B, NULL},
/* etc ... */
{NO_STATE, NO_EVENT, NO_STATE, NULL}
};
state_e next_state(
state_e current,
event_e event)
{
transition_s *tp = transition_table;
while (tp->current != NO_STATE)
{
if ((tp->current == current) &&
(tp->event == event ))
{
if (tp->action)
{
(tp->action)(tp);
}
return tp->next;
}
tp++;
}
return NO_STATE;
}
/* dummies to pass compilation */
int there_is_a_reason;
event_e what_happened();
void some_obscure_process()
{
state_e current_state = INITIAL_STATE;
state_e new_state;
event_e event;
while (there_is_a_reason)
{
event = what_happened();
new_state = next_state(current_state, event);
if (new_state != NO_STATE)
{
/* valid transition found */
current_state = new_state;
}
else
{
/* No valid transition for
* event from current_state
* This may or not be an error
*/
}
}
}
Roberto Waltman
[ Please reply to the group,
return address is invalid ]
Rui Maciel wrote, On 09/02/07 19:19:
Walter Roberson wrote:
>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.
Whether they are complicated or not can depend on what you are doing.
>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.
Yes, certainly worth doing once or twice.
>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?
A simple one could be something like:
int state = 0;
functype funcarray[] = { func1, func2, ... };
for (state = START; state != FINISHED; state = funcarray[state]())
continue;
Obviously each function returns the new state and all functions have to
have the same parameter list. Similarly a simple approach with switch is:
for ( state = START; state != FINISH; ) {
switch (state) {
case START: ... state = whatever; break;
case FRED: ... state = whatever; break;
}
}
With as much additional complexity as you require.
I know some people do not like the introduction of a state variable, but
others do not like the use of goto. You have to select the pattern that
best matches your problem, including possibly using a mixture.
--
Flash Gordon
Rui Maciel said:
<snip>
Sarcasm and bitterness aside, I fail to see the point of your post.
That figures.
Was there one?
Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain, - www.
Richard Heathfield wrote:
Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
And yet the one with unconditional jumps will end up being faster. :D
Christopher Layne said:
Richard Heathfield wrote:
>Yes, and it's this - that there is a huge body of experience within
the profession to show that structured programming constructs are a
massive improvement on unconditional jumps, with a real payoff in
maintenance cost reduction. A typical well-coded state machine will
comprise a loop containing a switch statement, with each case
relating to a state and selecting a new state according to
circumstances.
And yet the one with unconditional jumps will end up being faster. :D
If that's your bottleneck, you are a fortunate fellow indeed.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain, - www.
Rui Maciel <ru********@gmail.comwrites:
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?
Most "structured" control-flow constructs correspond more or less
directly to some concept in the real-world thing that you're
modelling. An if, if/else, or switch statement corresponds to making
a decision and acting on it. A loop corresponds to doing something
repeatedly. A function call corresponds to doing a bunch of related
stuff viewed as a single task.
A goto statement, though, *usually* corresponds only to a construct
within your program, not something in the real world. And it's been
argued that it's the label that's the real problem, not the goto.
When you look at a label in your code, you can't tell how you got
there without, in the worst case, analyzing the whole program; your
preconditions are messed up.
A finite state machine, though, is the exception to this (and the only
one I can think of). A label corresponds to a state in the machine; a
goto corresponds to a transition from one state to another. If you
write your code carefully, the code itself perfectly reflects the
structure of the thing that you're modelling. If you end up with
spaghetti code, it's only because you're modelling a spaghetti
machine.
On the other hand, there is another obvious way to implement a finite
state machine, using a variable (likely an enum) to represent the
current state, and a switch statement within a loop. The current
state is represented as the value of a variable rather than where you
currently are in the running program, and a state transition is done
by setting the variable rather than by executing a goto. This makes
it easier to execute common code regardless of the state, for example
by adding:
printf("state = %d\n", state);
at the top of the loop. It also lets you implement more complex
situations, such as having two simultaneous state machines; just store
their states in two variables.
If you're sure your state machine is going to remain simple enough,
you can go ahead and use gotos if you like. But consider using a
switch in a loop if you might need the additional flexibility later
on.
(The other cases in C where gotos are reasonable, IMHO, are
multi-level break and continue, and bailing out of a nested control
structure when an error occurs. But these are necessary only because
C lacks explicit multi-level break and continue statements and
exception handling. In a language that does support these constructs
directly, using goto for them would be very poor style.)
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
On Fri, 09 Feb 2007 17:19:00 -0800, Keith Thompson <ks***@mib.org>
wrote:
>A goto statement, though, *usually* corresponds only to a construct
within your program, not something in the real world. And it's been
argued that it's the label that's the real problem, not the goto.
When you look at a label in your code, you can't tell how you got
there without, in the worst case, analyzing the whole program; your
preconditions are messed up.
Yes and no. A goto statement, e.g., goto X, says that the next thing to
do is X. The implication of this is that when we do X, it shouldn't
matter how we got there. In other words if there is a precondition that
is true whenever we goto X then the semantics of the goto construct are
satisfied. The problem with gotos in unstructured code is that there
are no defined preconditions for labels and consequently there is no
check at the goto as to whether preconditions are met.
"Christopher Layne" <cl****@com.anodizedwrote in message
news:11***********@news-west.n...
Richard Heathfield wrote:
>Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
When you look at a label in your code, you can't tell how you got
there without, in the worst case, analyzing the whole program; your
preconditions are messed up.
Why analyze the whole program? a label does not have complete program scope
so you know you got there from within the same function.
Roberto Waltman wrote:
For some reason I have never seen FSMs as anything other than tables
(with or without function pointers,) and felt that straight code,
switch statements, etc. are the wrong/unnatural way of implementing
them. Seems to be the other way around for most people.
A simple implementation follows. It is easily extended with default
actions, default transitions for given events, timeouts, etc.
Please note that:
(a) The linear search approach will be inefficient for large FSMs
Which is why you see a lot of methods using switch, gotos, and tables of
function pointers.
Serve Laurijssen wrote:
>And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
tongue in cheek.
"Serve Laurijssen" <se*@n.tkwrites:
"Christopher Layne" <cl****@com.anodizedwrote in message
news:11***********@news-west.n...
>Richard Heathfield wrote:
>>Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
What definition would that be?
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"Serve Laurijssen" <se*@n.tkwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>When you look at a label in your code, you can't tell how you got
there without, in the worst case, analyzing the whole program; your
preconditions are messed up.
Why analyze the whole program? a label does not have complete program scope
so you know you got there from within the same function.
True.
Of course, in the *worst* case the whole program is one function.
8-)}
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Serve Laurijssen wrote:
"Christopher Layne" <cl****@com.anodizedwrote in message
news:11***********@news-west.n...
>Richard Heathfield wrote:
>>Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
Bertrand Russell said (among other things)..
"All generalizations are false, including this one."
--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Keith Thompson wrote, On 10/02/07 23:54:
"Serve Laurijssen" <se*@n.tkwrites:
>"Christopher Layne" <cl****@com.anodizedwrote in message
news:11***********@news-west.n...
>>Richard Heathfield wrote:
Yes, and it's this - that there is a huge body of experience within the
profession to show that structured programming constructs are a massive
improvement on unconditional jumps, with a real payoff in maintenance
cost reduction. A typical well-coded state machine will comprise a loop
containing a switch statement, with each case relating to a state and
selecting a new state according to circumstances.
And yet the one with unconditional jumps will end up being faster. :D
such general statements are, by definition, false
What definition would that be?
The definition of the C language which allows implementations to make
the one with unconditional jumps slower ;-)
--
Flash Gordon
On Feb 9, 8:14 am, Rui Maciel <rui.mac...@gmail.comwrote:
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.
Correct. The C language standard itself creates this problem, for
really, no good reason. The simplest way to improve the C standard
for finite state machines is to extend either the continue or goto
statements to be able to go to a specific case label. In that way a
FSM can be implemented inside of a switch statement without paying the
exorbitant cost of rerunning a literal switch operation on every state
transition. This kind of thinking is basically beyond what the C
standards committee is capable of conceiving.
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
In the C language? I'm afraid so. The cleaner *LOOKING* solution is
a switch() inside of a for(), but its not *that* much cleaner and it
is a *HELL* of a lot slower.
[...] or is it
unjustified and there is some godsend method which I'm missing out on?
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
In the C language? I'm afraid so. The cleaner *LOOKING* solution is
a switch() inside of a for(), but its not *that* much cleaner and it
is a *HELL* of a lot slower.
I know you know your stuff Paul, but don't you think "a hell of a lot slower"
is a bit of an overstatement?
We're talking a single compare here within the switch and then a jump.
And that's not even considering what the compiler might optimize it to in the
long run.
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
I don't think the overhead is *that* bad. we******@gmail.com wrote:
>
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
What's wrong with nested switch statements or tables of function pointers?
--
Ian Collins.
On Feb 10, 5:26 pm, Christopher Layne <cla...@com.anodizedwrote:
websn...@gmail.com wrote:
In the C language? I'm afraid so. The cleaner *LOOKING* solution is
a switch() inside of a for(), but its not *that* much cleaner and it
is a *HELL* of a lot slower.
I know you know your stuff Paul, but don't you think "a hell of a lot
slower" is a bit of an overstatement?
The equivalent of an extra branch miss *PER* state transition. On
today's processors that's about 15 clocks or so. Think about that in
terms of a parser implemented as a FSM, where you are expecting each
state to be processed in, say, 5 clocks or so plus, say, a randomly
predicted branch (so half of those 15 clocks) at about 8 clocks. So
by adding an extra mis-predicted branch, you've just halved your
performance (a direct goto has an amortized cost of about 1 clock; but
it can be less in optimal circumstances).
We're talking a single compare here within the switch and then a jump.
We're talking about doing the switch in the first place. switch's
cannot be well predicted unless they follow a trivial pattern with at
most two branch targets. In general, for most FSMs, switch's cannot
be predicted at all.
And that's not even considering what the compiler might optimize it to in
the long run.
There's not really anything the compiler can do unless its a forever
for (as in for(;;)) and the compiler is willing and able to do some
really serious optimizations for switches (something I have never
seen.)
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
I don't think the overhead is *that* bad.
Look. A few years back here, someone dared to challenge me to a
direct competition on this very issue for implementing a CSV parser
right here in this very newsgroup. We both implemented it using
FSMs. After he finally figured out that fread() can be faster then
millions of fgetc()'s (I basically told him so, so that the
competition would not be a complete joke), the real competition began,
and I was still able to clean his clock. Not even James Antill was
able to post much of a threat. The two other "competitors" in this
little duel, each had their own agenda and were incentivised to beat
me (the first, as a matter of honor/pride, and the second to push his
own string library).
Why couldn't they beat me? Because I was the only one who implemented
the FSM with gotos. And that was just too "gross" for them to deal
with. But the performance difference is very measurable.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/
On Feb 10, 5:34 pm, Ian Collins <ian-n...@hotmail.comwrote:
websn...@gmail.com wrote:
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
What's wrong with nested switch statements or tables of function pointers?
Well, nothing if you don't care about performance. You can use bubble
sorts too if you like. Have a blast.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com writes:
On Feb 9, 8:14 am, Rui Maciel <rui.mac...@gmail.comwrote:
>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.
Correct. The C language standard itself creates this problem, for
really, no good reason. The simplest way to improve the C standard
for finite state machines is to extend either the continue or goto
statements to be able to go to a specific case label. In that way a
FSM can be implemented inside of a switch statement without paying the
exorbitant cost of rerunning a literal switch operation on every state
transition. This kind of thinking is basically beyond what the C
standards committee is capable of conceiving.
[...]
Ignoring the gratuitous insults, there's no reason you can't have
labels within a switch statement.
switch (x) {
case FOO: FOO:
/* do some stuff */
break;
case BAR: BAR:
/* do some other stuff */
break;
/* etc. */
}
Wrap it in a macro if you like:
#define LABEL(name) case name: name:
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this. we******@gmail.com wrote:
On Feb 10, 5:34 pm, Ian Collins <ian-n...@hotmail.comwrote:
>>websn...@gmail.com wrote:
>>>No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
What's wrong with nested switch statements or tables of function pointers?
Well, nothing if you don't care about performance. You can use bubble
sorts too if you like. Have a blast.
Assuming the branch logic dominates over the state actions, which would
appear to be both a premature and speculative optimisation.
I may well be wrong, I've only ever implemented FSMs (using function
pointers) on CPUs without an instruction cache.
Care to post an example?
--
Ian Collins. we******@gmail.com wrote:
The equivalent of an extra branch miss *PER* state transition. On
today's processors that's about 15 clocks or so. Think about that in
terms of a parser implemented as a FSM, where you are expecting each
state to be processed in, say, 5 clocks or so plus, say, a randomly
predicted branch (so half of those 15 clocks) at about 8 clocks. So
by adding an extra mis-predicted branch, you've just halved your
performance (a direct goto has an amortized cost of about 1 clock; but
it can be less in optimal circumstances).
Allow me to do some of my own tests. I'm not disagreeing.
Look. A few years back here, someone dared to challenge me to a
direct competition on this very issue for implementing a CSV parser
right here in this very newsgroup. We both implemented it using
FSMs. After he finally figured out that fread() can be faster then
millions of fgetc()'s (I basically told him so, so that the
competition would not be a complete joke), the real competition began,
and I was still able to clean his clock. Not even James Antill was
able to post much of a threat. The two other "competitors" in this
little duel, each had their own agenda and were incentivised to beat
me (the first, as a matter of honor/pride, and the second to push his
own string library).
Why couldn't they beat me? Because I was the only one who implemented
the FSM with gotos. And that was just too "gross" for them to deal
with. But the performance difference is very measurable.
http://groups.google.com/group/comp....69b3cbee182484
That one?
On Feb 10, 6:29 pm, Christopher Layne <cla...@com.anodizedwrote:
websn...@gmail.com wrote:
The equivalent of an extra branch miss *PER* state transition. On
today's processors that's about 15 clocks or so. Think about that in
terms of a parser implemented as a FSM, where you are expecting each
state to be processed in, say, 5 clocks or so plus, say, a randomly
predicted branch (so half of those 15 clocks) at about 8 clocks. So
by adding an extra mis-predicted branch, you've just halved your
performance (a direct goto has an amortized cost of about 1 clock; but
it can be less in optimal circumstances).
Allow me to do some of my own tests. I'm not disagreeing.
Good man. Find out for yourself.
Look. A few years back here, someone dared to challenge me to a
direct competition on this very issue for implementing a CSV parser
right here in this very newsgroup. We both implemented it using
FSMs. After he finally figured out that fread() can be faster then
millions of fgetc()'s (I basically told him so, so that the
competition would not be a complete joke), the real competition began,
and I was still able to clean his clock. Not even James Antill was
able to post much of a threat. The two other "competitors" in this
little duel, each had their own agenda and were incentivised to beat
me (the first, as a matter of honor/pride, and the second to push his
own string library).
Why couldn't they beat me? Because I was the only one who implemented
the FSM with gotos. And that was just too "gross" for them to deal
with. But the performance difference is very measurable.
http://groups.google.com/group/comp....hread/86a3ddf0...
That one?
That's actually a follow up involving Michael B. Allen. (It all
started when he made the ridiculous claim that the C std library could
not be beat in terms of performance on strings.)
This is the original thread that I was thinking of: http://groups.google.com/group/comp....3b05cfb3818d7/
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/
On Feb 10, 6:25 pm, Ian Collins <ian-n...@hotmail.comwrote:
websn...@gmail.com wrote:
On Feb 10, 5:34 pm, Ian Collins <ian-n...@hotmail.comwrote:
>websn...@gmail.com wrote:
No you pretty much got it. In C, FSMs are gross, because the only
acceptable way of doing them is with gotos.
>What's wrong with nested switch statements or tables of function
pointers?
Well, nothing if you don't care about performance. You can use bubble
sorts too if you like. Have a blast.
Assuming the branch logic dominates over the state actions, which would
appear to be both a premature and speculative optimisation.
Sure, sometimes 15 clocks doesn't matter. So your per-state
operations needs to be 300-1000 clocks (or about 600 to 3000 pipelined
x86 instructions) before you decide that state transition performance
isn't that important. (Just like bubble sort for 25 elements is
probably good enough.) Of course, its easy to find examples where the
the per-state operations are way less than that (any parser). I can't
think of a single counter example where the state transition is really
high like that off the top of my head though. Perhaps you can?
I may well be wrong, I've only ever implemented FSMs (using function
pointers) on CPUs without an instruction cache.
Care to post an example?
In my response to Christopher Layne you have direct examples of two
users implementing "for() switch()" based state machines, and myself
who made a goto dominated state machine implementation. You can go
download those and see for yourself. They complained that my
implementation was obfuscated, because of the gotos, but of course
that was as a cover for the fact that my solution comes out faster
precisely because of this.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
On Feb 10, 6:25 pm, Ian Collins <ian-n...@hotmail.comwrote:
>>I may well be wrong, I've only ever implemented FSMs (using function
pointers) on CPUs without an instruction cache.
Care to post an example?
In my response to Christopher Layne you have direct examples of two
users implementing "for() switch()" based state machines, and myself
who made a goto dominated state machine implementation. You can go
download those and see for yourself. They complained that my
implementation was obfuscated, because of the gotos, but of course
that was as a cover for the fact that my solution comes out faster
precisely because of this.
OK, I will. I must admit I've never looked at using gotos for FSMs.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
By the way, your sig appears to be missing the space after the --, so
some news readers (like Mozilla) don't pick it up.
--
Ian Collins. we******@gmail.com wrote:
In my response to Christopher Layne you have direct examples of two
users implementing "for() switch()" based state machines, and myself
who made a goto dominated state machine implementation. You can go
download those and see for yourself. They complained that my
implementation was obfuscated, because of the gotos, but of course
that was as a cover for the fact that my solution comes out faster
precisely because of this.
I'm checking out the code right now.
BTW: This line fails parsing:
test5.csv:"1234 West "Q" St. (for "Quantum", or "Quality")", 0
Whereas this line does not:
test6.csv:"1234 West ""Q"" St. (for ""Quantum"", or ""Quality"")", 0
Should that be the case?
On Feb 10, 6:06 pm, Keith Thompson <k...@mib.orgwrote:
websn...@gmail.com writes:
On Feb 9, 8:14 am, Rui Maciel <rui.mac...@gmail.comwrote:
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.
Correct. The C language standard itself creates this problem, for
really, no good reason. The simplest way to improve the C standard
for finite state machines is to extend either the continue or goto
statements to be able to go to a specific case label. In that way a
FSM can be implemented inside of a switch statement without paying the
exorbitant cost of rerunning a literal switch operation on every state
transition. This kind of thinking is basically beyond what the C
standards committee is capable of conceiving.
[...]
Ignoring the gratuitous insults, there's no reason you can't have
labels within a switch statement.
switch (x) {
case FOO: FOO:
/* do some stuff */
break;
case BAR: BAR:
/* do some other stuff */
break;
/* etc. */
}
Wrap it in a macro if you like:
#define LABEL(name) case name: name:
Not a bad idea, assuming you have only one FSM in a given function
scope. Of course, you are still using gotos as well. (See, this is
what structured programming is all about -- no you won't find
"structured programming" in the C language standard ...)
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/
On Feb 10, 7:24 pm, Christopher Layne <cla...@com.anodizedwrote:
websn...@gmail.com wrote:
In my response to Christopher Layne you have direct examples of two
users implementing "for() switch()" based state machines, and myself
who made a goto dominated state machine implementation. You can go
download those and see for yourself. They complained that my
implementation was obfuscated, because of the gotos, but of course
that was as a cover for the fact that my solution comes out faster
precisely because of this.
I'm checking out the code right now.
BTW: This line fails parsing:
test5.csv:"1234 West "Q" St. (for "Quantum", or "Quality")", 0
Whereas this line does not:
test6.csv:"1234 West ""Q"" St. (for ""Quantum"", or ""Quality"")", 0
Should that be the case?
Yes, I did have some examples that were not parsable for severe
conditions testing purposes. I'm one of these people who doesn't
think "Undefined Behaviour at the least provocation" is an acceptable
state of affairs.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ This thread has been closed and replies have been disabled. Please start a new discussion. |
