Abstract
There are some things a FSM cannot handle[5]. The author attempts addresses this by adding memory-based States connected to logic “gate” junction pseudo states. This enable Statecharts to handle more complex applications while still remaining a transition network at its core.
Josef Betancourt, November 27, 2018
Notes
2023-05-25: The forthcoming XState v5 will have something called “Higher-order guards”, see https://stately.ai/blog/announcing-xstate-v5-beta#higher-order-guards
Is this similar to the gate concept introduced in this post?
1. Background
Hierarchical Finite State Machines (HFSM), especially the Statechart (UML state machine), are a useful tool in increasingly complex applications like Graphical User Interfaces. They allow the logical behavior flow requirements to be expressed in a declarative model.
The state of the art, Statecharts, are defined in diagrammatic terms by David Harel as:
“statecharts = state-diagrams + depth + orthogonality + broadcast-communication”. [1]
In real world use, various frameworks and libraries such as the SCXML, provide additional constraints, and Executable Content[4] to that declarative state transition network. These other feature are actually executing an imperative flow of control. So it could be argued that the state graph does not really specify the system in a declarative model.
Why isn’t the state graph enough? While StateCharts do limit the combinatorial state explosion that are a drawback of traditional FSM, they export some of the complexity to a side channel or dimension of the Statechart run-to-completion behavior. These are ‘extended state machines’[2].
2. Example
A GUI form presents a list of fields that must be completed or activated by the user. There is also a Done button that the user clicks to signal that the form is ready to be submitted.
Requirement: All fields must be activated by the user. When Done is clicked, an error message is shown if all field have not been activated, else the form is submitted. This is a common ‘validation’ scenario in form processing. The fields, for example, could be checkboxes. The Done button invokes a validation process to determine if the form is ready for submission.
A naive Statechart of this scenario would make each field and the Done button states. Each field could even be a concurrent state (in an orthogonal region) of the form. But, when the Done button is clicked and the form must transition to a Validating state, how is the state of all the buttons used to determine the transition to error or submit? How is the ‘all fields were checked’ captured in a Statechart?
A programmatic solution is just to transition to a validation state that determines if all fields were activated. In a Statechart this complexity can be handled by an invoked program/script that evaluates a transition guard to a target state: error or submission. This guard uses the extended state to allow this determination.
Note:
This is just a simple example. That it could be done with only present Statecharts is not the issue. It is probably not a perfect example for this topic.
The UML statechart standard, for example, has a richer set of states for this purpose. Pseudo States such as: join, fork, junction, choice, and exitPoint.
David Khourshid, the developer of XState, responded to this example at https://github.com/davidkpiano/xstate/issues/261#issuecomment-442451581
“Have you seen the semantics of <final>
states (as in SCXML)? https://xstate.js.org/docs/guides/final.html
We can model “all fields must be valid” by setting 'valid'
as the “final” state for each orthogonal node and listening for the done.state.*
event.”
And then gave a code example.
3. Synchronous AND transitions
Petri Net approach
The example scenario could be trivially solved using a simple Petri Net model. Each form field is a ‘place’ and when it is activated, a ‘mark’ or token is placed there. All the places connect to a ‘Transition’ that fires when all the input places have a mark. This fired transition puts a mark into the Valid place.
State Memory
Borrowing from Petri Nets, we can use marks by adding memory to a state. This memory allows the synchronous use of prior state transitions. History states are already one type of memory used in Statechart standard. By generalizing the use of memory, more complex systems can be modeled.
Why ‘synchronous’? A machine can have one current state. In a Statechart, nested states form an XOR. To handle complexity, Statecharts also provide an AND in the form of orthogonal substates. These are called ‘parallel’ in the XState implementation [6]. But, they could loosely be termed asynchronous, since their behavior could be independent of the superstate container.
Definition
State memory is a numeric limit value attribute used as a modulus. The current value dynamically changes. The limits are:
n=-1: latch,
n=0: no memory (default),
n=1: toggle,
n=>1: roller
The values allow the state to be repeatably reused in operational in reactive state changes.
4. Operation
To provide a transition via an AND, a state must have a non-zero memory limit. If the machine re-transitions to the same state, the memory value determines when the memory is cleared. The preset memory size value is the increment modular rollover. Whenever the state is entered, the current value is increment. When the value reaches the memory size, the current value is set to zero.
A size of zero, turns off memory. A negative size, causes a state transition to a state to always have a memory of that occurrence, no incrementing. A value of one clears the memory on each transition, so acts as a toggle. When size is greater than one, subsequent transitions to the state will begin to increment the memory until the value of the memory size setting.
When all the memory states have a current value the AND fires, and the machine transitions to the target state of the AND. Unlike a Petri Net, a fired AND also resets all the input state’s current memory to zero. In practice an implementation would make this behavior also configurable per each AND relation.
States with memory are ‘normal’ states in a Statechart. Their ‘memory’ aspect only affects behavior when used with an AND pseudostate.
5. Symbol in visual diagram
The simplest realization in visual form is a Petri Net solid bar |. A bar is also used in UML activity diagrams to indicate a fork/join. Since the bar already has so many connotations, an actual military style AND circuit symbol or a European style & rectangle could be used. The simplest thing that would work is a solid bar: |.
6. Example solution using Statechart memory
With the aforementioned approach the Petri Net equivalent solution is shown below. Note that this diagram is not showing how to formally add memory and gates to the standard Statechart visual notation.
7. Generalization to Gates
Adding memory to a state and its use to create an AND pseudostate leads to the possibility of other types of pseudostates to tackle fine-grained complexity and details. Since these are more like logic ‘gates’, calling these “gates” seems appropriate.
With the addition of OR (||) and NOT (o), many other gates could be created, such as NAND, NOR, and so forth. This is similar to the many types of gates and their combinations that capture hardware logic and specified using Hardware Description Languages (HDL)[3].
8. Conclusion
The addition of state memory that connect to gates enables creation of more complex and detailed Statechart or HFSM models. More work is required to evaluate this approach and modify or abandon.
In a way this effort bridges the gap from high level software back to hardware. It may be possible to use Computer Aided Design (CAD) technologies in this realm, especially if extendable Statecharts could be used as component building blocks.
References
- Statecharts – A Visual Formalism for Complex Systems by David Harel
- Extended States: https://en.wikipedia.org/wiki/UML_state_machine#Extended_states
- Hardware description language: https://en.wikipedia.org/wiki/Hardware_description_language
- Executable Content: https://www.w3.org/TR/scxml/#executable
- “What exactly can finite-state machines not do?”: https://cs.stackexchange.com/questions/14093/what-exactly-can-finite-state-machines-not-do
- Parallel State Nodes: https://xstate.js.org/docs/guides/parallel.html
Links
- “What exactly can finite-state machines not do?”. https://cs.stackexchange.com/questions/14093/what-exactly-can-finite-state-machines-not-do
- Introduction to Hierarchical State Machines (HSMs). https://barrgroup.com/Embedded-Systems/How-To/Introduction-Hierarchical-State-Machines
- Statecharts – A Visual Formalism for Complex Systems by David Harel
- HAREL, D.; POLITI, M. Modeling Reactive Systems with Statecharts: the Statemate Approach. McGraw-Hill, 1998. http://www.wisdom.weizmann.ac.il/~dharel/reactive_systems.html
- Harel, david. “Statecharts in the Making: A Personal Account”. http://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts.History.pdf
- SCXML: https://www.w3.org/TR/scxml/
- XState: https://xstate.js.org/docs/
- “UML 2 State Machine Diagrams: An Agile Introduction”. http://agilemodeling.com/artifacts/stateMachineDiagram.htm
- UML state machine: https://en.wikipedia.org/wiki/UML_state_machine
- Unified Modeling Language: https://www.omg.org/spec/UML
- ‘Precise semantics of the UML state machine specification’: https://www.omg.org/spec/PSSM/
- “Patterns for using React with Statehart based state machines”: https://medium.freecodecamp.org/patterns-for-using-react-with-statechart-based-state-machines-33e6ab754605
- “Behavior Modeling With State Machine And Activity Diagrams”. https://www.kth.se/social/upload/256/Behaviour%20Modeling%20with%20State%20Machine%20and%20Activity%20Diagrams.pdf
- “Guidelines: Statechart Diagram”: http://sce.uhcl.edu/helm/rationalunifiedprocess/process/modguide/md_stadm.htm
- Petri Networks: https://www.youtube.com/watch?v=dUYRjsEUr1o
- Finite-state machine: https://en.wikipedia.org/wiki/Finite-state_machine
- Douglass, Bruce Powel (January 1999). “UML Statecharts”. Embedded Systems Programming.
- Simons, Anthony JH. “On the Compositional Properties of UML Statechart Diagrams.” In Rigorous Object-Oriented Methods. 2000.
- Vijaykumar, Nandamudi Lankalapalli, Berkenbrock, Gian Ricardo, Carvalho, Solon Venâncio de, Andrade, Valéria Maria Barros de, Swamy, Gurrala Veereswara, & Rao, Mokka Jagannadha. (2012). Memory embedded in Markov models specified in Statecharts: simulation versus analytical approaches. Gestão & Produção, 19(4), 663-675. https://dx.doi.org/10.1590/S0104-530X2012000400001
- epYme documentation. “ASM++: a modern Algorithmic State Machine methodology for RTL designs”. http://www.epyme.uva.es/asm++/
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.