Another technique for implementing FSMs is the STATE pattern.[1] This pattern combines much of the efficiency of the nested switch/case statement with much of the flexibility of interpreting a transition table.
Figure 36-2 shows the structure of the solution. The Turnstile class has public methods for the events and protected methods for the actions. It holds a reference to an interface called TurnstileState. The two derivatives of TurnstileState represent the two states of the FSM. Figure 36-2. The STATE pattern for the Turnstile class
When one of the two event methods of Turnstile is invoked, it delegates that event to the TurnstileState object. The methods of TurnstileLockedState implement the appropriate actions for the Locked state. The methods of TurnstileUnlocked-State implement the appropriate actions for the Unlocked state. To change the state of the FSM, the reference in the Turnstile object is assigned to an instance of one of these derivatives. Listing 36-7 shows the TurnstileState interface and its two derivatives. The state machine is easily visible in the four methods of those derivatives. For example, the Coin method of LockedTurnstileState tells the Turnstile object to change state to the unlocked state and then invokes the Unlock action function of Turnstile. Listing 36-7. Turnstile.cs
The Turnstile class is shown in Listing 36-8. Note the static variables that hold the derivatives of TurnstileState. These classes have no variables and therefore never need to have more than one instance. Holding the instances of the TurnstileState derivatives in variables obviates the need to create a new instance every time the state changes. Making those variables static obviates the need to create new instances of the derivatives in the event that we need more than one instance of Turnstile. Listing 36-8. Turnstile.cs
State versus StrategyFigure 36-2 is strongly reminiscent of the STRATEGY pattern.[2] Both have a context class, and both delegate to a polymorphic base class that has several derivatives. The difference (see Figure 36-3) is that in STATE, the derivatives hold a reference back to the context class. The primary function of the derivatives is to select and invoke methods of the context class through that reference. In the STRATEGY pattern, no such constraint or intent exists. The STRATEGY derivatives are not required to hold a reference to the context and are not required to call methods on the context. Thus, all instances of the STATE pattern are also instances of the STRATEGY pattern, but not all instances of STRATEGY are STATE.
Figure 36-3. STATE versus STRATEGYCosts and BenefitsThe STATE pattern provides a strong separation between the actions and the logic of the state machine. The actions are implemented in the Context class, and the logic is distributed through the derivatives of the State class. This makes it very simple to change one without affecting the other. For example, it would be very easy to reuse the actions of the Context class with a different state logic by simply using a different set of derivatives of the State class. Alternatively, we could create Context subclasses that modify or replace the actions without affecting the logic of the State derivatives. Another benefit of this technique is that it is very efficient. It is probably just as efficient as the nested switch/case implementation. Thus, we have the flexibility of the table-driven approach with the efficiency of the nested switch/case approach. The cost of this technique is twofold. First, the writing of the State derivatives is tedious at best. Writing a state machine with 20 states can be mind numbing. Second, the logic is distributed. There is no single place to go to see it all. This makes the code difficult to maintain. This is reminiscent of the obscurity of the nested switch/case approach. The State Machine Compiler (SMC)The tedium of writing the derivatives of State, and the need to have a single place to express the logic of the state machine led me to write the SMC compiler that I described in Chapter 15. The input to the compiler is shown in Listing 36-9. The syntax is currentState { event newState action ... } The four lines at the top of Listing 36-9 identify the name of the state machine, the name of the context class, the initial state, and the name of the exception that will be thrown in the event of an illegal event. Listing 36-9. Turnstile.sm
In order to use this compiler, you must write a class that declares the action functions. The name of this class is specified in the Context line. I called it TurnstileActions. See Listing 36-10. Listing 36-10. TurnstileActions.cs
The compiler generates a class that derives from the context. The name of the generated class is specified in the FSMName line. I called it Turnstile. I could have implemented the action functions in TurnstileActions. However, I am more inclined to write another class that derives from the generated class and implements the action functions there. This is shown in Listing 36-11. Listing 36-11. TurnstileFSM.cs
That's all we have to write. SMC generates the rest. The resulting structure is shown in Figure 36-4. We call this a three-level FSM.[3]
Figure 36-4. Three-level FSMThe three levels provide the maximum in flexibility at a very low cost. We can create many different FSMs simply by deriving them from TurnstileActions. We can also implement the actions in many different ways simply by deriving from Turnstile. Note that the generated code is completely isolated from the code that you have to write. You never have to modify the generated code. You don't even have to look at it. You can pay it the same level of attention that you pay to binary code. Turnstile.cs Generated by SMC, and Other Support FilesListings 36-12 through 36-14 complete the code for the SMC example of the turnstile. Turnstile.cs was generated by SMC. The generator creates a bit of cruft, but the code is not bad. Listing 36-12. Turnstile.cs
FSMError is the exception that we told SMC to throw in case of an illegal event. The turnstile example is so simple that there can't be an illegal event, so the exception is useless. However, larger state machines have events that should not occur in certain states. Those transitions are never mentioned in the input to SMC. Thus, if such an event were ever to occur, the generated code would throw the exception. Listing 36-13. FSMError.cs
The test code for the SMC-generated state machine is very similar to all the other test programs we've written in this chapter. The differences are minor. Listing 36-14.
The TurnstileController class is identical to all the others that appeared in this chapter. You can see it in Listing 36-2. Following is the DOS command used to invoke SMC. You'll note that SMC is a Java program. Although it's written in Java, it is capable of generating C# code in addition to Java and C++ code. java -classpath .\smc.jar smc.Smc -g smc.generator.csharp.SMCSharpGenerator turnstileFSM.sm Costs and BenefitsClearly, we've managed to maximize the benefits of the various approaches. The description of the FSM is contained in once place and is very easy to maintain. The logic of the FSM is strongly isolated from the implementation of the actions, enabling each to be changed without impact on the other. The solution is efficient and elegant and requires a minimum of coding. The cost is in the use of SMC. You have to procure, and learn how to use, another tool. In this case, however, the tool is remarkably simple to install and use, and it's free. |