Re: State Machine/Class Granularity

Responding to Wavemaker...

As a sanity check, I'm going to describe some of my progress writing a
state machine code generator; it's in the form of a builder class. Any
comments or criticisms are welcome.

After tweaking it over the past couple of days, I've settled on what I
hope is a useful design. The StateMachineBuilder class builds state
machines as strings representing the actual state machine code. After
being built, the string can be written to file, printed or whatever.
He's a snippet of code of the StateMachineBuilder in action:

Let me ask a very basic question: What is the purpose of your builder? Is it simply to generate the nuts & bolts FSM infrastructure code in an application with FSMs for a known problem? Or is the intent to build FSMs dynamically (e.g., the FSM itself is defined at run-time)? In the first case the builder is just a tool for providing automation of code writing as a convenience to the developer. The second case is more like what a commercial transformation engine does (i.e., taking arbitrary specifications from an external source and constructing code in a problem-independent manner).

The reason I ask is that you mention getting input from a UI, which suggests the FSMs are being designed "on the fly", either at run-time or as part of a higher level (RAD-like) IDE for designing applications.

If you are just looking for an automation tool for individual applications you might think about simply using source templates. Most of the infrastructure is defined in lookup tables which have to be filled in anyway and the actions are normal methods whose bodies have to be written anyway. In addition, languages like C++ have convenient facilities (macros, #define, etc.) for managing synchronization. Synchronization is more manual but one can help oneself through process (e.g., comments in the template: if THIS table is updated, check consistency with THAT table).

What you describe below is pretty much what a translation transformation engine does when it processes a Statechart from a UML drawing tool. Instead of a UI, an XMI reader for the drawing tool repository is providing all the ASCII strings you use as arguments. That's fine and I applaud your initiative but it may be overkill unless you have such a generic construction requirement that externalizes the FSM specifications. OTOH, if you already have most of the code done... B-)


StateMachineBuilder builder = new StateMachineBuilder();

builder.AddUsing("System");

builder.NamespaceName = "StateMachineExample";
builder.ClassName = "Keyboard";

//   State         Event       NextState     Action
builder.AddTransition(
    "Default",    "CapsLock", "CapsLocked",  null);

builder.AddTransition(
    "Default",    "AnyKey",   "Default",    "DisplayLowercase");

builder.AddTransition(
    "CapsLocked", "CapsLock", "Default",     null);

builder.AddTransition(
    "CapsLocked", "AnyKey",   "CapsLocked", "DisplayUppercase");

builder.InitialState = "Default";

builder.Build();

Console.WriteLine(builder.StateMachine);

null means a no operation (a NoOp method is substituted by the state
machine). For invalid operations, an "Invalid" action would be
appropriate. The builder would then create an Invalid action method in
which the logic for dealing with invalid transitions could be placed.
Also, self-transitions are handled by having the next state name the same as the current state name. Maybe there would be a better way to indicate this such as using hyphens (e.g. "--") in the next state category?

You really don't care if an event is reflexive to the state because the table takes care of getting the right action in either case. Conceivably it could be a performance enhancement so that one doesn't have to do ASCII key lookups somewhere. However, reflexive events are rare enough that simply checking for the special case for every event probably makes any gain moot.

However, this segues to another issue of performance. You don't want to be doing STT lookups using ASCII keys. So State and Event want to be converted to a nice integer index somewhere along the line. In a translation transformation engine that would one the primary jobs of the builder. It would also make sure the conversion table was around so that when code was created from the text-based AAL text event generation the integer indices would be substituted in the event ID in the produced code.

IOW, apropos of the point above, a major reason one has a builder in a general purpose code generator is because one /must/ convert convenient ASCII 4GL representation into something more efficient. But for your own development of an individual program you already know exactly what needs to be done so you can bypass the conversion step. (More precisely, encode it directly in tables.)



What I like about this is that the STT is built right into the code.
It's clearly laid out (erm, with the exception of some line wrapping I
had to put in for this post). Also, it would be easy to build a GUI
front end to make state machine generation even easier.

Right. The calls to addTransition are essentially just laying out an STT. You will even group the calls together and comment them as if it were an STT. It's the same table with some syntactic sugar.

As far as the GUI is concerned, you are providing an interface that doesn't care where the ASCII comes from. IOW, the interface captures the invariants of FSM creation and parameterizes the details in nice, portable, source-indpendent ASCII via the STT paradigm. Note that your builder interface could be a Facade class that serves as a subsystem interface to the FSM construction subject matter. Then one can freely substitute the source between GUI, browser, command line, XMI reader, etc. That's another justification for doing things as you have and you may have gotten to exactly the same place purely from the perspective of application partitioning.


Here is part of the code generated by the builder; it's in the
constructor of the state machine:

eventQueue.Subscribe("CapsLock", 0, this);
eventQueue.Subscribe("AnyKey", 1, this);

The event queue is passed to the state machine's constructor. The state
machine knows which events it's interested in, so it subscribes to those
events there. The first parameter of the Subscribe method is the name of
the event. The event name does not have to preexist before being
subscribed to. If it doesn't already exist, the event queue "registers"
it and gives it a unique event ID. The second parameter is the
substitute event ID the event queue should use for this state machine
when the specified named event is raised. And the last parameter is, of
course, the state machine itself so that the event queue has an instance
to dispatch the subscribed events to.

Very good. However, I am concerned about the mechanism the event queue uses to provide the mapping. It will have a target instance address in hand from the event itself. Is the intention to match that with subscribed 'this' pointers to determine the substitute event ID?

What I am getting at is that I think you need some other mechanism for identifying the class. You are going to be accessing a static member anyway, so all you need is the class name to generate code (e.g., <class name>::consumeEvent(...) in C++) and you will have a target instance handle in hand with the event to pass as an argument. If you employ a unique integer class identifier for each class, you can register both the same way

eventQueue.ClassSubscribe("Keyboard", 14);
....
eventQueue.Subscribe("CapsLock", 0, "Keyboard");
....

(Though in a full code generator one would probably keep the class mapping table somewhere else that the FSM builder accesses because it would be useful in other contexts.)

Now the event has '14' as a target class ID and some number for "Capslock" to use to look up the '0' for the local event ID. At the same time it uses '14' to look up the class name to insert in the code for the call.


In addition to some other boiler plate code, the builder generates empty
action methods, for example:

private void DisplayLowercase(object data)
{
    // TODO: DisplayLowercase logic.
}

private void DisplayUppercase(object data)
{
    // TODO: DisplayUppercase logic.
}

What's interesting to me is how this approach to state machines has
driven my design. For example, I had designed a state machine previously
representing a slave clock. This clock receives MIDI clock messages from
an external device, interprets them, and generates tick events at the
specified timing resolution. The clock periodically checks (about every
half-second or so) to see if it is still receiving clock messages. If it
has stopped receiving clock messages (say the MIDI cord to the computer
became unplugged), it would need to raise an event to let the rest of
the subsystem know and transition back to a default state.

I had put this logic in the form of a guard inside a "Running" state
handler. But this required the handler to know how to make transitions.
This is a no-no, I've since learned. :-) With this approach to state
machines, the action handlers do not have any knowledge about states or
transitions, so I was faced with a challenge when redesigning the state
machine. I solved the problem with the addition of another state. This
got rid of any need for a guard, and since I dislike them, I liked this
solution better. At any rate, I think this approach to state machines
drove me towards a better design.

I think that is mostly attributable to the fact that the FSM forces one to follow FSA rules. (I would argue OOA/D requires one to follow the same rules but in a more subtle way so deviation and foot-shooting is easier.) It is nontrivial to build good state machines and get them to interact properly. But the effort is worth it because once one gets them right they tend to be very robust.


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@xxxxxxxxxxxxxxxxx
Pathfinder Solutions  -- Put MDA to Work
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
(888)OOA-PATH



.

Relevant Pages

  • Re: State Machine/Class Granularity
    ... It enforces some constraints such as making sure each state machine has a unique name and ID and resides in the subsystem's namespace. ... So I would expect the builder to build every state machine exactly the same way once it is provided with the events, transitions, and action identifiers. ... It seems to me that the only thing that has changed is the location of some of the code that is being generated (i.e., from EventQueue to class). ... the base class never has to be touched by the code generator; it's only generating code for the derived class. ...
    (comp.object)
  • Re: State Machine/Class Granularity
    ... Since those are just pairs, those declarations are trivial to provide in your state machine builder UI. ... So if you wanted to create a subsystem and begin by adding a ... An instance of this class would be passed to the event queue at ...
    (comp.object)
  • Re: State Machine/Class Granularity
    ... >> internally to create the STT code for each state machine. ... When I say state machines in a subsystem, ... So I would expect the builder to build every state machine ... // A custom event queue for this subsystem. ...
    (comp.object)
  • Re: State Machine/Class Granularity
    ... > consecutive index to the event id for the local state machine. ... 2D table inside the event queue. ... it's in the form of a builder class. ... half-second or so) to see if it is still receiving clock messages. ...
    (comp.object)
  • Re: Alternatives to state machine for user-definable behavior without reprogramming?
    ... switching from one state machine data structure to the other when it is ... you mean "build the 'new' FSM while still using the 'old' ... can occur frequently, at up to a 3600RPM engine cycle rate, or 30Hz. ... The output waveform tables of a given ...
    (comp.arch.embedded)