State History Mechanism

The statechart was proposed by Dr. David Harel in his 1987 paper, which introduced a number of powerful augmentations to pure state machines as well as visual formalisms for expressing them. Statecharts were included as a core artifact type in the Unified Modeling Language (UML) which is the pre-eminent software modeling language.

One of the key new ideas in statecharts was the “history” mechanism, which we will now explore.

The Problem

State machines are an inherently limited kind of system in that they have no memory of what has happened except what you explicitly build into the states themselves. Consider this system:

Frame

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#History101

  -machine-

    $A
        |gotoC| -> $C ^

    $B
        |gotoC| -> $C ^

    $C
        |return| ^

##

Here we see that $C has no way to know what state preceded it. To solve this problem for a pure state machine we would have to do something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#History102

  -machine-

    $A
        |gotoC| -> $Ca ^

    $B
        |gotoC| -> $Cb ^

    $Ca
        |return| -> $A ^

    $Cb
        |return| -> $B ^

##

$Ca and $Cb would be identical except for the response to the |return| message. This is obviously inefficient.

The Solution

Automata theory holds that there are are three levels of increasing complexity and capability for abstract machines:

1. Finite State Machines
2. Pushdown Automata
3. Turing Machines

Pushdown Automata and Turning Machines share the trait of being able to store information for future use. Pushdown Automata specifically use a stack for storing history while Turning Machines theoretically have a “tape” to store information on. In reality if a system can store off data and access it later to make a decision it is effectively a Turing Machine.

For our problem with remembering the last state, a stack will do nicely thus giving us the power of a Pushdown Automata. To support this, Frame has two special operators:

Let’s see how these are used:

Frame

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#History201

  -machine-

    $A
        |gotoC| $$[+] -> "$$[+]" $C ^

    $B
        |gotoC| $$[+] -> "$$[+]" $C ^

    $C
        |return| -> "$$[-]" $$[-] ^

##

What we see above is that the state stack push token precedes a transition to a new state:

1

$$[+] -> $NewState

while the state stack pop operator produces the state to be transitioned into:

1

-> $$[-]

Recalling that FrameState is a delegate typedef in C# to allow references to methods, we can see that Frame generates a _stateStack_ variable which is initialized to a Stack<FrameState>() data structure.

C#

     //=========== Machinery and Mechanisms ===========//

     ...

     private Stack<FrameState> _stateStack_ = new Stack<FrameState>();

     private void _stateStack_push(FrameState state) {
         _stateStack_.Push(stateContext);
     }

     private FrameState _stateStack_pop() {
         FrameState state =  _stateStack_.back();
         return _stateStack_.Pop();
     }     
 

Also generated are the push and pop functions for the state stack operations.

Frame

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

 #History202

  -interface-

  gotoA
  gotoB
  gotoC
  goBack

  -machine-

    $Waiting
        |>| print("In $Waiting") ^
        |gotoA| print("|gotoA|") -> $A ^
        |gotoB| print("|gotoB|") -> $B ^

    $A
        |>| print("In $A") ^
        |gotoB| print("|gotoB|") -> $B ^
        |gotoC| print("|gotoC|") $$[+] -> "$$[+]" $C ^

    $B
        |>| print("In $B") ^
        |gotoA| print("|gotoA|") -> $A ^
        |gotoC| print("|gotoC|") $$[+] -> "$$[+]" $C ^

    $C
        |>| print("In $C") ^
        |goBack| print("|goBack|") -> "$$[-]" $$[-] ^

    -actions-

    print [msg:string]

##

Refactoring Common Behavior

In the sprit of staying DRY let’s refactor out the common transition shared by $A and $B into a parent state $AB:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

 #_History203_

    -interface-

    gotoA
    gotoB
    gotoC
    goBack

    -machine-

    $Waiting
        |>| print("In $Waiting") ^
        |gotoA| print("|gotoA|") -> $A ^
        |gotoB| print("|gotoB|") -> $B ^

    $A => $AB
        |>| print("In $A") ^
        |gotoB| print("|gotoB|") -> $B ^

    $B => $AB
        |>| print("In $B") ^
        |gotoA| print("|gotoA|") -> $A ^

    $AB
        |gotoC| print("|gotoC| in $AB") $$[+] -> "$$[+]" $C ^

    $C
        |>| print("In $C") ^
        |goBack| print("|goBack|") -> "$$[-]" $$[-] ^

    -actions-

    print [msg:string]

 ##

We can see that the duplicated |gotoC| event handler is now moved into $AB and both $A and $B inherit behavior from it.

Below we can see that the system reports out it is now transitioning from $AB rather than from the individual states:

NOTE: History203 demonstrates the recommended best practice of using a Frame specification to define a base class (in this case _History203_) and then derive a subclass to provide the implemented actions for behavior.

Conclusion

The History mechanism is one of the most valuable contributions of Statecharts to the evolution of the state machine formalism.

However, whereas Statecharts were declared to be a visual formalism (Harel, 1987), Frame is intended to be a symbolic language that can generate equivalent code and documentation. As such, the Frame notation will favor a terse textual syntax that is (hopefully) both clear and powerful.