Ways to fix Statecharts composablility

[rekreanto]

Programming with Statecharts is awesome; they bring a logical visualizable structure to reactive software such as UI, reducing technical debt and enabling performing changes and extensions with confidence. But, awesome as they are, they do not compose: You can not build a big statechart from smaller component Statecharts without introducing extra plumbing with additional complexity in the form of agents or similar.

Imagine how much more powerful Vue or React are thanks to the fact that you can compose your app out of components. Now extrapolate this to Statecharts. How awesome would Statecharts be if they were composable? Imagine the libraries you would build: Maybe all your favorite UI abstractions ready to be composed into whatever app is on today's agenda. Maybe we would build stuff that we today consider inconceivable? Maybe we could make UX experimentation so much closer to the metal? etc. etc. What would you build assuming composable statecharts?

I find it jarring that Harel's Statecharts looks rather mathematical, but are yet non-compositional. So I put some thought into why. Here are some ideas that I arrived at. They might be all wrong though, and I would be delighted to hear your take on this topic!

Which features are to blame for the non-composablity of statecharts?

Is this lack of composability inherent in the nature of Statecharts? If not; which features do compose and which can we pinpoint as culprits and fix?

Here is my list:

Feature        Composable
===========================

Atomic States     yes
Or-sates          yes
And-states        yes

Extended State    NO
Broadcast         NO
History           NO

My impression is that the first three features are natural mathematical primitives and combinators, while the last three are more of ad-hoc solutions that does their work, but yet lacks the mathematical naturalness/simplicity of the former three. The essential reason why the last three does not compose, seems to be that they are global in their nature: Global stuff do not compose, since its parts collide.

Now let's look at each of the culprit features:

Redesigning External state for Composability

The problem with External state is that it is global per state machine, so let's just remove it and in stead introduce unified state: Unified state is in essence an Algebraic Data Type (ADT) (a data structure you can build using values, or-combinators, and and-combinators). ADT:s has been in programming languages since a decade before the introduction of Statecharts, so it's nothing new or strange; just mount the external state (the values) at the fringes of the control state. (This will also get rid of the need for null values). Now that state is unified, transactions will also have to be unified or generalized: They will have to combine the case analyses of classic statecharts with the function application of classic programming.

Redesigning Broadcast for Composability

The problem with Broadcast is that it is global per state machine, so let's just remove it and in stead introduce transaction bubbling: A transaction can be bound to an event in any substate and must be declared in its ground state (often called scope), i.e. the closest state that does not change as a result of the transaction. This is related to event bubbling as in e.g. js or Vue; just let the event pass up to parent components until a match is found. In this model, there is no way for a branch state to communicate directly with another branch state; it must in stead invoke a transaction of a common parent.

Redesigning History for Composability

The problem with History is that it is global per state machine, so let's just remove it and in stead introduce declarations at the enclosing state, that we can call the scope. Then we have solved another problem as well: History is cleared automatically as soon as the scope is exited.

---

This post was copied from the old spectrum.chat forum with some slight modifications.

[brucou]

I like your thinking though I do not necessarily with your arguments. Composability in statecharts is a feature that have actually been researched for some time. I added a paper that talks a bit about the subject. Let me see if I find the link. There: #9

This explains how you can build statecharts from smaller statecharts without loosing composability and without changing the semantics of statecharts. But you got it right. At core sharing state is an impediment to modularity. And the state of a state machine is {extended state, history state, control state} in the absence of parallel machines. With parallel machines the state become an array of the state of each parallel machine AND the broadcast state (that impacts microsteps and macrosteps execution). So as you mentioned, any of these things makes it harder to modularize. So in general statecharts are not composable, and I don't think that can be changed IN GENERAL.

If you want C to be composed of A and B, with A and B independent standalone entities, then they can't be sharing anything with C. This is a problem that many React developers face whether they are aware of it or not, but once a component use Context, it stops being composable -> you can't reuse it anymore without carrying the context with you.

But true composability can be achieved around the lines of what the paper recommends:

• no transitions going inside sub machines
• no transitions from the inside of sub machines to outside
• no reading or update of state external to the sub machine
• rather than coordinating through shared state, coordination happen through events
• etc. see the paper

Now you can get a bit closer with other techniques but none is perfect. Similar to what you recommend with ADT, you can use lenses to peak into the global extended state, and associate any statechart component with its own lense that can thus only see and modify the accessible portion of the global extended state. Imagine a big machine that composes a routing machine and several pages machines. Each page modify its own state independently, but at some point they may need to modify the routing state of the big machine. Each page has its own state inside the state of the big machine, and read/update it through lenses provided by the big machine. That is modular. But at some point they may need to modify state that is external to them, like the routing state and transition outside the page to another page that they cannot know in advance. To modify state external to them they need to have prior knowledge of their environment. That breaks modularity. Same goes for the transition to another page. Pages are then no longer standalone pieces, they are no longer independent modules.

[rekreanto]

Thanks for the explication! I agree with the points you make and appreciate the example you use. They were helpful in my effort to understand more about composability.

[ EDIT: removed rest of my comments, as they likely are of little general interest. For the interested, they are accessible using the history function, and can be summarized: "I'm not convinced of the relevance of OO-paradigmatic research to fundamental Statecharts principles." ]

[brucou]

Sure. You can do your own research, formalize your ideas in a paper or any other suitable form and have it peer-reviewed by the community you are interested in. I do recommend you though to read the paper I quoted and understand the ideas exposed in it, because they are bound to be useful for your own endeavour.

[rekreanto]

You can do your own research, formalize your ideas in a paper ...

@brucou I'm no position to do any of that. Just sharing my thoughts based on my efforts to learn Statechart fundamentals in the hope of getting interesting and helpful input (I got a lot of that in the forum and very thankful for that). This time I might have just wasted peoples time. Sorry if that's the case; not my intention. Always thankful for your feedback and helpful comments!

[brucou]

I don't consider my time wasted, so don't worry. Questions and answers, trial and errors, thinking and investigating, this is how we learn. Even if all the paths do not lead somewhere, you still learn.

[mogsie]

I appreciate the effort you put into this. Personally I haven't seen a great need to have composable, reusable statecharts; I think maybe because of the problems you mention make it hard to really have a clean interface, and makes me shy away from considering it being an option. Instead of trying to compose a statechart of more statecharts, I think I would have a strict contract between the different statecharts that was based entirely on the external contract of the statechart, e.g.:

• the events it consumes
• the guards it can call out to
• the actions it performs

You could, perhaps, declare that you have two machines, X and Y, that have the same interface (events, guards, actions), but have different behaviour. A third machine might be able to make use of X or Y interchangeably, communicating with it by passing events to it, and performing any actions it does. An action from this X or Y machine might then be treated as an event in the parent "third" machine.

This is almost the same as regular component composition, whereby you have e.g. a button that has a good internal behaviour because it's defined by a statechart, but it only exposes its public API consisting of events, guards, actions etc. When that button is included in a larger component (e.g. a form)—it too is governed by a statechart, so it too is well-functioning. But the statecharts don't need to know about each other.