cplusplus.co.il

Using the state design pattern to implement FSMs

Posted on: 13/11/2009

The State design pattern is a very useful design pattern. In this article we will exploit it to provide a very slick and elegant implementation of a Finite State Machine (FSM).

First of all, a FSM consists of a finitie number of states and a predefined set of rules defining the transitions between all these states. Each state can either ACCEPT or REJECT the input – the FSM accepts the input IFF it ends up on an accepting state at the end of execution. In our design, each state will be modeled by a distinct class derived from an abstract base State class. Each state class will also contain all of its relevant transition logic. This architecture will enable us to provide a very flexibe, powerful, yet intuitive and simple, implementation of any FSM.

The FSM we are going to build will be a Deterministic pushdown automaton. In our case it means it will have a stack (or, extra memory) in each state. Please note that since we’re programming and don’t have to really follow all FSM rules, some of our states will use the stack to descide whether to ACCEPT or REJECT, at runtime.

The FSM we are going to implement will answer a very specific calling; it has to accept only inputs of the form “aa..abb..b” where the number of a’s and b’s is equal. For example: ACCEPT “ccdd” and REJECT “rrrrfff”. I would like to review this implementation from the buttom and up, so here’s how usage of our FSM is going to look like:

int main () {
    State::StatePtr curr(new Initial());
    BOOST_FOREACH (char s, std::string("aaabbb"))
        curr = curr->next(s);
    std::cout << (curr->accepted() ? "Accepted!" : "Rejected!") << std::endl;
    // prints: Accepted!
    return 0;
}

Like you can see, each state will return the next state upon receiving the next input, through invocation of its next() method. This kind of design is very easy to extend, maintain, and understand, and is very powerful in what it can achieve.

Now, let’s review how State is implemented. As you could guess, its an abstract base class, defining the interface of any State class: it defines the next() method which returns the next state, and the accepted() method which answers the most important question here.

struct State {
    typedef boost::shared_ptr<State> StatePtr;

    virtual StatePtr next (char input) const = 0;
    virtual bool accepted () const = 0;

    virtual ~State () {}
};

Having seen the definition of an abstract State, it’s time to review all the concrete states of our FSM.

The first interesting state is the Initial one. It simply provides the required transition logic, and accepts the current state – since the empty input is indeed of the desired form.

struct Initial : State {
    StatePtr next (char input) const;
    bool accepted () const { return true; }
};

State::StatePtr Initial::next (char input) const {
    return StatePtr(new Incrementing(input, 1));
}

Looking at Initial::next method, we are left wondering what is this Incrementing state? Incrementing state just keeps a count of the number of times the first char has appeared. That’s why it requires the identity of the char (input) and the number of times it has appeard in its constructor. Let’s have a peak at the implementation of the Incrementing class:

struct Incrementing : CountingState {
    Incrementing (char chr, int cnt) :CountingState(chr, cnt) {}

    StatePtr next (char input) const;
};

State::StatePtr Incrementing::next (char input) const {
    if (input == chr_)
        return StatePtr(new Incrementing(chr_, cnt_+1));
    return StatePtr(new Decrementing(input, cnt_-1));
}

The incrementing class is very simple: it keeps track of the number of appearances of the given char. The transition is to the Decrementing state, which basically just decrements the same count. The input is ofcourse accepted IFF the count is zero. At this point you may be wondering what is this inherited CountingState class? Well, since Incrementing and Decrementing are very close in nature, their common properties were refactored into an abstract CountingState class to prevent code duplication (or even worse, copy&paste!). Achieving same goal with better means is left as an excercise.

The code of CountingState and Decrementing states is pretty straighforward and will be provided below, so there’s no need to go over it. The next interesting bit is the Trap state, a state you are very likely to meet in most FSMs.

struct Trap : State {
    StatePtr next (char) const;
    bool accepted () const { return false; }
};

State::StatePtr Trap::next (char) const {
    return StatePtr(new Trap());
}

This state is exactly like its called – a trap. Transition to this state is carried out when there’s no hope of ever reaching an accepting state. In our case, the Decrementing state is passing control to this state when a different character is received as input. We could ofcourse shift to this state at more occasions (for instance, when count goes below zero), but it isn’t essential.
An important thing to notice here is that the parameter of Trap::next() is left unnamed, which keeps the compiler from complaining about unused variables (as a side note, I’d love to mention I strongly believe in warning-free compilations).

— Please note that the supplied implementation can be improved: if you’re worried about all the dynamic memory management overhead, it could be easily avoided by using custom allocators or the FlyWeight design pattern, or various different other solutions. Also, all states could be encapsulated within a proper class (represnting the entire FSM) etc. I was only trying to show the principle.

Here’s the complete source code:

#include <string>
#include <iostream>
#include <boost/foreach.hpp>
#include <boost/shared_ptr.hpp>

// ---- states ----

struct State {
    typedef boost::shared_ptr<State> StatePtr;

    virtual StatePtr next (char input) const = 0;
    virtual bool accepted () const = 0;

    virtual ~State () {}
};

struct Initial : State {
    StatePtr next (char input) const;
    bool accepted () const { return true; }
};

struct Trap : State {
    StatePtr next (char) const;
    bool accepted () const { return false; }
};

struct CountingState : State {
        CountingState (char chr, int cnt) :chr_(chr), cnt_(cnt) {}
       
        bool accepted () const { return !cnt_; }

    protected:
        const char chr_;
        const int  cnt_;
};

struct Incrementing : CountingState {
    Incrementing (char chr, int cnt) :CountingState(chr, cnt) {}

    StatePtr next (char input) const;
};

struct Decrementing : CountingState {
    Decrementing (char chr, int cnt) :CountingState(chr, cnt) {}

    StatePtr next (char input) const;
};

// ---- transitions ----

State::StatePtr Initial::next (char input) const {
    return StatePtr(new Incrementing(input, 1));
}

State::StatePtr Trap::next (char) const {
    return StatePtr(new Trap());
}

State::StatePtr Incrementing::next (char input) const {
    if (input == chr_)
        return StatePtr(new Incrementing(chr_, cnt_+1));
    return StatePtr(new Decrementing(input, cnt_-1));
}

State::StatePtr Decrementing::next (char input) const {
    if (input == chr_)
        return StatePtr(new Decrementing(chr_, cnt_-1));
    return StatePtr(new Trap());
}

// ---- main(): test case ----

int main () {
    State::StatePtr curr(new Initial());
    BOOST_FOREACH (char s, std::string("aaabbb"))
        curr = curr->next(s);
    std::cout << (curr->accepted() ? "Accepted!" : "Rejected!") << std::endl;
    // prints: Accepted!
    return 0;
}
Advertisements

1 Response to "Using the state design pattern to implement FSMs"

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: