State Machine Implementation

Question

I'm looking for some general

1. Optimization
2. Correctness
3. Extensibility

advice on my current C++ Hierarchical State Machine implementation.

Sample

variable isMicOn = false
variable areSpeakersOn = false
variable stream = false
state recording
{
        //override block for state recording
        isMicOn = true //here, only isMicOn is true              
        //end override block for state recording
}
state playback
{
        //override block for state playback
        areSpeakersOn = true //here, only areSpeakersOn = true
        //end override block for state playback
        state alsoStreamToRemoteIp
        {
                //override block for state alsoStreamToRemoteIp
                stream = true //here, both areSpeakersOn = true and stream = true
                //end override block for state alsoStreamToRemoteIp
        }
}

goToState(recording)
goToState(playback)
goToState(playback.alsoStreamToRemoteIp)

Implementation

Currently, the HSM is implemented as a tree structure where each state can have a variable number of states as children.

Each state contains a variable number of "override" blocks (in a std::map) that override base values. At the root state, the state machine has a set of variables (functions, properties...) initialized to some default values. Each time we enter a child state, a list of "overrides" define variable and values that should replace the variables and values of the same name in the parent state. Updated original for clarity.

Referencing variables

At runtime, the current states are stored on a stack.

Every time a variable is referenced, a downwards stack walk is performed looking for the highest override, or in the case of no overrides, the default value.

Switching states

Each time a single state frame is switched to, the state is pushed onto a stack.

Each time a state is switched to, I trace a tree descension that takes me from the current state to the root state. Then I do a tree descension from the target state to the root state until I see the current trace matches the previous trace. I declare an intersection at where those 2 traces meet. Then, to switch to the target state, I descend from the source, popping state frames from the stack until I reach the intersection point. Then I ascend to the target node and push state frames onto the stack.

So for the code sample above

Execution trace for state switch

• Source state = recording

• Target State = alsoStreamToRemoteIp

• descension from source = recording->root (trace = [root])

• descension from target = alsoStreamToRemoteIp->playback->root (trace = [playback, root])

• Intersects at root.

To switch from recording to alsoStreamToRemoteIp,

1. Pop "recording" from the stack (and call its exit function... not defined here).
2. Push "playback" onto the stack (and call the enter function).
3. Push "alsoStreamToRemoteIp" onto the stack (and call the the enter function).

Answer 1

I'm not sure I follow all the details here. However, it seems that you are describing an FSM (finite state machine) implementation where you have multiple state machines. Sometimes, when a particular event (E1) occurs in a particular state (S1) of FSM F1, you need to enter a new FSM (call it F2) to simplify the processing overall).

If that's the case, then when E1 occurs in S1, you need to invoke an action routine that takes over the event reading and implements the F2 FSM. When invoked, it starts processing in the start state of F2, and handles the relevant sub-events. When it reaches its end state, the interpreter for F2 finishes. It might return some information to the F1 action routine that was suspended while F2 ran, and the next state in F1 may be affected by that.

The rest of your description - stuff like 'override blocks' - won't make much sense to people without access to your implementation.

Answer 2

Two things:

1: For most cases just represent the state of your program as a Model, and interact with it directly or through the MVC pattern.

2: If you really need a FSM, i.e. you want to randomly make a bunch of actions to your model, only some of which are allowed at certain times. Then....

Still keep the state of your program in a Model (or multiple Models depending on decomposition and complexity) and represent states and transitions like.

class State:
   def __init__(self):
      self.neighbors = {}

Where neighbors contains a dictionary of of {Action: State}, so that you can do something like

someAction.execute() # Actions manipulate the model (use classes or lambdas)
currentState = currentState.neighbors[someAction]

Or even cooler, have an infinite loop randomly selecting an action from the neighbors, executing it, and moving state indefinitely. It's a great way to test your program.