[boost] [fsm review] Comparison with ad-hoc FSM coding

16 Aug 2008

      Dear All,

I have just spent a few minutes comparing an ad-hoc FSM implementation 
with an implementation using the proposed library.  The example that 
I've used is the USB device state machine, which I recently had to 
understand for an embedded application, and I've put an image of the 
state graph here:

http://chezphil.org/tmp/fsm.png

For more info, google("USB 2.0 spec") (you'll find a zip file with a 
PDF in it) and see the start of chapter 9.  Note that it seems to me 
that the "power interruption" transition is wrong and should go to 
"attached" rather than "powered", and that I have ignored the 
"suspended" states.

The behaviour is essentially as follows: a device is "attached" until 
the hub supplies power, when it becomes "powered".  It then waits for a 
reset, at which point it starts listening for messages at the "default 
address" (zero); the host ensures that only one device is in this state 
at any time.  When the host sends a set_address message it changes to 
the "address" state, and when the host sends a set_configuration 
message it changes to the "configured" state for normal operation.

Here is my ad-hoc implementation (note that I haven't tried to even 
compile any of this code):

struct usb_device {

   enum state_t { Attached, Powered, Default, Address, Configured };
   state_t state;

   int addr;
   int configuration;

   usb_device(): state(Attached), addr(0), configuration(0) {}

   void power_on() {
     state = Powered;
   }

   void power_off() {
     state = Attached;
   }

   void reset() {
     state = Default;
     addr = 0;
     configuration = 0;
   }

   void set_address(int addr_) {
     addr = addr_;
     state = (addr==0) ? Default : Configured;
   }

   void set_configuration(int configuration_) {
     configuration = configuration_;
     state = (configuration==0) ? Address : Configured;
   }
};

In comparison, here's what I've come up with using Boost.FSM:

struct Attached;
struct Powered;
struct Default;
struct Address;
struct Configured;

typedef mpl::vector<Attached, Powered, Default, Address, 
Configured>::type StateList;

struct PowerOn;
struct PowerOff;
struct Reset;
struct SetAddress {
   int addr;
   SetAddress(int addr_): addr(addr_) {}
};
struct SetConfiguration {
   int configuration;
   SetConfiguration(int configuration_): configuration(configuration_) {}
};

struct Common {
   int addr;
   int configuration;
};

struct Attached: fsm::state<Attached,StateList>, Common {
   void on_process(const PowerOn&) {
     switch_to<Powered>();
   }
};

struct Powered: fsm::state<Powered,StateList>, Common {
   void on_process(const PowerOff&) {
     switch_to<Attached>();
   }
   void on_process(const Reset&) {
     switch_to<Default>();
   }
};

struct Default: fsm::state<Default,StateList>, Common {
   void on_enter_state() {
     addr = 0;
   }

   void on_process(const PowerOff&) {
     switch_to<Attached>();
   }
   void on_process(const Reset&) {
   }
   void on_process(const SetAddress& set_address) {
     addr = set_address.addr;
     if (addr != 0) {
       switch_to<Address>();
     }
   }
};

struct Address: fsm::state<Address,StateList>, Common {
   void on_process(const PowerOff&) {
     switch_to<Attached>();
   }
   void on_process(const Reset&) {
     switch_to<Default>();
   }
   void on_process(const SetAddress& set_address) {
     addr = set_address.addr;
     if (addr == 0) {
       switch_to<Default>();
     }
   }
   void on_process(const SetConfiguration& set_configuration) {
     configuration = set_configuration.configuration;
     if (configuration != 0) {
       switch_to<Configured>();
     }
   }
};

struct Configured: fsm::state<Configured,StateList>, Common {
   void on_process(const PowerOff&) {
     switch_to<Attached>();
   }
   void on_process(const Reset&) {
     switch_to<Default>();
   }
   void on_process(const SetConfiguration& set_configuration) {
     configuration = set_configuration.configuration;
     if (configuration == 0) {
       switch_to<Address>();
     }
   }
};

The latter is clearly more verbose than the former.  Some of the 
verbosity would go if I put the common events (e.g. PowerOff) into a 
base class, but that adds verbosity of its own.

There are a few characteristics of this particular design that favour 
the ad-hoc code.  Firstly, the device's behaviour is allowed to be 
undefined if an unexpected event occurs.  Secondly, many events have 
the same effect irrespective of the state (e.g. power off).  Finally, 
the effect of events often depends on their data (i.e. zero has a 
special meaning).

I would also say that the turnstile example given in the library 
documentation could be implemented more concisely using an ad-hoc 
approach (would someone like to try?).

Perhaps more complex FSMs would benefit more from what this library 
offers.  In that case, can we see an example?  I note that this library 
is targeted at simpler FSMs than Boost.Statechart (which I have not 
used).  Is there a category of FSMs that are simple enough that 
Boost.Statechart's features are not needed (e.g. hierarchy) yet too 
complex for an ad-hoc implementation?

Regards,

Phil.

[boost] [fsm review] Comparison with ad-hoc FSM coding

Phil Endecott