State machine design
| Line 1: | Line 1: | ||
==Finite State Machine== | ==Finite State Machine== | ||
1. Design a simple finite state machine. | 1. Design a simple finite state machine. | ||
| + | 2. Extend the design to allow deterministic or non-deterministic variants. | ||
| + | |||
| + | ==Simple FSM | ||
| + | |||
There are 2 classes, the finite state machine (FSM) and state. This is a deterministic fsm. Every state has a map with all its transitions to all outgoing states. So the FSM just calls up the getNextStat()-method of the current state and passes over the specific transition (e.g. integer value). The state returns the next state in case it's not a finishing state. | There are 2 classes, the finite state machine (FSM) and state. This is a deterministic fsm. Every state has a map with all its transitions to all outgoing states. So the FSM just calls up the getNextStat()-method of the current state and passes over the specific transition (e.g. integer value). The state returns the next state in case it's not a finishing state. | ||
[[Image:Fsm1.jpeg]] | [[Image:Fsm1.jpeg]] | ||
==Non-/Deterministic FSM== | ==Non-/Deterministic FSM== | ||
| − | |||
| − | === | + | ===smelly-Solution=== |
[[Image:Fsm2.jpeg|800px]] | [[Image:Fsm2.jpeg|800px]] | ||
The Design consists of 2 hierarchies. On the left side is an abstract class FSM where DFSM and NDFSM inherit from FSM. On the right side there are the deterministic State (DState) and the nondeterministic State (NDState) which are derived from the abstract class State. It pretty much works exactly the same way as the simple design of the fsm above except that the NDState can return a set of states since one transition can have many resulting states. So basically the type specific fsm asks the state for the next state-object, the state objects returns its next. This is pretty much the problem here. It is a [[Parallel hierarchies problem]] where the [[Tell, don't ask]] principle gets violated. | The Design consists of 2 hierarchies. On the left side is an abstract class FSM where DFSM and NDFSM inherit from FSM. On the right side there are the deterministic State (DState) and the nondeterministic State (NDState) which are derived from the abstract class State. It pretty much works exactly the same way as the simple design of the fsm above except that the NDState can return a set of states since one transition can have many resulting states. So basically the type specific fsm asks the state for the next state-object, the state objects returns its next. This is pretty much the problem here. It is a [[Parallel hierarchies problem]] where the [[Tell, don't ask]] principle gets violated. | ||
| − | === | + | ===dd-Solution=== |
[[Image:Fsm3.jpeg|800px]] | [[Image:Fsm3.jpeg|800px]] | ||
Revision as of 09:24, 3 October 2008
Contents |
Finite State Machine
1. Design a simple finite state machine. 2. Extend the design to allow deterministic or non-deterministic variants.
==Simple FSM
There are 2 classes, the finite state machine (FSM) and state. This is a deterministic fsm. Every state has a map with all its transitions to all outgoing states. So the FSM just calls up the getNextStat()-method of the current state and passes over the specific transition (e.g. integer value). The state returns the next state in case it's not a finishing state.
Non-/Deterministic FSM
smelly-Solution
The Design consists of 2 hierarchies. On the left side is an abstract class FSM where DFSM and NDFSM inherit from FSM. On the right side there are the deterministic State (DState) and the nondeterministic State (NDState) which are derived from the abstract class State. It pretty much works exactly the same way as the simple design of the fsm above except that the NDState can return a set of states since one transition can have many resulting states. So basically the type specific fsm asks the state for the next state-object, the state objects returns its next. This is pretty much the problem here. It is a Parallel hierarchies problem where the Tell, don't ask principle gets violated.
dd-Solution
A nicer solution for that design is to apply the Double Dispatch, so that the FSM doesn't ask the state to return the FSM the next state/states. It pretty much just tells the state to do whatever it has to do with the transition. So the FSM passes a certain transition (here an integer number) and itself to the state. Since the state knows what its next state/s is/are, it just changes the FSM's current reference to the next state object. So instead of asking, here everybody just "tells"!
