Hello and welcome to the Modern Embedded Systems Programming course. My name is Miro Samek and today I'd like to start a new segment of lessons about STATE MACHINES. This subject is closely related to event-driven programming and active objects introduced in the last lesson.

As it is actually a continuation, let's get started by copying the previous code for lesson-34 to lesson-35.

Get inside the new lesson-35 directory and double-click on the project "lesson" to open it in the ARM/KEIL micro-Vision IDE.

To remind you quickly what happened so far, in the last lesson, you've learned about the best practices of concurrent programming, and the Active Object design pattern that naturally implements and automatically enforces these best practices.

You also started to build your own, event-driven, Active Object framework, called Micro-C-A-O, because it was based on the traditional Micro-C-OS-2 RTOS, which you then applied to build a small Blinky-Button application.

But already that small example showed some looming problems with the event-driven approach. Specifically, the part of the code that blinks the Green-LED required you to invent a boolean flag that was called isLedOn, and which you needed to remember the state of the Green-LED between the TIMEOUT events.

Please note that this boolean flag was NOT needed in the original RTOS thread, because in a sequential code the waiting between events happened by means of BLOCKING inside the OSTimeDly() function. After receiving the expected event the code unblocked and simply handled the event, because you knew exactly which event was received. Therefore, you didn't need to do anything special to remember where in the sequence of events you were.

This is an example of maintaining the context between events naturally and automatically. As it turns out, this automatic context management is quite expensive, because, as you recall from the previous lessons about the RTOS, the context of a thread during a blocking call requires a whole private stack in the precious RAM. But the automatic context management surely is convenient, if you can live with hard-coded event sequences. 

All this is in stark contrast to event-driven code, which cannot block, and instead has to *return* to the event loop after every event. Such code obviously loses the stack context between events. Consequently, event-driven systems tend to use less stack space, but instead require a different form of preserving the context from one event to the next.

The most popular is the manual context management, where programmers invent flags and variables, such as your isLedOn flag in your Blinky active object.

This approach seems to work initially, and the isLedOn flag certainly didn't loom as a big problem in a simplistic Blinky-Button event-driven active object.

But in most real-life programs, such approach is almost guaranteed to degenerate into unwieldy "spaghetti" code, which I'd like to quickly demonstrate with the event-driven Visual Basic calculator example.

I understand that this is not an embedded system and is not even written in C, but it illustrates well the main problems, without the need to explain how a calculator like that is supposed to work.

So the Visual Basic 4-operation calculator obviously adds, subtracts, multiplies, and divides.

But if you try some less usual sequences of key-presses, you would discover quite a few "corner cases" leading to crashes or misleading behavior.

One such "corner case" is the following sequence of operations:

3, +, -, = 4, =.

The calculator crashes with "Run-time error 13". 

One might argue that this is a meaningless sequence of events, but at the same time it is also obvious that no user actions should crash the software like that.

So, the calculator apparently has trouble correctly responding to events in different contexts.

But if you look at the underlying code, you will find out that managing the context is really the central concern here and most of the code is devoted to it.

Even though you might not be familiar with Visual Basic, I hope you can recognize a bunch of variable declarations with the sole purpose to remember the current context.

For example, the DecimalFlag remembers whether the decimal point has been entered to avoid displaying multiple decimal points in a number. Similarly, the NumOps variable remembers the number of operands entered so far, to distinguish between the first and second operand in an expression. And so on.

Then, there are a bunch of event-handler subroutines each designed to handle a group of related keypress events. For example, the minus-key that confused the calculator before, is handled in the subroutine Operator_Click(), which handles the plus, minus, multiply and divide keys and happens to be the most complex one.

Here you can see that the various flags and variables are checked in nontrivial conditions, then modified and re-checked again, so that it is really hard to know for sure which path through the code will be taken in a given situation.

Apparently, a 4-operation calculator is already complex enough to reach the limit of such manual context management, because attempts to fix one bug tend to create another.

The real problem here is that the variables and flags provide too much of redundant and poorly organized information, which then can easily become internally inconsistent.

But the improvised context management reflects the correct intuition of the software developers that you don't need to remember the *whole* history of past events, only certain *aspects* of it.

Specifically, to handle events correctly you just need to remember the *relevant history*, which is only what influences the *future* behavior of the system, and events don't contribute equally to that relevant history.

For example, an electronic controller for a computer keyboard generates either lower-case or upper-case key codes. This behavior depends on whether the Shift key has been pressed or released, but it doesn't matter which other keys have been pressed or released, or how many of them were pressed.

Therefore, the whole relevant history of the keyboard can be reduced just to two classes: the "normal" class, where the keys generate lower-case codes, and the "shifted" class, where the same keys generate upper-case codes.

Which leads to the most important concept of "State".

"State" of a system is an *equivalence class* of past histories of a system, all of which are equivalent in the sense that the future behavior of the system given any of these past histories will be identical.

Thus the concept of "State" is the most efficient representation of the relevant history. It is the minimum information that captures only the relevant aspects for the future behavior and abstracts away all irrelevant aspects.

The concept of "State" naturally leads to the concept of "State Machine", which is the set of all states, that is equivalence classes of relevant histories, plus the rules for changing from one state to another. These rules are called *transitions* and capture the fact that some events contribute to the relevant history while others do not. Those events influencing the future behavior trigger the state transitions.

A very nice aspect of the "State Machine" concept is its compelling graphical representation in form of state diagrams. In the modern- Unified Modeling Language (UML) notation, states are represented as rounded-corner rectangles with the name of the state in the name compartment and regular state transitions are represented as arrows labeled by the triggering events.

In the UML you can also have so called "internal transitions", which do not cause change of state but only execute *actions* in response to a given event. These are represented just as triggering events inside states.

The *actions* are listed after the slash character and are allowed on both kinds of transitions, internal and regular.

Additionally, every state machine needs to have an initial transition that points to the default state, which is active when the state machine is created and before any events are dispatched to it.

A state machine can have many more features, and there are many kinds of state machines used in software, including the modern hierarchical state machines also known as UML statecharts. I'm going to cover some of the most important variants of state machines in the future lessons.

But for today, I just want you to remember one universal feature in all state machine formalisms, and that is the Run-to-Completion event processing. RTC means that a state machine can process only one event at a time, so the processing of one event must necessarily end before the processing of the next event can begin.

Well, surprise, surprise, the RTC semantics universally assumed in all state machine formalisms matches exactly the RTC semantics assumed in all event-driven systems, such as Active Objects you've learned in the last lesson. So, in other words, state machines are an ideal mechanism to specify the behavior of Active Objects.

As an example, let's build the state machine representing the behavior of your BlinkyButton active object, but without the isLedOn flag.

For this, I will use the freeware QM graphical modeling tool from my company, Quantum Leaps. This is not to say that you necessarily need such tools to apply state machines. A piece of paper or a whiteboard for drawing state diagrams is completely adequate, especially in the beginning.

But for a screencast like this, an electronic drawing tool is more convenient. Also, while you certainly know how paper and pencil work, it might be more interesting for you to see how to use a graphical modeling tool.

When you launch QM for the first time, it opens the New Model dialog box, whereas you can choose from a few models as your starting points. One of them: Blinky, seems close enough to what you are doing, so let's select that one.

Next you can re-name your new model to BlinkyButton and you can choose the location of your model as the directory of today's lesson.

OK, so the model already comes with a Blinky state machine, but I'll delete it so that you can see how a state machine like that is built from scratch.

So the design process typically goes as follows:

A good place to start is the default state and the initial transition, because this establishes the initial condition of the system.

At this point you might not even know how to name this default state, but don't worry, because it will become clearer as you flesh out the initial transition.

In case of your BlinkyButton the initial transition will perform the following actions: turn the Green-LED off and arm a time event to expire in the off-time.

By the way, the QM tool provides two fields for specifying the action. The smaller filed is for the pseudocode, which is just a very concise comment as to what the action is all about. The bigger filed below, can contain the actual code in C, which, if provided, will be used for automatic code generation. Only the pseudocode is shown in the diagram, which reduces the clutter.

But going back to the state machine, the actions on the initial transition mean that the default state represents the "off" state of the BlinkyButton, so let's name it "off".

Now, when the TIMEOUT event arrives in this "off" state, you need to turn the Green-LED ON and you need to arm the time event for the on-timeout.

But this means that you can no longer stay in the "off" state, so you need a different state, which logically should be called "on".

So, let's add the "on" state and point the transition to go there.

Now, when the TIMEOUT event arrives in the "on" state, you transition to the "off" state. In the actions on this transition you turn the Green-LED OFF and you arm the time event for the off-time.

At this point the blinking feature is complete, but this is the Blinky-*Button* state machine, so it must also handle the BUTTON_PRESSED and BUTTON_RELEASED events.

These events will be handled in the so called internal transitions, which just execute actions but don't trigger a change of state.

The internal transition for the BUTTON_PRESSED event turns the Blue-LED on and shortens the blink time for the Green-LED by 2.

The internal transition for the BUTTON_RELEASED event just turns the Blue-LED off.

But these two events need to be handled also when the Green-LED is on, which means that you need to repeat the same internal transitions in the "on" state as well.

Of course, such repetition is perhaps not a big deal in a toy example like your BlinkyButton here, but in real-life projects repetitions like that can, and will, pile up. This is exactly the problem that the modern hierarchical state machines are designed to address. But I have to leave the discussion of hierarchical state machines to another lesson.

Because today, I'd still like to show you how you can implement the just designed BlinkyButton state machine in C.

The implementation technique I'm going to show you is not necessarily the most efficient or elegant. I will discuss other implementations in the future lessons in the state machine segment. But today, I'll show you the most straightforward way.

As you remember from the state machine definition, the main job of a state machine is to remember its current state. For that, you obviously need a variable, which in state machine implementations is commonly called the "state variable".

The most straightforward way to represent the state variable is to simply make it an enumeration of all possible states. In the BlinkyButton state machine you have states "off" and "on", so the enumeration will define OFF_STATE and ON_STATE constants.

The state variable replaces all flags and variables that were part of the improvised, manual context management. In the simplistic BlinkyButton example, this means that you can get rid of the isLedOn flag, which  might not look like much of an improvement.

But please remember that in more advanced state machines, like for example the calculator, you have still only one state variable, which then replaces many more variables like those ones you saw in the Visual Basic example.

But moving on, now you need to decide where to put the state machine code. As it turns out, the ideal place for this is the active object dispatch function. 

This is because the surrounding active object framework calls dispatch only when there is an event to process. Otherwise, the active object is completely dormant and does noting.

This happens to be exactly how a state machine operates. When there are no events, a state machine just waits in its current state and does absolutely nothing. This dormant condition is depicted in blue color in the QM modeling tool.

Only when an event arrives, the state machine is activated to process the event in one of the transitions. This active condition is depicted in red color in the QM modeling tool. 

With this understanding, let's now re-code the BlinkyButton-dispatch function as a state machine.

At this point, let's still keep the original code for reference, but remember to delete it eventually.

Starting with the initial transition, the way it is organized in your Micro-C-A-O framework, the initial transition needs to be executed when the dispatch function receives special INIT event signal.

To implement this, you check if the event signal is INIT_SIG and if so,

you execute the actions on your initial transition, such as Blue-LED off and arm the Time-Event to fire in the off-time.

After the actions, you set your private "state variable", conveniently accessible through the "me" pointer, to the target of the initial transition. At this point, you can explicitly return, because you're done.

Now comes the most interesting part of coding the states. In this most straightforward method, you use the switch statement that discriminates based on your state variable.

You can then immediately provide all the cases for all the states in your state machine.

After all the possible states, I recommend to add the default case, where you can put an assertion, because reaching the default case means that your state variable has become and invalid state. 

Now you can flesh out the state cases. For this, you use the second level switch statement, but this time discriminating based on the event signal. 

For the "off" state, you find that the first signal it handles is TIMEOUT, so you provide a case for it. Inside this case, you execute the actions listed in the diagram.

But you also notice that this a regular state transition that goes to the state... "on". You code it by explicitly changing your state variable to ON_STATE.

The next event handled in your "off" state is BUTTON_PRESSED, so you provide a case for it.

The actions associated with this internal transition are the same as you already coded in your old version, so you simply copy it from there.

Note that an internal transition causes no change of state, so you don't modify your state variable.

The last BUTTON_RELEASED internal transition in your "off" state is coded in similar way as BUTTON_PRESSED. Again, you don't modify your state variable.


Next, you move on to the "on" state, where you have the TIMEOUT event.

After the actions, you code the regular transition, which goes to... the "off" state.


The two remaining internal transitions in the "on" state are handled identically as you've already coded in the "off" state, so you simply copy over that code.

At this point you've implemented the whole state machine, so you can delete the old code.

But now, I'd like you to take a step back and recount what just happened.

Well, the state machine is not necessarily smaller than your old code, but this is mostly due to the repetitions in handling the Button events that I promise to address in the future.

More importantly, however, I hope you've noticed that the whole state machine coding experience was very different than any other code you've written before. 

Specifically, once you've worked out a few simple rules of mapping state machine elements, like states and transitions, to code, you could apply them mechanically. The actual coding did not require much thinking, because all the thinking has been already done when the state machine was designed.

In fact, I hope you can now imagine how a modeling tool, like QM, could *automatically generate* such code by applying the same simple rules as you did. 

By the way, QM can actually do this, it can automatically generate code from your state diagrams, although it uses a different implementation strategy than you've just seen. I'll explain other state machine implementation strategies in the future lessons.

But going back to your today's coding experience, I hope you can now quite easily see how every part of the code corresponds to the parts of the state diagram. This property is called "traceability" between code and design, and is a required property in safety-critical software.

And the last point I'd like to bring up is that you now know how to extend your code. Should you add new states or new events to your state machine or change things around, you know exactly which parts of code your need to change. This property is called "extensibility" and this is another great benefit of using state machines.

Alright, but to wrap up for today I still need to check whether the state machine code actually works, so let me do it right now.

The compiler reminds me to cleanup the isLedOn flag from the constructor, but otherwise the state machine code builds with zero errors and zero warnings.

So, let me load the code to the Tiva LaunchPad board and run it.

Well, as you can see, the BlinkyButton example works just as it did before.

This concludes this first lesson in the State Machine segment. In the next lesson, you'll learn about other variants of state machines as well as the common misconceptions and misunderstandings about state machines.


If you like this channel, please give this video a like and subscribe to stay tuned. You can also visit state-machine.com/quickstart for the class notes and project file downloads.