embedded software boot camp

Linear statechart notation

Monday, November 15th, 2010 by 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.

10 Responses to “Linear statechart notation”

  1. Lundin says:

    I think the only ones getting urges to hang themselves because of state charts are UML people. Everyone else simply draws state charts as plain old flowcharts. They are perfectly linear and it is a notation that most programmers are familiar with. Esentially it is exactly what that program in the picture does. You can call it “linear notation” or whatever you want: a rose by any other name…

    • Miro Samek says:

      Yes, unfortunately many people confuse statecharts with flowcharts. These are two *completely* different concepts (please see my article “A crash course in UML state machines: Part 1″ available at http://www.eetimes.com/design/automotive-design/4008247/A-crash-course-in-UML-state-machines-Part-1).

      Statecharts and flowcharts represent diametrically opposed programming paradigms.

      Statecharts represent *event-driven* programming, in which a system (state machine) sits in a certain state and waits for an event. Once the event arrives, the state machine processes the event quickly, possibly changes the state, and goes back to waiting. The state machine is dormant while waiting in a state (rounded-corner box in a diagram). Processing is triggered only when an event arrives (so graphically processing corresponds to an arrow).

      In contrast, flowcharts represent traditional *sequential* programming. Flowchart represents processing as boxes and transitions from one box to the next *automatically* upon completion of the processing assigned to the box. No events are needed. Graphically, compared to statecharts, flowcharts reverse the sense of boxes and arrows.

      Pure flowcharts have been made basically obsolete a long time ago by “structured programming” (Fred Brooks provides a critique of flowcharts in “The Mythical Man Month”). The “linear notation” for flowcharts is simply the “structured code” (IFs, ELSEs, and WHILEs).

      State machines, and especially hierarchical state machines, are a completely different concept from flowcharts. The “linear statechart notation” I am proposing in this post is in a way an equivalent of “structured programming” for state machines. I think it is a big deal.

      • Lundin says:

        There’s nothing stating what the arrows in a flowchart represent. It could be events, interrupts or whatever. I design event-driven applications all the time, and I don’t encounter any problems with flowcharts: they are just a pseudo-code specification of the behavior of the program.

        Judging by your posts, the only difference is that UML statecharts by definition are idle. So what, just make an arrow in the flowchart pointing back into itself… no big deal. I can write “have event occured?” inside the flowchart. What’s the big deal?

        All of this is just bubbles and arrows, charts are to define the rough functionality of the program. All petty details such of how to wait, how to poll events etc are best left to a programmer, when the chart is interpreted to a program. The programmer ain’t so dumb that he replaces the effective OS API wait-for-event instruction with an ineffective polling while-loop, just because I used a flowchart and not a statechart.

        A program is sequential by its nature, because there exists no computer in the world that is not executing programs starting at the top, and then proceeding downwards. CPUs may very well execute several things at once, but always top-to-bottom. You may need several charts, one for each thread/process/ISR, and you will need to do that no matter if you are using UML statecharts or flowcharts.

        I got fed tons of UML back in school, but none ever mentioned flowcharts. Looking back at my education, I never quite understand why, but I think it has something to do with religious believes. Only when disembarking into the real world of engineering, I found out about flowcharts. Their main advantage against UML state charts, is that they are not only de facto standard, but also convention among engineers. If I draw a flowchart, everyone knows what I’m doing and my team can quickly move on to the actual program design and algoritms with minimum confusion.

        • Miro Samek says:

          I’m sorry that it took so long, but I really wasn’t sure even where to begin my reply to your last comment. Your level of confusion simply cannot be addressed in a reasonably sized response. But it seems to me that many people are just as confused about state machines and flowcharts as you are. So, in the end I decided to write more about statecharts versus flowcharts in this blog, because after all, cutting through this confusion is one of my main goals here. I promise to try my best to explain why statecharts and flowcharts are two *completely* different things, and why I believe state machines matter in embedded software. For now, I’d like to recommend my articles originally published in C/C++ Users Journal “Who Moved my State” (http://www.drdobbs.com/cpp/184401643) and “Back to Basics” (http://www.drdobbs.com/184401737).

          • Lundin says:

            I’m not confused at all, you are not even reading my posts. Again, flowchart vs statechart has nothing to do with how the actual program mechanics are implemented! Unless of course you let tools like Rhapsody generate all the code, as a replacement for reason and programming knowledge, then it would indeed matter plenty.

            And the other way around, whether the implementation uses switch statements or function pointers etc is quite uninteresting from the program design’s point-of-view.

            I’m not arguing against using state machines in the actual program. Many embedded applications are in fact impossible to design without a state machine, such as application layers for just about any fieldbus, where a state chart is integrated with the standards.

            As I’ve worked with both OO in the C language and PC programming, there is nothing new to me in those links. I’ve worked plenty with RAD tools and design patterns (aka “useful algoritms”).

            I actually think you are the one confused here… did you know this site is for embedded systems? Those links are about PC programming. How exactly is Visual Basic and RAD tools relevant to embedded system programming? IDEs such as VB and Delphi may be “event-driven”, (although underneath them lies the Windowproc message pump which is a switch-based state machine), but they rely on the following:

            - no real-time requirements what-so-ever
            - no deterministic behavior what-so-ever.
            - an incredibly fast CPU so that the ineffectiveness and arbitrary behavior of the program isn’t easily noticed.
            - keeping the GUI events unexposed to multi-threading as far as possible.

            This is about as far from realtime embedded systems as you can get.

            “The actions actually executed are determined by events, which arrive in largely unpredictable order and timing, so the path through the code is likely to differ every time such software is run.”

            This is acceptable for desktop applications but not for deterministic, real-time embedded systems! You simply -can’t- implement something like VB:s events in such a system. The program can’t run around doing arbitrary tasks whenever it feels like it, just because you can hide away this arbitrary behavior behind a powerful CPU.

            If you do, you have zero control of the program and you are designing in a whole bag of worms of unexpected workload peaks. You thought spaghetti unconditional jumps were bad? Try spaghetti program behavior. The more powerful the CPU is, the harder these bugs will be to detect. This is exactly what Michael Barr warns against in his series of articles about RMA which you can read on this site.

            Instead, an embedded system state machine needs to be completely predictable, with deterministic state changes, with a failsafe state from where the state machine starts over from scratch, often combined with some HW reset.

          • Lundin says:

            You don’t alawys have RTOS, you could be on a bare CPU, but still need an event-driven state machine. Then there is no OS scheduler present, so it becomes even more crucial that all events are of a deterministic nature, or else the program will go haywire realtime-wise.

            OS-less state machines are typically of a top-down nature, starting at system bootup/reset, moving down to failsafe mode, and then through several steps move further down to the running modes. Which in turn makes the dreaded flow chart quite suitable for describing them.

  2. Daniel Michel says:

    Hello Miro,

    I totally agree with your observation that having a linear, hierarchical view of a state machine is very helpful to understand a state machine. But, in my opinion, this is just one way to look at a state machine. In general, a certain view should always highlight *one* aspect of the state machine.

    Thus, the hierarchical view is useful for examining containment relations, just as in the Explorer of your screen shot. However, the state chart diagram should provide a different view: For example, I’d like to see transitions of different nesting levels that are relevant. I think that if the state machine becomes larger, the linearization of the diagram may even be contra-productive, since transition arrows are potentially longer and more interwoven.

    Thus, I like the linear view in the Explorer, but not in the diagram.

    Apart from giving the developer the control over how states are arranged in the diagram, another feature is very important to support complex state machines: The developer must be able to introduce separate diagrams for sub-states of specific composite states. In UML this is known as submachine states. I’ve been using Rhapsody a lot, and I think the diagramming support for state machines is one of its strengths, especially with regard to submachines.

    • Miro Samek says:

      Hi Daniel,

      Thank you for the insightful comments.

      I see your point regarding large state machines and potentially very long transitions. To counteract the very elongated diagrams, I would allow more than one vertical columns inside composite states. An example of this is shown in the screen shot http://www.state-machine.com/qm/shot0.jpg.

      However, I’d like to point out other, more local, elements of the proposed notation. For example, you see that all transitions (both regular transitions and internal transitions) originate at the left state edge and extend right, which allows easy and unambiguous labeling the transitions. This arrangement also facilitates searching for transitions, because they are literally listed top-to-bottom in the source state. If you don’t see a transition in this list, you know for sure that the state does not handle this particular event. No more searching all edges and corners is necessary.

      Another important element of the proposed notation (which is a “non-normative” UML) is that the internal transitions are represented as lines terminated with a square. (In UML, an internal transition is represented as text only inside the entry/exit compartment.) This new notation for internal transitions makes it very easy to model the situation where an event needs to trigger a regular transition or an internal transition, depending on a guard condition. This situation comes up very often in practice, for example see the Ship state machine, state “exploding”, event TIME_TICK. To show this simple choice in the “normative” UML, you would need to repeat the same trigger twice, once in the internal transition compartment, and once on the regular transition. You also would need to put the complementary guards on the repeated triggers (otherwise the diagram would be illegal). The problem is that the triggers are far apart in different places of the diagram, so it is very hard to see what the complementary [else] guard relates to.

      I also agree with you that bigger state diagrams must make effective use of abstraction. In other words, it should be possible to collapse a composite state or expand it (to go up or down the level of abstraction). UML addresses this requirement through the concept of submachine states. IBM Rhapsody supports submachine states as separate diagrams, but you probably agree that it is typically a bad idea to insert the submachine diagram into a submachine state (which Rhapsody tries to support as well). The resulting diagram typically looks really bad and cluttered.

      So here again, the complex, fully 2-dimensional structure of traditional UML statecharts stands in the way. Consider how easy it is to collapse or expand a node in the Explorer view. The proposed “linear statechart notation” would make collapsing and expanding states almost as easy in the statechart diagram.

      I’d be interested to hear your comments, especially about the “non-normative” notation for internal transitions.

      –Miro

  3. Daniel Michel says:

    Hello Miro,

    I must say that I still find the diagram of your screen shot more complicated than the corresponding UML diagram. But I guess that’s because UML is what I’m used to.

    I agree with your point on listing internal and external transitions together, that’s clearly an advantage. However, the perferct diagram tool for me (which Rhapsody is clearly not, btw), would offer exactly this linear representation of all transitions in the Explorer view. Because that’s what the Explorer view is there for: It shows a hierarchical tree of the elements in a state machine. And when the Explorer is able to do that, I don’t need it in the diagram, thus the diagram can focus on different aspects.

    The problem with guards on internal and external transitions is in fact a problem, even though I see it as a minor one. Often the situation can be improved by introducing an additional inner state that handles both transitions as external ones. Thus, the guard is needed only once. But, when not adhering to strict UML anyway, one has the freedom to design a solution that grabs the problem at the root. Your solution to that problem is quite nice.

    I see your points, and I agree with you that UML is not the best solution for all the problems out there. But, for state machines, I guess I’d stay with UML. An important reason for preferring UML over other approaches is the “U” in UML: It is an established, well-known standard, and that fact IS important for decisions in companies or teams.

    Btw, I’m currently developing a generator for UML state machines that produces code that runs on QP. If you’re interested, I could share my findings so far. You can reach me by email on dmi (-AT-) zuehlke (-DOT-) com.

    Regards,
    Daniel

    • Miro Samek says:

      Thanks again for more insights.

      Frankly, I don’t see how a diagram drawn ad-hoc could be significantly simpler than the diagram drawn more systematically according to the “linear notation”. Please note that the “linear statechart notation” *is* legal UML. I’ve thrown in the non-normative notation for internal transitions, but even without this extension the “linear notation” retains most of its benefits.

      Speaking of non-normative UML, please believe me that I didn’t take the departure from the Standard lightly. I realize that a step away from the Standard in the QM tool could mean losing the more experienced UML users, who already work with existing UML tools. (This could well be the most lucrative part of the market, because the practicing modelers are used to paying a lot for their UML tools). Your comments seem to corroborate my concerns.

      But having a choice between compliance and genuine usefulness I gravitated toward usefulness in QM. Strict compliance to the UML Standard seems to me more a marketing rhetoric than real benefit to the user. Every tool on the market today has its deep idiosyncrasies, and even with UML 2.3 and XMI, you effectively do have a tool lock-in. In practice a model generated with Rhapsody will not work with, say Enterprise Architect, or any other tool.

      Regarding code generation from big UML tools, such as Rhapsody, there is a small aftermarket for code generators and frameworks, which is an indicator that the code and RTOS bindings available “out of the box” with such tools aren’t quite adequate. You might have heard about the Embedded UML RXF (Real time eXecution Framework) from Willert.de. Peter Mueller provides a tool called SinelaboreRT (sinelabore.com), which generates state machine code from XMI. I’d like to find out about your approach.

Leave a Reply