[Qt-interest] The State Machine Framework - do's and don'ts

[K. Frank]

Hello Mihail -

Well, first of all, I don't think your question has a single right
answer.  I view state
machines as an approach to programming or a programming paradigm, like object-
oriented programming, functional programming, and so on.  (And you don't _need_
a state-machine framework to do state-machine programming -- it's like
doing object-
oriented programming in C -- you can do it without language or
framework support,
you just have to do more of the low-level work yourself.)

On Sun, Apr 18, 2010 at 11:23 AM, Mihail Naydenov <mlists at ymail.com> wrote:
> Hello, I have a simple, but important question about The State Machine Framework.
> A question about scale.
> ...
> Question is what are the right usages - the do-s?

When should you consider using state-machine techniques?  What kinds of
problems are likely to gain enough benefit from using state machines to make it
worth the bother?

The way I look at it (which is not the only way) state machines are a very good
way of organizing programs that are inherently asynchronous and event-driven.
(If they're not, you might as well just use good, old procedural programming.)
This is often referred to as "reactive programming" (because you react
to external
events.)  Note, gui's are often a good example of this.

The other key thing to look for is having a relatively small number of states,
where small does not mean numerically small, but small in some sense in
comparison to complexity of the problem you are solving, and where there
are relatively more, rather than relatively fewer ways you can get into a given
state.

A good counter-example is a text-edit window.  Sure, your "state" is the text
in the window, but there are potentially a huge number of states.  And, yes,
you can get to a given state via multiple paths (e.g., "1, 2, 4,
<backspace>, 3";
"1, 2, 3"; "1, 2, 3, 4, <backspace>"), but in practice, you get to a give state
through "relatively few" paths.

The idea is that in this kind of situation it is a simplification to
remember what
state you are in, rather than remembering how you got there.  (And, as a general
rule of thumb, if you find yourself needing to write code that says
"I'm in state 17,
but I got there by going through state 13." then you probably haven't
chosen your
states correctly, or maybe your problem isn't that well suited to using state
machines.)

The last thing is that I take the view that the states and the
transitions between
them (the "topology" of the state machine) is the "program" or "code" and the
events (by which I mean the actual stream of events you process) are the "data."
This ties into the notion that your state machine reacts to and/or processes an
external stream of asynchronous events.

Note, so far I haven't said anything about scale, because I don't
think that scale
is the primary consideration.  Having said that, I do tend to find
that in applications
of any realistic size, the higher levels are not efficiently described
by "relatively
few" states.  (E.g., "I have three mdi windows open, entry 4 in the third nested
sub-menu is currently selected, but not activated, document 4 has been modified,
but not yet auto-saved, and a pop-up modal dialog awaits a response."
is hardly a
single state I would want to implement in a state machine.)  So I tend
to see state
machines more often at the lower levels, but not because scale, itself, is the
determinant, but rather because the conditions that favor the use of
state machines
(such as those mentioned above) are more likely to hold true at lower levels.

As with most design questions, it's hard to give a check list of right
and wrong;
it's all about weighing the options and making trade-offs.

> ...
> None (IIRC) of the other examples for instance has more then one state machine, but this one creates (and destroys) not only new states, but also a new state machine for every tiny 20px torpedo and depth charge on the screen! At time it can have possibly 10 state machines running and even more states!
> Now I am puzzled.
>  Is this a case study -  pushing the max of the SM?...
> Or a glimpse in the future - where every button will be state aware, and the UI - state driven?
> Or just a toy.

I'm a big fan of a programming style where you have a lot of little
state machines that
interact by sending events to one another, so I don't consider this an abuse.

> Though Im sure it the last of the three, it will be very helpful to have some general guidelines about using  State Machine Framework.
> At the very least some relative performance and scaling metrics.(The cost of multiple states and states machines running.)

In my view, if you do want to be aggressive about using lots of little
state machines,
then performance may well matter -- and Qt's state-machine framework
may be heavier
than one might want.

Miro Samek has talked a lot about implementing state machines -- including
hierarchical state machines -- efficiently.  I don't buy everything he says, but
I found his book, "Practical Statecharts in C/C++" quite thought-provoking.
See it, for example, at amazon:

   http://www.amazon.com/Practical-Statecharts-Quantum-Programming-Embedded/dp/1578201101

I think that there is a lot of value to packaging state machines as
individual classes
(so that a concrete instance of a state machine is an instance of a
class).  It is
possible to do this in a way that you can derive one state machine from another,
and not only override actions in the derived class, but override the
topology of the
state machine, as well.  (Again, I think of the topology of the state
machine as the
"code.")  But this is difficult to do when the individual states (and,
in some frameworks,
the transitions) are themselves classes, or instances of classes, so
I'm not that
big a fan of the "state pattern" design pattern.  (Sorry, Qt!)  I just
think you lose
more than you gain when you go that route.  (Again, design is all
about trade-offs,
rather than right answers and wrong answers.)

> Is using micro states an abuse or "a glimpse in the future" after all?

I hope that it's "a glimpse in the future."  State machines are big in
the embedded
and real-time programming communities, and find some application in parsing,
often from the theoretical side.  But they're not widely used beyond
that.  I think
that's too bad, because I think that for certain kinds of business
logic (especially
asynchronous, event-driven stuff) they offer a very good programming paradigm.

There are barriers to use, however.  One barrier is lack of
familiarity.  This will
reduce itself over time as more programmers learn about these techniques, and
more frameworks become known, used, and battle-tested.

The other barrier, in my view, is that state-machine programming is
hard.  I don't
mean that building a simple state machine that implements simple logic is hard.
Rather, the kinds of problems where state machines offer real value
are themselves
hard, so using state machines effectively -- on problems where they
are likely to
be an effective tool -- is therefore hard.  (For example, I think that
asynchronous,
event-driven programming is hard -- some of the hardest programming I've done.)

But that's not the fault of state machines -- trying to solve these
problems _without_
state machines is, in my opinion, harder still.  (Try to write a
parser, let alone an
event-driven program, with pure if-then programming, and you'll shave
a few years
off your life.)

I would like to see the use of state machines mature and spread, so I
am very glad
that they are becoming more mainstream, and that Qt, among others, has developed
a state-machine framework.  (I'm looking for an opportunity to try out
the Qt framework
on a real problem.  Boost also offers a framework, of a rather
different design philosophy.)


Well, that's my long, at best partial answer to your short, simple question!

Good luck.


K. Frank


> Thank You
> MihailNaydenov