Boost logo

Boost :

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-08-16 11:29:01


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 list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk