Transitioning to a superstate

I'm relatively new to the world of finite state machines and have been focused on learning more about nested states.

Please excuse this long-winded post, but my example will help put my question in better context.

To learn more about Stateless, I put together a fairly simple traffic light simulator. The traffic light can be used as a standard red-yellow-green sequencer, or as a yellow or red flasher,

Basically, I have two top-level (root) states, InService and OutOfService, with triggers defined to transition between the two. OutOfService has no substates, but InService has two substates: SequencerMode and FlasherMode. SequencerMode has three substates: GreenOn, YellowOn and RedOn, while FlasherMode has two substates: FlashOn and FlashOff. OnEntry and OnExit methods perform all the necessary actions to 'drive' the traffic light. The traffic light's initial state is OutOfService.

I quickly reaped the benefits of a hierarchical state machine when I realized that each of my substates didn't need to know or define triggers for transitioning out of their parent state; only the parent state need do that (a substate inherits the triggers and transitions defined for their parent state). And since a state machine tree is recursive, I can nest my states as deep as I want, with each state inheriting everything from its branch of the tree.

That means I can fire the ToOutOfService trigger while in the OnGreen state, and the state machine will transition to the OutOfService state, even though that trigger is not explicitly permitted in the OnGreen state's configuration or even in its parent SequencerMode state's configuration; the trigger is defined in and gets inherited from the InService state.

So the benefits are obvious when transitioning 'up' the tree. But things aren't so clear to me when transitioning 'down' the tree.

Here's the problem I ran into: When I fired the ToInService trigger from the OutOfService state, the state machine happily transitioned to the InService state. And remained there. But that's not the behavior I wanted; I don't want my state machine to stay in the InService state, since that state doesn't perform any of the actual work to run the traffic light. Its sole purpose is to encapsulate the in-service states and behaviors of the traffic light, and define triggers and transitions inherited by its child states (SequencerMode and FlasherMode) and grandchild states (GreenOn, YellowOn, RedOn. FlashOn and FlashOff). Likewise, I don't want my state machine to remain in the SequencerMode or FlasherMode states, since they their purpose is to encapsulate the states and behaviors associated with their mode, and define the triggers and transitions for their child states.

The leaf states in my state machine tree - GreenOn, YellowOn and RedOn for the SequencerMode state, and FlashOn and FlashOff for the FlasherMode state - are where all the traffic light actions occur.

The best way I could get this to work the way I wanted was to fire triggers from some of my states' OnEntry methods. For example, here is the InService state's configuration:

      machine.Configure(State.InService)
        .Permit(Trigger.ToOutOfService, State.OutOfService)
        .Permit(Trigger.ToSequencerMode, State.SequencerMode)
        .Permit(Trigger.ToFlasherMode, State.FlasherMode)
        .OnEntry(_ => machine.Fire(Trigger.ToSequencerMode); // auto-forward to SequencerMode

Similarly, I configured the SequencerMode state this way:

      Machine.Configure(State.SequencerMode)
        .SubstateOf(State.InService)
        .Permit(Trigger.ToFlasherMode, State.FlasherOn)
        .Permit(Trigger.ToGreen, State.GreenOn)
        .OnEntry(_ => machine.Fire(Trigger.ToGreen); // auto-forward to GreenOn

Thus, when I fire the ToInService trigger from the OutOfService state, a transition to the state InService occurs. That state's OnEntry action then fires a ToSequencerMode trigger, which causes a transaction to the SequencerMode state, whose OnEntry action then fires a ToGreen trigger, which causes a transaction to the GreenOn state, where the traffic light begins sequencing between its GreenOn, YellowOn and RedOn states (via a timer).

This all seems to work fine, but for one issue.

Ideally, if I take my traffic light out of service and then put it back in service, I'd like the state machine to 'resume' where it left off while in service. For example, if the traffic light was running in Flasher mode when it was taken out of service, I'd like it to resume in that same mode when I put it back into service, rather than always transitioning, as I have it defined: OutOfService -> InService -> SequencerMode -> GreenOn. There's no way I know of to do this within the state machine itself; I have to instead maintain externally the most recent mode state (SequencerMode or FlasherMode) to be able to resume in that mode (via a PermitDynamic type trigger) when transitioning into the 'InService' state.

At least one other FSM application I evaluated - Appcelerate State Machine - implements UML's hierarchical transitions differently. First, it requires that all transitions always end up in a leaf state (a state with no substates). They then define several History configuration options to describe how transitions to superstates should be handled:

None: Each superstate automatically transitions to its initial substate. That substate then transitions to its initial substate, and so on, until a leaf state is reached.

Shallow: Each superstate enters into its last active substate; that substate then transitions to its initial substate, and so on, until a leaf state is reached.

Deep: Each superstate enters into its last active substate; that substate then transitions to its last active substate, and so on, until a leaf state is reached.

Another FSM application, NStateManager recently implemented auto-forwarding as a way of doing something similar to what I did, without my having to fire triggers in my states' OnEntry methods.

Does Stateless provide a way for me to do something similar to Appcelerate's Deep option, within the state machine itself? Does it maintain any sort of last active state information for substates?

I'd appreciate any insights anyone might have on this topic.

Thanks,

Paul

Does Stateless provide a way for me to do something similar to Appcelerate's Deep option, within the state machine itself? Does it maintain any sort of last active state information for substates?

So you're asking the Stateless state machine to maintain state? ;-)

I'm afraid the state machine is actually stateless, it has no knowledge of the past. The traffic light class will have to keep track of this, and then the state machine trigger handlers has to be configured to determine which target state is needed. This is a common solution to solve this sort of problem. The blink mode is also stateful information, although orthogonal to the operational state.

This was asked in #215 as well.

Thanks.

Yes, I realize that the Stateless package is, uh, stateless, which would rule out its maintaining any sort of hierarchy history (required by the Appccelerate state machine's Deep history setting, but not its None or Shallow settings; those do not require maintaining any history), but it doesn't answer the bigger question as to what it means to transition into a superstate,

In my traffic light state machine example, it makes no sense to transition to the InService state without also transitioning to one of the InService state's leaf states. The traffic light can't be in service without also being in either Sequencer mode or Flasher mode, and if in Sequencer mode, also be in one of its GreenOn, RedOn or YellowOn (leaf) substates,

I can obviously force each of my traffic light's superstates to automatically transition to one of its substates, by firing an additional event in its OnEntry method. But it feels awkward to have to do it that way; it would be more natural (and less prone to errors) to provide that behavior as part of the state machine's configuration syntax. I realize that would be difficult in Stateless, given that the state hierarchy is built from the bottom up (via the SubstateOf syntax).

I'm mostly curious to know if the Appccelerate State Machine's requirement - that all transitions must always end in a leaf state - is simply how they chose to implement the UML spec, or if the UML spec itself includes that same requirement.

Are there some obvious state machine examples out there where transitioning into a superstate should remain in that superstate and not automatically transition until reaching one of its leaf states?

Thanks,

Paul

I have read most of the UML specification at one point, but don't remember that always transitioning to a leaf state is required. Superstates is sometimes used for convenience, for catching common triggers for substates. Remaining in a superstates is useful when the substate represent a specialized mode of the superstate, but these modes can usually be represented as discrete states.

I think part of the problem you are facing is how to deal with orthogonal states. The traffic light can be in a combination of two states at the same time, InOperation/OutOfOperation and SequenceMode/FlashMode. Below I have tried to design two state machines for the traffic light. trafficlights

You can set the triggers to point directly to a leaf node, so you don't necessarily have to use the Entry method of the superstate. Designing a state machine is subject to taste, some people like to see lots of conditional triggers, some like to hide the logic indside internal transitions that fire new triggers. In the top model I selected the operational mode as the most important state, and chose to represent the out of service state as a substate. This makes the model somewhat more complex, but doesn't require to store the history. The lower model is more like you described the traffic light model. The main states are the operational states, and it requres some logic to determine which state to go to when exiting the out of service state. I just noticed that the two superstates of the top model is just for convenience, they have no triggers ;-)

Thanks for your comments, and the time you spent putting together those state diagrams!

Your second state diagram is the more accurate one, since my InService and OutOfService state are orthogonal (the entire traffic light is either in service or out of service). The initial state is OutOfService.

Using a dynamic transition to determine which state to transition to is certainly a viable option but not a desirable one in my opinion:

1) I try to avoid dynamic transitions wherever possible; I find they make my state machine's behavior more ambiguous and harder to debug.

2) More significantly, having the OutOfService state transition directly to one of the InService state's substates bypasses the encapsulation provided by the InService state. The OutOfService state shouldn’t need to know anything about the substates of InService (or if it even has any substates); it should simply transition to InService and let InService determine what actions and transitions should be taken when entered.

The analogy for hierarchical state machines are base classes (superstates) and derived classes (substates), where derived classes (substates) inherit the properties and methods (events) of their base classes (superstates).

Continuing the analogy, my question about transitioning directly to a superstate is analogous to trying to create an instance of an abstract base class: it can’t be done. An abstract base class serves only to define properties and methods that must be inherited by derived classes. You can only create an instance of one of its (non-abstract) derived classes.

The term pseudo-state refers to a state that is used strictly for encapsulating its substates. That's an apt description for my traffic light example: InService is a pseudo-state, as are SequencerMode and FlasherMode. They represent the abstract base classes for their derived substates.

A improved UML state diagram for my InService state box would show an initial transition to SequencerMode (a dot with a directed arrow pointing to the SequencerMode substate box). Likewise, my SequencerMode diagram would show an initial transition to the GreenOn substate box. Thus, when the ToInService event is triggered, the OutOfService state transitions directly to InService, InService transitions to its initial SequencerMode state, which in turn transitions to its initial GreenOn state. I can easily switch the InService state's initial state from SequencerMode to FlasherMode, without affecting the OutOfService state's configuration.

Stateless has no semantics or syntax for specifying a superstate’s initial substate; the best I’ve been able to come up with is to, as you suggest, transition directly to one of the superstate's leaf states, or use the superstate’s OnEntry method to fire an event to transition to its initial substate. Using OnEntry is a poor solution: if the superstate is entered via a transition to one of its substates, it's OnEntry method will fire an event to transition to its desired initial substate after the initial transition completes, possibly resulting in an incorrect ending substate. Using Stateless's OnEntryFrom syntax instead of OnEntry helps avoid that problem, at the cost of adding more complexity to the state machine definition.

I came across another HSM implementation recently that differentiates between a state’s initial action and its entry action. A state’s initial action is performed when the state is entered directly, while its entry action is performed when the state is entered indirectly (transitioning "through" the state to one of its substates). Providing some sort of OnInitial clause in a state's configuration would allow a user to define a method to be called only when transitioning directly into the state (the state's OnEntry method would be called when transitioning indirectly through the state). You could then use the OnInitial method to fire the appropriate event to transition to the superstate's desired initial substate).

The Appccelerate State Machine package seems to handle all this best, requiring you to define, through its DefineHierarchyOn configuration syntax, each superstate's initial substate and other substates, and how direct entry into the superstate should be handled (None, Shallow or Deep). As a result, there is no ambiguity in the state machine definition, nor any need for a state to know anything about the internal structure of the state it’s transitioning to. Of course, Appccelerate's requirement that all transitions must end in a leaf state may be too draconian for some; there may be legitimate reasons for wanting to transition to and remain in a superstate, although, admittedly, I haven't been able to come up with any good examples.

Paul

I don't like the dynamic transitions either, I often use an internal transition to capture the trigger, and do the logic in the handler. The handler then posts a new trigger. The InService state is mostly a convenience state, since its only use is to capture the ToOutOfService trigger. It would not take much effort to remove it entirely.

It's interesting that you should mention classes and sub-classes; I used objects as the state in #241 as a possible method for forking and joining. I don't agree completely that a superstate is like an abstract class, but it's a good analogy. I do remember that I have used the superstates, I had some equipment that was turned on, and the state machine moved to a Enabled state. When the equipment was fully powered up and passed its self check, the state machine would be notified and send a command to the equipment to start moving. The notification moved the state machine to a Moving state. However, the Moving state didn't have to be a substate of Enabled. There are many ways to model the behaviour.

Stateless is missing a few features, initial transitions are one of them. If you have time available then please feel free to add initial transitions :-) Just propose a change before starting to code.

Thanks for your comments.

Don’t underestimate the value of ‘convenience’. In a complex state machine with hundreds of states, the ability of substates to reuse properties defined in superstate’s becomes critical for avoiding errors of omission in the configuration.

I could certainly eliminate the InService state in my traffic light example, but that would mean having to duplicate the ToOutOfService event handler in its SequencerMode and FlasherMode substates. No big deal with only two substates, but if my traffic light contained several more modes, each with their own set of states, the situation could quickly get out of hand. Reusability is one of the most important and powerful benefits in hierarchical state machines.

My analogy of superstates with abstract base classes is accurate only if you accept that transitions into superstates result in further transitions until a leaf state is reached.

Your example does makes the case for allowing transitions directly into a superstate without requiring further transitions into one of its leaf states, as is the case today. The OnInitial syntax I proposed would allow for both models. If time (and learning) permits I may try to implement that feature.

Paul

Sent from my iPad

On May 3, 2018, at 2:36 AM, HenningNT notifications@github.com wrote:

I don't like the dynamic transitions either, I often use an internal transition to capture the trigger, and do the logic in the handler. The handler then posts a new trigger. The InService state is mostly a convenience state, since its only use is to capture the ToOutOfService trigger. It would not take much effort to remove it entirely.

It's interesting that you should mention classes and sub-classes; I used objects as the state in #241 as a possible method for forking and joining. I don't agree completely that a superstate is like an abstract class, but it's a good analogy. I do remember that I have used the superstates, I had some equipment that was turned on, and the state machine moved to a Enabled state. When the equipment was fully powered up and passed its self check, the state machine would be notified and send a command to the equipment to start moving. The notification moved the state machine to a Moving state. However, the Moving state didn't have to be a substate of Enabled. There are many ways to model the behaviour.

Stateless is missing a few features, initial transitions are one of them. If you have time available then please feel free to add initial transitions :-) Just propose a change before starting to code.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.

I have a similar need for a project I'm designing. One option I have considered is having multiple state machines. Rather than having it nested like you describe in a single state machine object, use multiple state machines objects for the independent children states. Parent states would explicitly fire triggers to their child state objects, not through internal state machine logic, but in OnEntry calls, similar to what you do in your first InService state.

In your example, you fire a trigger to the same state machine, but you could define a second inServiceMachine state that would handle its own transitions. When the parent transitions to an out of service state, the child could retain it's state, but be logically ghosted by the business logic of the rest of the program.

dotnet-state-machine / stateless

Transitioning to a superstate #248