[slevcom]

State machines are cool but they don't compose well out of the box. Behavior Graph let's you build a composable network of them so they become a practical software architecture. (Disclaimer, I am a coauthor) https://github.com/yahoo/bgjs

[tadfisher]

Hence the many mentions of statecharts in the linked document. A graph written using your library would translate trivially to a statechart.

[jayd16]

Why not? Don't they compose easily with sub-state-machines?

[slevcom]

Hi. Thanks for the reply. (Pardon my drawn out response. I can nerd out on this all day.)

I'm not aware of sub-state-machines as a standard concept. There are State Charts which are a superset of state machines and have their own notions of composition (XState is an implementation).

A sub-state-machine may feel like an intuitive concept but it does lead to a number of design decisions and related tradeoffs.

For example:

- We can have "State Machine A" influences "State Machine B". In order to make that happen there needs to be code in A that notifies B. Perhaps we do this with an explicit function call B. That's not too bad, but we are introducing a tight coupling between them.

- We can also have "State Machine A" influences a number of downstream state machines. Now we need many function calls or instead implement some observable or event protocol. That's also not too bad but its certainly not out of the box.

- Or we can have "State Machine A" and "State Machine B" both influence "State Machine C". In order to avoid updating C twice (glitches) we need some coordinating code that understand the dependency graph. I know from experience that is definitely not easy or obvious.

- And additionally we can address what it means for state machines to come and go over time which changes the dependency graph.

Behavior Graph is our implementation of those ideas in a slightly more general sense (we aren't restricted to _finite_ state machines and we have a generalized notion of events and observers).

I know talking about things this abstractly can make people's eye's glaze over so I won't belabor it too much, but that's what I mean by "don't compose easily out of the box".

[meheleventyone]

That’s interesting conceptually. Coming from a games background we don’t tend to think about the state machine as the primary element but wrap them inside other concepts. So an Entity might contain multiple state machines but communication and update is mediated by entities rather than between the state machines themselves. So I’m nodding along to the issues you raise but also feel like they get solved quite neatly with the game approach.

Sub-state machines or hierarchical state machines have been a thing in games for quite a long time. It’s a natural extension particularly for AI although IMO it’s mostly reducing a cognitive burden.

[michaelsbradley]

The folks behind the SCXML spec were trying to address some of those concerns, albeit in the abstract manner required of platform-independent spec authors:

https://www.w3.org/TR/scxml/

https://en.wikipedia.org/wiki/SCXML

Work on that goes back to the early 2000s, when XML was on the rise. One of the more important and lasting contributions of that work is likely Appendix D, "Algorithm for SCXML Interpretation":

https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation

I suggest ignoring the XML-specific aspects of it; consider that such tree-shaped data structures can as readily be encoded in JS objects (including stringified JSON). Also consider the larger spec's notions of `send` and `invoke` for "External communications":

https://www.w3.org/TR/scxml/#external-module

[tgv]

Sub-state machines have been around since at least 1970. They were used in NLP, where they were coined Augmented Transition Networks. Those were FSA with a stack (and variables), but when you don't do recursion, it's substituting an edge with another FSA.

Bad Wiki entry (because ATMs are really bad at parsing natural language), but at least it contains a reference: https://en.wikipedia.org/wiki/Augmented_transition_network

[arinlen]

> I'm not aware of sub-state-machines as a standard concept.

That just means you've never looked into it nor have much experience with state machines.

Sub-state machines are even supported as a basic features in some popular GUI frameworks such as Qt.

Qt in turn uses W3C's SCXML format[1] to represent state machines, which not only supports substates but also parallel states.

[1] https://www.w3.org/TR/scxml/

If anything, anyone with any experience writing any parser is already aware that the lexer represents a sub-state machine, and this is close to CS101.

[dqpb]

> I'm not aware of sub-state-machines as a standard concept.

Hierarchical State Machine.