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. Advertisements

  2. dr.oktopus

    K4 Monk Guest

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

  3. dr.oktopus

    dr.oktopus Guest

    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. 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 Doubez, Mar 1, 2011
    #4
  5. dr.oktopus

    James Kanze Guest

    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, Mar 2, 2011
    #5
  6. dr.oktopus

    dr.oktopus Guest

    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
    Yes, I wanted to find a better (and elegant) approach :)
     
    dr.oktopus, Mar 2, 2011
    #7
  8. 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 Doubez, Mar 2, 2011
    #8
  9. dr.oktopus

    James Kanze Guest

    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, Mar 3, 2011
    #9
  10. dr.oktopus

    Larry Evans Guest

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

    Jeff Flinn Guest

    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


    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. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.