Statechart Data - Statecharts are not flowcharts.

Statecharts are meant to be descriptions of reactive behavior. The outside world generates events, a state machine processes those events, responds with predefined actions, and then waits for the next event. A flowchart, on the other hand, receives data as input and transforms that data as it passes it along; stage after stage. Wikipedia has a whole section on this difference, my favorite (paraphrased) quote being:
 
In a state diagram, processing is associated with transitions, whereas in a flowchart processing is associated with nodes. A state machine sits idle in a state waiting for an event to occur; a flowchart is busy executing activities.


I find that a useful mantra to mumble to myself while setting up states ( thank goodness only my cats are around to complain ) because programming state machines has a different feel than programming normal procedural code. Frequently, I think, we as programmers want our code to be *doing* something. But, with state machines, your code is just sitting there, waiting to react, waiting for a chance to do something.

Another way to think about all this is that you aren't are writing instructions to control movement from state to state, but rather only documenting how those changes happen. Your machine code is only "following along" with changes happening elsewhere.  At it's essence, that is what a purely reactive system means. It reacts to the world, it doesn't control the world. ( The prime example Harel uses in his book, for instance, is an emergency warning system for aircraft. )

So, that's all great in theory, but how does it stand up in practice?  Consider a simple main menu with several choices...

Using a state machine to describe just this one screen would be overkill. In Flash, this one simple screen can easily be hooked up using a custom class derived from the screen's sprite, and a few event listeners attached to the buttons. The power of using a state machine isn't going to be about this single screen alone; it's going to come from sequencing menus together. The flow as a user moves from screen to screen.

In this example, "Start New Game" will take us to a screen where we can pick a specific character to play with, "Continue Adventure" is going load and display previously saved games; "Options" will present a way to adjust the volume of sound effects, etc.; the little speaker icon in the bottom left will keep us at the main menu, but will let us turn on and off sound all together; and so on.

It's no great leap to think of each one of the screens as a state, the selection of menu choices as events that transition us from screen to screen, the little speaker icon as an event with an action.
    Main Menu:
    - entry / display_options();
    - button[0] >> New Game.
    - button[1] >> Continue Game.
    - button[2] >> Options.
    ... 
    - speaker_icon / toggle_sound(); 
    New Game:
    - entry / display_characters();
    Continue Game:
    - init >> Load Saves.
      Load Saves:
      - entry /load();
      - loaded >> Select Game.
      Select Game:
      - entry /display_saves();
      - selected >> Confirm Choice.
      Confirm Choice:
      - entry /prompt_user_with_dialog();
      - response[no]  >> Select Game.
      - response[yes] >> Run Game.
    ...
Interestingly, however, while this doesn't break the mantra: "A state machine sits idle in a state", it is different than the world of embedded systems programming where statecharts arose.

As you move through the menus, by definition, new screens are coming and going. It feels like it only makes sense that "Main Menu" displays the menu, "Select Game" displays the saves, etc. But, that means rather than being purely reactive, this statechart is modifying the system that it's watching.

This self-modification creates an immediate "crisis". A situation that shows up in normal statemachine programming, but is particularly acute here:
  • Where does "New Game" get its list of characters from? 
  • How does "Select Game" get the list of saves from that "Load Saves" loaded?
  • If "Confirm Choice" is supposed to re-display the choice selected, how does it get that choice?
  • How does "Run Game" know which character was confirmed?
  • etc. 
Even more subtly, where are the references to the screens that are getting created being stored, and how do we access them? ( For instance, so that we can test "was that the sound icon getting clicked?", or in MainMenu/exit to remove the screen from the display list, or even destroy it completely. )
All of these questions boil down to: where are states getting their data from?  There's also a corollary question: if we're talking about self-modification, and shuttling data from place to place, this suddenly sounds like a flowchart; does that mean statecharts aren't suited to UI?

In the toaster example, you'll notice the UML statechart states there are curious references to "me".

  Baking: entry/set_temperature(me->temperature);
  Toasting: entry/arm_time_event(me->toast_color);   

Those "me's" refer to the machine itself. So, in fact, that suggests even simple machines do occasionally need data to operate well. And, indeed, most state machine implementations encourage the use of data storage within the machine object. So perhaps self-modification bends state-machines, but perhaps data storage does not.

Is that the end of the story? Why did I use the word "crisis" with respect to UI? The reason is that, even with the very simple UI above, you start to get the sense that if we stuff all the data for all the menus and other interface elements into the machine itself, it's going to get messy quick. ( Dawn is a small game, but even so there are 24 unique screens, 5 different popups, and 58 different statechart states. )

I'm going to try to spend a few posts looking at what options there are. There are pros and cons to each choice, and I haven't found anything out on the net that tries to look at the question. I don't believe there is a right answer per se ( though I do have some personal preferences ), and none of it is rocket science. ( Although, if you are in rocket science, and reading my blog, that's pretty cool. ) I think it's just useful now and then to pull out the toolbox, and shake it out to figure out what's accumulated in there.

3 comments:

Arnold Preg said...
This comment has been removed by the author.
Arnold Preg said...

Good read!
It's good to see someone else also struggling with the same problem as I do.
I did not even get to coding statecharts, but I see these shortcomings you are writing about. Did you finally buy "The Book" I mean Ian Horrocks's book?

ionous said...

Glad you liked it!

I need to put an ebay watch or something on Horrock's book. Last time I checked it was still 100+ dollars(!)

I've very much gotten into the mode lately of thinking about states as "static" units of code that (can) create dynamic objects. For the most part, those dynamic objects have the lifetime of the state -- I think it's almost a definition of when it's okay to create those dynamic objects -- but: occasionally, ref counting can let states hand-off bits of data to other states. I think it's the nature of this (generally) one-to-one binding that makes state charts differ from flow charts.

For hierarchical machines: the best way I can summarize is to say there's both state's "precondition data" -- what's necessary to exist in the world before the state could "run", and the data the state itself creates. Much of the time this latter data are actions and listeners, but it can also be things like a new menu screen. Sub-states have access to anything the container state sends to it. It's a contract that your code fulfills.

The specific state machine system you wind up using really has a dramatic influence on the way the data hand-off looks. In the ideal world, it'd be nice to have compile time checks that states require a specific precondition data type: but it's not always possible. Also, I've found, key to making ui/state programming feel more natural, is being able to share tear down code in state exit -- for instance, remove all registered listeners, destroy any created scenes ( or other objects ). The more automatic that tear down is, the easier state based programming feels.

I don't know when I'll get to document some of this stuff -- I'd like to be able to open source some of the editor work i've been doing -- but none of it is in a very complete... state... yet :\