TITLE: Finite State Machines AUTHOR: rmartin@rcmcon.com (Robert Martin), 14 Jul 95 There is an argument to be made for completely separating the state from the interface. Below is a design pattern that I use frequently when dealing with objects that are finite state machines. This pattern mentions a state machine compiler. If anybody would like a copy of that program, just drop me some email and I'll send it to you. ----------------------------------------------------------------------------- Three Level Fsm C++, Low Level ----------------------------------------------------------------------------- Intent Create Finite State Machines whose behavior is independent of their logic. This allows them to be derivable and extensible. Motivation Finite State Machines are often used to describe the logic that an application uses to convert its incoming events to its resultant behaviors. When the logic and behaviors are intermixed in the same algorithms, they become difficult to change and subject to error. It is difficult to separate control from logic because they often form a closed loop. The logic of the FSM invokes a behavior which in turn invokes another event in the FSM. Thus even when behavior and control are separated into two classes, as in the ObjectsForStates pattern, the two classes have source code dependencies upon each other. Thus it is difficult to use the behavior class with a different control class. Solution Describe the finite state machine in three layers of inheritance. The first layer supplies interfaces and implementations for the behaviors of the FSM. However, the events of the FSM are not known at this level, so this class is independent of control. This means that any of the behaviors that subsequently invoke events will be implemented as pure virtual functions at this level. The second layer is derived from the first and adds the functions that respond to the events of the FSM. It also employes the ObjectsForStates pattern or the Strategy pattern to implement the control logic of the FSM. It is possible for this level to be automatically generated from a state table or STD since, except for their names, this layer is independent of the behaviors. The third layer derives from the second and supplies those behaviors that must invoke subsequent events. Thus, since the first layer is completely independent of the control mechanisms of the FSM, it can become the base class for derivations that alter or extend the behaviors. It can also be used with different finite state machines by the derivation of another second and third layers. Structure Implementation The following code shows a typical implementation of the three levels. The second level has been automatically generated by a finite state machine compiler that employs the ObjectsForState pattern. The finite state machine for this example is a model of a subway turnstyle. The state table input to the finite state machine compiler is shown below. [ The format of the table is initial_state { current_state1 < optional_entry_action > optional_exit_action { event1 next_state transition_action event2 next_state transition_action ... eventN next_state transition_action } ... current_stateN < optional_entry_action > optional_exit_action { event1 next_state transition_action event2 next_state transition_action ... eventN next_state transition_action } } Note that this model handles both Mealy and Moore state machines. -adc] State Table Context TurnStyleLevel1 // the name of the context class FSMName TurnStyleLevel2 // the name of the FSM to create Initial Locked // Initial state. { Locked < Lock // Lock upon entry { Coin Unlocked {} Pass * Alarm Failed Broken LockError // indicate can't lock. } Unlocked InOrder { Fixed Locked {} } } This is a simple state machine. It starts out in the Locked state. If a coin is detected, it transitions into the Unlocked state. When the turnstyle detects the person "Pass" through, it returns to the Locked state. If, while in the Locked state, the person forces his way through, then we stay in the Locked state, and sound the alarm. If, while in the Unlocked state, the person deposits another coin, we light up a little "Thankyou" light. Whenever we enter the Locked state, we invoke the "Lock" action. This action can fail, resulting in a "Failed" event. Likewise, whenever we enter the Unlocked state we call the Unlock function. This function can fail, resulting in a "Failed" event. Upon failure, the FSM enters the Broken state. Upon entry into this state the OutOfOrder function is invoked, lighting a little light warning people away from the turnstyle. When the repairman fixes the turnstyle, the "Fixed" event occurs and the system returns to the Locked state. Upon exiting the Broken state the system calls the InOrder function which turns off the little out of order light. Level 1 -Behaviors Independent of Logic The first level is a class which defines the interfaces for all of the behaviors of the turnstyle. It also provides implementations for most of those behaviors. Only the Lock and Unlock functions remain unimplemented because they must invoke the "Failed" event which has not been defined at this level. class TurnStyleLevel1 { public: virtual void Lock() = 0; virtual void Unlock() = 0; virtual void Alarm(); virtual void LockError(); virtual void UnlockError(); virtual void Thankyou(); virtual void OutOfOrder(); virtual void InOrder(); protected: bool LockAndCheck(); bool UnlockAndCheck(); }; The last two member functions provide implementations for the Lock and Unlock functions. However the "bool" that these functions return must be translated to an event for the finite state machine. This translation will occur at level 3. Level 2 -The Control Logic This level has been entirely generated by the finite state machine compiler from the text shown above in the state table. class TurnStyleLevel2; class TurnStyleLevel2State { public: virtual const char* StateName() const = 0; virtual void Coin(TurnStyleLevel2&); virtual void Pass(TurnStyleLevel2&); virtual void Failed(TurnStyleLevel2&); virtual void Fixed(TurnStyleLevel2&); }; class TurnStyleLevel2BrokenState : public TurnStyleLevel2State { public: virtual const char* StateName() const {return "Broken";} virtual void Fixed(TurnStyleLevel2&); }; class TurnStyleLevel2UnlockedState : public TurnStyleLevel2State { public: virtual const char* StateName() const {return "Unlocked";} virtual void Coin(TurnStyleLevel2&); virtual void Pass(TurnStyleLevel2&); virtual void Failed(TurnStyleLevel2&); }; class TurnStyleLevel2LockedState : public TurnStyleLevel2State { public: virtual const char* StateName() const {return "Locked";} virtual void Coin(TurnStyleLevel2&); virtual void Pass(TurnStyleLevel2&); virtual void Failed(TurnStyleLevel2&); }; class TurnStyleLevel2: public TurnStyleLevel1 { public: // Static State Variables static TurnStyleLevel2BrokenState Broken; static TurnStyleLevel2UnlockedState Unlocked; static TurnStyleLevel2LockedState Locked; TurnStyleLevel2(); // Default Constructor // Event functions void Coin() {itsState->Coin(*this);} void Pass() {itsState->Pass(*this);} void Failed() {itsState->Failed(*this);} void Fixed() {itsState->Fixed(*this);} // State Accessor Functions void SetState(TurnStyleLevel2State& theState) {itsState = &theState;} TurnStyleLevel2State& GetState() const {return *itsState;} private: TurnStyleLevel2State* itsState; }; TurnStyleLevel2BrokenState TurnStyleLevel2::Broken; TurnStyleLevel2UnlockedState TurnStyleLevel2::Unlocked; TurnStyleLevel2LockedState TurnStyleLevel2::Locked; void TurnStyleLevel2State::Coin(TurnStyleLevel2& s) {} void TurnStyleLevel2State::Pass(TurnStyleLevel2& s) {} void TurnStyleLevel2State::Failed(TurnStyleLevel2& s) {} void TurnStyleLevel2State::Fixed(TurnStyleLevel2& s) {} void TurnStyleLevel2BrokenState::Fixed(TurnStyleLevel2& s) { s.SetState(TurnStyleLevel2::Locked); s.InOrder(); s.Lock(); } void TurnStyleLevel2UnlockedState::Coin(TurnStyleLevel2& s) { s.Thankyou(); } void TurnStyleLevel2UnlockedState::Pass(TurnStyleLevel2& s) { s.SetState(TurnStyleLevel2::Locked); s.Lock(); } void TurnStyleLevel2UnlockedState::Failed(TurnStyleLevel2& s) { s.UnlockError(); s.SetState(TurnStyleLevel2::Broken); s.OutOfOrder(); } void TurnStyleLevel2LockedState::Coin(TurnStyleLevel2& s) { s.SetState(TurnStyleLevel2::Unlocked); s.Unlock(); } void TurnStyleLevel2LockedState::Pass(TurnStyleLevel2& s) { s.Alarm(); } void TurnStyleLevel2LockedState::Failed(TurnStyleLevel2& s) { s.LockError(); s.SetState(TurnStyleLevel2::Broken); s.OutOfOrder(); } TurnStyleLevel2::TurnStyleLevel2() : itsState(&Locked) { Lock(); } Level 3 -Behaviors Dependent upon Control Finally, level 3 derives from level 2 and implement those behaviors that must invoke events in the FSM. These functions are Lock and Unlock which must call the LockAndCheck and UnlockAndCheck functions respectively, and then invoke the "Failed" event if the func- tions return false. class TurnStyleLevel3 : public TurnStyleLevel2 { public: virtual void Lock() { if (!LockAndCheck()) Failed(); } virtual void Unlock() { if (!UnlockAndCheck()) Failed(); } }; Since the first level provides all of the substantial behaviors that the finite state machine controls, but in no way depends upon any particular state machine, it can be reused by many state machines. It can also be the target of derivation so that its behaviors can be overridden or extended. Applicability Use this pattern in any context where behaviors may be controlled by more than one finite state machine, or where such behaviors need to be overridden and/or extended through inheritance. Consequences Virtual deployment of the action functions may add a small amount of execution time overhead. Also, the ObjectsForStates pattern used in level 2 adds lots of classes. Fortunately, since those classes can be generated by a compiler, they do not have to add to the programmers conceptual burden. Related Patterns ObjectsForStates, Strategy