Object-oriented – Finite state machine menu design

finite-state machineobject-orientedobject-oriented-design

I'm creating an FSM in python (it's a step sequencer and sample pad based on a Raspberry Pi 2).

Right now there are two states and the third is the Menu. This is handled by a class System which handles all the states. The Menu state has to edit the attributes of the other states, so I passed the other states to its constructor.

    class State(object):
        def buttonPress(self, numberButton):
            raise NotImplementedError

    class StepSequencer(State):
        def buttonPress(self, numberButton):
            ...

    class SamplePad(State):
        def buttonPress(self, numberButton):
            ...

    class Menu(State):
        def __init__(self,stepSequencer,samplePad):
            self.stepsequencer = stepSequencer
            self.samplepad = samplePad
        def buttonPress(self, numberButton):
            ...
        def setMenuItem(self, currentMenuItem):
            self.currentMenuItem = currentMenuItem

    class MenuItem(object):
        def __init__(self, text):
            self.text = text

    class System(object):
        def __init__(self):
            self.stepsequencer = StepSequencer()
            self.samplepad = SamplePad()
            self.menu = Menu(self.stepsequencer, self.samplepad)
        def setState(self,state):
            self.state = state
        def buttonPress(self, numberButton):
            self.state.buttonPress(numberButton)

I can't figure out how to create the structure for the menu. I thought of creating a class MenuItem for every menu item so the Menu state has all these objects and can change the current MenuItem, however, there are some things that I cannot overcome:

how can I declare all the menu items and pass them to the Menu state to create dynamically the structure of the menu?
having this menu:
```
Step Sequencer settings:
    Set samples
    Set volume
Sample Pad setting:
    Set samples
    Set volume
```
for example, if I want to have a slider that sets the volume, do I have to create another state to handle this? This state can be another state of the System or it must be a substate of the Menu state?
can I execute the code of each state using this logic? :
```
while(system.state = system.stepsequencer):
    ...
while(system.state = system.menu):
    ...
```
The state is changed by a listener in another thread. This seems a very unorthodox way of handling states but it seems to work. If this is effective, how can I handle the Menu substates?

Best Answer

Probably the best way to implement FSMs in OOP languages is sticking to the State Design Pattern

That pattern provides a general structure to design and implement FSMs, dividing the FSM in two "sides": The context and the state, being the state a hierarchy of all the different states the context can have (a context can only have a very limited amount of states at a single time, usually only one). Then, the state transitions are modeled, usually either in the client (the class that uses the context will decide when to explicitly transition to a new state, making the context instance behave differently), or in the states (when each state is responsible of checking the transition conditions and perform the actual transition). The first approach has the advantage of a lower cohesion between states, making them reusable in implementations of other FSMs, but with a much more complex client class. The second approach has the opposite side effects.

In your case, I'd model System with the role of Context, State with the role of State, and Menu (and its submenus) as different ConcreteStates. If StepSequencer and SamplePad are to be exclusive of a single menu/submenu, they'd be attributes of that individual state. Otherwise, (i.e., shared or persistent between menus), as attributes of System. That decision will depend on your actual needs.

Now, about your design (and this is a little off-topic), StepSequencer and SamplePad don't look like actual states (neither by their uses nor by their names). Personally, I'd bet it's that way just because their interface is apparently identical to that of states (def buttonPress(self, numberButton):). If that's the reason, and you did it that way to avoid duplicating code, don't. It's okay to have code duplicated in certain occasions (e.g., when the base interface is likely to change in different directions over time, as stated by Robert C. Martin in his book Clean Architecture). Keep this in mind and consider deriving them from a different base class other than State.

Related Solutions

Language to describe Finite State Machine

Since finite state machines are a basically subset of (labelled) directed graphs, what about something like DOT. It was just the first thing that popped up on a Google "directed graph language". I've never used it.

Implementing State Machines with Additional Variables

The computer science answer is that you do indeed have up to 18*3*2 distinct states to deal with. How these states should be encoded into your program depends on your goals.

By writing down all possible states and restricting yourself to simple state transitions, you have the advantage that your code corresponds directly to a DFA. This lets you check all state transitions easily (though tediously). By analysing the state transition table, you can prove that the program will always respond correctly to any input sequence. Without this explicitness, it can get difficult to show that the control flow exhibits certain constraints, e.g. that some state is only reachable when a is set. You can also show that the program will always halt.

Unfortunately, large numbers of states are not very maintainable. This is only a good solution if you need formal verification, and can preferably generate the necessary code from an automatically-checked model.

In most cases, you will want to focus on maintainability instead. Being obvious is more important than being absolutely 100% correct (you can ensure some level of correctness more cheaply through testing). The bad news is that state machines are not very easy to understand for more than three states or so. The there are various techniques to manage the cognitive load of state machines.

One you have already found: expressing only a set of primary states in the state machine, and handling secondary state separately. This can drastically simplify the code when most state transitions do not depend on the secondary states. However, it's easy to accidentally get the various states out of sync, e.g. forgetting to reset a secondary state whenever a certain primary state is left. This can be made more unlikely by requiring all state changes to go through a single function, that makes sure a complete state has been intentionally provided. If the state space is somehow constrained to certain combinations of values, this function can also perform consistency checks. So instead of

oldstate: event {
  if (a) {
    b = A
    → newstate1
  } else {
     // forgot: b = B
     → newstate2
  }
}

we would be forced to provide a b value with

oldstate: event {
  if (a) → state(newstate1, a: a, b: A)
  else   → state(newstate2, a: a, b: B)  // can't forget value for b
}

The biggest simplifications are possible when chopping up your complete DFA with its 108 states into nested DFAs. When you look at the complete state transition diagram, some parts of the graph will feature many transitions within that subgraph, but will only have few transitions entering that subgraph and one transition leaving the subgraph. You can then extract the subgraph as a separate DFA, and call the extracted DFA like a procedure/function. If the subgraph has multiple entry points, you need to pass the relevant state as parameters so that the suitable start state can be chosen. Compare also the Extract Method refactoring.

Sometimes, multiple extractable DFAs have the overall same structure: same states, same inputs, but differ in their output and in one dimension of the state (e.g. each is used for a different value of the b variable). Extracting these separately would hide their similarity and thus make maintenance more difficult. In such a case, you can make parts of the state transition table pluggable. We unify the states of the extracted DFAs, and represent the extracted table as data. If the state transitions have side effects or if the target state of a transition depends on other variables, the state transition table will hold function pointers. In an object oriented system, each extracted state transition table would be an object, and the cells of the table would be methods on these objects. The main state transition table now only considers the unified states, and delegates the state transition to that extracted state transition table that is required by the currently active secondary state.

oldstate: event {
  → transition_table_for(b).oldstate_event
}

In many cases, the secondary state can be directly represented as a pointer to the active state transition table.

Finally, it might be better to represent the state implicitly in terms of the control flow of imperative code, rather than hand-rolling a difficult to maintain state machine. Most programmers are used to reasoning about imperative programs. For example, any DFA can be expressed as a set of mutually recursive functions, where each function corresponds to a major state. (E.g. most handwritten parsers use a recursive descent approach, rather than specifying the tables for a LL or LR parser). Smaller states can be represent implicitly in the control flow within the function. The debuggability of such function-encoded state machines is excellent, since the stack trace contains relevant states that lead to the current state. However, an imperative encoding becomes tedious unless the state transition table is fairly sparse. If the DFA you are implementing was derived from an NFA, imperative encodings allow you to reduce the number of states back to the NFA states by using backtracking (though this does have an exponential worst case).

At this point, we have completely given up any chance of formal verification, but have possible arrived at a much terser and more maintainable representation. Where on this scale you want to be depends on the requirements and constraints of your project. E.g. I once saw a parser that could have been simplified by using conrol flow to represent the states. However, a requirement was that it operated asynchronously. Without language-level support for async operation, the state necessarily had to be made explicit.

Best Answer

Related Solutions

Language to describe Finite State Machine

Implementing State Machines with Additional Variables

Related Topic