Macro State in State Machine

[dannyt]

Hi,

I have been trying to catch up on interesting topics I have put to one side in the past and have spent a fun day reading about state machines and different architectures, I still have a great deal more to read and learn.

I keep coming across the term Macros / Marco state in a number of the topics and I am not fully sure I understand this term.

With regards to the JKI state machine, I think the Marco states are states where no work is actually done but new state transitions are push on the existing queue of states so that can easily find them. I have searched on Lava for this term and though it has lead me to reading a lot more threads about QSM & SM I still have not found out what people mean when using this term.

Any explanation would be appreciated.

regards

Dannyt

[PaulL]

Can you give an example link where this term appears?

I'm not sure what a Macro State would be. I know what a Superstate is.

Paul

[ShaunR]

Hi,

I have been trying to catch up on interesting topics I have put to one side in the past and have spent a fun day reading about state machines and different architectures, I still have a great deal more to read and learn.

I keep coming across the term Macros / Marco state in a number of the topics and I am not fully sure I understand this term.

With regards to the JKI state machine, I think the Marco states are states where no work is actually done but new state transitions are push on the existing queue of states so that can easily find them. I have searched on Lava for this term and though it has lead me to reading a lot more threads about QSM & SM I still have not found out what people mean when using this term.

Any explanation would be appreciated.

regards

Dannyt

A macro state is just a single sate that represents other multiple states (an alias if you like). Commonly, this would be things like initialisation/finalisation where (for example) the Init state could be an alias for Load Settings, Clear Display and then Set Window Position etc. But the term isn't limited to SMs , Excel has "Macro recording", for example, which will assign a single command to a number of operations that you do and will"replay" them back when executed (either by hitting a hot-key or explicitly running the macro)

[dannyt]

A macro state is just a single sate that represents other multiple states (an alias if you like). Commonly, this would be things like initialisation/finalisation where (for example) the Init state could be an alias for Load Settings, Clear Display and then Set Window Position etc. But the term isn't limited to SMs , Excel has "Macro recording", for example, which will assign a single command to a number of operations that you do and will"replay" them back when executed (either by hitting a hot-key or explicitly running the macro)

Thank you Shaun, that makes sense, along the lines I though people meant, just asking in case there was any more meaning to it than that.

typical topics include

JKI state machine

how do I model this

how many events

I am still working my way through these :-)

Danny

[PaulL]

Thank you Shaun, that makes sense, along the lines I though people meant, just asking in case there was any more meaning to it than that.

typical topics include

JKI state machine

how do I model this

how many events

I am still working my way through these :-)

Danny

I see. I will need to read through the topics but I can say this right away:

We use the State Pattern as described by the Gang of Four. In this pattern we would never create a macro or queue of states, although we can and do create macros of triggers (could be commands) that we can invoke serially on the statemachine. Specifying a series of states would be antithtetical to the concept of a statemachine, I think.

For instance, working off ShaunR's example, "Load Settings," "Clear Display," and then "Set Window Position" could all be separate commands (triggers) wrapped into an "Init" macro command, but these are not states. An Invoker calls the corresponding methods on the Context, which in turn delegates the operations to the State (so our abstract State would have the methods loadSettings, clearDisplay, and setWindowPosition, and the implementation behavior for these methods would vary between states--which is the point of having a statemachine).

One clarification is in order. It is both possible and reasonable for a Context method to invoke several methods on State in sequence (hence decomposing a command into smaller operations). So, we could alternately implement Context:init as State:loadSettings...State:clearDisplay...State:setWindowPosition. (For ease of comprehension in practice we only do this if won't change states along the way--and rarely, at that--but there is really no theoretical reason you couldn't change state at each step.) Even in this case, though, we are assembling a series of operations, not states. Again, I don't thing specifying a sequence of states is in keeping with the concept of a statemachine.

[PaulL]

One more clarification.

StandbyState:init (or whatever concrete state has an implementation of init) can consist of Context:loadSettings...Context:clearDisplay...Context:setWindowPosition if these methods don't vary according to the state.

[Daklu]

Just wanted to throw my $.02 behind Paul's comments. I've used a variation of the GoF State Machine pattern for several components and I'm quite liking it. (Is anyone surprised...?)

One of the big problems I had with QSMs is that they don't really stay in any one 'state.' Even when there is no transition to another state the SM is exiting and re-entering the same state. Same thing, you say? Not when you start adding more strictly defined behaviors to your state machine. Every state in my SMs can define any of four different kinds of actions:

1. Entry Actions -- These are actions that are performed exactly once every time this state is entered from another state.

2. Execution Actions -- These are actions that are performed continuously while the SM remains in the current state.

3. Exit Actions -- These are actions that are performed exactly once just prior to this state exiting.

4. Transition Actions -- The are actions that are performed exactly once when this state exits and are unique for every 'current state-next state' combination. When looking at a state diagram, these actions are associated with the arrows.

By recognizing these four different types of actions, it is much, much, easier for me to design and implement a state machine that does what I want it to do. I spend far less time fighting the implementation when trying to add an arbitrary new action. You can create a QSM that recognizes these four types of actions (my first experiments did) but I found it got pretty ugly pretty quickly and is error prone. Entry Actions and certain kinds of Execution Actions get particularly messy in a QSM. (Waiting actions do too.) I switched over to an object-based state machine and haven't looked back.

I don't think specifying a sequence of states is in keeping with the concept of a statemachine.

I fully agree, and that is another major issue I have with the QSM. When you look at a state diagram the arrows not only define the transitions the SM does make, but also defines the transitions the SM is allowed to make. The SM defines and restricts it's own behavior; it doesn't depend on an external entity to know details about what states are "valid" to call from its current state. If there's no arrow, the SM simply won't transition from one to the other regardless of the command it received, because it's an invalid command. Leaving that responsibility to the external entity is error prone. QSMs allow far too much external control over the SM's internals. (In fact, I try to write my components in such a way that the SM client isn't even aware the implementation uses a state machine.)

[drjdpowell]

For the benefit of Dannyt and others reading, "Queued State Machines" such as the JKI state machine are misnamed in that they are not actually state machines. True state machines are a different concept, and are what Paul_at_Lowell and Daklu are talking about. QSMs are more like queued command or queued operation machines, and thus the concept of a "macro" set of commands applies.

-- James

[CharlesB]

I agree with last two posts; needing also a "real" state machine, I have looked into the Statechart toolkit but not satisfied and quite expensive. Is there a template or an example of this, with JKI SM or something else?

[crelf]

We use the State Pattern as described by the Gang of Four. In this pattern we would never create a macro or queue of states, although we can and do create macros of triggers (could be commands) that we can invoke serially on the statemachine. Specifying a series of states would be antithtetical to the concept of a statemachine, I think.

One of the big problems I had with QSMs is that they don't really stay in any one 'state.' Even when there is no transition to another state the SM is exiting and re-entering the same state. Same thing, you say? Not when you start adding more strictly defined behaviors to your state machine.... When you look at a state diagram the arrows not only define the transitions the SM does make, but also defines the transitions the SM is allowed to make. The SM defines and restricts it's own behavior; it doesn't depend on an external entity to know details about what states are "valid" to call from its current state. If there's no arrow, the SM simply won't transition from one to the other regardless of the command it received, because it's an invalid command. Leaving that responsibility to the external entity is error prone.

For the benefit of Dannyt and others reading, "Queued State Machines" such as the JKI state machine are misnamed in that they are not actually state machines. True state machines are a different concept, and are what Paul_at_Lowell and Daklu are talking about. QSMs are more like queued command or queued operation machines, and thus the concept of a "macro" set of commands applies.

Excellent topic guys. I agree that using the term QSM is a misnomer, and we should use QMH (queued message handler) or the like instead.

[Daklu]

...we should use QMH (queued message handler) or the like instead.

NI had already laid claim to the name "QMH" as a starter template that ships with LV. It's vaguely similar to the QSM but completely sidesteps the problems associated with a producer-consumer QSM by virtue of only having a single loop.

I proposed calling it a "function machine" here, and "Hector" here, neither of which gained much traction. (Go figure...) I'd support calling it "painful," "job security," or "bad idea" if anyone else wanted to take up the cause. I'm still fairly well convinced the QSM pattern shown here is not a very good design for anything other than NI's exams or prototype (read: throwaway) code, but I've written much on that already and won't repeat myself here.

I agree with last two posts; needing also a "real" state machine, I have looked into the Statechart toolkit but not satisfied and quite expensive. Is there a template or an example of this, with JKI SM or something else?

If you're comfortable with objects I posted an object-based state machine here. I've refined it a bit since that post but the principles are sound.

[BobHamburger]

People are throwing the term "state machine" around in this thread (and in the general LV community at large) pretty cavalierly. When I took Digital Design as an undergraduate (granted, about a million years ago, or so it seems), we studied two kinds of state machines:

1. Moore: the outputs are uniquely determined by the state, and

2. Mealy: the outputs are determined by the transitions between states.

The other significant feature of a state machine is that, for every given state, the next state can be uniquely and deterministically quantified as a function of the current state and inputs. Each state selects its next state, but only its next state -- not the next 3 states, or 5 states, or whatever. However useful they may be -- and I'll admit to being a heavy user of the paradigm -- a QSM is not a state machine.

1. Entry Actions -- These are actions that are performed exactly once every time this state is entered from another state.

2. Execution Actions -- These are actions that are performed continuously while the SM remains in the current state.

3. Exit Actions -- These are actions that are performed exactly once just prior to this state exiting.

4. Transition Actions -- The are actions that are performed exactly once when this state exits and are unique for every 'current state-next state' combination. When looking at a state diagram, these actions are associated with the arrows.

Very interesting and very general purpose approach, a hybrid between Moore and Mealy, but personally I think I'd find it unnecessarily complex and confusing to maintain.

Oh, and one more thing... FSM has another important meaning to me beyond computer science.

Edited June 9, 2011 by BobHamburger

[CharlesB]

If you're comfortable with objects I posted an object-based state machine here. I've refined it a bit since that post but the principles are sound.

Thanks, I had found it since. See some questions I asked on this thread.

[Daklu]

When I took Digital Design as an undergraduate...

Two states... fire, no fire.

Very interesting and very general purpose approach, a hybrid between Moore and Mealy, but personally I think I'd find it unnecessarily complex and confusing to maintain.

My understanding is that it's a variation of a Harel state machine. I posted a non-oop implementation illustrating the idea here. It's not really that complex once you understand it. In truth anytime a state machine grows beyond a handful of states there really should be a diagram describing the state machine for future developers, and if you have a diagram it's very easy to understand and maintain.

[drjdpowell]

I'm still fairly well convinced the QSM pattern shown here is not a very good design for anything other than NI's exams or prototype (read: throwaway) code, but I've written much on that already and won't repeat myself here.

That is a flawed design, due to the use of the same queue for both internal operations of the lower loop and incoming messages from the event structure in the upper loop, leading to indeterminacy in the order of operations. Good design always uses separate queues. I, personally, would recommend anyone starting to use "QSMs" (how about "Queued Operation Machines", QOM?) to use a good template such as the JKI statemachine toolkit to avoid these types of design mistakes (which I sadly recall making myself).

-- James

[Daklu]

That is a flawed design...

I agree, yet I run across many experienced developers who still use it without recognizing it has significant issues.

I, personally, would recommend anyone starting to use "QSMs" (how about "Queued Operation Machines", QOM?) to use a good template such as the JKI statemachine toolkit to avoid these types of design mistakes (which I sadly recall making myself).

No teachers are as effective as personal experience.

The JKI SM is a big improvement over the QSM illustrated above. It does not, however, solve all the issues with QSMs. IMO what it does is decrease the opportunity for common mistakes by imposing more constraints on the developer. That's not meant as a criticism and imposing constraints is not necessarily bad... it just means that the problem space in which the solution can be cleanly applied is reduced. (Of course, it's been a while since I've looked at the JKI SM and I've never used it extensively, so it could be that I've misunderstood how to best apply it.)

Personally, I would recommend people starting to use QSMs take some time to learn the difference between a state diagram and a flowchart and explore consequences of choosing one over the other.

[drjdpowell]

Personally, I would recommend people starting to use QSMs take some time to learn the difference between a state diagram and a flowchart and explore consequences of choosing one over the other.

The flowchart tends to seem more intuitive to me for what I'm doing, so the badly-named QSM is good for me. Admittedly, this may be just a lack, on my part, of a clear understanding of the value of state diagrams.

-- James