Lambda the Ultimate

that sounds quite relevant and interesting even if not :-)

Harel notes in his STATEMATE papers and books that he does NOT expect people to directly implement statecharts in code, and considers it a poor implementation technique.

A lot of people totally miss this fact. There are so many papers derived from his work, Ph.D. dissertations even, that completely miss Harel's wisdom.

Harel instead advocates it simply for visualization of the design space, in particular to show composition scenarios.

The fact Harel understood his work was not good for implementation, is why he is such a genius. He has a real eye for simplicity.

Just a note that Harel's paper from HOPL-III, Statecharts in the Making, was previously mentioned on LtU.

In the HOPL paper. Harel says:

My take was that the basic requirement of a tool for developing systems that are dynamic in nature is the ability not only to describe the behavior, but also to analyze it and execute it dynamically. This philosophy underlies the notion of a visual formalism, where the language is to be both diagrammatic and intuitive in nature, but also mathematically rigorous, with a well-defined semantics sufficient to enable tools to be built around it that can carry out dynamic analysis, full model execution and the automatic generation of running code; see [H92].

[H92] D. Harel, "Biting the Silver Bullet: Toward a Brighter Future for System Development", IEEE Computer 25:1 (1992), 8–20.

Z-Bo, I dont see how this squares with "not good for implementation." I think quite the opposite.

It is important that the semantics of a visual formalism be detailed and rigorous enough to be usable for implementation purposes. It does not follow that you should use it for implementation purposes. Direct execution of the visual formalism is the preferred way to prototype a system as its specification changes. Software code is a possible executable formalism, but it is not the preferred way to do things.

The major problem with a direct implementation is that you throw away what Harel calls the functional view and behavioral view that a visual language inherently provides (otherwise it is really just flourishes around text). The STATEMATE toolset does provide a textual language for describing behavioral aspects of programs so that direct implementation (into a third generation language) is unnecessary.

The question is, Why would you spend the effort to write something in a lower-level language when the same problem can be solved at a higher-level and then efficiently translated into the lower-level language? Direct implementation in a low-level language like C++ requires expert understanding of the C++ object model, and as demonstrated by Miro Samek in his two books on Statecharts it is easy to slip up and produce a solution with unnecessary overhead. Samek calls out various implementations for such overhead. When you are writing a real-time system, not having every bit of this implementation completely model-driven and controlled by compilation seems a bit silly. (Aside: Functional reactive programming language DSLs in Haskell are often translated into C or a C-like language before being compiled by gcc (or, more recently, clang).) Samek also enumerates a lot of common anti-patterns in implementing hierarchical state machines in software code, including such dealbreakers as corrupting events.

The real dealbreaker, though, is implementing history. You will not want to write software code that does transitions based upon previous system states, at least not code in a third generation language. (Although, in general, permitting such history is probably best separated out into its own object and access to history can then be handled through a clear collaboration between the journaling and navigation mechanisms for taking actions based on the history. In this way, you do not have any actions that include conditional checks, but instead simply encode the action behaviors into object state machine states.) When doing maintenance, then, it becomes much easier to understand the implications of modifying the system.

Harel, in his last book on statecharts [1], does a great job explaining this all. He contrasts models as prototypes versus doing design using model specifications.

As one last aside, I was recently reading an article on Gamasutra (or was it Gamedev.net?) about the conclusions of a bunch of Game AI experts from various fields of AI applied in game programming. One of the big shifts mentioned was the move away from writing C++ code (or even a scripting language like Lua) to describe hierarchical state machines. In fact, hierarchical state machines were not used at all, because they often encoded rigid abstractions about the problem domain. Instead, game AI folks are composing behavior abstractions bottom-up and forming trees of actions.

Many who have published papers that "refine Harel statecharts" are often really refining the abilities to basically hack C++ into the modeling language, which seems to destroy all the points I've raised above.

Bottom line: "refinement of Harel statecharts" smells a lot like an economist publishing a paper about "refinement of Nash equilibrium". I don't buy it, and question whether they're sane methodologically. These complicate system-under-development maintenance and also compiler design, because now your ad-hoc extension language needs to know how to safely integrate these sublanguage features.

Z-Bo, I dont see how this squares with "not good for implementation." I think quite the opposite.

Doubt we're far apart. Just thought I'd clarify and share some experience/knowledge.

[1] D. Harel and M. Politi, Modeling Reactive Systems with Statecharts: The STATEMATE Approach, (with M. Politi), McGraw-Hill, 1998.

indeed! i keep coming across Maude when searching about such topics. given the recent notes on LtU about Coq, i am really wishing i had the time and energy to teach myself a "real" programming environment.

I sense Maude is slowly gaining popularity - it's been many years in the making. The author finally has two books on the subject, Reflection in Rewriting Logic and All About Maude, and general purpose functional languages based on term rewriting systems are starting to become more popular (Q, Pure, etc...).

Maude's really all about metaprogramming, though.

I would greatly enjoy reading the wisdom of somebody who has had the time to compare/contrast such things as AADL, SPARKAda, SCADE, etc.; it seems like there are several possibly Good Ideas floating around out there, I wonder how they all overlap. (Go go google. Looks like there are folks who see AADL and SCADE as complementary cf. the ASSERT project search hit. According to another hit, SCADE is closed but well featured whereas AADL is open but young.)

You can get pretty far without these tools, simply by doing design well and using other tools.

On .NET, there is Cecil, Gendarme, CCI-Metadata, etc. that all help.

Model-driven really implies attention to the model at the architectural level. Most people who talk about architecture tend to cut corners and rather than think of things holistically, break them apart, decomposing the problem the wrong way.

Methodology matters.

a) because i'm not educated enough yet and b) because that sounds like a big problem. probably what i was thinking would only be possibly remotely useful for problems of a certain class: those amenable to simple proofs which manage to cover their state space, or those which are small enough that generate + test can cover them. but the wider, more general, less 100% coverage with proofs, approach of using modeling etc. is interesting to me to learn about.