Horror! Using goto statement in finite state machines?

Discussion in 'C Programming' started by Rui Maciel, Feb 9, 2007.

  1. Rui Maciel

    Rui Maciel Guest

    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:
     
    Rui Maciel, Feb 9, 2007
    #1
    1. Advertising

  2. Rui Maciel

    Ben Pfaff Guest

    Rui Maciel <> writes:

    > 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

    http://benpfaff.org
     
    Ben Pfaff, Feb 9, 2007
    #2
    1. Advertising

  3. 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.
     
    Richard Heathfield, Feb 9, 2007
    #3
  4. In article <45cc9e06$0$4471$>,
    Rui Maciel <> wrote:
    >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
     
    Walter Roberson, Feb 9, 2007
    #4
  5. >>>>> "RM" == Rui Maciel <> writes:

    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



    --
    Charlton Wilbur
     
    Charlton Wilbur, Feb 9, 2007
    #5
  6. Rui Maciel

    santosh Guest

    Charlton Wilbur wrote:
    > >>>>> "RM" == Rui Maciel <> writes:

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

    <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.
     
    santosh, Feb 9, 2007
    #6
  7. Rui Maciel

    Flash Gordon Guest

    santosh wrote, On 09/02/07 18:19:
    > Charlton Wilbur wrote:
    >>>>>>> "RM" == Rui Maciel <> writes:

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

    > <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
     
    Flash Gordon, Feb 9, 2007
    #7
  8. Rui Maciel

    Rui Maciel Guest

    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:
     
    Rui Maciel, Feb 9, 2007
    #8
  9. Rui Maciel

    Rui Maciel Guest

    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:
     
    Rui Maciel, Feb 9, 2007
    #9
  10. Rui Maciel

    Michael Guest

    On Feb 9, 8:14 am, Rui Maciel <> wrote:
    > 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
     
    Michael, Feb 9, 2007
    #10
  11. "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 ]
     
    Roberto Waltman, Feb 9, 2007
    #11
  12. Rui Maciel

    Rui Maciel Guest

    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:
     
    Rui Maciel, Feb 9, 2007
    #12
  13. Rui Maciel

    Rui Maciel Guest

    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:
     
    Rui Maciel, Feb 9, 2007
    #13
  14. Rui Maciel

    Ian Collins Guest

    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.
     
    Ian Collins, Feb 9, 2007
    #14
  15. "Michael" <> wrote 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.
     
    Malcolm McLean, Feb 9, 2007
    #15
  16. 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.
     
    Christopher Layne, Feb 9, 2007
    #16
  17. 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"
     
    Christopher Layne, Feb 9, 2007
    #17
  18. Rui Maciel

    Lew Pitcher Guest

    On Feb 9, 2:47 pm, 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.


    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
     
    Lew Pitcher, Feb 9, 2007
    #18
  19. Rui Maciel

    Eric Sosman Guest

    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.

    --
     
    Eric Sosman, Feb 9, 2007
    #19
  20. On Fri, 09 Feb 2007 19:26:52 +0000, 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?


    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, Feb 9, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sidney Cadot
    Replies:
    0
    Views:
    2,419
    Sidney Cadot
    Apr 18, 2004
  2. Martin Maurer
    Replies:
    3
    Views:
    689
    Andrew Hall
    Jun 14, 2004
  3. Henrik Vallgren
    Replies:
    0
    Views:
    804
    Henrik Vallgren
    Jun 15, 2004
  4. Stephan Kuhagen
    Replies:
    12
    Views:
    589
    Stephan Kuhagen
    Nov 30, 2006
  5. Aardalath
    Replies:
    4
    Views:
    429
    Aardalath
    Jan 27, 2009
Loading...

Share This Page