[diggan]

For you who enjoying using state machines but wish they did even more and/or were embedded in each other (nested state machines!), check out this thing called State Charts!

Here is the initial paper from David Harel: STATECHARTS: A VISUAL FORMALISM FOR COMPLEX SYSTEMS (1987) - https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res...

Website with lots of info and resources: https://statecharts.github.io/

And finally a very well made JS library by David Khourshid that gives you lots of power leveraging statecharts: https://github.com/davidkpiano

While we're at it, here are some links to previous submissions on HN regarding statecharts with lots of useful and interesting information/experiences:

- https://news.ycombinator.com/item?id=18483704

- https://news.ycombinator.com/item?id=15835005

- https://news.ycombinator.com/item?id=21867990

- https://news.ycombinator.com/item?id=16606379

- https://news.ycombinator.com/item?id=22093176

My own interest in Statecharts comes from wanting/trying to use them for UI development on the web, think there is lots of value to be had and time to be saved by using leveraging it.

[RossBencina]

To these links I would also add Miro Samek's book "Practical UML Statecharts in C/C++," which covers details of implementing (hierarchical) statecharts. The book includes a chapter that analyses different ways of encoding extended state machines (Miro concludes a function pointer, with one event handler function per state is the best for C/C++. I don't think this is the encoding that the linked Rust article uses). A simple algorithm for implementing HSMs is described. A large portion of the book is devoted to what you might call "UML Statecharts -- The Good Parts," the parts of the UML statecharts spec that are easy to implement in a real-time setting, and idioms/patterns to achieve similar results as the parts of the spec that are not easy to implement.

Some of Miro's online writings:

https://barrgroup.com/embedded-systems/how-to/state-machines... https://barrgroup.com/embedded-systems/how-to/introduction-h...

https://www.drdobbs.com/who-moved-my-state/184401643

[Edit: clarity]

[bobbiechen]

Thanks for the links!

State machines are pretty cool - I took a digital systems class and found that the concept is straightforward and with a little practice defining states and transitions gets a lot easier. Then implementing a finite state machine (+datapath) with something like SystemVerilog is extremely straightforward.

If statechart libraries can help you define what these states are and how data is used, that would be amazing - basically making the whole thing declarative and much less prone to programming error. Google's Paxos Made Live paper [1], on the engineering challenges of actually implementing Paxos, actually attests to this value in section 6.1:

Fault-tolerant algorithms are notoriously hard to express correctly, even as pseudo-code. [...]

We addressed this problem by coding the core algorithm as two explicit state machines. For that purpose,we designed a simple state machine specification language and built a compiler to translate such specifications into C++.

[...]

We believe that choosing a specification language makes it easier to reason about and modify our state machines than an explicitly coded implementation that is intermingled with the rest of the system. This is illustrated by the following experience.

Towards the end of our development of the fault-tolerant log, we had to make a fundamental change in our group membership algorithm. Prior to this change, a replica roughly went through three states. [...but] Intermittent failure turned out to be more common than originally anticipated because normal replicas exhibit intermittent failures from time to time.

Thus, we needed to change the algorithm to have two states. Either a replica was in the group or it was out. A replica could switch between these two states often during the lifetime of the system. It took us about one hour to make this change and three days to modify our tests accordingly. Had we intermingled our state machines with the rest of the system, this change would have been more difficult to make.

[1] http://static.googleusercontent.com/media/research.google.co...

[cstrahan]

For more on statecharts, check out Ragel: http://www.colm.net/open-source/ragel/

> Ragel compiles executable finite state machines from regular languages. Ragel targets C, C++ and ASM. Ragel state machines can not only recognize byte sequences as regular expression machines do, but can also execute code at arbitrary points in the recognition of a regular language. Code embedding is done using inline operators that do not disrupt the regular language syntax.

http://web.archive.org/web/20170718234646/https://zedshaw.co...

RubyConf 2015 - Stately State Machines with Ragel by Ian Duggan: https://www.youtube.com/watch?v=Tr83XxNRg3k

[jononor]

Anyone have a good reference for using Ragel for non-parser tasks? I do a lot of embedded in C and am used to model FSMs for modelling processes, though I still hand-code all of them, which is tedious...

Even invented my own DSL and compiler a while back, but never really had the time to get it good enough to be useful.

[wahern]

Source code is closed source and at an old employer, unfortunately, but I once used Ragel to write a non-blocking MySQL client library using the regular expression features for packet parsing and, separately, a state chart for query and session state--basically, which type(s) of packet to expect next and otherwise documenting how session states transitioned.

If I had to do it again[1] I might not use Ragel for either packet parsing or session state. The MySQL wire protocol is rather simple, and Ragel has a steep learning curve, which made hacking on the library unnecessarily difficult for others. At the time I was already knee-deep in Ragel for other stuff, so it was the path of least resistance for me. But for more complex state management I would definitely return to Ragel as the expressive syntax is worth all the documentation and commentary in the world. And because of how well Ragel supports embedded code blocks (including for non-blocking/asynchronous I/O designs), you can maintain proximity between critical code and the state chart directives, which improves both expressiveness and self-documentation. That's the real power of Ragel--it's source code-level interfaces. On the surface the interface seems a little clunky (no interoperability at code AST level), but in practice it's second to none.

[1] Of course, the second time around you already know the pain points and contours of the problem so it's much simpler to open-code an elegant, minimal solution. So it's not much of a comment on Ragel to say that I wouldn't do it again.

[rwmj]

Based on the idea of statecharts, we generate a C library that implements a particular complex network protocol: https://github.com/libguestfs/libnbd/tree/master/generator All the files called state* are involved, but the hierarchical state machine is described in this one: https://github.com/libguestfs/libnbd/blob/master/generator/s...

[taneq]

> (nested state machines!)

Also known as hierarchical state machines. (web searches) Oh, which are also called state charts. So yes, those!

[mwcampbell]

Your mention of statecharts reminds me of Ragel [1], which Zed Shaw used when implementing the HTTP parser in Mongrel. I wonder if something similar could be done with Rust macros.

[1]: https://www.colm.net/open-source/ragel/

[rumanator]

> For you who enjoying using state machines but wish they did even more and/or were embedded in each other (nested state machines!), check out this thing called State Charts!

I'm surprised no one mentioned this yet, but At has first class support for state charts and state machines in Qt's state machines framework.

https://doc.qt.io/qt-5/statemachine-api.html

[imtringued]

I just saw this page https://statecharts.github.io/faq/an-event-always-has-one-ac...

>Because if you think harder about it, an event will usually have some deviation from doing that action. Most buttons are clickable, and when you click it, then you perform the action. However, some users doubleclick most buttons, and in those cases, rarely do you want to repeat that action.

This type of event duplication has been the source of glitches in pretty much every html5 based game. What happens is that there is a dialogue with an onclick handler and triggering the handler causes the dialog to close with an animation. If you click the dialogue again before it closes it will execute the onclick handler again. This lets you duplicate quest rewards in a lot of RPGs.

[mhd]

Another formalism that's quite interesting is Petri Nets[1] (of which exist several variations, colored, hierarchical etc.).

Just, please, don't implement them in Oracle stored procedures.

[1]: https://en.wikipedia.org/wiki/Petri_net

[gentleman11]

What exactly do the libraries provide? When I use state machines, if it’s small, a switch is all you need; and if large, the State pattern is great. Ie, what am I missing out on?

The main challenge for me is when a given state comes with a “Tick” method that gets invoked via current_state.Tick() - Eg, in an update method in Unity. This makes them a tiny bit more hairy to work with, and I am not certain what the best practice is to keep this very simple.

I know bob martin has a video course on creating a custom compiler to generate state machines from tables. That seems neat too

[mntmoss]

In the end they're all situational formalisms. Imperative code is by definition implementing a state machine.

One thing that you can often get by moving the state machine a bit away from the source code as tends to be the case with these libraries is a definition that specifies I/O more concretely. In something like the Unity3D Tick() case, I/O is open-ended: All game state is available, and that state may itself impact when Tick() is called via various concerns of concurrency(timing, update order, etc.). When trying to apply a formal model it's usually a really bad sign to see a very broad "tick" or "update" callback dumped into execution - it leads towards hacky code that sets flags and uses frame boundaries to confirm events.

Game engines don't always have the best examples of these patterns, since games can so often get away with shoddy usage.

[gentleman11]

It’s tricky because the alternative is a bunch of switch statements that just check state == sitToStand or state == FooInProgress every frame, which just moves the logic away from the state itself. Ie, the different behaviours are not just on transitions.