finite state machine

Discussion in 'C++' started by dr.oktopus, Mar 1, 2011.

  1. dr.oktopus

    dr.oktopus Guest

    Hello,
    I am moving my first steps into the wonderful world of oop.
    I have considered this approach in writing a fsm.

    class fsm {

    public:
    void run_fsm (void); // advance machine for 1 step

    private:
    void (*state) (void);

    void state1 (void);
    void state2 (void);
    ..
    };

    void fsm::run_fsm (void)
    {
    state();
    }

    void fsm::state1 (void)
    {
    ..
    if (statehastochangetostate2)
    state = state2;
    ..
    }

    void fsm::state2 (void)
    {
    ..
    if (statehastochangetostate1)
    state = state1;
    ..
    }

    It is a simple fsm, but what I would like to know
    are your opinions about this approach.
    I don't try to compile it (I don't have a compiler at hand),
    but I think it should work.
    Suggestions?
    Thanks,
    willy
     
    dr.oktopus, Mar 1, 2011
    #1
    1. Advertising

  2. dr.oktopus

    K4 Monk Guest

    On Mar 2, 2:55 am, "dr.oktopus" <> wrote:
    > Hello,
    > I am moving my first steps into the wonderful world of oop.
    > I have considered this approach in writing a fsm.
    >
    > class fsm {
    >
    > public:
    >         void run_fsm (void);  // advance machine for 1 step
    >
    > private:
    >         void (*state) (void);
    >
    >         void state1 (void);
    >         void state2 (void);
    >         ..
    >
    > };


    too many voids! aargh!
     
    K4 Monk, Mar 1, 2011
    #2
    1. Advertising

  3. dr.oktopus

    dr.oktopus Guest

    >
    > too many voids! aargh!- Nascondi testo citato
    >


    Yes, I know, I know. I forgot that c++ hates voids.
    (I come from the C universe).
    But do you think apart that, it is good, however?
     
    dr.oktopus, Mar 1, 2011
    #3
  4. On 1 mar, 22:55, "dr.oktopus" <> wrote:
    > Hello,
    > I am moving my first steps into the wonderful world of oop.
    > I have considered this approach in writing a fsm.
    >
    > class fsm {
    >
    > public:
    >         void run_fsm (void);  // advance machine for 1 step
    >
    > private:
    >         void (*state) (void);
    >
    >         void state1 (void);
    >         void state2 (void);
    >         ..
    >
    > };
    >
    > void fsm::run_fsm (void)
    > {
    >         state();
    >
    > }
    >
    > void fsm::state1 (void)
    > {
    >         ..
    >         if (statehastochangetostate2)
    >                 state = state2;
    >         ..
    >
    > }
    >
    > void fsm::state2 (void)
    > {
    >         ..
    >         if (statehastochangetostate1)
    >                 state = state1;
    >         ..
    >
    > }
    >
    > It is a simple fsm, but what I would like to know
    > are your opinions about this approach.
    > I don't try to compile it (I don't have a compiler at hand),
    > but I think it should work.


    It should not. state has type 'function pointer' while AHAIS it should
    be a pointer to a member function:

    void (fsm::*state)();

    And it is set like that:
    state = &fsm::state1;

    In addition to that, you have states but no events (and associated
    actions), no context and the transitions are not apparent. Your class
    is not testable.

    There is more than one way to design a FSM in C++ and IMO it would
    help you to read a way or two before trying to design your own or a

    --
    Michael
     
    Michael Doubez, Mar 1, 2011
    #4
  5. dr.oktopus

    James Kanze Guest

    On Mar 1, 9:55 pm, "dr.oktopus" <> wrote:

    > I am moving my first steps into the wonderful world of oop.
    > I have considered this approach in writing a fsm.


    > class fsm {
    > public:
    > void run_fsm (void); // advance machine for 1 step


    > private:
    > void (*state) (void);
    >
    > void state1 (void);
    > void state2 (void);
    > ..
    > };


    > void fsm::run_fsm (void)
    > {
    > state();
    > }


    > void fsm::state1 (void)
    > {
    > ..
    > if (statehastochangetostate2)
    > state = state2;
    > ..
    > }


    > void fsm::state2 (void)
    > {
    > ..
    > if (statehastochangetostate1)
    > state = state1;
    > ..
    > }


    > It is a simple fsm, but what I would like to know
    > are your opinions about this approach.


    For starters, if you want to use a pointer to function, it would
    be a pointer to member function. But IMHO, it's not a good
    approach. For very simple FSMs, the C solution of nested switch
    statements works well, even in C++, and I've used it numerous
    times. For anything non-trivial, however, I'll use a variant of
    the GoF State pattern: the FSM uses a State interface (and
    abstract class) with virtual functions for each event. Plus
    a derived class for each state, with a static instance of the
    class. Something like:

    class State
    {
    void* operator new(size_t);
    void operator delete(void*);

    public:
    virtual State const* event1() const { return this; }
    virtual State const* event2() const { return this; }
    // ...
    };

    The default implementation of each function, above, just
    ignores the event. Depending on the application, you may want
    to make the functions pure virtual, requiring every derived
    class to override them, or treat an unexpected event as an error
    condition.

    Again depending on the application, you might want to pass some
    data to the events, as an argument.

    Finally, you derive a separate class for each state, and create
    a static instance of it, somewhere where the other states can
    find it. (If all of the states are defined in the same source
    file, putting them in an unnamed namespace is a good solution.
    Otherwise, making them protected static data members of State
    works as well. And is the solution used in the GoF book, which
    predates namespaces.)

    A concrete event function might look something like:

    State const*
    SomeState::eventn() const
    {
    // State transition processing...
    return &nextState;
    }

    --
    James Kanze
     
    James Kanze, Mar 2, 2011
    #5
  6. dr.oktopus

    dr.oktopus Guest

    On 1 Mar, 23:22, Michael Doubez <> wrote:
    > On 1 mar, 22:55, "dr.oktopus" <> wrote:
    >
    >
    >
    >
    >
    > > Hello,
    > > I am moving my first steps into the wonderful world of oop.
    > > I have considered this approach in writing a fsm.

    >
    > > class fsm {

    >
    > > public:
    > >         void run_fsm (void);  // advance machine for 1 step

    >
    > > private:
    > >         void (*state) (void);

    >
    > >         void state1 (void);
    > >         void state2 (void);
    > >         ..

    >
    > > };

    >
    > > void fsm::run_fsm (void)
    > > {
    > >         state();

    >
    > > }

    >
    > > void fsm::state1 (void)
    > > {
    > >         ..
    > >         if (statehastochangetostate2)
    > >                 state = state2;
    > >         ..

    >
    > > }

    >
    > > void fsm::state2 (void)
    > > {
    > >         ..
    > >         if (statehastochangetostate1)
    > >                 state = state1;
    > >         ..

    >
    > > }

    >
    > > It is a simple fsm, but what I would like to know
    > > are your opinions about this approach.
    > > I don't try to compile it (I don't have a compiler at hand),
    > > but I think it should work.

    >
    > It should not. state has type 'function pointer' while AHAIS it should
    > be a pointer to a member function:
    >
    > void (fsm::*state)();
    >
    > And it is set like that:
    > state = &fsm::state1;
    >


    Right, it is a member which other member functions (of the same
    prototype) can be assigned to.

    state = &fsm::state1 cannot be summerized as state = state1 (like
    usually you can refer to members
    - obviously with your opportune declaration of fsm) ?
     
    dr.oktopus, Mar 2, 2011
    #6
  7. dr.oktopus

    dr.oktopus Guest

    > For very simple FSMs, the C solution of nested switch
    > statements works well, even in C++, and I've used it numerous
    > times.


    Yes, I wanted to find a better (and elegant) approach :)
     
    dr.oktopus, Mar 2, 2011
    #7
  8. On 2 mar, 21:49, "dr.oktopus" <> wrote:
    > > For very simple FSMs, the C solution of nested switch
    > > statements works well, even in C++, and I've used it numerous
    > > times.

    >
    > Yes, I wanted to find a better (and elegant) approach :)


    As James Kanze mentioned, the State pattern is the most popular and
    has many advantages.

    You could start here:
    http://accu.org/index.php/journals/1548

    You can also generate it from a bunch of template machinery and
    represent it as a transition table but it is not for the faint of
    heart (IIRC there is the macho and fsm libraries).

    --
    Michael
     
    Michael Doubez, Mar 2, 2011
    #8
  9. dr.oktopus

    James Kanze Guest

    On Mar 2, 9:56 pm, Michael Doubez <> wrote:
    > On 2 mar, 21:49, "dr.oktopus" <> wrote:


    > > > For very simple FSMs, the C solution of nested switch
    > > > statements works well, even in C++, and I've used it numerous
    > > > times.


    > > Yes, I wanted to find a better (and elegant) approach :)


    > As James Kanze mentioned, the State pattern is the most popular and
    > has many advantages.


    > You could start here:http://accu.org/index.php/journals/1548


    > You can also generate it from a bunch of template machinery and
    > represent it as a transition table but it is not for the faint of
    > heart (IIRC there is the macho and fsm libraries).


    It's very simple to write a small generator in a scripting
    language to generate most of the boilerplate of an FSM. It
    would only take about 10/15 lines of AWK to convert something
    like:
    [<state>]
    <event> <nextState> <action>
    ...
    into the declarations and definitions of the derived classes
    used in the State pattern. Whether it's worth it or not...
    I've generally found that with a good editor, you can type to
    full text in as quickly as you can write the generator and the
    source it parses. So if you only need one FSM, it's probably
    not worth the bother. If you need a lot of them, however, it's
    worth considering.

    --
    James Kanze
     
    James Kanze, Mar 3, 2011
    #9
  10. dr.oktopus

    Larry Evans Guest

    Larry Evans, Mar 3, 2011
    #10
  11. dr.oktopus

    Jeff Flinn Guest

    Larry Evans wrote:
    > On 03/01/11 15:55, dr.oktopus wrote:
    >> Hello,
    >> I am moving my first steps into the wonderful world of oop.
    >> I have considered this approach in writing a fsm.
    >>

    > [snip]
    > Searching posts to boost development mailing list:
    >
    > http://www.boost.org/community/groups.html
    >
    > will show other ways of doing this. For example:
    >
    > http://article.gmane.org/gmane.comp.lib.boost.devel/109836/match=fsm
    >
    > HTH.
    >
    > -Larry


    More specifically there's the transition table approach of the Meta
    State Machine library described at:

    http://www.boost.org/doc/libs/1_46_0/libs/msm/index.html

    and the state char approach of the Statechart library at:

    http://www.boost.org/doc/libs/1_46_0/libs/statechart/doc/index.html

    Jeff
     
    Jeff Flinn, Mar 3, 2011
    #11
  12. dr.oktopus

    dr.oktopus Guest

    Ok. Thanks to all.
     
    dr.oktopus, Mar 3, 2011
    #12
  13. dr.oktopus

    DeMarcus Guest

    On 2011-03-01 22:55, dr.oktopus wrote:
    > Hello,
    > I am moving my first steps into the wonderful world of oop.
    > I have considered this approach in writing a fsm.
    >
    > class fsm {
    >
    > public:
    > void run_fsm (void); // advance machine for 1 step
    >
    > private:
    > void (*state) (void);
    >
    > void state1 (void);
    > void state2 (void);
    > ..
    > };
    >
    > void fsm::run_fsm (void)
    > {
    > state();
    > }
    >
    > void fsm::state1 (void)
    > {
    > ..
    > if (statehastochangetostate2)
    > state = state2;
    > ..
    > }
    >
    > void fsm::state2 (void)
    > {
    > ..
    > if (statehastochangetostate1)
    > state = state1;
    > ..
    > }
    >
    > It is a simple fsm, but what I would like to know
    > are your opinions about this approach.
    > I don't try to compile it (I don't have a compiler at hand),
    > but I think it should work.
    > Suggestions?
    > Thanks,
    > willy



    I don't have any suggestions but you can get more ideas from here.

    http://www.boost.org/doc/libs/1_46_0/libs/statechart/doc/index.html
    http://www.boost.org/doc/libs/1_46_0/libs/msm/doc/HTML/index.html

    Also the book C++ Template Metaprogramming by Abrahams and Gurtovoy
    contains a chapter on FSM.

    Hope this helps.

    /Daniel
     
    DeMarcus, Mar 9, 2011
    #13
    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. deejayfred
    Replies:
    0
    Views:
    581
    deejayfred
    Oct 2, 2003
  2. SomeDude
    Replies:
    3
    Views:
    3,222
    arant
    Aug 14, 2006
  3. Inderkal
    Replies:
    8
    Views:
    1,326
    rickman
    Dec 9, 2004
  4. Roberto Nunnari
    Replies:
    2
    Views:
    8,600
    Thomas Weidenfeller
    Feb 4, 2004
  5. Davide T

    "Tag" Finite State Machine

    Davide T, Dec 10, 2003, in forum: HTML
    Replies:
    5
    Views:
    432
    Eric Bohlman
    Dec 10, 2003
Loading...

Share This Page