[prog.c++] Let's talk about hierarchical finite state machines and their support in SObjectizer-5.5

Finite state machine is a probably one of most basic and widespread thing in software development. Finite state machines (FSM) are actively used in many areas. For example in such niches as SCADA- and telecom systems FSM are used almost everywhere.

In this article we will try to speak about hierarchical FSM. And then we will try to take a look at FSM's support in SObjectizer-5. SObjectizer is one of a few OpenSource and live "actor" frameworks for C++ and actors in SObjectizer are FSMs. We will speak why SObjectizer's actors are FSMs and which capabilities they have.

A Brief Introduction Into Finite State Machines

It is hard to explain in a shot article such big topics as automata theory in general and finite state machines in particular. Because of that an basic understanding of these topics are required from a reader.

Advanced Finite State Machines And Their Features

There are several "advanced features" of FSM which significantly simplify usage of FSM. Let's talk about them briefly.

Disclaimer: if a reader has a good knowledge of UML's statechart diagrams then he or she doesn't find anything new here.

Hierarchical Finite State Machines

Maybe the most interesting and the most important feature is a possibility to organize a hierarchy of FSM's states. This possibility allows to avoid an exponential growth of number of state switches as FSM become more and more complex.

It is easier to explain that by using an example. Let's imagine that we have an interactive kiosk (infokiosk). A welcome screen must be shown first. An user can choose "Services" and go to the pages with description of various services. Or an user can choose "Profile" and go to the pages with personal information and preferences. Or an user can choose "Help" page.

This can be expressed by the very simple statechart diagram:

Now let's try to add a reaction to "Cancel" button. When an user press "Cancel" the return to the welcome screen must be done:

Our statechart becomes more complex. But we still control it.

Now we can go further and add subpages for "Services" page. There will be "Popular Services", "New Services" and "All Services" sections. From any on these pages we should return to the welcome screen on "Cancel" button. Our statechart become yet more complex:

So far, so good. But we do not handle "Back" button. When an user press it we should return to the previous screen. Let's add this:

Now we can imagine how a real fun would looks like. But we haven't started handling "Profile" and "Help" pages yet. If we try this our FSM, which was very simple at the very beginning, will become totally unmaintainable.

A hierarchy of FSM states can help here. We can create two top-level states: WelcomeScreen and UserSelection. Top-level sections (like "Services", "Profile", "Help") will become nested states for UserSelection state. And because of that they will inherit reactions for some signals/actions from their parent state. It allows us to define a reaction to "Cancel" button for UserSelection state. There is no need to redefine it for nested/children states. It makes our FSM more laconical and observable:

One can see that reactions for "Cancel" and "Back" are defined in UserSelection. The reaction for "Cancel" works for all UserSelection's substates (including a compound substate ServicesSelection). But ServicesSelection has its own reaction for "Back": switch to ServiceScreen is performed instead of switching to WelcomeScreen.

FSM that uses states hierarchy is called Hierarchical FSM (HFSM).

Enter/Exit Handler

It is very useful to have an ability to set enter/exit handlers. Enter handler will be called when FSM enters a specific state. Exit handler will be called when FSM leaves a state. For the example above it is possible to create an enter handler for every state. These enter handlers will change the content of infokiosk's screen when the state changed.

The example above can be slightly extended. Suppose we have two substates for WelcomeScreen: BrightWelcomeScreen and DarkWelcomeScreen. Infokiosk's screen has maximum brightness in BrigthWelcomeScreen, but brightness should be reduced in DarkWelcomeScreen. We can define enter handler for DarkWelcomeScreen which will decrease screen's brightness. We can also define exit handler for DarkWelcomeScreen to increase screen's brightness back.

Time Limit For A State

Sometimes it is necessary to automatically change FSM's state after some time. For the example above we can limit time spent in BrightWelcomeScreen to one minute. After one minute the FSM should switch to DarkWelcomeScreen.

State History

State History is another very interesting HFSM's feature.

Suppose we have some HFSM described by the following statechart diagram:

This HFSM can switch from TopLevelState1 to TopLevelState2 and back. But there are several nested states in TopLevelState1. If HFSM switches from TopLevelState2 to TopLevelState1 then two states are activated: TopLevelState1 and NestedState1. NestedState1 is activated because it is the initial substate for TopLevelState1.

Now suppose that this HFSM switches from NestedState1 to NestedState2. InternalState1 is activated inside NestedState2 because InternalState1 is the initial substate for NestedState2. Then we switch our HFSM to InternalState2. We have three active states: TopLevel1, NestedState2 and InternalState2.

We switch our HFSM to TopLevelState2. There is only one active state now. It is TopLevelState2.

Suppose we want to switch back to TopLevelState1. Exactly to TopLevelState1, not to some on its substates. Which states will be activated?

If TopLevelState1 has no history then we will have two active states: TopLevelState1 and NestedState1 (because NestedState1 is the initial substate for TopLevelState1). It means that all previous history of TopLevelState1 will be lost.

If TopLevelState1 has shallow history then we will have three active states: TopLevelState1, NestedState2 and InternalState1. NestedState2 will be activated because it will be stored in TopLevelState1's history. InternalState1 will be activated because it is the initial substate. It means that shallow history contains history only for direct substates of TopLevelState1, but not goes deeper.

If TopLevelState1 has deep history then we will also have three active states, but there will be significant difference: TopLevelState1, NestedState2 and InternalState2. It is because full deep history will be stored inside TopLevelState1 and this history will be restored on return to TopLevelState1.

Orthogonal States

Until this moment we speak about HFSM which can have only one active substate at the same logical level. For example, HFSM from the previous section can have only one active NestedState* substate inside TopLevelState1.

But there could be cases where several substates should be active at the same time. Those substates are called orthogonal (or concurrent) states.

The classical example for orthogonal states is well known computer's keyboard with NumLock, CapsLock and ScrollLock modes. We can say that NumLock/CapsLock/ScrollLock can be described as orthogonal substates inside Active state:

All that you want to know about HSM, but...

There is a fundamental article about formal statechart notation from David Harel: Statecharts: A Visual Formalism For Complex Systems (1987).

Several cases which can occur during work with FSM are described in this paper. With very simple and understandable examples based on usual electronic handwatch use-cases. If you don't read this paper yet I would recommend to read it.

Finite State Machines In SObjectizer-5

For the rest of the article we will speak about SObjectizer and SObjectizer-related things. If you don't understand the code examples it can be necessary to read the official documentation or slides with introduction to SObjectizer.

Agents In SObjectizer Are Finite State Machines

Agents in SObjectizer are FSMs. And always were FSMs. Even if agent's author doesn't define his/her own states for the agent there is the default state which is used automatically. For example if a developer wrote a simple agent like such:

class simple_demo final : public so_5::agent_t { public:   // Signal to print agent's status.   struct how_are_you final : public so_5::signal_t {};   // Signal to finish agent's work.   struct quit final : public so_5::signal_t {};   simple_demo(context_t ctx) : so_5::agent_t{std::move(ctx)} {     // Agent is trivial. Make all subscriptions in the constructor.     so_subscribe_self()       .event<how_are_you>([]{ std::cout << "I'm fine!" << std::endl; })       .event<quit>([this]{ so_deregister_agent_coop_normally(); });   } };

the developer can forget that all subscriptions are made for the default state. But if some user's states are added then the developer should think which subscriptions for every state should be created. For example this is a simple (and wrong) modification for agent shown above):

class simple_demo final : public so_5::agent_t {   // State to be used when agent is free.   state_t st_free{this};   // State to be used when agent is busy.   state_t st_busy{this}; public:   struct how_are_you final : public so_5::signal_t {};   struct quit final : public so_5::signal_t {};   simple_demo(context_t ctx) : so_5::agent_t{std::move(ctx)} {     so_subscribe_self()       .event<quit>([this]{ so_deregister_agent_coop_normally(); });     // React to how_are_you differently in every state.     st_free.event([]{ std::cout << "I'm free" << std::endl; });     st_busy.event([]{ std::cout << "I'm busy" << std::endl; });     // Work should be started in st_free state.     this >>= st_free;    } };

We define two different event handlers for how_are_you signal. Every handler will be used in different state.

This modification is wrong because in st_free and st_busy states the quit signal won't be handled at all. It is because we kept the subscription for quit signal in the default state. The simplest way to fix this error is to create the corresponding subscriptions for st_free and st_busy:

simple_demo(context_t ctx) : so_5::agent_t{std::move(ctx)} {     st_free       .event([]{ std::cout << "I'm free" << std::endl; })       .event<quit>([this]{ so_deregister_agent_coop_normally(); });     st_busy       .event([]{ std::cout << "I'm busy" << std::endl; })       .event<quit>([this]{ so_deregister_agent_coop_normally(); });     this >>= st_free;    }

But there is a smell of copy-and-paste and this is not good. We can avoid copy-and-paste by introduction of the parent state for st_free and st_busy:

class simple_demo final : public so_5::agent_t {   // The parent for all substates.   state_t st_basic{this};   // State to be used when agent is free.   // It is the initial substate for st_basic.   state_t st_free{initial_substate_of{st_basic}};   // State to be used when agent is free.   state_t st_busy{substate_of{st_basic}}; public:   struct how_are_you final : public so_5::signal_t {};   struct quit final : public so_5::signal_t {};   simple_demo(context_t ctx) : so_5::agent_t{std::move(ctx)} {     // Event handler for quit signal is defined for st_basic.     // Because of that is will be inherited by all substates.     st_basic.event<quit>([this]{ so_deregister_agent_coop_normally(); });     st_free.event([]{ std::cout << "I'm free" << std::endl; });     st_busy.event([]{ std::cout << "I'm busy" << std::endl; });     this >>= st_free;    } };

From the historic point of view the support for hierarchical FSM was added not so much time ago -- in Jan 2016.

Why SObjectizer's Agents Are FSMs?

This question has very simple answer: by accident because SObjectizer has roots in SCADA area, where FSMs are used widely. We decided to make SObjectizer's agents FSMs. This is very useful if FSMs are necessary in a particular task. And there is a special default state in every agent which are automatically used if there is no need in FSMs.

But if we take a look at the basic principles of Actor Model then we can found many similarities between Actors and FSMs:

• actor is an entity with behaviour;
• actors react to incoming messages;
• when an incoming message arrives an actor can:
  • send some (limited) number of messages to other actors;
  • create some (limited) number of new actors;
  • define a new behaviour for itself for processing of new messages.

It is even possible to say than Actors are just simple FSMs.

Which Advanced Features Of HFSM Are Supported By SObjectizer-5.5?

SObjectizer-5.5 supports almost all advanced features mentioned above except orthogonal states. Other useful things, like nested states, enter/exit handlers, time limits, shallow and deep history are available for a developer just out of box.

The first attempt of addition of orthogonal states to SObjectizer-5.5 failed by several reasons. From one side the internals of SObjectizer-5.5 make this task very difficult, maybe a very big redesign of SObjectizer-5.5 subscription mechanics is required. From another side there are some very difficult question about agent's behaviour in presence of several orthogonal states.

A bunch of problems with implementation of orthogonal states' support was too big and complex to cope with it. Moreover we don't have a real-life cases where the only way to solve a problem was usage of orthogonal states. Usually several separate agents bound to the same work context can be used instead.

But if someone needs orthogonal states in SObjectizer-5 and have interesting use-cases to deal with then let's talk. Maybe with your help we could add this feature in the future.

How HFSM Looks Like In SObjectizer-5.5?

We will try to give a brief overview of SObjectizer's HFSM support. More detailed information about this topic can be found in the official docs.

Nested States

To declare a nested state it is necessary to pass a result of initial_substate_of or substate_of expression to state_t's constructor:

class demo : public so_5::agent_t {   state_t st_parent{this}; // The parent state.   state_t st_first_child{initial_substate_of{st_parent}}; // The first child substate. The initial one.   state_t st_second_child{substate_of{st_parent}}; // The second child substate.   state_t st_third_child{substate_of{st_parent}}; // The third child substate.   state_t st_first_grandchild{initial_substate_of{st_third_child}}; // Yet another nested level.   state_t st_second_grandchild{substate_of{st_third_child}};   ... };

If a state S has several substates C1, C2, ..., Cn, then one and only one of them must be marked as the initial substate. The check for this rule is performed at run-time.

SObjectizer-5.5 has a hard limit for deep level of nested states: only 16 levels are allowed. The corresponding check is performed at run-time.

The main trick with nested states is the presence of several active states at the same time. For example, there is state A with substates B and C, and B has its own substates D and E:

If state A is activated then three states are activated actually: A, A.B and A.B.D.

The presence of several active states has impact on two very important things.

The first one is the search of event handler for an incoming message. In the example above the search for an event handler will be started in state A.B.D. Then, if A.B.D hasn't the event handler, the search will be continued in the parent state: A.B. Then, if A.B also hasn't the event handler, the search will be continued in the top-level state: A.

The second thing is the calling order for enter/exit handlers. But we will speak about it bellow.

Enter/Exit Handler

Enter and/or exit handler can be specified for an agent's state by using state_t::on_enter() and state_t::on_exit() methods. Usually these methods are called inside so_define_agent() method (or inside of agent's constructor if agent is trivial and inheritance is not supposed to be used):

class demo : public so_5::agent_t {   state_t st_free{this};   state_t st_busy{this}; ...   void so_define_agent() override {     // ATTENTION: enter/exit handlers must be specified before switching agent's state.     st_free.on_enter([]{ ... });     st_busy.on_exit([]{ ...});     ...     this >>= st_free;   } ... };

Probably the most tricky moment is the usage of on_enter/on_exit handlers for nested substates. Let's speak about the example above yet another time. We have states A, B, C, D and E:

Suppose every state has on_enter and on_exit handlers.

Suppose state A is activated. It means that we will have three active states: A, A.B and A.B.D. During state activation procedure the following handlers will be called: A.on_enter, A.B.on_enter and A.B.D.on_enter. In the exact that order.

Suppose we make transition into A.B.E. Handlers A.B.D.on_exit and A.B.E.on_enter will be called.

If we then switch the agent to state A.C then A.B.E.on_exit, A.B.on_exit and A.C.on_enter will be called.

If the agent will be deregistered while it is in A.C state then A.C.on_exit and A.on_exit will be called just after the return from so_evt_finish().

Time Limits

Time limit for a state can be specified by using state_t::time_limit() method. As for on_enter/on_exit the time_limit method usually called in so_define_state() or in the agent's constructor:

class led_indicator : public so_5::agent_t {   state_t inactive{this};   state_t active{this}; ...   void so_define_agent() override {     // Allow to stay in active state for 15s only.     // After that time the agent should be switched into inactive state.     active.time_limit(15s, inactive);     ...   } ... };

If the time limit is specified for a state then SObjectizer will start count the time when the state is activated. If agent leaves the state and then returns to it back then SObjectizer will restart time counter.

It is necessary to be careful with time limits of nested states:

class demo : public so_5::agent_t {   // The top-level states.   state_t A{this}, B{this};   // Substates for A.   state_t C{initial_substate_of{A}}, st_D{substate_of{A}}; ...   void so_define_agent() override {     A.time_limit(15s, B);     C.time_limit(10s, D);     D.time_limit(20s, C);     ...   } ... };

Suppose state A is activated. It means that states A and C are activated actually. SObjectizer will start time counters for A and for C. After 10s the agent will be switched to D state and SObjectizer start time counter for D. But time counter for state A won't be stopped because A is still active. And the agent will be switched to B after 5s.

State History

Agents don't have history for states by default. To turn state history on it is necessary to pass constants shallow_history or deep_history to the state_t's constructor. For example:

class demo : public so_5::agent_t {   state_t A{this, shallow_history};   state_t B{this, deep_history};   ... };

State history is a very tricky topic especially in presence of nested states with own histories. Because of than it is better to look at the official documentation and do some experiments. And ask us if you have some questions ;)

just_switch_to, transfer_to_state, suppress

The most frequently used methods of state_t have already been described above. But there are some more methods which are also useful and can simplify dealing with complex HFSM.

Method just_switch_to() is useful when the only reaction to an incoming message is the switch to another state. You can write:

some_state.just_switch_to<some_msg>(another_state);

instead of:

some_state.event([this](mhood_t<some_msg>) {   this >>= another_state; });

Method transfer_to_state() is very useful when we have to handle a message M in several states S2, ..., Sn such way: it is necessary to switch to S1 first and only then handle M. Let's see that in the following example:

class demo : public so_5::agent_t {   state_t S1{this}, S2{this}, ..., Sn{this};   ...   void actual_M_handler(mhood_t<M> cmd) {...}   ...   void so_define_agent() override {     S1.event(&demo::actual_M_handler);     ...     // For all other states we have to switch agent to S1 and then handle M.     S2.event([this](mhood_t<M> cmd) {       this >>= S1;       actual_M_handler(cmd);     });     ... // The same way for all other states.     Sn.event([this](mhood_t<M> cmd) {       this >>= S1;       actual_M_handler(cmd);     });   } ... };

Instead of copy-and-paste the same code for similar event handlers in S2, ..., Sn it is better to use transfer_to_state():

class demo : public so_5::agent_t {   state_t S1{this}, S2{this}, ..., Sn{this};   ...   void actual_M_handler(mhood_t<M> cmd) {...}   ...   void so_define_agent() override {     S1.event(&demo::actual_M_handler);     ...     // For all other states we have to switch agent to S1 and then handle M.     S2.transfer_to_state<M>(S1);     ... // The same way for all other states.     Sn.transfer_to_state<M>(Sn);   } ... };

Method suppress() disables the search for an event handler for the state. For example, suppose we have the parent state A where std::abort() is called in event handler of message M. And we have a child state B where message M can be safely ignored. We should define the event handler for M in B, otherwise the handler from A state will be called. Because of that we have to write something like:

void so_define_agent() override {   A.event([](mhood_t<M>) { std::abort(); });   ...   B.event([](mhood_t<M>) {}); // Don't do anything.       // But presence of that handler disables search for a handler in parent states.   ... }

Method suppress() allows to declare this case more clearly:

void so_define_agent() override {   A.event([](mhood_t<M>) { std::abort(); });   ...   B.suppress<M>(); // Don't do anything.       // But presence of suppress() disables search for a handler in parent states.   ... }

A Very Simple Example

SObjectizer-5.5 contains a very simple example that simulates blinking led indicator. The statechart for the agent from that example is:

And there is the code of the agent:

class blinking_led final : public so_5::agent_t {    state_t off{ this }, blinking{ this },       blink_on{ initial_substate_of{ blinking } },       blink_off{ substate_of{ blinking } }; public :    struct turn_on_off : public so_5::signal_t {};    blinking_led( context_t ctx ) : so_5::agent_t{ ctx }    {       this >>= off;       off.just_switch_to< turn_on_off >( blinking );       blinking.just_switch_to< turn_on_off >( off );       blink_on          .on_enter( []{ std::cout << "ON" << std::endl; } )          .on_exit( []{ std::cout << "off" << std::endl; } )          .time_limit( std::chrono::milliseconds{1250}, blink_off );       blink_off          .time_limit( std::chrono::milliseconds{750}, blink_on );    } };

Almost all work is done in enter/exit handlers for blink_on state. But there are also time limits for blink_on and blink_off which are important too.

A Much More Complex Example

There is also much more complex example in SObjectizer-5.5: intercom_statechart. It simulates behaviour of intercom's control panel. The statechart for the main agent from the example looks like:

This example is complex because it supports special secret codes for every apartment and separate service code. These codes allow to open the door without calling an apartment.

This example uses many interesting things. But it is very large to be discussed inside that article. If you want to imagine how really complex HFSM can be expressed in SObjectizer then you can take a look at that example. Any questions can be asked in comments for that article.

Is It Possible To Use Another Implementation Of FSM With SObjectizer?

SObjectizer-5.5 has internal support of HFSM with rich features set. We think it is obvious that this support was implemented to be used. Also some SObjectizer's mechanisms, like message delivery tracing-а, know about agent's states and can handle them appropriately.

But if an user don't want to use SObjectizer's state_t... It is also possible. And it can be meaningful in some cases.

For example, state_t is rather heavy object. It contains std::string, a couple of std::function, some counters and several pointers. On 64-bit Linux with GCC-5.5 sizeof(state_t) is 160 bytes. And this is without dynamic memory which can be allocated inside std::string and/or std::function...

If you have to create millions of agents and every agent has dozens of states then SObjectizer's state_t can eat too much memory.

In such case you can use another implementation of FSM and pass messages to your FSM manually. Something like:

class external_fsm_demo : public so_5::agent_t {   some_fsm_type my_fsm_;   ...   void so_define_agent() override {     so_subscribe_self()        .event([this](mhood_t<msg_one> cmd) { my_fsm_.handle(*cmd); })        .event([this](mhood_t<msg_two> cmd) { my_fsm_.handle(*cmd); })        .event([this](mhood_t<msg_three> cmd) { my_fsm_.handle(*cmd); });     ...   }   ... };

In that case you pay for efficiency by a large amount of handwork and lack of some features from SObjectizer. But it is your choice.

Conclusion

Thanks for all readers spending time on this article. It would be great to receive some feedback in comments.

I will be glad to answer questions, so do not hesitate to ask about what remains unclear.