Hello and welcome to the Modern Embedded Systems Programming course. My name is Miro Samek and in this sixth lesson on state machines I would like to give you the first glimpse of modern hierarchical state machines. Today, you will learn what hierarchical state machines are and how they differ from the traditional finite state machines. You will also get an idea how to implement state hierarchy in C and you'll see which aspects are easy and which are harder to implement. Finally, you 'll port your TimeBomb application from the toy Micro-C-AO framework to the professional QP/C framework, where hierarchical state machines are fully supported. As usual, let's start with copying the previous lesson-39 directory and renaming it to lesson-40. Get inside the new lesson-40 directory and double-clink on the project "lesson" to open it in the uVision IDE. To remind you quickly what happened so far, in the previous lesson you've learned the "optimal" state machine implementation, which you evolved from an idealized "domain-specific language" for state machines. That's why the implementation was very readable with a clear, one-to-one correspondence between the state machine elements in the diagram and the corresponding code. The implementation had also small memory footprint and was reasonably efficient in the CPU use. But, the optimal implementation has one more huge advantage, and that is, that it is very easy to extend it to support the modern version of state machines, which will be the subject of this lesson. But, I'm getting ahead of myself, because you first need to see the biggest problem with the traditional state machines. To illustrate what I mean, suppose that you need to extend your TimeBomb application to allow the user to defuse the bomb. Specifically, the second button on your TivaC LauchPad board should now defuse the bomb and should turn the Blue-LED on to show that the bomb is defused. The most important aspect is that the defusing should work at any stage, including when the bomb already started to time out. In the state diagram, this means that you now need an additional state: "defused" with an entry action that turns the Blue-LED on. And then you need transitions triggered by the BUTTON2_PRESSED event that lead to this new state. The ability to ALWAYS defuse the bomb means that the BUTTON2_PRESSED transition has to be repeated in ALL existing states, because otherwise the bomb would NOT defuse reliably. Now in your code, to replicate these changes from the diagram, you need to add the new "defused" state. In the code, you typically work by copying, pasting, and modifying the existing elements to reuse the established coding patterns, rather than writing them from scratch. So for example, you can copy the "boom" state-handler function and modify it for the "defused" state. Similarly, you can copy the BUTTON_PRESSED transition and modify it for BUTTON2_PRESSED. Then, to replicate the transition, you copy it and paste in all the states. At this point, the TimeBomb state machine itself is done, but you still need to add the new BUTTON2_PRESSED and RELEASED event signals. And you need to modify the Board Support Package to configure the GPIO for the SW2 button as input. A tricky aspect here is that SW2 is multiplexed with the NMI line on the TivaC MCU, so before you can use it as an input, you need to unlock the access to this pin. Only now you can configure the SW2 pin as input, just like SW1. Once the pin in correctly configured, you need to generate and post the BUTTON2_PRESSED events to the TimeBomb active object, which you copy and modify from the SW1 button. Here, you take advantage of the switch debouncing algorithm, which was discussed in lesson-37, and which allows you to debounce up to 32 signals simultaneously. Before you build the code, though, please make sure that the compiler optimization is NOT set to -OZ image size. For some reason, which looks really like a compiler error, the code will not work when the -OZ optimization is selected. The last step is of course to check how it works... Let's open the debugger and run the code free. When you press the SW2 button, the Blue-LED lights up, which means that you are in the "defused" state. Alright. Second test: Reset the board and run the code free. Now, press SW1 button. The TimeBomb starts to blink red. But when you press the SW2 button, again the Blue-LED lights up and the bomb stops timing out. So, all is fine and the new defusing feature seems to be working fine. But, suppose that you want to debug the new BUTTON2_PRESSED transition. The problem is that you now have four of those, so where do you put your breakpoint? Even if you have enough breakpoints, you run the risk of missing some of the transitions. For instance, suppose that you missed one right here. When you run the previous test again, you typically hit one of your breakpoints. But, sometimes you take the transition without hitting a breakpoint, so your debugging is unreliable. Another facet of the same problem is with maintaining such code. For instance, if you need to modify in some way the repeated transitions, you need to do this identically in all instances. It's just too easy to miss some of the instances, or make slightly different changes in some places, and thus introduce inconsistencies. Well, all these problems are well known, because all of them stem from violating one of the most important principles of software development: the DRY principle, which stands for Don't Repeat Yourself. Please note that the repetition in the code is ultimately the problem of the original state machine design, of which the code is merely a faithful reflection. As it turns out, this problem with repetitions in traditional state machines is fundamental and is known as the "state-transition explosion". What that means is that complexity of the state machine solution to a given problem tends to grow disproportionately faster than the complexity of the problem. For example, an additional state and an additional transition in the TimeBomb state diagram would be an increase of complexity that is proportional to the increased complexity of the problem. But the 4 repeated transitions add the extra complexity. Of course, as the problem grows more complex, the repetitions pile up even faster and "explode", making the traditional state machines unworkable for bigger problems. This is probably one of the main obstacle to a widespread adoption of state machines in embedded software. Fortunately, a very elegant solution to this problem has been known since the late 1980's, when David Harel invented advanced state machines that he called "statecharts". The main innovation of "statecharts" is the introduction of hierarchically nested states and therefore "statecharts" are also called "hierarchical state machines". So, first let me show you how hierarchical state nesting looks and then I'll explain how it works and how it helps to eliminate the troublesome repetitions. So, the extension of the state machine formalism is to allow states to contain other states. Specifically, in your TimeBomb state machine, you can surround the four of the original states with another state, which you can call "armed". This introduces a state hierarchy, in which state "armed" is at a higher-level and therefore is called the superstate. The internal states are then at a lower-level and are called substates. The meaning of the state hierarchy is that the behavior of the superstate applies to all its substates. With this in mind, you can now move the BUTTON2_PRESSED transition up one level to the "armed" superstate, so that it applies to all four substates of "armed". The semantics associated with state nesting now means that, while the state machine is in the substate "wait4button" and the BUTTON2_PRESSED event occurs, the event is NOT ignored, as it would be the case in the traditional, non-hierarchical state machine. Instead, the event is propagated to the higher-level state "armed", where it triggers the transition to "defused". On the other hand, if a substate already handles a given event, it will NOT be propagated to the supersate. This is how substates can override the behavior from the supersates. However, in case of your TimeBomb, the transition in the "armed" superstate is exactly what you want, so you can delete the repeated transitions in all substates and rely on the common transition already defined in the superstate "armed". The end result is that you could replace the 4 repeated transitions with just one, so this is how state hierarchy allows you to get rid of the repetitions and instead capture the common behavior in the higher-level states. But at this point, I hope that you might remember already seeing something like that in this video course. Well, actually, similar combination of abstraction and hierarchy came up already a few times before. The more recent one was in Lesson-33 about event-driven programming on Windows with the original Win32 API. In that lesson, you've seen how all Windows events are first passed to the Window-Procedure (Win-Proc), but the events not handled explicitly there are not discarded, but rather passed on to the Windows System, where they are handled according to the "characteristic look and feel" of the Windows GUI. This mechanism is known under the names: "Ultimate Hook" or "Programming by Difference". Another occasion when you've applied "Programming by Difference" was in lesson 30 about "inheritance". You learned there that "inheritance" is a mechanism of capturing commonalities in a higher level superclass in order to reuse them in the lower-level subclasses. So, you can also think of hierarchical state nesting as a form of inheritance called "behavioral inheritance" in which substates inherit the behavior from their superstates. In fact, an alternative view of the TimeBomb statechart could be explicitly hierarchical, as shown on the left as the traditional inheritance tree, or in the nested form on the right, as in the QM model explorer view. By the way, in a tree view like that, it's often convenient to think of the whole state machine as nested inside a single "top" state, which typically is not shown in the diagram, but turns out to be a useful concept for implementing hierarchical state machines. Speaking of which, how would you code your updated TimeBomb hierarchical state machine? Well, again, let's first look at your existing code as a specification of a state machine, not just implementation. With this perspective, the question becomes: how to unambiguously specify the hierarchical state nesting? For this, you can take clues from other forms of inheritance, like the class inheritance, where all that needs to be done is for a subclass to specify the single superclass that it inherits. So similarly, all a substate-handler needs to do is to specify its superstate. Now, the obvious most appropriate place to specify the superstate is the default case, because at this point the event is not being handled, so instead of being ignored, it should be passed on to the superstate. Alright, so you can introduce a macro SUPER(), similar to the macro TRAN(), with a parameter being the superstate-handler, like TimeBomb_armed in this case. Now, so you can copy this macro into all substates of "armed". But the state "defused" is not a substate of "armed". In that case, you can still use the SUPER() macro, but the superstate is the implicit "top" state, encoded as Hsm_top. Now, you need to add the TimeBomb_armed state-handler, which is similar to TimeBomb_defused in that it nests only inside Hsm_top. In that "armed" state, you copy the BUTTON2_PRESSED transition from any of the substates. You add the prototype of the new "armed" state-handler. And you can also delete all the repeated transitions from the substates of "armed". So, this is actually all that needs to be done to convert your traditional finite state machine into a hierarchical state machine. This is what I meant by saying that the "optimal" state machine implementation is easily extensible. But you still need to add the SUPER() macro and the Hsm_top state-handler to the event-processor, which is now part of your Micro-C-AO framework. Let's start with renaming the class FSM, which stands for Finite State Machine to HSM, which stands for Hierarchical State Machine. Now, let's add the macro SUPER() based on the existing macro TRAN(). Here, you should be careful not to clobber the state variable, because unlike during a transition, when you specify the superstate, you actually don't change the current state. Instead, let's set an additional attribute temp in the Hsm class, and add it as the temporary storage specifically for the superstate. Also, you now need to return a different SUPER_STATUS, which you need to add to the State enumeration. Finally, you need to add the prototype of the Hsm_top state-handler. In the implementation of the event processor inside the Micro-C-AO-dot-C file, you again replace Fsm with Hsm. Next, you add the Hsm_top state-handler, which ignores all events, so it always returns the IGNORED_STATUS. And finally, you need to augment the Hsm_dispatch() operation to implement the state hierarchy. Here, you add a check whether the current state-handler returns the SUPER_STATUS and if so, that means that the same event must be tried in the superstate, which is now provided in the temp attribute. Actually, because the state nesting is not limited to one level only, this should be a while-loop that continues as long as the state-handlers return the SUPER_STATUS. When the loop then terminates, it's because a transition is taken, or because you reached the top state, which returns IGNORED_STATUS. Either way, in case it was a transition, you exit the previous state and enter the new state, as before. This is a gross simplification, because with hierarchical states, you need to correctly exit all the nested source states and you also need to correctly enter all the nested target states, but let's keep this for now and see how this works. The code builds correctly, so let's load it to your TivaC LanuchPad board and perform some basic tests. First test: reset: Green-LED, SW2 button – Blue-LED, meaning "defused" state. This means that the inherited BUTTON2_PRESSED transition was taken. Second test: reset: Green-LED, SW1 button – blinking Red-LED, SW2 button – Blue-LED, meaning "defused" state. This means that the inherited BUTTON2_PRESSED transition was taken again. Third test: reset: Green-LED, SW1-button – blinking Red-LED, White-light: we're in "boom". SW2 button – no visible change. This looks like a flaw in the state machine design, because the LEDs aren't turned off on the way out of the "boom" state, so turning the Blue-LED on in the "defused" state makes no noticeable difference. Alright, so let's correct this problem first in the state machine, and then in the code. Here, possibly the best fix would be to add an exit action to "boom", which would exactly undo the entry actions. So, if the entry action turns all LEDs ON, the exit action should turn all LEDs OFF. But for the sake of today's subject, let's move this exit action to the higher-level of the "armed" superstate. I will explain the exact semantics of entry and exit actions in hierarchical state machines in a future lesson, but they are intuitive, in that a transition out of a state, hierarchical or not, must cleanly exit the state. But, there is more. For example, a superstate "armed" can have its own, nested initial transition to one of its substates, such as "wait4button". The meaning of such nested initial transition is that any direct transition to "armed", like for example BUTTON2_PRESSED from "defused", is required to also take the initial transition, so the end state will be "wait4button". Alright, so let's actually add all these new elements to your code. First, let's grab the entry action to "boom", copy it to "armed", change it to exit and reverse the actions. Now, the nested initial transition in "armed" is a new element. You can code it by the case with the special signal INIT_SIG followed by the TRAN() macro with the substate name as the target. Finally, the transition from "defused" to "armed" is also coded in the already established way. At this point, your application-level code for hierarchical state machine contains the most major elements and, as you can see, it is quite straighforward. The code even compiles, but it obviously won't work, because the nested exit and entry actions as well as nested initial transitions are not yet implemented in your Hsm_dispatch() operation. The bad news here is that, in the general case of multiple levels of sate nesting, these elements are tricky and quite complex to implement. The good news is that all that complexity is confined to the Hsm_dispatch() and Hsm_init() operations inside the active-object framework, which means that the complexity can be completely hidden from your application-level, state-machine code. But at this point you are really reaching the limits of your toy Micro-C-AO framework. So instead of implementing the complete rich semantics of hierarchical state machines from scratch in Micro-C-AO, in the last segment of today's lesson I will show you how to move on to a professional-grade QP/C framework. QP/C provides not just full implementation of hierarchical state machines, but also much more complete implementation of active objects. The framework will also enable you to apply automatic code generation, which is very much a part of the modern embedded systems programming and which I'd like to show you in the next lesson. Actually, you've been already using various parts of QP/C over many lessons, including this one. You've also already gone through the porting exercise back in lesson-27 about the RTOS, where you replaced the toy MiROS RTOS that you've been building as a teaching aid until that point with the QXK kernel from QP/C. Interestingly, back then, the tricky parts turned out not to be the context-switch magic. You did the Context-switch in the first two lessons on RTOS. The tricky parts turned out to be the complex inter-thread communication mechanisms. The situation repeats here again with the modern hierarchical state machines, because the tricky parts turned out not to be the state-hierarchy. This was handled in a simple while-loop. The complexity lies in the proper handling of transition chains of exit actions from the current state configuration and entry actions into the target state configurations. The process of moving an application from one framework to another is a form of refactoring and is called porting an application. It is like replacing the foundation from under a house with minimal disturbance to the house itself. To start the porting, let's create the groups QPC and QPC_port, similar to uCOS-II and uCOS-II_port. Now you can delete the Micro-C-OS groups. And also, to make sure that none of the Micro-C-OS stuff is being used, let's go to the current lesson 40 project on disk and delete the files app_cfg.h, os_cfg.h, uc_ao.c and uc_ao.h. Also, you need to remove these files from your project. Next, you need to add the QPC source code to the QPC group. If, by any reason you don't have QPC yet, please visit the companion web-page to this video course at state-machine.com/video-course and download QPC in a ZIP file. Inside the QPC directory, go to src/qf sub-directory and select all the files. This is the code for state machines and active objects. In addition to this, you will need to choose the real-time kernel for QP/C. For this lesson, choose the simplest, non-preemptive QV kernel in the QV sub-directory. I will explain the other real-time kernels available in QP/C in the future lessons. And finally, you will need the specific port of the QV kernel for your ARM Cortex-M processor and the ARMCLANG toolchain you are using. For this, you go up to the ports directory and down to arm-cm, and inside there to qv and armclang sub-directory for your specific compiler. The next step is to adapt the include paths for your compiler. You need to add here the qpc\include sub-directory, the qpc\src sub-directory and the specific qpc port with the QV kernel and ARMCLANG compiler. These changes should be now sufficient to compile the QP/C framework itself, as you can test with of the QP/C source files. Now you can move on to adapting your application, starting with the Board Support Package (BSP). Here, in the BSP-dot-H header file, you add the Q-prefix to the items that now come from the QP framework. The practice of starting all names with the common prefix is quite popular in designing reusable software, because it minimizes potential name conflicts and helps to recognize the framework API in the code. You can also remove the BSP_ASSERT macro, because the assertion mechanism is already provided in QP/C. And you also add the constant BSP_TICKS_PER_SEC to replace similar constant from uC/OS-II. Now, inside the BSP-dot-C source file you perform similar changes. You replace the Micro-C-AO header file with QPC-dot-H. And instead of the Micro-C-OS-II time-tick hook you use directly the SysTick_Handler ISR. Here, you replace the time event processing with QF_TICK macro. And you also replace Event with QEvt and Active_post with QACTIVE_POST macro. You delete the other Micro-C-OS hooks. And you replace BSP_start with the QP/C callback QF_onStartup(). Just to remind you, callbacks are functions that you need to provide, but you don't call, because they are called by the framework. The naming convention for QP callbacks is that they all start with on..., like QV_onIdle, QF_onStartup, or QF_onCleanup. At this point you can try to compile the updated BSP, and you fix the remaining issues, like the parameters for the QACTIVE_POST macro. OK, so with the BSP done, you move on to adapting the most interesting part, which is your TimeBomb state machine code in main-dot-c. Here, you replace the header file to use QP/C and you provide the module name for the QP/C assertions. But then, you need to make a bunch of global replacements to adjust the API to the QP/C framework. Specifically, you need to replace: Active with QActive TimeEvent with QTimeEvt State with QState Event with QEvt TRAN with Q_TRAN EXIT signal with Q_EXIT_SIG ENTRY_SIG with Q_ENTRY_SIG INIT_SIG with Q_INIT_SIG SUPER with Q_SUPER HANDLED_STATUS with Q_HANDLED() Please note that these are all rather trivial name substitutions, which don't really change the structure of your state machine code. In other words, QP/C uses the exact same "optimal" sate machine implementation you've learned in the last lesson and extended today for hierarchical state machines. Now, there are still some adjustments for the QP API, but perhaps the most interesting change for the QV kernel is that you don't need the expensive per-thread stack. A few more changes, but finally the project builds cleanly, so the very last thing to do is to check how it works. Reset: Green-LED, SW1-button: blinking Red-LED, SW2-button: blue-LED meaning "defused" state. But now, SW2-button again: combination of Blue and Green-LEDs, meaning back to the armed superstate and wait4button substate. Now, SW1-button: solid Blue-LED and blinking Red-LED and finally White LED, meaning the "boom" state. Of course, the Blue-LED should be turned off in the exit action from "defused", but I leave as an exercise for you. More importantly, however, all aspects of state hierarchy now work correctly. This concludes this first glimpse of hierarchical state machines. I devoted a lot of time to the implementation, because I wanted to disprove the common misconception that hierarchical state machines are too hard to code manually. As you saw, given the right, "optimal" state machine implementation strategy the complications were quite manageable. But still, coding state machines is manual labor that can and should be automated. In the next lesson I will show you exactly this: automatic generation of state machine code. Stay tuned! If you like this channel, please give this video a like and subscribe to stay tuned. You can also visit state-machine.com/video-course for the class notes and project file downloads. Finally, all the projects are also available on GitHub in the Quantum Leaps repository "modern embedded programming course". Tanks for watching!