Object-Based State Machine Pattern

[Daklu]

There's been a lot of discussion about state machine patterns the last couple months. Admittedly a good part of it is because I'm so vocal in my dislike for the QSM, but Paul posted an excellent document recently and Justin and Norm pimped the JKI state machine and the TLB state machines respectively at NI Week.

Last night I posted a broken example of an object-based state machine. This morning I was feeling guilty about it, so here's a version without the missing libraries. To reiterate from last night's post...

------------------------------

Here's a state machine for a Total Phase Beagle I2C monitor I recently put together using the pattern I described on Paul's other thread and Felix mentioned here. The benefit of having separate sections of code for entry, do/execution, exit, and transition actions can't (IMO) be overstated. It's way easier for me to understand and extend than any flavor of QSM. QSMs are further limited by the restriction of only performing entry actions and must repeatedly exit and reenter the same state.

Notes:

- Project code is available for LV 2009 or LV 2010. They are otherwise identical.

- The project is dependent on the attached vip. Install it using VIPM before opening the project.

- The attached vip is currently intended for LapDog developer use. Obviously you are free to use it, but it may not be compatible with future versions. It's an updated version of the library I posted here. (Please pay no mind to the really lame LapDog palette icon. I'm hoping someone comes up with something better.)

- I replaced the original Beagle library with a ghost "BeagleApi" library. The vis in the ghost library are there simply for their connector panes--there's nothing in them.

- There's not much documentation... I didn't expect to be sharing it yet.

- The BeagleStateMachine class is the main public api. It contains the data required for the state machine to operate and shared accessors to that data for the state objects.

- Each state is a separate class that derives from BaseState.

- TestBeagleStateMachineLibrary is an example of how to use this state machine. Or you can build an Actor class around it.

- The state diagram below is also on the bd of BeagleStateMachine:Execute.

- If I ever get tempted to use a QSM again for anything non-trivial... please shoot me. The pain isn't worth it.

[Edit 9-12]

Uploaded a new copy of the 2010 version. The previous version was still attempting to link to a different MessageLibrary.

lapdog_lib_message_library-0.7.0.1.vip

BeagleStateMachine2009.zip

BeagleStateMachine2010.zip

[mje]

Still seem to be missing some dependencies. Of note, I'm getting complaints about MessageQueue.lvclass, Message.lvclass, and ErrorMessage.lvclass.

Seems neat though, can't wait to look more into this!

[ShaunR]

Still seem to be missing some dependencies. Of note, I'm getting complaints about MessageQueue.lvclass, Message.lvclass, and ErrorMessage.lvclass.

Seems neat though, can't wait to look more into this!

You need to first install

lapdog_lib_message_library-0.7.0.1.vip

which has that class

[Black Pearl]

Looks really cool.

Did take me some time to follow the cycle from Paul's big paper through the other threads, and I certainly miss some of the discussions.

A lot of half finished thoughts from my side, but I just throw them in the debate as fuel for all of you:

Bidirectional Association of by-val classes

This has kept me thinking for some time when studying the association meta-class of uml for my latest post on my blog. At first I was convinced that by-val design only allows uniderctional associations of classes. But theoretical thinking told me, that if class A contains class B, I can place class A in a LVObject in class Bs private data (inside the Get method). Later I then can retrieve class A back from B with a type cast and update the values of B inside A.

If I read the code correctly, this is implemented between StateMachine and State. If so, thanks for the proof.

Dynamic dispatch instead of enum/case

This was discussed on the NI forum recently (I don't remember the thread).

Basically, the traditional enum shift register and case structure design is completly replaced by dynamic dispatching. Again, if I understand this correctly, thanks for the demonstration.

Readability of the design

This is dating back to my first analysis of state machines. I did browse some text-based implementations of state machines. I think they used a very similar design. At that time, I felt the case/enum SMs in LV very superiour as they directly present me the code instead of the general state machine design.

This is nothing if I have an up-to-date documentation in uml as presented. But getting to the concrete code takes me a couple of clicks more than when I use the traditional non-OOP approach. I would list this as a big con because I have to do a lot of 'cowboy coding' on customers site and neither have the uml tools available there nor the time for proper modelling.

But I see that I have the possibility to attack a task by at least two ways: EITHER going through the state machine and accessing the concrete dynamic dispatch vi of Enty, DoActiitiy or Exit OR going through the class of the states and having in the PE for every class access to all three Activities.

Now comes the theoretical stuff:

state machine theory I: transisitons

I checked the wikipedia entry on state machines. The mathematical modell suggests that a state machine has states, transisitions and an alphabet. From this, the state classes should not have access to the command queues (alphabet). Also they should not contain the transitions, tranisition logic and TransisitionActivity.

state machine theory II: Entry state

The initial state is also part of the state machine definition. So the private data cluster of the stateMachine class should contain a set (array) of state classes and an initial state (which is 'listed inside'/ 'an element of' the set of states (can you force this?).

uml I: transisitions

I just did have a very brief look at the state machines in the uml specs. Transisitons are seperate from States. The transitions are performed by the state machine meta-class and not the state meta-class.

This is a bit tricky in the implementation, but described in the specs:

• If the states DoActivity finishes execution, it's generating an event/trigger.
• If a trigger is received by the SM, the DoActivity is aborted
• Certain triggers can be deffered as an attribute (?) of the state.

I didn't get all of this in my head at first reading, so propably anyone who mights try to improve the design be adjusting it to uml: Superstructure Chapter 15; Tranisitions 15.3.14; 15.3.11; current spec.

uml II: pseudostates

To get even more out of such a state machine design, we could target the list of pseudo-states. I consider all parallel process options to be really cool in LV, so fork and join could be nice to have. Even more I'm struggling with the concepts of Deep and Shallow History.

uml III: orthogonal regins, sub-statemachines

Now I'm really leaving my LV knownledg and completely focus on uml state machines. Is it possible to have a general (reusable) state machine class (and each specific state machine is inherited from this with it's own set of states)? Can we do a nesting of state machines (the top SM contains a state that contains another SM)? Can we find a deign to have two and more SM's running in parallel as 'orthogonal states', including proper mechanism to stop the others in case of severe errors in one of them?

Ok, enough of theory. Hope this hobby of mine helps you to get projects out and is not just a waste of time. My professional work is completly non-OOP, non-uml.

Felix

[Daklu]

At first I was convinced that by-val design only allows uniderctional associations of classes.

An association (as I understand it) is a more general link betweeen classes on the UML diagram. It could be composition, dependency, delegation, inheritance, etc. I can have an association between two classes without either class definition containing an instance of the other. For example, if ClassA:Method1 has a ClassB input terminal, ClassA is dependent on ClassB without necessarily containing ClassB. At the same time ClassB:Method2 can have ClassA as an input terminal. This is a bi-directional association and allowed in Labview. Labview disallows bi-directional composition of classes. No cycles allowed in class definitions. That's where LVObject (or some other parent class) comes into play.

Yes, you are reading the code correctly. Since the BaseState definition contains the BeagleStateMachine class, the BeagleStateMachine definition cannot contain BaseSate in the NextState field, so I used LVObject. Note the BeagleStateMachine's NextState accessor methods do use BaseState as input/output terminals, so there is a bi-directional dependency between the two classes.

Basically, the traditional enum shift register and case structure design is completly replaced by dynamic dispatching.

Yep, functionally it is a more well-defined variation of the Standard State Machine template provided with LV. My intent has been to find a better alternative to the QSM, not necessarily a more defined variation of the Standard State Machine template. That that's what I ended up with speaks to NI's foresight in including that template in the first place. Too bad it's not more widely used.

Readability of the design

In my experience OO programs are almost always harder to understand than procedural programs by just reading the code. It takes a lot of work to understand the relationships and responsibilities of the objects. However, once you understand those relationships OO code is easier to understand and easier to modify.

I would list this as a big con because I have to do a lot of 'cowboy coding' on customers site and neither have the uml tools available there nor the time for proper modelling.

I've done a lot of UML modelling on whiteboards. I also use pencil and paper when a whiteboard isn't handy. The primary goal of my modelling is to figure out a design that will meet the requirements, not create a complete, formally-accurate UML representation of the program. I try to include enough documentation to help others understand the relationships. Usually that means a class diagram and some sequence diagrams for the more complex operations. Recently I've taken a suggestion from Ben and started including documentation bitmaps on the block diagrams.

the state classes should not have access to the command queues (alphabet).

This is one of the key differences between a state machine and the QSM. A QSM has a command queue; a state machine does not.

In a QSM the queue controls state sequencing. In a state machine the state machine controls sequencing. In "real" state machines the machine monitors input signals and acts based on those input signals. Nothing tells the machine to make a transition; it decides when to make the transition based on the input signals. In earlier implementations of this pattern I used a DVR of a boolean cluster to represent the state machine's input signals. In this implementation I switched over to a message queue for transmitting input signals since all my input signals are essentially requests to go to a new state.

In a nutshell this is one of the major problems of the QSM. The queue in a QSM is issuing commands the state loop must follow. In this model the queue is for issuing requests to switch states. It is a subtle difference, but the consequences are huge.

[Edit]

On re-reading I think you're saying the state machine should have access to the input signals, but the states should not. Is that correct?

Also they should not contain the transitions, tranisition logic and TransisitionActivity.

This was an implementation compromise. I've considered a more pure model where the state object would invoke a transition object, which in turn would execute its actions and prepare the next state object. I haven't run across a state machine where I needed a lot of independent transition actions, so the additional complexity isn't worth it. If actions need to be performed on a specific transition when exiting a state, you can override the StateTransition method, query NextState to determine which transition is taking place, and drop the transition code in a case structure.

I just did have a very brief look at the state machines in the uml specs. Transisitons are seperate from States. The transitions are performed by the state machine meta-class and not the state meta-class.

As I understand it, UML specs define model behavior not implementation details. The modelling rules and objects may or may not translate directly into code. I'd have to see a very clear benefit to justify the additional complexity of an implementation that matches UML behavior. (That's not to say it isn't there... just that I don't see enough payback yet.)

Is it possible to have a general (reusable) state machine class (and each specific state machine is inherited from this with it's own set of states)?

Dunno yet. Probably, but I'd want to let the design age a while first.

Can we do a nesting of state machines (the top SM contains a state that contains another SM)?

Yep. Imagine the code in the Test vi (but written for a different state machine) being in one of the of the state's Execute method.

Can we find a deign to have two and more SM's running in parallel as 'orthogonal states', including proper mechanism to stop the others in case of severe errors in one of them?

Yep. I wrapped the above state machine in AQ's Actor Framework so it will spawn a parallel thread. As long as the state machines are written with the appropriate input and output signals there's no reason it can't be done.

[Daklu]

[Copied Paul's question from another thread to try and keep discussion contained.]

Just one question: What approach do you use to handle the distinction between entry and do/execution? Exit actions are easy since they occur when there is a trigger and one can just perform the exit actions while spelling out the transition to the next state. To distinguish between entry and do/execution one needs to do something else, perhaps include a Boolean or Enumeration to indicate whether we are currently in the entry or do/execution (kind of a state within a state)? I've pondered before the best way to do this but I haven't implemented such a thing so far. I just have normal state behavior (equivalent to do/execution) and exit behavior (on the transition). Adding the entry behavior would be nice!

Just to make sure we're all on the same page, here's how I use the various terms:

Entry Action - Executes one time every time the state is entered, regardless of the previous state.

Execution* Action - Executes continuously until the state decides it's done.

Exit Action - Executes one time every time the state is exited, regardless of the next state.

Transition Action - Executes after exiting one state but before entering the next state. Each transition action is associated with one arrow on the state diagram.

(*Also known as "Do Actions" or "Input Actions," depending on the literature.)

To distinguish between entry and do/execution one needs to do something else, perhaps include a Boolean or Enumeration to indicate whether we are currently in the entry or do/execution (kind of a state within a state)?

You're thinking in QSM terms where each case is a state. That's a flawed approach. It requires you to repeatedly exit and re-enter the state so you can monitor the queue for new messages. As you said, you have to somehow keep track of whether we're re-entering this state or entering it from another state to be able to handle entry actions.

I skip all that confusion and use separate vis for EntryActions, ExecutionActions, ExitActions, and StateTransition methods. The action sequencing is done by the StateMachine:Execute method, as shown below. The outer loop executes only one time for each state. The inner loop continues executing the state's ExecutionActions method until the state receives a combination of input signals the state understands as a trigger to transition to a new state.

[Daklu]

Still seem to be missing some dependencies.

Thanks for the heads up. I hadn't correctly redirected all the prior MessageLibrary links in the 2010 version. A mass compile would correct the problem but it was still annoying. I've recompiled and uploaded the 2010 version again.

[Black Pearl]

An association (as I understand it) is a more general link betweeen classes on the UML diagram. It could be composition, dependency, delegation, inheritance, etc. I can have an association between two classes without either class definition containing an instance of the other. For example, if ClassA:Method1 has a ClassB input terminal, ClassA is dependent on ClassB without necessarily containing ClassB. At the same time ClassB:Method2 can have ClassA as an input terminal. This is a bi-directional association and allowed in Labview. Labview disallows bi-directional composition of classes. No cycles allowed in class definitions. That's where LVObject (or some other parent class) comes into play.

Inheritance and Dependencies are not Associations. If I remember correctly, they both are decendants of 'relationship', while the Association is a Classifier itself.

Also note, that associations connecting properties (so not methods or parameters).

Because they are connecting properties and properties can be stored in the classes private data (if the properties belong to the class), it is always necessary to have the type cast in LV for bidirectional associations. It was clear to me that you can have bidirectional associations with by-ref implementations (also requiring the type casts). I was questioning if the same is possible with by-val design, which you showed is practical code.

[Edit]

On re-reading I think you're saying the state machine should have access to the input signals, but the states should not. Is that correct?

Yes, that was my point. From the formal point, the state machine should contain the 'alphabet', the states, the transitions, the initial state and the final states (Σ,S,s₀,δ,F). But I'm not sure if this really would lead to a 'better' code. Doing it all the way as 'correct uml' with region->vertex->state seems like an overkill to me at the moment.

I was actually looking at the mathematical model.

This was an implementation compromise. I've considered a more pure model where the state object would invoke a transition object, which in turn would execute its actions and prepare the next state object. I haven't run across a state machine where I needed a lot of independent transition actions, so the additional complexity isn't worth it. If actions need to be performed on a specific transition when exiting a state, you can override the StateTransition method, query NextState to determine which transition is taking place, and drop the transition code in a case structure.

I'm ok with an implementation compromise. I was thinking more about this. From a 'formal point of view' where I just look at the abstract state machine, it is very clear to me that states (executing code fragments) should be seperate from transitions (defining the order the code fragments are executed). I think this seperation is even more functional than Entry/Do/Exit.

As I understand it, UML specs define model behavior not implementation details. The modelling rules and objects may or may not translate directly into code. I'd have to see a very clear benefit to justify the additional complexity of an implementation that matches UML behavior. (That's not to say it isn't there... just that I don't see enough payback yet.)

This is one of the big questions: to what extend should code reflect the uml meta-model, how concrete (or strict) should be the uml syntax.

Felix

[Daklu]

Inheritance and Dependencies are not Associations. If I remember correctly, they both are decendants of 'relationship', while the Association is a Classifier itself.

I learn something new every day. Thanks for correcting my misunderstanding.

I do think in general language (if not in uml syntax) inheritance and dependencies are specific types of associations. At least that's how I use it. In the early phases of a model I'll use an association to link two classifiers that need to collaborate in some unknown way to achieve a goal. Later on as the model and software takes shape I'll usually replace it with something more specific. Are my models wrong? Possibly, but since I'm the primary customer of my implementation models and I understand my intent, I'm okay with playing a little loose with uml syntax. (I'd happily use more correct syntax if 1: I knew what the correct syntax was, and 2: I could use the correct syntax without addition cost in time.)

This is one of the big questions: to what extend should code reflect the uml meta-model

If by meta-model you mean the relationships between components in the uml spec, I think not at all. My impression is that the uml spec is primarily for people implementing uml modelling software, perhaps as a way to make models interchangable. It doesn't tell you how to use uml to model the software or how to implement the model.

For example, when I'm working with new technologies or processes I'm not familiar with I'll model the problem domain using uml. The point of this model is to make sure I understand the customer's requirements and give us a common reference for communicating. I'll use classifiers to identify components of the customer's system: DUT, Test Station, Operator, Network, etc. Sometimes these classifiers become software components, sometimes they don't. (Rarely do they become a single class.) I'm not even thinking about software design at this point so I don't really care.

how concrete (or strict) should be the uml syntax

I think that's a question that has to be answered by each programmer considering the environment they work in and the goal of the uml model. Highly regulated industries may have very strict rules regarding uml models. For me, the purpose of modelling isn't to create a model or even to document the code. It's to work through design issues and create software that meets the customer's requirements.

[Black Pearl]

I learn something new every day. Thanks for correcting my misunderstanding.

I do think in general language (if not in uml syntax) inheritance and dependencies are specific types of associations. At least that's how I use it. In the early phases of a model I'll use an association to link two classifiers that need to collaborate in some unknown way to achieve a goal. Later on as the model and software takes shape I'll usually replace it with something more specific. Are my models wrong? Possibly, but since I'm the primary customer of my implementation models and I understand my intent, I'm okay with playing a little loose with uml syntax. (I'd happily use more correct syntax if 1: I knew what the correct syntax was, and 2: I could use the correct syntax without addition cost in time.)

I enjoy the discussion with you, because it really helps me to understand my own issues (in this case uml) better .

As the metamodelling is a field somwhere between mathematical/philosophical domain and formal (computer) languages, it comes to splitting hairs about every single word. In addition I'm a bit frustrated why associations are classifiers and not relationships.

So slightly modifying your statement above: 'inheritance and dependencies are specific types of associations relationships' is according to the uml specs.

After writing the previous post, I actually found an explanation why associations are classifiers: they own properties.

Back to splitting hairs: a link is the instance of an association.

If by meta-model you mean the relationships between components in the uml spec, I think not at all. My impression is that the uml spec is primarily for people implementing uml modelling software, perhaps as a way to make models interchangable. It doesn't tell you how to use uml to model the software or how to implement the model.

Nope. They specify the model.

So, whatevery you do, a state in your (any) uml model ownes an optional 'entry'-Behaviour.

If your implemenation of a state machine has an entry code, but your uml model has not, your model is incomplete (which is not bad!).

If your model has an entry behaviour but your implementation has not, your work is not finished; so either: a) rework the model so there is no 'entry' behaviour, b) code the 'enrty' (if possible by your state machine design) or c) make a state machine design that allows for an 'entry' code.

To get a bit philosophical, we make our lifes easier be needing to make less decisions. Having a good knownledge of uml and LV eliminates a) from above choices (never model what we can't do because we now what we can't do) and make c) more easy because we know a state machine design that allows for entry/doActivity/exit.

Felix

[CharlesB]

I downloaded and looked at the code, it looks great!

I have a few questions, though:

• Transitions seem to be handled in Entry and Exit actions. But what if I want an action to be executed only in a from one state to the other? (i.e. a transition action)
• I will use the SM from the GUI, which will trigger state changes. Can I use the SendMessage method for that? I ask this because it is currently a private method of the SM
• What needs to be done if I want a more generic SM class that will be inherited, in order to be reusable from one case to the other?
• Have you considered to make it an OpenG package?

Charles

[Daklu]

I've attached a state machine template I've been working on. It requires LV2010 and the LapDog Messaging Library v1.2. The main state machine loop is designed to run in parallel with other processes, so I've wrapped it in another construct I use--a SlaveLoop object. SlaveLoop.ExecutionLoop is where you'll find the main state machine loop. You can take it out of there and drop it on a Main.vi if you want to ditch the slave loop. IIRC the main differences between the original state machine implementation and this template are, a) the "inner" while loop is now implemented in each state's ExecutionActions methods instead of on the State Machine Loop diagram, and b) the error handling mechanisms in BaseState.TransitionActions is a little more robust.

I'll answer your questions in the context of the template, not the original example.

Transitions seem to be handled in Entry and Exit actions. But what if I want an action to be executed only in a from one state to the other? (i.e. a transition action)

Transition actions are implemented by checking which state is present in the NextState field and casing out the possibilities. The ExecutionActions method sets the NextState field when the input conditions trigger a state change, but the current state isn't actually changed until the TransitionActions method executes. Transition actions are ideally implemented by overriding the BaseState.TransitionActions method, but strictly speaking they could also be implemented in the MyState.ExitActions method. If you do override the TransitionActions method, be sure to call BaseState.TransitionActions right before exiting your method. BaseState.TransitionActions does the error checking (substituting the ErrorState if an error is present) and prepares the NextState object for execution.

I will use the SM from the GUI, which will trigger state changes. Can I use the SendMessage method for that? I ask this because it is currently a private method of the SM

The way I typically handle that is by having the GUI events call SlaveLoop methods. The mediator loop in SlaveLoop.ExecutionLoop handles the message and in turn sends messages to the state machine. The mediator loop appears to be a needless complication, but that is where I implement multiple triggers when I want to progress through a series of states, such as when exiting the state machine.

What needs to be done if I want a more generic SM class that will be inherited, in order to be reusable from one case to the other?

This state machine is implemented as a collection of classes, not a single class. I haven't explored inheriting an entire state machine since I haven't had a reason to do so. Subclassing a single state within your state machine might be possible--I haven't tried it. The main complication is if your parent class has data the subclass requires you'll need some way to set the parent data when the subclass in created. (I do that in BaseState.TransitionActions so the new state object has correct queue references.)

Have you considered to make it an OpenG package?

The Beagle code specifically or this state machine pattern in general? The Beagle code, no. The State Machine template, yes. (Well, a VI package, not an "OpenG" package. LapDog and OpenG have slightly different purposes and don't quite fit together.) There are a couple things that have been delaying releasing the template as a package:

1. This template is copy-and-paste reuse, not vi.lib reuse. I need a scripting tool that will copy the template library to the user's project directory and include it in the project. Scripting isn't my strong point and I don't have time to figure it out. This is the biggest reason.

2. It depends on the LapDog Messaging Library. I'm reluctant to release code with dependencies on other packages because it can easily lead to a variation of dll hell. It will probably be okay since this is a template, but I'm still not very comfortable doing it.

3. I have other LapDog packages in my queue that have had a higher priority. If there's demand for the template I can certainly shift priorities.

[Edit - Replaced the zip file with the correct one.]

LD StateMachineTemplate.zip

[CharlesB]

Wow, thanks! I was working on a generic SM based on your code too, and just finished when I saw your answer Never mind, it got me diving in the code. However I think the attachment is still the old code

[Daklu]

Doh! Sorry about that. I was in a rush trying to get the post finished this morning and stupidly linked to the wrong zip file. I attached the correct (I hope) zip to my post above.

[Daklu]

By the way, here's an example (LV2009) of similar Harel state machine behavior without using objects. The main differences between this and the object implementation are that there is no state specific data or error handling in this example. The example also doesn't have any execution actions other than monitoring messages from the user.

A couple things worth noting:

0. This example makes extensive use of local variables in the state machine loop. I did this for simplicity. Usually I will have a separate display loop and have the state machine send messages to it when fp controls need to be updated.

1. The producer loop does not directly initiate state transitions. It sends a message to the state machine requesting a state transition, which the state machine will do if a valid transition is requested. If an invalid transition is requested the state machine ignores the message, though in the past I have sent debug or status messages to the UI to let the user know what is happening. Allowing producer loops to directly control state transitions is IMO the single biggest flaw in the traditional QSM. You have to break that link if you want to create more robust and scalable code.

2. Using a "real" state machine means all my transition logic *has* to be contained in the state machine loop instead of distributed across several loops. It's way easier to verify that my code correctly implements the state diagram and way harder for other developers to use the state machine loop incorrectly. There is simply no way for a rogue producer to initiate a transition that violates the conditions defined by the state machine.

3. This model provides better separation from the UI. I have often seen devs disable front panel controls to prevent invalid transitions when using a QSM. I usually ran into synchronization issues when tried that--controls wouldn't always be enabled or disabled at the right time. Here I don't have to worry about that--the state machine just ignores the message. If I want to disable a control I'll have the UI display loop do that in response to the state transition messages sent by the state machine. (Not shown in the example.)

4. It's ridiculously easy (and safe) to have multiple producers controlling the same state machine loop. Just give the new producer a reference to the state machine's input queue and start sending it messages. Asynchronicity is not an issue as far as the state machine is concerned. (Try that with a QSM! )

------------

When I wrap everything in classes the concept seems more complicated that it really is. I hope this example helps people understand the core functionality at work and why I think it's time for the Labview community to move away from the QSM (unless you're taking a certification exam.)

If anyone feels like comparing implementations I'm curious what a traditional QSM looks like that has this same behavior.

SimpleStateMachine.vi

[CharlesB]

Hi there,

It's great to have a simplified version of the object-based SM.

A few comments on the last version you posted:

- I would definitely go for a vi.lib version. Having to duplicate the SM base code is counter-intuitive and will keep people from using it. This is also useful if you want to have several SM in the application, or even nested SMs. The work required to switch to such a version is not difficult: I already done it, for now I'm passing the initial state as an argument to Execute.vi, and modified "create base state" to take as argument the state type you want to create.

- Binding the SM to a particular messaging framework is not great, also. Not that the lapdog one is bad, but people are surely using their own one, so we should let them choose. This way you have a SM framework doing only SM, and people add messaging with customizing the base state, or something like this (surely there's better way)

- These 2 points allow to make a true VI package

I'm still working on making a simple example without messaging and "library-based", if anyone is interested let me know

[Daklu]

- I would definitely go for a vi.lib version.

It's very unlikely I will release this version as a package deployed to vi.lib. Doing so prevents customizing the existing state classes to meet the specific application requirements. It's possible to add plumbing that allows overridden core state classes to be used in place of the core state classes, but it adds complexity to the implementation (which is already difficult for many to understand) and I don't see much value in that feature. Putting the state machine template in vi.lib works best when you have many state machines across several projects with similar behavior. Single developers or small groups working in a relatively small domain are likely to be able to do that. As a developer creating code for other developers, I need to keep it as flexible and easy to use as possible.

Having to duplicate the SM base code is counter-intuitive and will keep people from using it.

It's just like any other template code available in LV... except this template includes several classes the work together whereas most other templates fit on a single block diagram.

This is also useful if you want to have several SM in the application, or even nested SMs.

The template doesn't prevent having multiple or nested state machines in an app. Just give each containing library a unique name.

The work required to switch to such a version is not difficult: I already done it, for now I'm passing the initial state as an argument to Execute.vi, and modified "create base state" to take as argument the state type you want to create.

Can you post it?

- Binding the SM to a particular messaging framework is not great, also. Not that the lapdog one is bad, but people are surely using their own one, so we should let them choose. This way you have a SM framework doing only SM, and people add messaging with customizing the base state, or something like this (surely there's better way)

I agree everyone tends to use their own messaging system. Unfortunately there isn't a clean way (I can think of right now) to allow users to inject an arbitrary messaging system without modifying the core code. The states *have* to get signals from external sources somehow, be it queues, notifiers, DVRs, etc. That said, I'm perfectly willing to discuss alternatives.

I'm still working on making a simple example without messaging and "library-based", if anyone is interested let me know

Of course.

[CharlesB]

It's very unlikely I will release this version as a package deployed to vi.lib. Doing so prevents customizing the existing state classes to meet the specific application requirements. It's possible to add plumbing that allows overridden core state classes to be used in place of the core state classes, but it adds complexity to the implementation (which is already difficult for many to understand) and I don't see much value in that feature. Putting the state machine template in vi.lib works best when you have many state machines across several projects with similar behavior. Single developers or small groups working in a relatively small domain are likely to be able to do that. As a developer creating code for other developers, I need to keep it as flexible and easy to use as possible.

At some point of the day I thought about asking user to give an intermediate base class that inherits SM's base class, but that's impossible and nobody will bother. We reach the limit of LabVIEW OO model (why don't we have template or duck-typing ?).

It's just like any other template code available in LV... except this template includes several classes the work together whereas most other templates fit on a single block diagram.

OK. I'm just not used to this paradigm (copy and paste) for giving librairies. Template updated? Download update and re-customize it....

IThe template doesn't prevent having multiple or nested state machines in an app. Just give each containing library a unique name.

True

Can you post it?

Attached.

II agree everyone tends to use their own messaging system. Unfortunately there isn't a clean way (I can think of right now) to allow users to inject an arbitrary messaging system without modifying the core code. The states *have* to get signals from external sources somehow, be it queues, notifiers, DVRs, etc. That said, I'm perfectly willing to discuss alternatives.

You mean something like interfaces ?

Seriously, I think it's better to ship code with standard queue (thus no shiny error cluster message), if users have their framework they can use it instead.

Also, IMHO the model you use in slave queue is a bit complex, maybe you can give people just an input queue to trigger state changes and they'll message what they want on output. In my case for example I already have Model VIs (in terms of MVC) that message the stuff out to View.

I'm no guru enough to make a nice stuff, and by short of time I think I'm gonna use the SimpleSM.vi you posted, which perfectly fit my need for a simple and clean SM. I'm frustrated by the nice stuff you can get on C#, but LabVIEW just can't enable us to build such a quick and clean thing.

Maybe a simple thing would be to provide the SM with a dictionary of state->trigger->next-state? Would be glad to help but sincerely out of time

LDSM.zip

Edited June 14, 2011 by CharlesB

[drjdpowell]

Hi Daklu,

Most of your criticism of the (badly named) "QSM" is all down to the flawed design of using the same queue for messages to the QSM and "states" (really operations) within the QSM. This flaw may be common, but it is not inherent to QSMs, and templates such as the "JKI statemachine" don't have it. There is no asynchronicity in a properly designed QSM (your point 4), nor do producer loops directly initiate QSM "states" (point 1). As to better separation of the UI (point 3), I'm not sure ignoring messages is all that great an idea (I have visions of the annoyance my Users will have after pressing "start", and coming back 5 hours later to find the equipment just sitting there).

Point 2 is complicated since a QSM isn't actually a state machine and thus isn't a good way to implement a complex state diagram. But how good is a true state machine at implementing a complex flow chart? Aren't you making the same error as "QSM for everything" people by suggesting "true state machine for everything"? Is a hammer a useless tool just because people have mislabeled it as a type of saw?

-- James

By the way, here's an example (LV2009) of similar Harel state machine behavior without using objects. The main differences between this and the object implementation are that there is no state specific data or error handling in this example. The example also doesn't have any execution actions other than monitoring messages from the user.

A couple things worth noting:

1. The producer loop does not directly initiate state transitions. It sends a message to the state machine requesting a state transition, which the state machine will do if a valid transition is requested. If an invalid transition is requested the state machine ignores the message, though in the past I have sent debug or status messages to the UI to let the user know what is happening. Allowing producer loops to directly control state transitions is IMO the single biggest flaw in the traditional QSM. You have to break that link if you want to create more robust and scalable code.

2. Using a "real" state machine means all my transition logic *has* to be contained in the state machine loop instead of distributed across several loops. It's way easier to verify that my code correctly implements the state diagram and way harder for other developers to use the state machine loop incorrectly. There is simply no way for a rogue producer to initiate a transition that violates the conditions defined by the state machine.

3. This model provides better separation from the UI. I have often seen devs disable front panel controls to prevent invalid transitions when using a QSM. I usually ran into synchronization issues when tried that--controls wouldn't always be enabled or disabled at the right time. Here I don't have to worry about that--the state machine just ignores the message. If I want to disable a control I'll have the UI display loop do that in response to the state transition messages sent by the state machine. (Not shown in the example.)

4. It's ridiculously easy (and safe) to have multiple producers controlling the same state machine loop. Just give the new producer a reference to the state machine's input queue and start sending it messages. Asynchronicity is not an issue as far as the state machine is concerned. (Try that with a QSM! )

------------

When I wrap everything in classes the concept seems more complicated that it really is. I hope this example helps people understand the core functionality at work and why I think it's time for the Labview community to move away from the QSM (unless you're taking a certification exam.)

If anyone feels like comparing implementations I'm curious what a traditional QSM looks like that has this same behavior.

[Daklu]

Most of your criticism of the (badly named) "QSM" is all down to the flawed design of using the same queue for messages to the QSM and "states" (really operations) within the QSM. This flaw may be common, but it is not inherent to QSMs, and templates such as the "JKI statemachine" don't have it.

One of the problems with the QSM's poor name is that it doesn't give a clear idea of what it actually is. As near as I can tell there is no concensus on what characteristics make a QSM a QSM. Everyone has their own idea about what a QSM looks like. I generally focus my criticisms on the producer-consumer QSM model I posted here because I see it used a lot and many people do not understand its structural flaws.

The reason I don't use QSM's of any flavor run much deeper and reflect a fundamentally different approach to programming.

There is no asynchronicity in a properly designed QSM (your point 4)

That's my point. Project requirements, not implementation, determine whether or not asynchronicity is needed.

Case in point: Several months ago I wrote a small, independent component that captured, processed, stored, etc. I2C data from several sensor chips. It ran on a computer dedicated to collecting data while a robot did various things to the DUT. It had a front panel that allowed operators to start and stop data collection, view data, save to disk, etc. After a while the operators decided they wanted the component to start collecting, stop collecting, save data, etc automatically based on commands from the computer controlling the robot, BUT, they also wanted to be able to interact with the front panel at the same time. One process, two clients.

"Bottom of the ninth and QSM Engineering is down by six runs..."

At bat: Ugly Hack

On deck: Race Conditions

In the hole: Mayhem

nor do producer loops directly initiate QSM "states" (point 1).

JKI's state machine combines the producer and consumer, so the statement is rather meaningless in that context. I don't remember ever runing across a PC-QSM in the wild where the producer loop didn't directly initiate state changes. (Except for my own explorations before switching to object state machines, but that doesn't really count.)

As to better separation of the UI (point 3), I'm not sure ignoring messages is all that great an idea (I have visions of the annoyance my Users will have after pressing "start", and coming back 5 hours later to find the equipment just sitting there).

In the example I posted the default behavior of any state is to ignore a message. You, the programmer, add code to enable the correct message response. QSMs have the opposite behavior; by default they accept and execute every message they receive regardless of the state of the loop. You, the programmer, have to write code to prevent an incorrect message response. Which is the safer approach? Which is easier to verify? As change requests come in and you add more messages, which is going to be easier to maintain?

In the case of your Start button, the state machine ignores the message if a start message doesn't make any sense given the application's current condition. Maybe it's already running. Maybe the instruments aren't initialized. Maybe there's an error. It doesn't matter why the message is invalid, it just matters that the message is invalid. This makes the state machine robust to errant messages and near bulletproof.

To handle user interfaces, usually my state machines will broadcast general messages ("DataCollectionStarted") to notify clients about what is happening in the state machine. Client code can choose to do (or choose not to do) things like disabling a start button, popping up a dialog box, or electrocuting the user if desired. But this is implemented in UI code. It is not part of the state machine.

Point 2 is complicated since a QSM isn't actually a state machine and thus isn't a good way to implement a complex state diagram. But how good is a true state machine at implementing a complex flow chart?

It's interesting you say this. I have no idea where exactly QSMs came from, but I've long suspected there were three main things that influenced its creation:

1. A strong desire to keep the block diagram size to a single screen or less.

2. An unhealthy reluctance to create sub vis.

3. Using flow charts as the primary (and perhaps only) tool to model the application.

Your question reflects the fundamental differences I mentioned earlier. I don't implement complex flow charts because flow charts don't do a good job of modelling a solution to requirements placed on modern-day applications. Flow charts are particularly useless (IMO) for modelling event-based programming. I do use flowcharts during development to clarify processes and decision making, but my application is not structured around flow charts.

When I have sequential processes that can be modelled accurately using a flow chart, I implement it the same way as everybody else--with case structures, loops, and sub vis. It's far, far easier to follow the logic when well-named sub vis and switching conditions are layed out sequentially than when I have to flip back and forth between case frames as they manipulate the state queue.*

(*Using a queue to control execution flow is one of my biggest issues with all QSM patterns. There's potential there for creating self-learning applications and other interesting behaviors that aren't explicitly defined during development, but when was the last time you wanted an application to do something unpredictable? Execution flow is most clearly expressed by using wires to connect sub vis.)

Aren't you making the same error as "QSM for everything" people by suggesting "true state machine for everything"? Is a hammer a useless tool just because people have mislabeled it as a type of saw?

I'm not suggesting using a state machine for everything... just those things where a chunk of functionality needs to have different responses to the same message depending its current state. Things like instrument APIs and high level application logic. I don't typically use state machines in my UI code, but I may at some point. It's usually not required.

State machines do play a major role in my applications because application behaviors usually have to change depending on the state of various components. I also uses message handling loops a lot. A message handling loop looks a lot like a PC-QSM consumer loop. The difference is in how it is used and what limitations I put on it:

1. The most important thing is that I do not--ever--let a message handling loop put messages on its own queue. This rule prevents any sequential dependencies between cases from forming. In fact, I don't allow the queue wire to connect to the case structure at all. That makes it easy to see that I (or someone else) hasn't accidentally created an internal sequential dependency. If I want to reuse the code in another message handling case I make it into a sub vi and call the sub vi from both cases.

2. Message handling loops don't have any self-state. It's not "uninitialized," "initialized," "running," etc. The loop is either executing or its not. It may, depending on the needs, maintain information about loops it communicates with, but it is not stateful in itself.

3. Each message must be independent of all other messages. That is, messages can be called in any order and at any time and the message handler must remain fully functional. As long as I've adhered to rules 1 and 2 this one usually follows without any additional effort.

State machines and messages handlers are the two flavors of loops I use on my block diagrams for non-trivial applications. The diagram below illustrates the differences in a nutshell. (Notice neither of them puts messages on their own queue.)

[drjdpowell]

One of the problems with the QSM's poor name is that it doesn't give a clear idea of what it actually is.

Hi Daklu,

Another of the problems with the bad "QSM" name is that there are many conversations where someone brings up "QSM" and it triggers comment about their flaws as true state machines, "state diagrams" and such, WITHOUT ascertaining if the original use of the QSM pattern was anything to do with "different responses to the same message depending its current state". I suspect most use (and certainly better use) is more similar to what you use your message handler for. It may even be intended (dare I say it) as a structure for programing without separating the UI from the rest of the code! We lesser programmers tend to do that. So I did get the mistaken impression that people were suggesting true state machines for all sorts of purposes that seemed to me to be a poor fit.

2. An unhealthy reluctance to create sub vis.

You might be right. I think (lest I'm mistaken) that a QSM like JKI's is interchangeable with a QMH with appropriate subVIs (and the JKI-SM can meet your three conditions for QMHs). In my own use of the JKI-SM, my first uses definitely were flawed by too little use of subVI's, while lately I use a mix of mostly subVIs for low-level operations and frames of the case structure for higher-level ones. Your argument that case structures, loops and subVI's is clearer than a queue for complex processes is a much better one than your state-machine related criticisms; now your talking about what people use "QSMs" for.

-- James

[Daklu]

We lesser programmers tend to do that.

Let me quickly address this comment first. I realize you may have intended it as a tongue-in-cheek comment or maybe as a bit of self-deprecating humor. Either way, I want to make it clear I do not think I am a "greater" programmer or that others are "lesser" programmers. We are all just programmers attempting to write applications that best fit our customer's needs. To do that we draw on our experiences and knowledge. My experiences and knowledge don't make me any more or less of a programmer than anyone else. I do think the LV path I travelled over the past 5 years has led me to develop coding practices that produce better code, but that is not the same as being a better programmer.

Another of the problems with the bad "QSM" name is that there are many conversations where someone brings up "QSM" and it triggers comment about their flaws as true state machines, "state diagrams" and such,

What with this thread being about object-based state machines and all I figured it's kind of an inherent assumption that we're talking about state machines.

WITHOUT ascertaining if the original use of the QSM pattern was anything to do with "different responses to the same message depending its current state".

Unfortunately Amazon isn't carrying "The Idiots Guide to the Complete History of the QSM" and my searches for its origin or how it was originally intended to be used have not been fruitful. I'm left to surmise it's original intent based on what it does well and how I see it implemented.

I suspect most use (and certainly better use) is more similar to what you use your message handler for.

I suspect many *think* they are using it in a way similar to how I use a message handler. What I see (especially in applications that have evolved over time) is message handling loops that no longer simply process messages, but which take on the characteristics of a state machine. That's not to say I see that from the typical Lava contributor... it's just what I see in general.

I think (lest I'm mistaken) that a QSM like JKI's is interchangeable with a QMH with appropriate subVIs (and the JKI-SM can meet your three conditions for QMHs).

I don't call them QMH's... that just leads to more confusion. Usually I call them "mediators" or "mediator loops," since that's often the role they fill in my code. (Mediating messages between different functional parts of the application.) "Message Handling Loop" might be a better generic term--emphasize the message instead of the queue.

Yes, strictly speaking, a JKI-SM or PC-QSM can be made to be functionally equivalent to an MHL. It is possible to create sequences of states and manipulate the state queue in a way that gives the same result as the sub-vi's and case statements of an MHL. My question is why? Using queue-based sequencing makes the code harder to understand and is more difficult to verify.

We could take it a step further and instead of queueing of states, we could link sub vis to create sequences within each state. After a state executes we could have it return immediately to the message receiving state. But if we want to do that, why use a JKI-SM at all? Seems to me we've just discarded nearly all of the functionality the framework provides and our code will be a lot simpler by using something else.

The one thing that all QSM's support (and even encourage) is actively manipulating the flow of execution via some sort of queue. That, to me, is the defining feature of a QSM. That's the practice I'd prefer to see follow the path of the "Goto" statement. Do we *have* to use that functionality in a QSM-type structure? Nope. Are we going to use it when a customer is breathing down our neck and it's the fastest way to give them what they want? Probably. Are there better patterns that don't expose us and our customers to those issues. I believe the answer is yes, which is why I continue to talk about it.

Your argument that case structures, loops and subVI's is clearer than a queue for complex processes is a much better one than your state-machine related criticisms; now your talking about what people use "QSMs" for.

I appreciate the feedback. It's always a struggle to figure out the best way to communicate what is a really a set of complex interacting issues. I'm not sure I agree with the implied assertion that most people use QSMs to implement complex stateless processes. I've seen plenty of QSMs (and written plenty of my own) that ended up attempting to represent states as well. Often that results in lots of conditional logic in the Timeout case or weird waiting loops and queue manipulation in subsections of the execution flow diagram.

I've written a lot about the QSM. Ultimately my writings have taken a two-pronged approach, though it may not have always been clear:

1. If you use a QSM to sequence a series of stateless processes, create sub vis and wire them together directly.

2. If you use a QSM to implement something that has states, use a real state machine.

The prong that resonates with any particular person depends on what they are using the QSM for. I don't think I can focus on one argument and ignore the other.

I'll also add that my LV experience has been almost exclusively in the desktop application space and that is the platform I'm referring to. I've never done FPGA, Fieldpoint, or CRIO in Labview. It may very well be that the QSM is one of the better patterns for those platforms. I don't have the knowledge or experience to make a claim one way or the other.

[drjdpowell]

Sorry, should have used a smilie of some kind. Not an effective smilie user. There.

On a side note, I have just learned that there is a practice CLA exam and tried a go of it last night. Being an ATM program with obvious state-fullness I used a state machine, my first real one ever, I think!

-- James

[Daklu]

Sorry, should have used a smilie of some kind.

Actually, I was glad you made the comment. It gave me a nice segue into my response.

I often worry that I come across as an arrogant know-it-all descending from the mountain top to bless the unwashed masses with my wisdom. Every now and again I feel like I need to make a statement assuring people that's not how I think about myself. I talk a lot about my ideas and the things I'm doing with the hope of generating discussion. Hopefully through the free exchange of ideas we can discover new and better ways to build our applications.

On a side note, I have just learned that there is a practice CLA exam and tried a go of it last night. Being an ATM program with obvious state-fullness I used a state machine, my first real one ever, I think!

Very cool! Any chance you could post it? Don't worry about the spit and polish or completenesss--I'm interested in seeing your state machine implementation. I'm also curious what differences (if any) you noticed in your dev process or your code by implementing it as a state machine instead of a QSM. I know what *I* think about state machines vs. QSMs, but it might just be the way my brain is wired.

[ironically, certification exams are one of the few places where I do recommend using a QSM. The problems are broken down in a way that assumes a QSM implementation and given the time constraints it's easier to go with the flow.]

[drjdpowell]

I often worry that I come across as an arrogant know-it-all descending from the mountain top to bless the unwashed masses with my wisdom.

I don't think you give that impression.

Any chance you could post it? Don't worry about the spit and polish or completenesss--I'm interested in seeing your state machine implementation.

It's not even close to complete (the four-hour time limit would be a killer), but I can show the statemachine with a case that is; the "Main Menu" when the user selects the "Fast Cash $50" option (see attachment).

I'm also curious what differences (if any) you noticed in your dev process or your code by implementing it as a state machine instead of a QSM. I know what *I* think about state machines vs. QSMs, but it might just be the way my brain is wired.

[ironically, certification exams are one of the few places where I do recommend using a QSM. The problems are broken down in a way that assumes a QSM implementation and given the time constraints it's easier to go with the flow.]

I found the ATM problem to be obviously calling for a state machine; it practically defines all the states for you. The problem equally seems to call for some LVOOP, again practically defining all the classes: "User Console" and "Account Database", with children "Simulated Console" and "Simulated Database" (ready for the eventual replacement with "Physical Console" and "Enterprise Database").

If I were to use a JKI-SM (though I wouldn't be allowed the template on the exam), I might instead have had "Macros" such as...

"// Main Menu

Card Slot >> disable

Keypad >> disable

Menu State >> Main

Display Message >> Main Menu

Wait for User Input

Process Main Menu Input"

... with the "Process Main Menu Input" calling (if the User pushed this button) "Fast Cash $50", which would call "Withdrawal >> Complete".

The QSM version would not be terrible but would be clearly poorer than a true SM. But this problem is very clearly definable as a statemachine. Most programs I write involve "do the task requested before returning to idle", with the complexity of the task being more easily broken down into sub-tasks than states. For complex tasks, JKI-style macros are quite clear and they're quick to write compared to wiring up subVIs. The subVI option is clearer than JKI-SM frames, and I can appreciate some of the other advantages you point out, but the real reasons I've started to use subVI's more and more lately is the advantages of OOP classes and dynamic dispatch.

BTW, what do you think of the provided example solution to the ATM example test? The one where it's done with Action Engines.

-- James

Edited June 23, 2011 by drjdpowell