Arch 1 – Welcome to Statecharts

The Architecture Series

In this series, we will look into modern software architecture and advanced design techniques for reactive and asynchronous systems. While the focus is on embedded systems, the same concepts and techniques apply very well to any systems that require responsiveness and reliability, including back-end servers and web applications for IoT systems.

Traditionally embedded systems are defined as systems with constrained resources, such as those running on a microcontroller with 256KB of flash and 64KB of SRAM. Nowadays, this definition is getting blurred. Popular embedded Linux platforms can easily come with a CPU running at over 1GHz and with gigabytes of memory which can hardly be considered resource constrained. The advent of IoT systems moves a lot of features that were once running on embedded devices up to the cloud or web application. For example sensor data measured by an embedded device can now be displayed on a web browser instead of on the device LCD. In other words, a web application can be viewed as an extension or a part of an embedded system.

Despite the evolution, one nature of embedded systems has not changed and remains at its core. That is asynchronicity. An asynchronous system must handle various inputs (from users, sensors, network, etc.) arriving at different time and in different order, resulting in a large number of cases that the system needs to consider. Specifying what the system should do in all these cases (determinism) and having the system behave correctly all the time (reliability) is a much more difficult task than it appears.

In this series, we will introduce a model-based event-driven architecture designed with asynchronicity, determinism and reliability at its heart. We will show you how to build a statechart framework and practical applications with this architecture.

Outline

In the following episodes of this Architecture series, we will cover the following topics in depth:

1. Toolchains for STM32 development boards
2. Object-oriented design with C++
3. Statecharts and hierarchical state machines
4. Event-driven architecture and framework with QP
5. Design examples for GPIO, UART, I2C, SPI, Sensor, LCD and WiFi modules
6. Integration with web application
7. Debugging and profiling with interactive console

What is Software Design

In the most general terms, the goal of software design is to program a computer to perform the actions that we want it to do. It may sound like an over-simplification, but it does bring up a couple interesting questions:

1. Do we really know ourselves what we want a computer to do? Is our knowledge complete and free of contradictions? Can we capture this knowledge systematically?
2. Assuming the answers to the above questions are “yes”, how do we transfer this knowledge to a computer in a precise and straight-forward manner?

Even in the age of AI and machine learning, these questions are still relevant to us, particularly in the fields of safety or mission-critical systems.

Two Key Concepts

Knowledge Representation

The first set of questions are about knowledge representation, i.e. how to represent our knowledge about system behaviors. It can be tricky since knowledge is very abstract. Human thoughts are very flexible but often are not precise enough. We do better in reasoning about sequential logic (like if … then …, do … while …, wait until … etc.) than reasoning about things that can happen in parallel.

We need a tool to help us with that – a tool that helps us define system behaviors, capture them and visualize them.

It is such a difficult problem that it took a computer scientist to find a solution. It was David Harel who created statecharts back in late 1980s to solve this exact problem – how to specify system behaviors for embedded systems (a fighter jet in his case).

This is David Harel’s original paper on statecharts [1]:

Statecharts: A Visual Formalism For Complex Systems. David Harel. Science of Computing Programming 8. 1987.

(http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf)

He later gave a personal account on the creation of statecharts in another paper [2]:

Statecharts in the Making: A Personal Account. David Harel. ACM Communications. March 2009.

(http://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts.History.pdf)

His Statecharts in the Making paper [2] is a must-read for any software engineers. It is surprising that some of his observations back in the 80s that inspired the creation of statecharts are still happening every day in the software industries.

For example, he noticed that in the development of a flight control system “someone, eventually, would make a decision about what happens when you press a certain button under a certain set of circumstances. However, that person might very well turn out to be a low-level programmer whose task it was to write some code for some procedure, and who inadvertently was making decisions that influenced crucial behavior on a much higher level.” [2]

Could we fix this issue by simply listing out the requirements (or stories) about what the system should do when a certain button is pressed in all situations?

The problem came down to our natural thought process and language being not precise enough to capture parallel behaviors. David Harel noted that it was “difficult for them to convince me that a two-volume, 2000 page document, written in structured natural language, was a complete, comprehensive and consistent specification of the system’s behavior.” [2]

David Harel concluded that there was a need to “come up with some kind of structured and hierarchical extension of the conventional state machine formalism.” [2] which has become statechart.

Knowledge Mapping

Now let’s address the second question – how do we transfer our knowledge to a computer in a precise and straight-forward manner?

If we simply program our sequential logic into code, it won’t take long for our program to evolve into a big messy ball of spaghetti. This is a mapping problem. We need an effective tool to map our knowledge of system behaviors into executable code. Such tools have pretty much existed since the creation of statecharts, but they were very expensive. It was the introduction of Quantum Framework/Platform by Miro Samek in 2000 that made it truly affordable and practical to general developers.

Today there are many statechart tools available for various computing languages, including:

1. scxmlcc (jp-embedded/scxmlcc: The SCXML state machine to C++ compiler (github.com))
2. The Boost Statechart Library (The Boost Statechart Library – Overview – 1.81.0)
3. Qt SCXML (Qt SCXML 6.4.1)
4. xstate (xstate – npm (npmjs.com) )
5. miros (Python Statecharts | miros (aleph2c.github.io))

Among them, QP remains a good candidate for embedded systems due to its small size, high efficiency and minimal dependencies. Check out this article [3] for the very first introduction of QP:

State-Oriented Programming. Miro Samek. Embedded System Programming. August 2000.

(State-Oriented Programming, 8/2000 (state-machine.com))

You may learn more about QP and its licensing model on its website:

Modern Embedded Software – Quantum Leaps (state-machine.com)

Software Design Is…

Now we are ready to answer the question of “What is software design?” It is

1. A complete and precise specification of system behaviors that fulfills the requirements. We call it the behavioral model which is the representation of our knowledge about what the system is required to do. Statecharts are simple yet powerful tools that help us achieve this.
2. A software architecture that supports the execution of the model. Quantum Platform (QP) is one of such tools that help us map statecharts to C/C++ code effectively.

Design-Centric Vision

Modern software practices rely heavily on unit testing, refactoring and continuous integration (CI), which play a very important role to the success of complex software projects. However, a dedicated and maintainable software design process does not seem to receive equal attention. In fact, there is no conflict between testing/CI and design, and with the right tools they work very well together.

We are fortunate today as there are many great tools at our disposal for software development. To name a few, we have:

1. Git for source control and code review
2. CMake for configuration and build control
3. Jenkins for build automation
4. Unit test frameworks for unit testing
5. Agile and Jira for project management
6. Python for process automation.
7. Static and dynamic code analysis tools.

What is missing in the list above is a dedicated tool for design. As we have seen earlier, statechart is a great design tool that can precisely specify system behaviors and map requirements to executable code. We believe software design should be a core activity of our development process, rather than being an accidental output of our coding and testing exercise. This is our design-centric vision:

Reference

1. Statecharts: A Visual Formalism For Complex Systems. David Harel. Science of Computing Programming 8. 1987.(http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/Statecharts.pdf)
2. Statecharts in the Making: A Personal Account. David Harel. ACM Communications. March 2009. (http://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts.History.pdf)
3. State-Oriented Programming. Miro Samek. Embedded System Programming. August 2000. (State-Oriented Programming, 8/2000 (state-machine.com))