seeking help: approaches to model based development?

Assuming that one cause of software problems is insufficient coverage of the state space (so data goes into some range that causes the program to run in an unexpected and bad way), I wonder if one could approach that issue by trying to deal with the state space more explicitly: start with a null program and iteratively break it down and define its behaviour over the full state space, all the while proving that it is correct, eventually reaching a "full" program. (Perhaps only for restricted problem domains.)

What are the current best languages/tools/practices along those lines? In my head I have some image of a 'star trek'y interface, perhaps vaguely akin to the Subtext GUI, which allows the developer to 'see' how they are progressing in decomposing things. I realize visual approaches might well have issues as the decomposition gets ever more branching.


(I am actively reading up on things like Spin, MBSE, SPARKAda, etc. but have no practical experience with any such thing, so remain skeptical and clueless even after reading up on things.)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


I haven't ever used Epigram, only lurked on the mailing list, but I get the impression that the interactivity of it helps construct correct programs. Not very graphically, but still perhaps along the lines of the nebulous thought/question I had.

Hierarchical StateCharts

Hierarchical StateCharts (Harel) are a fine approach to the design and implementation (though automatic code generation) of small systems, e.g., user interfaces for embedded devices. I'm not sure if this is the kind of state decomposition you had in mind, but it is certainly one way to handle it.

Though some tools exist, it would be wonderful to have improved validation tools for Hierarchical State Charts.


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.

not good for implementation?

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.

Execution versus implementation

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 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.


related to the visual nature of the state charts: i wish i could afford SCADE Suite.

Maude and MOVA


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

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.


and ilk

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

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.


For about MIT's analyzer, Alloy, developer by Daniel Jackson (and others).

I wonder if one could

I wonder if one could approach that issue by trying to deal with the state space more explicitly: start with a null program and iteratively break it down and define its behaviour over the full state space, all the while proving that it is correct, eventually reaching a "full" program.

I'm not sure what you mean by "state space" here? Lets say your input space is the set of all strings and your output space is the set of all valid Java programs in byte-code format. The function that shall be verified is the Java compiler. Can you clarify your terminology using this example and how model checking is intended to help?

probably not

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.

While hardly bleeding edge

Inform 7 is quite inspiring as modeling languages go.