HOPL-III: Statecharts in the Making

Another HOPL-III paper: Statecharts in the Making: A Personal Account by David Harel. This paper reads much different than most of the others, as the author admits to being mostly an accidental PL designer - backing into it from a mathematical perspective.

This paper is a highly personal and subjective account of how the language of statecharts came into being. The main novelty of the language is in being a fully executable visual formalism intended for capturing the behavior of complex real-world systems, and an interesting aspect of its history is that it illustrates the advantages of theoreticians venturing out into the trenches of the real world, "dirtying their hands" and working closely with the system's engineers. The story is told in a way that puts statecharts into perspective and discusses the role of the language in the emergence of broader concepts, such as visual formalisms in general, reactive systems, model-driven development, model executability and code generation.

The Statecharts language arose from the domain of avionics and real-time state modeling. The author's main goal was to turn what were visual doodles into executable models - finite-state-automata. Both UML and Rhapsody use parts of the Statecharts engine. The paper provides a good background for the subject of visual programming languages - a topic that periodically crops up on LtU. I found the emphasis on topology, as opposed to geometry, as the mathematical basis of visual programming to be of interest (though perhaps obvious to those who are more familiar with the subject):

When it comes to visuality, encapsulation and side-by-side adjacency are topological notions, just like edge connectivity, and are therefore worthy companions to edges in hierarchical extensions of graphs. Indeed, I believe that topology should be used first when designing a graphical language and only then one should move on to geometry. Topological features are a lot more fundamental than geometric ones, in that topology is a more basic branch of mathematics than geometry in terms of symmetries and mappings. One thing being inside another is more basic than it being smaller or larger than the other, or than one being a rectangle and the other a circle. Being connected to something is more basic than being green or yellow or being drawn with a thick line or with a thin line. I think the brain understands topological features given visually much better than it grasps geometrical ones. The mind can see easily and immediately whether things are connected or not, whether one thing encompasses another, or intersects it, etc.

Provides a nice refutation for the recent brouhaha of those who think math is irrelevant for process modeling - a solid mathematical foundation is even more critical for languages that concentrate on expression in unique fashions.
(Previous LtU links to HOPL-III papers)

Comment viewing options

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

[OT] "math is irrelevant"

I think most of the "brouhaha" over the "math is irrelevant" story can be attributed to two things:

  1. A journalist who didn't really understand what Karl Fant was getting at, and produced a sensationalized article that wasn't really representative of Fant's intentions
  2. A bunch of slashdotters who either didn't read the article, or weren't able to see through the journalistic sensationalism to Fant's actual point

My reading of the article (as well as a skim of the table of contents from Fant's book) is that Fant is not trying to claim that math itself is irrelevant. Rather, I think he's claiming that the notion of algorithms is something fundamentally aimed at representing and solving problems in mathematics (that is, after all what Turing developed the TM for), and that the broader field of computer science needs a different kind of model. This is hardly a revolutionary idea: the pi-calculus and other process algebras are fundamentally non-algorithmic, since they deal with processes that alter their behavior in response to inputs received during a "computation"; Peter Wegner has been writing about "interactive computation" and moving beyond the Turing model for years; Petri nets and the Actors model provide yet other mathematical representations of non-algorithmic computations. Moving beyond or away from algorithms doesn't mean abandoning mathematics as a tool of computer science. It does mean choosing mathematical tools that reflect the goals of computer science, rather than those that reflect the goals of mathematics.

Easy to misinterpret

The first chapter of the Fant's book is online: A Critical Review of the Notion of the Algorithm in Computer Science. Although the journalist somewhat overstated the case, I think that just because mathematics are computer science are separate disciplines, does not mean that maths can not be used for process modeling. Rather, I think that we need to search for is the correct mathematical language on which to stake our ground. As the examples you provide, and the Statecharts language show, the question is one of which mathematical model/notation you choose to utilize.

Unfortunately, the argument in many places that I've seen has been concerning class hierarchies amongst programmers, which is an even worse interpretation.

"Invocation Model"

My impression (although it's hard to find any details) is that Fant's "Invocation Model" is yet another mathematical way of representing interactive processes. What I find disappointing is that he's (a) doing a rather poor job of explaining what he's doing, and (b) I have yet to see him make any acknowledgment of any of the other work that's been done in this area (by Petri, Milner, Hoare, Wegner, Cardelli, Hewitt, Clinger, Parrow, Sangiorgi, Roscoe, Bergstra, Klop, and many, many others). The result is lots of stories in the popular press (like this one) that talk about "mathematics not being an appropriate conceptual foundation for CS", which is (IMHO) a blatantly false assertion, and no mention of the fact that these "revolutionary" ideas are in fact the direction the CS has been headed in since about the time Petri published his PhD dissertation.

[OT cont.] Fant's reputation / patent connection?

I know nothing about this Fant fellow, so I'm curious if anyone else has a sense of his background/reputation. The reason I ask is that one of the slashdotters (Nick Fortune) raised an issue that I would never have dreamed of in this context, namely of positioning the debate over software patents (see his comment here). Perhaps it's a bit paranoid or cynical to think this way but, then again, maybe it's merely naïve not to.

My Google search on Fant's full name yields as its top hit a biographical page at Theseus Research with a list of patents (relating to "NULL convention logic") prominently displayed ... but perhaps that's the same search Mr. Fortune did, and whence his cynicism.

So does anyone know independently of Mr. Fant's reputation?

Just slightly more on-topic, I hope this sort of thing never intrudes too much into PL design ("Well, we can't use the obvious pineapple upside-down continuation semantics for this language feature until the patent expires in 2037, so let's just leave it out for now.").

Wandering back on topic?

Of all things PL design, visual languages and tools are seemingly the most apt to be captured (for example, Mathematica and UML). And relating this back to Harel's article and his motivation for going commercial with Statecharts:

In a discussion with Amir Pnueli in late 1983, we decided to take on a joint PhD student and build a tool to support statecharts and their execution. Amir was, and still is, a dear colleague at the Weizmann Institute and had also been my MSc thesis supervisor 8-9 years earlier. Then, at some point, a friend of ours said something like, "Oh fine, you guys will build your tool in your academic setting, and you'll probably write some nice academic papers about it." And then he added, "You see, if this statechart stuff is just another idea, then whatever you do will not make much difference anyway, but if it has the potential of becoming useful in the real world then someone else is going to build a commercial tool around it; they will be the ones who get the credit, they will make the money and the impact, and you guys will be left behind".

[OT] Relevancy of Mathematics

The "irrelevancy" of mathematics is nothing new; the idea comes up over and over again. It would be laughable if not for the weight it carries with some.

One complicating fact is that, honestly, educators do a terrible job at connecting mathematics and computer science. The gulf left behind is just too big for most people to bridge themselves.

Another problem is the selection of required topics for a typical Bachelor's Degree in CS. Typically it's Calc 1, Calc 2, a semester of discrete, and maybe another semester of Calculus. Calculus is not terribly useful to most programmers, unless they happen to be programming something involving Physics, Geometry, or symbolic or numerical calculus. Calculus is sometimes useful for analyzing algorithmic complexity.

What many people don't realize is that learning to program is learning how to do mathematics, just in a rather different way than mathematics is traditionally taught, and typically covering different topics than the traditional curriculum.

So, what topics in

So, what topics in mathematics do you think SHOULD be studied by cs students?

I suggest moving this

I suggest moving this discussion to a new thread (or to one of the many places where these issues were discussed before).

Obviously formal logic is a must

Obviously formal logic is a must. Programming is applied logic. Discrete math is definitely a good one that is usually taught.
Abstract algebra is another very good one to have. Order/lattice theory would be good too. Oddly, complex analysis (which requires a good chunk of calculus) is a very good one too for many problems and also linear algebra. (Or kill 10 birds with one stone and learn the geometric calculus.) Topology is useful but it tends to be less obvious (or, alternately, more theoretical).

I would say the first four will directly and immediately improve every coder's understanding of computer science and be useful in programming with the right tools. The later ones are more specialized (but not that specialized) and/or (usually) more theoretical i.e. very good to know, but "day-to-day" type of concerns. They are things that are surprisingly widely applicable.

Some may note that I haven't listed category theory. I would certainly recommend it as a way to approach many of the above listed topics, but "pure" category theory is either not as relevant or can be covered by the others in a patchwork way. (That said, the categorical notion of (co)continuity is amazingly powerful. Thorsten Altenkirch's paper Representations of first order function types as terminal coalgebras pretty much reduces to the well-known continuity properties of adjoints and a few other minor and easy results in category theory.)

I say that often

What many people don't realize is that learning to program is learning how to do mathematics, just in a rather different way than mathematics is traditionally taught, and typically covering different topics than the traditional curriculum.

I repeat this often: to program is to do mathematics. Unfortunately this point is not usually made during the education of programmers.

Topology and programming

Harel's point about topology brings to mind Milner's (and others) work on the use of "bigraphs" to provide a fundamental basis for understanding concurrency. See here or here for examples of applying bigraphs to mobile processes Petri nets. See here for information on programming languages founded on bigraphs.

Relation to Statecharts

The first link from Milner contrasts Bigraphs to Statecharts.

A very different application from ours, but still in concurrency, is Harel’s statecharts. A statechart is a generalisation of the transition diagram of an automaton, in which the states have hierarchical structure, represented by the regions of the chart. The difference from bigraphs is fundamental: a bigraph represents a single distributed state, while a statechart represents the dynamic behaviour of a whole system.


Thanks for the quoted contrast - I'd forgotten that was in the paper. What's interesting to me is that several different researchers seem to be looking at topology as a basis for understanding computation (albeit in different ways). That's something I was quite surprised to see, when I first came across it. Perhaps because I was used to thinking of computation algorithmically, and hadn't considered how other mathematical tools might apply :-)

The final example in section

The final example in section 3 is hilarious.

A good candidate...

...for a final exam question. Figure out what happens when you push the button given that specification. :-)

With the correct answer

With the correct answer being "Who the heck knows!?"