Back to ObjectValue Logo articles

         Finite State Machines: A Model of Behaviour for C++

Immo Hüneke

1          Introduction

Ralph Hodgson [1] writes “Reuse depends on the idea of ‘plugability’. Compatibility with the architecture of the new application requires our components to behave consistently.... Plugability exists in a framework when there are generalized classes which prescribe a model of behaviour.... for example the Model-View-Controller (MVC) architecture [3, 4]....  Apart from MVC, what other examples of architectures do we know? To progress on methods and reusability, a taxonomy of components and ways of describing and categorizing architectures are needed.”

This paper attempts to provide a partial answer by suggesting an “architecture” for the implementation of Finite State Machines in C++. It presents a small example of its use, based on Bill Birch’s idea for an FSM parser implemented in LISP with OO extensions [2].

2          Finite State Machines

Finite State Machines are objects characterized by a single state variable which determines all decisions. Incoming events are processed strictly according to the current state of the machine. After each event has been processed, the state is updated. FSMs are amenable to analysis by various mathematical techniques.

However, once coded, an FSM can be difficult to understand and therefore to maintain. Implementations generally resort to nested case statements or employ tables of pointers to functions. In most programming languages, there can be no compile-time safeguard that the index into a table or case statement will always be in the correct range.

Object-oriented languages offer a way forward through polymorphism. An FSM can be implemented as an object, which exploits polymorphism to generate different behaviours in response to an event dependent on the object’s current state.

3          Quote Parser Example

Here is an example of a very simple FSM that looks for quoted strings in a character stream, taken from Bill Birch’s paper. The desired function is to perform the following mapping:

Example Input

Example Output

I say, “now is the time ” for all good men “to come to ” the aid of “the party.”

now is the time
to come to
the party.

 

The finite state table for this FSM looks like this:

 

             States

Events

Inside quotes

Outside quotes

 

A quote character is received (‘"’).

Action: output the collected string from the buffer, terminated by a newline.

Action: reset the collection buffer.

 

 

New state: outside quotes.

New state: inside quotes.

 

Any non-quote character is received.

Action: add the character to the collection buffer.

Action: none.

 

 

New state: inside quotes.

New state: outside quotes.

 

The corresponding state transition diagram is shown below.

 

4          Implementation in an Object-Oriented Language

The language used in the example implementation is C++ release 2.0.

It was decided to represent each FSM and each state by an object. However, multiple instances of the FSM class may co-exist and share a single instance of each state. The states are all subclasses of a single abstract state class. The diagram below attempts to illustrate this idea.

 

 

4.1       The Test Program

The program merely has to create an instance of FSM and send a series of events to it. Here it is, in its entirety (for those who are unfamiliar with C++, the program declares the variable “fsm” to be of type “QuoteParser”):

#include "qparser.h"

#include "stream.h"

 

int main ()

{

        char c;

        QuoteParser fsm;

 

        while (cin.get (c))

                fsm.event (c);

}

 

4.2       The FSM Class

The class is coded in three files. Two of these are headers, the third contains the code for the member functions. Strictly speaking, if this class were to form part of a library, every member function should be coded as a separate file. However, the liberal use of virtual functions, which is recommended for future enhanceability, causes almost all function bodies to be incorporated in the finished program anyway.

The header is divided into two files, in order to hide the private and protected portions of the class declaration from the view of users of the class. First, the class declaration (qparser.h):

#ifndef QPARSERH

#define QPARSERH

 

class QuoteParser {

 

#include "qparser.hpr"  // private and/or protected members

 

public:

        QuoteParser ();

        virtual void event (char c);

        virtual ~QuoteParser () {delete buffer;}

};

 

#endif  QPARSERH

Next the private header file, qparser.hpr:

class QuoteParserState;

class PString;

 

protected:

        QuoteParserState* state;

        PString* buffer;

The primary interface of QuoteParser to clients is the event handler, QuoteParser::event (). There are also a constructor and a destructor function.

An earlier version of this paper used a more complex QuoteParser, which contained a buffer area and buffer control structures instead of simply a PString object. It therefore had to provide externally the buffer manipulation functions needed for the event processing in each state. At that time, the author thought it was a deficiency of C++ that there was no way to tell the compiler about the restriction that these interfaces were only for use by one other class.

However, it is now clear that this “deficiency” was in fact an indication that a separate class was required to hold the characters being accumulated. Such a class was produced (Pascal-like String or PString). It turns out that this new class is of much more general use than the earlier FSM. Its full listing is provided as an appendix. Not only can characters be added to the end of a PString, other PStrings or character strings can be appended as well. Moreover, the standard function operator<<() can be used for output, due to the fact that an implicit conversion to char* is provided.

Shown below is the implementation of the class, qparser.c. Notice the way in which the event handler works. It first decides what kind of event has been sent to the FSM. In many FSMs, this would not be required, since the event is identified outside the FSM itself. In fact, it is also possible to code the FSM in such a way that a different event handler function is called for each event type. This may be the most efficient in many cases.

Having identified the event, the handler calls the corresponding member function for the current state – QuoteParserState::aQuote () or QuoteParserState::aChar (). The value returned is the new state (and not just a symbol or code for a state).

Because the member variable state has the type QuoteParserState*, it can store pointers to subclasses of QuoteParserState. This is how C++ implements polymorphism. In this case, it means that state actually points to an instance of either QuoteParserStateIn or QuoteParserStateOut at any particular time. When the call is made, the virtual function table of the called class is used to look up the actual function which is executed. All this happens invisibly to the programmer.

#include "qparser.h"

#include "qpstate.h"

#include "pstring.h"

 

void QuoteParser::event (char c)

{

        if (c == '"')

                state = state->aQuote (*buffer);

        else

                state = state->aChar (*buffer, c);

}

 

QuoteParser::QuoteParser ()

{

        state = QuoteParserState::reset ();

        buffer = new PString;

}

 

4.3       The Abstract State Class

The abstract state class is required for two reasons.

          It permits the state variable of the FSM to have a polymorphic type which can hold pointers to instances of any state.

          It allows common behaviour of the subclasses (ie the concrete states) to be generalized to just one place.

The latter point requires some explanation. In most practical FSMs, a large proportion of the cells in the table contain the entry “error”. Such default behaviour can be specified once in the abstract class and simply inherited by all concrete states, which will override only the actions for valid combinations of event and state.

In some large FSMs it may prove useful to generate a hierarchy of abstract states above the concrete states; for example in communications protocols this would be used to group states which belong to the same phase of a session.

As before, the header file is divided into two physical files. The first one shown below is qpstate.h (notice that no constructor function is needed, as the class contains no non-static member variables):

#ifndef QPSTATEH

#define QPSTATEH

 

class PString;

 

class QuoteParserState {

 

#include "qpstate.hpr"          // private and/or protected members

 

public:

        virtual QuoteParserState* aChar (PString& s, char c)

                {return this;}

        virtual QuoteParserState* aQuote (PString& s)

                {return this;}

        static QuoteParserState* reset () {return out;}

        virtual ~QuoteParserState () {}

};

 

#endif  QPSTATEH

Next the private header file, qpstate.hpr:

protected:

        static QuoteParserState *in, *out;

There are two event-handling functions here, both of which define the default behaviour (do nothing, keep the same state). The third member function is declared static, which means that it can be called without requiring an actual instance of QuoteParserState to receive the function call. It is used merely to return the initial state for a newly-created FSM.

The two member variables are similarly declared static. This means that they are shared by all instances of this class (and, due to their “protected” status, of its subclasses as well). The purpose of these is to allow any state to find an instance (the only instance, in fact) of any other state, without resorting to global names.

The implementation module for the class, qpstate.c, initializes these member variables:

#include "qpstate.h"

#include "qpstin.h"

#include "qpstout.h"

 

QuoteParserState::in = new QuoteParserStateIn;

QuoteParserState::out = new QuoteParserStateOut;

No function bodies are required, as all the member functions are coded in line. If you follow the chain of cause and effect from the test program through the FSM class to the abstract state class, you will see that the static initialization above must always take place. Thus instances of the concrete states are created for use by the program if and only if the program calls the FSM.

4.4       The Concrete State Classes

The concrete state classes implement the desired behaviour of the FSM by redefining the abstract class’s event handling functions. The “in quotes” state is presented first. The header file is called qpstin.h:

#ifndef QPSTINH

#define QPSTINH

 

#include "qpstate.h"

 

class PString;

 

class QuoteParserStateIn : public QuoteParserState {

 

public:

        virtual QuoteParserState* aChar (PString& s, char c);

        virtual QuoteParserState* aQuote (PString& s);

};

 

#endif  QPSTINH

This class has no member variables at all. This follows from the fact that the state objects themselves have no state (ie they are re-entrant), which is a necessary condition if they are to be shared among all FSMs. However, in some practical FSMs it may be desirable to incorporate member variables such as statistical counts, so that a management function can determine how many times each state has been entered. Such counts would of course represent totals for all FSMs using the state.

The implementation is in qpstin.c:

#include "qpstin.h"

#include "pstring.h"

 

#include "stream.h"

 

QuoteParserState* QuoteParserStateIn::aChar (PString& s, char c)

{

        s += c;

        return this;

}

 

QuoteParserState* QuoteParserStateIn::aQuote (PString& s)

{

        cout << s << "\n";

        return out;

}

The “out of quotes” state is even simpler, since it inherits the default do-nothing action for a non-quoted character. The class declaration is in qpstout.h:

#ifndef QPSTOUTH

#define QPSTOUTH

 

#include "qpstate.h"

 

class PString;

 

class QuoteParserStateOut : public QuoteParserState {

 

public:

        virtual QuoteParserState* aQuote (PString& s);

};

 

#endif  QPSTOUTH

The implementation is in qpstout.c:

#include "qpstout.h"

#include "pstring.h"

 

QuoteParserState* QuoteParserStateOut::aQuote (PString& s)

{

        s.reset ();

        return in;

}

 

5          Discussion

5.1       Maintainability

This FSM worked first time when it was coded, which may be just a result of its extreme simplicity, but can also be taken as an indication that this approach to the coding of FSMs is likely to protect against programming errors.

The fact that each function corresponds to one cell in the table, with action and next-state neatly laid out one after the other, should make it easy to check that the table has been implemented correctly.

The complete absence of programmer-defined symbolic constants makes it possible for the compiler to check the syntactical correctness of the FSM. Errors are still possible, of course:

          Individual action sequences may have been incorrectly coded.

          The table may have been incorrect in the first place.

In the lifetime of an FSM, its behaviour may need to be modified in some way. Because a redesign of the table can be laborious using conventional languages, this sometimes leads to code which violates the purely state-driven approach.

The way in which the FSM has been implemented in the above example tends to discourage such programming practices because it prevents direct access to the internal variables of the FSM class or the buffer by the action routines.

5.2       Shared State Objects

Is it necessarily the case that one instance of each state class should be shared by all instances of the corresponding FSM class?

If this is not done, the implementor is faced with two possible choices:

1.         Create one instance of every state as soon as an instance of FSM is created.

2.         Create a new state object each time the FSM changes state, destroying the old state object.

Neither option appears as efficient as the static allocation of state objects in the example. Moreover, the static option shares with choice (1) the advantage that there can never be a memory allocation error during a state change.

There are conceivably situations under which the population of FSMs hardly changes during a program’s lifetime, and where it is desired to keep per-FSM data in each state. In these cases, choice (1) must be the correct option. However, the pointers in the abstract state class cannot then be static, and must be initialized in the constructor function for the class.

5.3       Where to put Data?

There are basically three places where data pertinent to the FSM can be stored:

1.         In the FSM class.

2.         In the state class.

3.         Outside (in some object with global scope).

Normally, the data will be stored in the FSM itself (or in another object towards which the FSM object has a pointer). Access routines will be provided whereby the action routines contained in the state objects may read and write the data. This ensures that all instances of the FSM are independent of each other.

Storage of variables in the state classes only makes sense if they are not shared between FSMs. If the states are replicated, the programmer can look for categories of data, such as the character buffer in the example above, which are meaningful only as long as the FSM remains in one specific state. These are candidates for storing in the state object.

Where an FSM is guaranteed never to be instantiated more than once in a program, other considerations may dictate that the data is stored globally. This kind of FSM is unlikely to be re-useable easily, however.

5.4       Genericity

It was originally intended to define a generic FSM to act as a base class for more specific FSMs. This class (or set of classes) would therefore be a vehicle for re-use.

In practice, it turns out that C++ does not lend itself easily to this form of re-use. Instead, the most convenient approach is to take an existing FSM class and to use a copy of its source code as the template for a new one.

The reason for this is to be found in the compile-time type checking performed by C++. Unlike Smalltalk-80, in which any message can be sent to any object, C++ checks for type conformance of all arguments and return values.

Because all the member functions of the state classes are application-specific, it transpires that there is no useful commonality left which could be generalized to an ancestor class. Similarly, the only member function of FSM which could be generalized is event (), but this is of no use because its argument types depend on the application.

5.5       Ease of Use

It has been suggested that even with the approach outlined above, large state machines will still be difficult to code and understand. It may therefore be necessary to provide a preprocessor capable of turning input in tabular or state-transition-diagram form into C++ code.

While this may be true, the author believes that a clear object-oriented style of writing FSMs in C++ is nevertheless valuable, irrespective of whether the code was written by machine or by human programmers. For a start, it will aid debugging of the individual action routines. Before a code generator can be written to produce FSM code automatically, it will be necessary to prove that the approach outlined in this paper is feasible with large FSMs and that it brings sufficient benefits.

A problem related to the use of FSMs in a program regards the way in which an FSM enters its initial state. For convenience, most state tables contain some event which results in the creation of a new FSM. This is not an accurate reflection of what happens in reality: each FSM is created by some other part of the program in response to an external event detected by that part of the program (eg at program start). A typical situation is that the program receives a message on a communications link, in response to which a new transaction object is created (an instance of an FSM class).

Provided that this situation is explicitly recognized, it should be possible to find adequate solutions in any particular case. For the example above, a dispatcher object could be created to accept all incoming messages and to create new transaction instances as needed.

            References

[1]       Hodgson, R “On the Question of Object-Oriented Method”. Draft Proceedings of OOPS-30 (9 March 1990), 50-51.

[2]       Birch, PW “Object-Oriented Finite State Machines”. Unpublished paper (15 March 1990).

[3]       Knolle, NT “Variations of Model-View-Controller”. JOOP 2, 3 (September 1989), 42-46.

[4]       Krasner, GE and Pope, ST “A Cookbook for Using the Model-View-Controller User Interface Paradigm in Smalltalk-80”. JOOP 1, 3 (August 1988), 26-49.


            Appendix: A Pascal-Like String Class

Instances of this class behave in most respects just like standard C (or C++) character strings. However, they automatically resize themselves on demand to hold whatever length of string they contain, and both single characters and strings can be appended to them.

Notice the conversion operator, operator char* (). The existence of this member function ensures that a PString can be used in any situation where a character string is called for. This property is used in the FSM example, where an instance of PString is sent to the standard output using the << operator.

Moreover, a PString can be concatenated with another PString by virtue of the fact that any character string can be appended to a PString using the member function operator+= ().

The public declaration of PString is in pstring.h:

#ifndef PSTRINGH

#define PSTRINGH

 

class PString {

 

#include "pstring.hpr"// private and/or protected members

 

public:

        PString ();

        virtual void reset ();          // empty the string

        virtual PString& operator+= (char *s);

        virtual PString& operator+= (char c);

        virtual operator char* ();      // conversion operator

        virtual ~PString ();

};

 

#endif  PSTRINGH

The non-public member variables and functions are held in pstring.hpr:

protected:

        char *buffer;

        int bufsize, index;

 

        virtual void checkBufSize (int length, int extra);

The implementation of the class is held in pstring.c. Most of the code should be self-explanatory:

#include "pstring.h"

#include "string.h"

 

static const int allocSize = 32;  // amount to allocate each time

 

void PString::reset ()

{

        index = 0;

        if (bufsize != 0)

                delete buffer;

        buffer = new char [bufsize = allocSize];

}

 

PString& PString::operator+= (char* s)

{

        int length = strlen (s);

 

        checkBufSize (index + length, 1);

        memcpy (buffer + index, s, length);

        index += length;

        return *this;

}

 

PString& PString::operator+= (char c)

{

        checkBufSize (index, allocSize);

        buffer[index++] = c;

        return *this;

}

 

void PString::checkBufSize (int length, int extra)

{

        if (length >= bufsize)

        {

                char *tempbuf =

                        new char [bufsize = (length + extra)];

                memcpy (tempbuf, buffer, index);

                delete buffer;

                buffer = tempbuf;

        }

}

 

PString::operator char* ()

{

        *this += '\0';  // terminate string properly

        return buffer;

}

 

PString::PString ()

{

        bufsize = 0;

        reset ();

}

 

PString::~PString ()

{

        if (bufsize != 0)

                delete buffer;

}

 



Created Thu Oct 23 22:32:26 2003

Copyright ObjectValue Ltd.

Back to ObjectValue Logo articles