Archive for August, 2002

Quantum Programming

Saturday, August 17th, 2002 Michael Barr

I don’t buy many books about embedded systems. Most books of relevance find their way to me as review copies. I try to read, or at least skim, all those that look promising. Unfortunately, I’ve found that relatively few are worthy of permanent space on my bookshelf or recommendation to others. Which is why I want to tell you about one recent standout.

Perhaps you recall the article “State-Oriented Programming,” which appeared precisely two years ago in Embedded Systems Programming magazine? If not, suffice it to say it described a very simple manual coding technique for turning hierarchical state machines into compact C or C++ programs. Though I was certainly impressed by the authors and their approach, I didn’t then recognize the brilliance of the underlying ideas.

The primary author’s recent publication of a book-length treatment of the topic has helped me see the light. The book, by Miro Samek, is titled Practical Statecharts in C/C++ (CMP Books). However, the title of the book is a major understatement. What stands out in my mind is not the practical nature of the solution it provides to a common recurring problem, but the downright revolutionary ideas behind that solution.

The author’s so-called “Quantum Programming” may ultimately change the way embedded software is designed. Never before has there been a viable alternative to the traditional main()+ISR vs. RTOS problem. Preemptive multitasking only works well in specific scenarios, while main()+ISR comes with its own set of problems when you try to scale it. A third way is needed.

This book presents a solution, based around state machines, that is compact (5KB is all that’s typically required), realized in C and C++ (no fee or royalties), of theoretical value in any language (even assembly), and can support multiple state machines running in parallel if necessary. It’s also the first good way I’ve seen to deal with the inheritance of state behavior in hierarchical state machines. Samek calls his implementation the “Quantum Framework.”

Before quantum programming, there were basically three approaches to state machine implementation: switch statements, tables of function pointers, and object-oriented programming constructs. The handling of substates in hierarchical state machines was complex in all three approaches. Hierarchical state machines are common, with part of each state’s behavior being determined by its parent state and the rest by the substate itself. This is difficult to implement in the traditional approaches because it either requires duplication of code or additional function/method calls. At best, the results tend toward spaghetti code.

In a nutshell, the quantum programming technique is a design pattern for direct efficient implementation of flat or hierarchical state machines. It uses the popular and proven UML statecharts as its graphical specification language, and leaves the choice of implementation programming language up to the developer. Hierarchical states are implemented via an externally-driven “event processor,” the use of which ensures that substates need not duplicate the functionality of their parents (and grandparents).

I believe that Miro Samek’s innovative techniques will quickly become popular, and I have already put them to good use. If you read only one book about embedded systems this year, make it Practical Statecharts in C and C++.