Statechart Programming Languages

2025-01-2

Jan 22, 2025

In reference to an earlier article and my reading of Harel’s Statecharts paper[1], I was asked for further references on how to learn more about Statecharts and state-machine based programming.

I’ve always rolled my own version of these things, so I don’t have direct exposure to other languages or learning tools.

I asked an LLM and I’ve included the responses below.

In my mind there are several key factors to effective use of Statecharts in programming:

The need to use state diagrams. You can simply draw diagrams on paper then transpile them to code, or, you can compile the diagrams to code using something like draw.io[2] and t2t[3].

Popular programming languages, like Python, Rust, etc. are sequential programming languages and, thus, are the antithesis of state-based programming. Functional programming languages do not allow for multiple inputs and outputs that arrive spread over time. The notation used for such functional languages - text - discourages the very idea of having inputs and outputs spread over time, hence, discourages state-based thinking. If you insist on using Functional Programming to program calculator-like solutions, then it behooves you to eschew state, but, ignoring state is not such a good idea for a vast number of non-calculator problems. In general, computers that use CPUs have state, mutate state and have control flow. CPUs are meant to be bolted to RAM and to mutate that RAM.
Text-based notation does not easily handle the notion of multiple input/output ports. You need to deal with multiple input/output ports to effectively use Statecharts and state-machines. For example, UNIX has always had the concept of multiple ports (called FDs), but, the text-based nature of the Bourne Shell (sh, and successor like csh, bash, zsh, etc.) makes it unpleasant to use anything but stdin, stdout, and stderr. Consequently, we don’t see code that makes more elaborate use of those other ports. What’s actually needed is a Visual Shell that allows multi-branch pipelines (see the VSH example of 0D[4]).
It should be noted that internet-based clients and servers are itching to act like orthogonal state machines, but can’t due to a lack of programming languages more suited to this kind of programming.

Parental Authority[5]. Statecharts use something that looks like inheritance, but, is exactly opposite to inheritance. Child states must obey a parent state’s state transitions - children cannot override the operation of parents. Most popular languages provide the notion of classes based on inheritance which allows overriding of inherited methods. This simple difference discourages the use of the kind of anti-inheritance that I dub “parental authority”. Parauth (“parental authority”) is extremely useful for managing control flow, but, class-based inheritance muddies the concept and makes it hard to learn and to reason about. We see examples of parauth at work in windowing / GUI systems: the outer-most window gets first dibs on an incoming event (like mouse movement). If the outer-most window processes the event, the event does not trickle down to any child windows. Child windows get to deal with the event only if the outer-most window declines to do anything with the event. This process is recursive. Yes, one can implement this kind of trickle-down event-flow using popular, sequential programming languages, but you have to work harder to do so, whereas the concept is built right into Statecharts.
Orthogonal States. In Statecharts, “orthogonal states” are essentially separate threads, each running one independent state machine. It is difficult to get the same effects using only one thread and using sequential programming languages. It’s not impossible, but, it is more difficult. The idea behind Statecharts is to make one slice of programming easier to manage. Statecharts are best at dealing with complex control flows, e.g. machine control, internet, IoT, mouse handling, etc. where there might be multiple happy paths instead of the functional approach wherein just one path is the chosen “right way” and all other possibilities are deemed “exceptions”. We’ve let the concept of orthogonality wither because of our over-emphasis on only the functional programming paradigm. We see a resurgence of this concept in ideas like coroutines and green threads. The best approach to solving state-based problems, using what we’ve got, is to spawn separate threads each containing one state machine and allowing them to free-run. Once such a problem has been solved and solution settled upon, the code can be optimized. This approach works much faster than trying to solve similar problems using only sequential programming languages. The idea of using sequential programming languages to solve reactive problems - like mouse handling - has generated a plethora of complicated frameworks containing lots of quirks and gotchas.

I learned about state machines before I learned about programming.

In electronics, everything starts out as being parallel and asynchronous. State machines make instantaneous sense coming from that angle.

In software, though, everything starts out as being synchronous and, essentially single-threaded (despite the fact that programming languages claim to support multi-tasking). This make state machines hard to implement and hard to comprehend.

Historically, the big problem with state machines was the “state explosion” problem. Harel’s Statecharts fix that problem, as does my 0D[4] stuff. I think that we are seeing a different kind of “state explosion” due to functional thinking, but, the problem hasn’t yet been satisfactorily solved - we are only nipping away at the edges of the software-bloat explosion problem with concepts like imports, namespaces, await, etc.

My chat with Claude 3.5 follows...

Question 1

Are there any programming languages based mostly on statecharts and state machines?

Yes, there are several languages and frameworks that are centered around state machines and statecharts. Some notable examples:

SCXML (State Chart XML) - While not a standalone programming language, it's a W3C standard for describing statecharts that can be used to generate code in various languages. It's particularly useful for user interface and workflow modeling.

Esterel - A synchronous programming language specifically designed for complex reactive systems. It uses a state-machine based approach and is particularly popular in safety-critical systems like aviation software.

StateML - A domain-specific language focused on state machine programming. It provides a more natural way to express state transitions and behaviors compared to traditional imperative programming.

Argos - A visual synchronous programming language based on hierarchical state machines. It's similar to Esterel but with a stronger focus on visual programming concepts.

I should mention that while these exist, most developers tend to use state machine libraries or frameworks within mainstream programming languages rather than dedicated state machine languages. For example:

- XState in JavaScript

- Akka in Scala

- Spring State Machine in Java

- Boost.MSM (Meta State Machine) in C++

Would you like me to elaborate on any of these in particular? I'd be happy to share more details about their specific approaches to state machine programming.

Question 2

Harel's Statecharts specify a concept called "orthogonal states". In essence each orthogonal state machine is a separate thread. Which of the above languages makes orthogonal states independent from other states?

Looking at the languages I mentioned, Esterel and SCXML directly support Harel's concept of orthogonal states and treat them as independent parallel/concurrent regions:

Esterel was actually developed around the same time as Harel's Statecharts (1980s) and explicitly implements orthogonal states as concurrent threads. Each orthogonal component runs independently and can communicate through signals, staying true to Harel's original vision.

SCXML implements orthogonal states through its <parallel> element, where each child state machine runs independently. These really are separate threads of execution that can evolve independently.

However, I need to correct my earlier response about some of the others:

StateML and Argos, while state-machine based, don't fully implement true orthogonal states in the Harel sense. They have parallel state constructs but don't guarantee the independence of execution that Harel specified.

There's also an interesting language I should have mentioned initially: Rhapsody, which was actually co-developed by Harel himself. It directly implements the Statecharts formalism including true orthogonal states as independent threads.

Would you like me to go into more detail about how any of these languages specifically implement orthogonal states? I find the different approaches to concurrent execution particularly interesting.

Question 3

Harel's Statecharts implement control flow structuring that is the opposite to method inheritance in class-based languages. Which of the above languages encapsulate control flow as per Statecharts?

This is a fascinating aspect of Statecharts - their hierarchical structuring through containment and refinement is indeed the inverse of class inheritance. In Statecharts, the "super-state" contains and controls its substates, whereas in OOP the subclass inherits and can override its superclass behavior.

Looking at the languages I mentioned:

SCXML implements this containment-based hierarchy correctly. Higher-level states contain and control the behavior of their substates, and transitions at higher levels can interrupt and override lower-level behavior - exactly as Harel specified. The <state> elements can be nested to create this hierarchical control structure.

Esterel also follows this pattern through its module system and hierarchical state composition. When a higher-level state interrupts, it properly preempts all contained substates, maintaining the correct hierarchical control flow.

Rhapsody, being co-developed by Harel, naturally implements this hierarchical containment model faithfully.

I need to correct my earlier statements about StateML and Argos though - while they have hierarchical states, they don't fully implement the control flow structuring that Harel specified. They tend to mix OOP-style inheritance with state containment in ways that don't strictly follow the Statecharts formalism.

The key distinction is that in true Statechart implementations, the container state has complete control over its substates, including the ability to interrupt them at any point. This is different from OOP where subclasses have the final say in overriding behavior. Would you like me to elaborate on any specific aspects of this containment-based control structure?

Conclusion

I’ve essentially stopped needing to use Statecharts, because as Zac Nowicki pointed out, 0D[4] provides intuitive management of control flow and data flow differently from Statecharts, while continuing to succinctly handle the same kinds of problems.

In 0D, Choreographer parts (previously called “Containers”) allow one to nest parts in ways that are similar to Statecharts. Mevent sending (previously called “message sending”) allows one to build simple software little-networks with orthogonality, and, without using full-blown operating system processes and threads. Thus far, every problem I’ve faced was naturally solved using 0D notation without even thinking about Statecharts.

Statecharts did, though, influence the design of 0D, especially in showing that it was possible to use diagrams to program electronic computers, instead of using only synchronous programming languages.