ST 7 Hierarchical State Design as a Recursive Partitioning Problem

The first step of statechart design is to identify states of a component.

You need a distinct state when:

1. A component exhibits specific behaviors or responses characteristic to a certain situation. For example, the Train component has a Manual, Auto, Commanded and Scheduled state to represent different modes of operation.
2. A component is waiting for something to occur, e.g. for a timer to expire, for a DMA operation to complete, for a network message or an event to arrive.

The second point is particularly interesting. For algorithm design, the focus is on the active computation. For statechart or asynchronous design, the focus is on waiting while the component is not doing anything!

In statechart design, you repeat the above process to identify substates within each state. It is OK if you don’t find any more substates as you have reached a leaf state.

The way each non-leaf state (S) is divided into substates is analogous to creating a “partition” in set theory. In any situation when a component is in state S, it must be in *exactly one* of its substates. This simple concept goes a long way to yield a complete (no gaps between states) and consistent (no contradiction) design. (Let’s ignore parallel states for now.)

For example, when the Train component is in the Auto state, it must be either idle or active (engaged). No situations are left unconsidered, and no contradiction (i.e. both idle and active) is possible. Similarly, when it is in the AutoActive state, it must be either at rest, accelerating, decelerating or cruising (running). Again, there are absolutely no gaps or overlaps between these substates.

This partitioning looks obvious with statecharts, but it couldn’t be taken for granted if we were simply using ad hoc flags to represent states implicitly. The tree diagram shows the overall state hierarchy of the Train component. The highlighted states are included in the partial statechart explained in the previous post. We will jump out of the Train component to look at the overall software architecture in the next post.