Statechart Semantics Using Frame
(Frame is a new Domain Specific Language (DSL) focused on enabling developers to easily create programs using automata. See the Frame documentation as well as Getting Started With Frame to find tools and other resources to explore the Frame language.)
Harel Statecharts and UML
In 1987 Dr. David Harel published a paper introducing several powerful innovations on classic automata modeling and implementation approaches called Statecharts.
Although not inherently more powerful than Turing machines, Statecharts introduced visual software modeling techniques that made automata easier to design and practically use. His approach is a key part of software engineering approaches like the Unified Modeling Language (UML) and Model Based Software Engineering (MBSE).
Frame directly supports three key concepts from Harel Statecharts:
- Enter/Exit events for states
- Hierarchical State Machines
- State History Mechanism
In this article we will explore these concepts and Frame’s syntax to support them. A fourth unsupported Statechart innovation, Orthogonal Regions is also discussed.
Enter/Exit Events For States
Software developers usually are creating stateful software (read — some kind of automata), whether they realize it or not. There is a state machine lurking inside their code — they just can’t see it. This fact is often obscured, however, due to the fact that modern programming languages have no true first-class concept of state.
Instead, the current logical state of a system is derived from conditional tests on low level data. Changing the logical state of a system is simple to do — just update one or more data values and the software silently slips into a new logical state.
However, it is often the case that some kind of activity needs to happen when entering and exiting logical states. Typically this is done in an ad-hoc manner in all the places in the code where that transition could occur. This article on state machines and game programming provides one of the best examples of the hairballs of code these situations can spool up.
To address this situation, Statecharts introduced the new idea of automatic notifications when transitioning into as well as out of a state. These are called the enter and exit events respectively and are extremely powerful mechanisms for simplifying system design. Here is an example from Harel’s paper:
Frame implements this feature by sending special messages (the enter message “>” and exit message “<”) to the system machine when transitioning into and out of states:
$Working
|>|
print("Enter $Working state") ^
|<|
print("Exit $Working state") ^Above we can see a $Working state that handles both messages, printing an appropriate output for each.
Here is this functionality in context of a complete system:
#EnterExitEvents
-interface-
next
-machine-
$Begin
|next|
-> $Working ^
$Working
|>|
print("Enter $Working state") ^
|<|
print("Exit $Working state") ^
|next|
-> $Begin ^
##The first state after the -machine- block keyword is special and is defined to be the “start state” of the system. Above we see that our demo system therefore starts life in the $Begin state.
-machine-
$Begin
|next|
-> $Working ^Upon receiving a “next” message the system transitions into the $Working state which prints its entry message after this transition.
$Working
|>|
print("Enter $Working state") ^
|<|
print("Exit $Working state") ^
|next|
-> $Begin ^When an external caller then calls “next” again, the system will transition back to $Begin, triggering the exit event message and completing the cycle.
Adding a main() function to the program we can now drive the system to transition the machine and emit the messages.
fn main {
var sys:# = #EnterExitEvents()
loop var x = 0; x < 2; x = x + 1 {
sys.next()
}
}
#EnterExitEvents
-interface-
next
-machine-
$Begin
|next|
-> $Working ^
$Working
|>|
print("Enter $Working state") ^
|<|
print("Exit $Working state") ^
|next|
-> $Begin ^
##You can run the program online here.
Hierarchical State Machines
The second innovation in Statecharts supported by Frame is Hierarchical State Machines (HSMs). Automata need to handle handle every possible event for every state they are relevent to redundancy of behavioral code. This can result in significant duplication of common behavior between states.
To improve this situation, Statecharts introduce Hierarchical State Machines in order to factor out common behavior from a set of states into a parent state and keep it in one place.
Harel showed a simplified example of this kind of redundancy in automata in his paper:
Above are three states A, B and C. We can see that states A and C share a common transition to B. Here is a Frame system modeling the diagram above:
#Figure1
-machine-
$A
|c| -> $C ^
|b| -> $B ^ // This is redundant
$C
|b| -> $B ^ // This is redundant
$B
|a| -> $A ^
|c| -> $C ^
##
Harel’s solution to the redundancy of the shared transition between A and C was to introduce a parent state D and put the transition there, thus normalizing the system behavior in this regard.
Frame easily does this same refactoring using the dispatch operator “=>”.
#Figure2
-machine-
// Dispatch any unhandled events to $D
$A => $D
|c| -> $C ^
// Dispatch any unhandled events to $D
$C => $D
$D
|b| -> $B ^
$B
|a| -> $A ^
|c| -> $C ^
##Below we can see the Frame graphic showing a functionally identical model to Harel’s diagram.
Redundancy of behavior between states is a frequently cited drawback of programming automata. Through the dispatch mechanism, Frame aligns with the Statechart approach to addressing this practical problem coding automata.
State History Mechanism
One of the more complex Statecharts features is its history mechanism (see the H* icon in the upper right of the picture above). History provides a means to return to the prior state without knowing what it was. In this way, the system runtime takes care of remembering rather than the programmer being responsible for some kind of memento tracking.
Frame provides two special tokens for managing the state stack, which can be used to provide the history capability for Frame. The first is the state stack push operator $$[+]. This token pushes the current state onto the stack and is typically used just prior to a transition to a new state. The second is the state stack pop operator $$[-] which pops the stack for the last pushed state and returns it.
These tokens can be used with a transition like this:
$A
// Push $A on the state stack and
// transition to $C.
|gotoC| $$[+] -> $C
$C
// Pop the top state from the stack and
// transition to it ($A in this case).
|return| -> $$[-] ^Adding labels to the transition, here is a simple program showing the features:
#HistoryDemo
-machine-
$Start
|>|
rand() > .5 ?
-> "A" $A
:
-> "B" $B
:| ^
$A
|gotoC| $$[+] -> "$$[+]" $C ^
$B
|gotoC| $$[+] -> "$$[+]" $C ^
$C
|return| -> "$$[-]" $$[-] ^
##
Above we see we will randomly transition to $A or $B states. The machine then uses the state stack mechanism to return to whichever state it transitioned from.
Readers who are highly knowledgeable regarding Statechart semantics may take exception that this approach is not the full Statechart history implementation. While this is true, the additional complexity of the full specification is rarely, if ever, critical or even valuable in complex system design. The simplified approach implemented in Frame has proved to be a reasonable compromise between power and simplicity.
Orthogonal Regions
The final big concept in Statecharts is a visual design pattern supporting parallel state machines. This is often known in the literature as a system-of-systems. This level of holistic complexity is where the clarity and power of automata is typically most valuable and visible.
Below we see a larger Avionics System subdivided into three regions, each containing its own state machine running in parallel with the others.
These three subsystems — general-mode, radar, abc-system (and others not shown to the right) are run in parallel as part of a larger Avionics System. Typically sub-systems will also be interacting with each other in complex and hard-to-describe ways.
It was this kind of system-of-systems problem, though on a much smaller scale than running an aircraft, that spawned the idea of Frame. Below are the state diagrams from the patent for a study planner the author created for an educational product for Microsoft:
Unfortunately, Frame does not support system-of-system semantics directly in the language — yet. However, this can be accomplished manually and fairly easily by creating a hierarchy of controller systems to align with a parent-child hierarchy of sub-systems. For Harel’s Avionic System, a top-level “AvionicSystem” controller would be responsible on start up to launch each of the subsystems and, upon system shutdown, manage their orderly retirement.
This will be a future area for research for Frame syntax and involve exploration of a runtime environment and communication system that can support these complex semantics.
Conclusion
The Frame language was initially designed as a textual language supporting the Statechart innovations discussed in this article. This differs from Harel’s original vision of developers of the future literally drawing software using modeling tools like engineers in other disciplines.
Unfortunately, the challenges in actually laying out software designs has proved to make the activity inefficient and frustrating. The modeling tools that are so successful for designing buildings, machines and other natural artifacts have not worked for software. Why?
Software does not map to the constraints of the physical world and often can be unnaturally complex. Complex software components do not have inherient natural relationships nor fit easily or usefully in a 2D (or event 3D) representation.
This fact has hampered the evolution of “software engineering” into something similar to what civil, electrical and other engineering disciplines do with their toolsets.
Frame is a pragmatic compromise between the visual and textual means of creating software. The textual language is designed to be a simple way to quickly express systems as a composition of states and relationships. As a byproduct of this design approach, it can also provide the same visual representation as Statecharts, but with no wasted effort to layout complex system topology.
Both aspects will continue to evolve in future versions of the Frame langauge.
