Archive for the ‘state machines’ Category

Turning automatic code generation upside down

Tuesday, February 14th, 2012 Miro Samek

Much ink has been spilled on the Next Big Thing in software development. One of these things has always been “automatic code generation” from high-level models (e.g., from state machines).

But even though many tools on the market today support code generation, their widespread acceptance has grown rather slowly. Of course, many factors contribute to this, but one of the main reasons is that the generated code has simply too many shortcomings, which too often require manual “massaging” of the generated code. But this breaks the connection with the original model. The tool industry’s answer has been “round-trip engineering”, which is the idea of feeding the changes in the code back to the model.

Unfortunately, “round-trip engineering” simply does not work well enough in practice. This should not be so surprising, considering that no other code generation in software history has ever worked that way. You don’t edit by hand the binary machine code generated by an assembler. You don’t edit by hand the assembly code generated by the high-level language compiler. This would be ridiculous. So, why modeling tools assume that the generated code will be edited manually?

Well, the modeling tools have to assume this, because the generated code is hard to use “as-is” without modifications.

First, the generated code might be simply incomplete, such as skeleton code with “TODO” comments generated from class diagrams. I’m not a fan of this, because I think that in the long run such code generation is outright counterproductive.

Second, most code generating tools impose a specific physical design (by physical design I mean partitioning of the code into directories, and files, such as header files and implementation files). For example, for generation of C/C++ code (which dominate real-time embedded programming), the beaten path is to generate <class>.h and <class>.cpp files for every class. But what if I want to put class declaration in a file scope of a .cpp file and not to generate the <class>.h file at all? Actually, I often want to do this to achieve even better encapsulation. A typical tool would not allow me to do this.

And finally, all too often the automatically generated code is hard to integrate with other code, not created by the tool. For example, a class definition might rely on many included header files. But while most tools recognize that and allow inserting some custom beginning of the file, they don’t allow to insert code in an arbitrary place in the file.

But, how about a tool that actually allows you to do your own physical design? How about turning the whole code generation process upside down?

A tool like this would allow you to create and name directories and files instead of the tool imposing it on you. Obviously, this is still manual coding. But, the twist here is that in this code you can “ask” the tool to synthesize parts of the code based on the model. (The “requests” are special tags that you mix in your code.) For example, you can “ask” the tool to generate a class declaration in one place, a class method definition in another, and a state machine definition in yet another place in your code.

This “inversion” of code generation responsibilities solves most of the problems with the integration between the generated code and other code. You can simply “ask” the tool to generate as much or as little code as you see fit. The tool helps, where it can add value, but otherwise you can keep it out of your way.

The idea of “inverting” the code generation is so simple, that I would be surprised if it was not already implemented in some tools. One example I have is the free QM tool from my company (http://www.state-machine.com/qm). If you know of any other tool that works that way, I would be very interested to hear about it.

Protothreads versus State Machines

Thursday, June 9th, 2011 Miro Samek

For a number of years I’ve been getting questions regarding Protothreads and comparisons to state machines. Here is what I think.

Protothreads are an attempt to write event-driven code in a sequential way. To do so, protothreads introduce a concept of “blocking abstraction” to event-driven programming–something that event-driven programming is trying to get rid of in the first place.

Obviously, to be compatible with event-driven programming, protothreads cannot *really* block, at least not in the same sense as traditional threads of a conventional blocking RTOS can. Instead, a protothread is still called for every event and still *returns* to the caller without really blocking. However, when a given event does not match the “blocking abstraction”, the protothread returns without doing anything and without progressing. Only when the current event matches the “blocking abstraction” the protothread advances to the next “blocking abstraction” and also returns. Please note that protothreads allow standard flow control statements, such as IF-THEN-ELSE and WHILE loops between any two “blocking abstractions”. Therefore the program feels more “natural” for designers used to the traditional sequential programming style. You simply see the expected sequence of events.

Protothreads are indeed a simplification, but only for *sequential problems*, in which only specific sequences of events are valid and all other sequences are invalid. Examples for using protothreads include the sequence of events for initializing a radio modem.

However, protothreads lose their advantage entirely if there are many valid sequences of events. This is actually the most common situation in event-driven systems. State machines are capable to handle multiple sequences of events easily. In fact, state machines are getting simpler when the sequence of events matters less. In contrast, protothreads are getting more and more complex when they need to accept more sequences of events.

So, in the end, protothreads are an attempt to replace state machines, which are considered complex and messy by the inventors of the protothread mechanism. But, the “messiness” of state machines is obviously a very subjective statement. A good state machine implementation technique can remove many (most) accidental difficulties of coding state machines. I mean, if a state machine as depicted in a state diagram is simple, and if the code does not reflect this simplicity, the problem is with the implementation technique, not with the inherent complexity of a state machine.

The bottom line: good state machine implementation techniques eliminate most reasons for using protothreads. State machines are far more generic and flexible, because they can easily handle multiple sequences of events. In comparison, protothreads are intentionally crippled state machines that transition implicitly from one “blocking abstraction” to another executing code in between as the “actions” on such implicit transition.

Is an RTOS really the best way to design embedded systems?

Tuesday, June 7th, 2011 Miro Samek

LinkedIn RTE group

Recently I’ve been involved in a discussion on the LinkedIn Real-Time Embedded Engineering group, which I started with the question “Is an RTOS really the best way to design embedded systems?“.

The discussion, which has swollen to way over 600 comments by now, has sometimes low signal to noise ratio, but I believe it is still interesting.

I consider this discussion to be a continuation of the topic from my April blog post I hate RTOSes.

As before, my main point is centered on the fundamental mismatch of using the sequential programming paradigm (RTOS or superloop) to solve problems that are event-driven by nature.

I’m really curious what the visitors to EmbeddedGurus think.

Linear statechart notation

Monday, November 15th, 2010 Miro Samek

The traditional fully 2-dimensional structure of UML state diagrams is too much rope to hang yourself with. There is no standard drawing order or pattern; some designers start from the top, some from the middle, and others just “go with the flow”. Transitions can originate at any state edge and go in any direction, so they are easy to miss in any nontrivial diagram because you don’t know exactly where to look.

In many ways, UML state diagrams resemble the old way of drawing tree structures (e.g., a family tree) with the root in the middle and branches fanning out in all directions. But today nobody draws hierarchical structures that way anymore. If you look at your file-system explorer you will see the hierarchical structure of directories and files arranged linearly, top-to-bottom. The “linear statechart notation” that I would like to propose here is based on the same idea.

The goal of the “linear statechart notation” is to make the diagrams more structured and legible by reducing the use of horizontal dimension.

As an example of the “linear notation” consider the state diagram shown in the screen shot from the free QM tool.  (This statechart shows the lifescycle of a space ship in a simple “Fly ‘n’ Shoot” game.) First please take a look at the hierarchical model explorer pane on the left-side of the screen. You see the Ship object, its attributes and methods followed by the Statechart with the hierarchically arranged elements below. Now, please take a look at the state diagram in the middle. You will see the one-to-one correspondence between the diagram and the explorer view. Please note that the state diagram is essentially 1-dimensional.

Finally, please take a look at the right-hand side, which is a screenshot of the *generated code* in the Eclipse-based tool (Atollic TrueSTUDIO in this case). The generated code corresponds to the state “flying”, which is highlighted in the diagram. Interestingly, the code itself is an extension of the “linear notation” that zooms into the “flying” state. Again, just go from the top to bottom in the code, inside the “flying” state in the diagram, and in the “flying” element in the model explorer. You see exactly the same elements represented in the same order, from the entry action, through the events TIME_TICK, PLAYER_TRIGGER, DESTROYED_MINE, HIT_WALL, and HIT_MINE. I think this consistency and tracibility is great.

I’d like to hear your comments about the proposed notation. I also hope that this post explains a bit how the free QM tool works and generates code.

Free state machine tool for embedded systems

Saturday, November 6th, 2010 Miro Samek

I realize that I stalled a little my series about RTOSes, event-driven programming, state machines and frameworks for embedded systems. I certainly will come back to this subject, but today I wanted to let you know about a new, free, graphical tool for drawing state machines and generating production-quality embedded code.

Traditionally, such tools haven’t particularly caught on in the embedded space, mainly because too often such tools fail to pull their own weight. Developers find themselves fighting the tool at every step of the way: from drawing the diagrams to trying to live in a straight jacket of the code structure it generates.

The new, free QM tool from Quantum Leaps (my company) is different, because it was designed from the ground up around the code-centric approach. Unlike other graphical tools, QM gives you complete control over the generated code structure, directory names, file names, and elements that go into every file. You can mix your own code with the synthesized code and use QM to generate as much or as little of the overall code as you see fit. At the low level, QM respects your graphical layout as much as possible and will not re-attach or re-route connectors, resize nodes, or adjust text annotations. You will find that you don’t need to fight the tool.

Even though a lot of effort went into making QM as UML-compliant, the tool is innovative and might work differently than other graphical state machine tools on the market. For example, QM does not use “pseudostates”, such as the initial pseudostate or choice point. Instead QM uses higher-level primitives of initial-transition and choice-segment, respectively. This simplifies state diagramming immensely, because you don’t need to separately position pseudostates and then connect them. Also, QM introduces a new notation for internal transitions, which allows actual drawing of internal transitions (in standard UML notation internal transitions are just text in the state body). This notation enables showing internal transitions with regular state transitions in a choice point–something that comes up very often in practice and was never addressed well in the standard UML.

The QM tool is available now for a free download and free, unrestricted use from state-machine.com/qm. I’d appreciate any comments about the tool, comparisons to other similar tools, code generation, UML, state machines, etc.