State machine design

Revision as of 02:44, 17 August 2009

Finite State Machine

1. Design a simple finite state machine.

2. Extend the design to allow deterministic or non-deterministic variants.

DTSTTCPW

• The client works directly with states
• The client is responsible for executing the state machine

Violations

• Stable abstractions principle: Changing the implementation of the machine will require changes to the client.

Deterministic Finite State Machine

• The client now only sees the DeterministicFiniteStateMachine class
• We can change the implementation behind the DeterministicFiniteStateMachine class without changing the client
• The client doesn't have to execute the state machine, it just calls run()

Non-Deterministic Finite State Machine

• Each state can have multiple transitions on a single input
• Multiple states can be active at one time
• The interface is identical, so the client need not be concerned with these complications

Solution

This solution uses the Intelligent children pattern to avoid the Parallel hierarchies problem that would occur if a DeterministicState could interact with a NonDeterministicFSM.

• The client doesn't need to be concerned weather the machine is deterministic or not
• The machine passes the input to the active state(s) and a reference to itself.
• The state(s) are then able to tell the machine which state(s) is now active.
• The NonDeterministicState can make several calls to FiniteStateMachine.setCurrentState() to set several states as active
• This now conforms to Tell, don't ask and Law of Demeter.

Disadvantages

• Coupling now exists in both directions between FiniteStateMachine and State. However this coupling is fairly weak. The concrete FiniteStateMachines only depend on the interface provided by State. Likewise, the concrete States only depend on the interface provided by FiniteStateMachine. So things are only coupled to interfaces.

Is It 'Right'?

One good indication that this design is now "right" is that we can substitute classes in all possible ways and the program will continue working. For example, we could have a DeterministicFiniteStateMachine which uses NonDeterministicStates. With some combinations the results may or may not be very useful, but the program will continue to work none the less. In other words this design conforms to the Liskov substitution principle.