State Machines in Rust | Hacker News Reader

State Machines in Rust

blog.yoshuawuyts.com

297 pointsbambambazooka112 comments

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.

> (nested state machines!)

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

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...

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/

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

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.

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.

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...

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

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

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.

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.

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]

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.

> 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

In my experience, state machines are very nice in theory, but in practice, over time, they devolve into a mess of spaghetti code.

Because they are not in a single scope, loops become the equivalent of a bunch of gotos and managing lifetimes and locks becomes a problem because you can't use scope based mechanisms such as RAII.

In Rust, if you want a state machine, generators are probably the long term way to go.

https://doc.rust-lang.org/nightly/unstable-book/language-fea...

By using generators, the compiler will generate the state machine for you based on your code, and you can use structured loops and scope based cleanup.

State machines really shine in networking protocols where a state machine is part of the spec. I do agree though that when used in applications where it isn’t abundantly clear what the state machine is, or what that state machine is evolving over time that it isn’t the best abstraction.

Resource managing is not a problem with state machines. Quite the opposite: you should acquire/free resources in well defined states of the machine (typically the different entry/exit points).

Generators are great for tasks that fit well but in the general case state machines are more powerful and easier to debug.

I agree that if your state machine starts evolving without control then it will be a mess (like any design).

> Because they are not in a single scope

That all depends on the tool. Despite being cross-language (or rather, because of it), Ragel's source code-level interfaces don't require indirection through callbacks or function pointers. Ragel has a rich set of operators for embedding code blocks at transition points, operators for embedding expressions to control transitions, and operators for controlling how Ragel saves/restores state. You can organize your code nearly as freely as when open-coding a solution--a million little functions, a single gigantic function, or something in between.

The problem with many tools that are tightly integrated with a language--such as in-language AST manipulation, or via lambadas or closures--is that they're constrained by the expressiveness of the host language. You can see this with Lisp macros--you can trivially hack the s-expression tree to implement incredible semantic changes, but if the problem isn't best described using simple function (and specifically s-expression) syntax, then good luck identifying the semantics on inspection or understanding the implementation.

Hand-coding state machines approximates hand-coding continuation passing style (CPS) transformation.

Generators are essentially similar to automatic CPS transformation.

I've had exactly the opposite experience -- I've found state machines to be "spaghetti code reducers" -- no longer checking a "bag of flags" to decide how to respond to the event.

For example, the "up" volume button on your phone could mean ringer adjust, MP3 playback volume adjust, take a photo, increase screen brightness, etc. In other words, it depends on what the phone is doing, i.e. its state.

Otherwise, code becomes "if (in_call == true) { adjust_volume(); } else if (camera_mode == true) { take_photo(); } else if ...

Just my 2 cents...

C++20 supports enums as non-type template parameters, so I think it'd be possible to do it with enums there. Something like:

    enum class Color{Green, Yellow, Red};

    template<Color C>
    struct State{};

    auto newState() -> State<Color::Green>  {...};

    auto next(State<Color::Green>) -> State<Color::Yellow> {...}

    auto next(State<Color::Yellow>) -> State<Color::Red> {...}

    auto next(State<Color::Red>) -> State<Color::Green> {...}

    int main(){
      const auto state = newState(); // Green
      const auto state = next(state); // Yellow
      const auto state = next(state); // Red
      const auto state = next(state); // Green
      const auto state = next(state); // Yellow
    }

Rust will also support it one day, as part of the const generics feature. Partial support is there behind a feature flag.

https://play.rust-lang.org/?version=nightly&mode=debug&editi...

    #![feature(const_generics)]
    
    #[derive(PartialEq, Eq)] // enums used as const generics must be Eq
    enum Color { Green, Yellow, Red }
    
    struct State<const COLOR: Color>;
    
    impl State<{ Color::Green }> { fn next(self) -> State<{ Color::Yellow }> { State } }
    impl std::fmt::Debug for State<{ Color::Green }> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.write_str("green") } }
    
    impl State<{ Color::Yellow }> { fn next(self) -> State<{ Color::Red }> { State } }
    impl std::fmt::Debug for State<{ Color::Yellow }> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.write_str("yellow") } }
    
    impl State<{ Color::Red }> { fn next(self) -> State<{ Color::Green }> { State } }
    impl std::fmt::Debug for State<{ Color::Red }> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.write_str("red") } }
    
    impl State<{ Color::Green }> { fn new() -> Self { State } }
    
    fn main() {
        let state = dbg!(State::<{ Color::Green }>::new());
        let state = dbg!(state.next());
        let state = dbg!(state.next());
        let state = dbg!(state.next());
    }

Output:

    [src/main.rs:20] State::<{ Color::Green }>::new() = green
    [src/main.rs:21] state.next() = yellow
    [src/main.rs:22] state.next() = red
    [src/main.rs:23] state.next() = green

Are the braces around the const expressions planned to be optional in future? I'm wondering if this will work:

    impl State<Color::Green> {
        fn next(self) -> State<Color::Yellow> { ... }
    }

I believe they're intentional, to disambiguate from `mod Color { struct Green; }`, and because they can be arbitrarily complex expressions.

Currently the compiler gives "not a type" when the brackets are removed; I agree that it might be to disambiguate, but it's confusing and redundant syntax. I expect { } to be used strictly for blocks in Rust.

It's a block though, isn't it?

Color::Green is an enum variant while { Color::Green } is a (constant) block (expression) that evaluates to an instance which is used as a generic type parameter.

The difference might be more easily understandable if we look at an enum variant that holds a value, where the syntactic differences between variant and instance constructor are more clearly visible.

Color::RGB(u64, u64, u64) vs { Color::RGB(10, 20, 30) }

Hm, the RFC says the braces are needed if it is not an "identity expression" with the examples:

    const X: usize = 7;
    
    let x: RectangularArray<i32, 2, 4>;
    let y: RectangularArray<i32, X, {2 * 2}>;

So I'm still not sure if Color::Green is an identity expression, they say:

> Identity expression: An expression which cannot be evaluated further except by substituting it with names in scope. This includes all literals as well all idents

So... maybe? Depends on whether Color::Green is an ident or not. At the very least I'd expect this to work, but it doesn't yet:

    use Color::*;
    
    impl State<Green> { ... }

A name in scope is a path to a name, and Color::Green is also a path, so if impl<Green> works impl<Color::Green> would work as well.

C++ requires using the template keyword to disambiguate, i.e., one has to write `foo.template bar<22>()` as opposed to `foo.bar<22>()` (did you mean `(foo.bar < 2*2) > ()` ?).

The main reason Rust meta-programming is so much better than D and C++ is that Rust has an LL(k) grammar that's trivial to parse into ASTs that can be easily manipulated.

That feature alone is definitely worth the annoyance of having to use an editor that types `{}` for you when inputting a constant expression. It's the same with removing the `::` in `::<>` - can be done, but the costs are not worth the ergonomic improvement.

That is, I don't think the claim that the braces are redundant is correct - they are there for a reason: to keep a simple grammar, which happens to be one of the most important Rust features that everybody uses every day (every single proc macro uses this feature, that includes the `println!` in `println!("Hello World")` Rust examples).

Removing redundancy is not always a good idea, but the braces are redundant.

Can you elaborate? If you remove the braces, you break one of Rust's most important language features, an LL(2) grammar.

That is, those braces give Rust an LL(2) grammar, and therefore, are not redundant.

If you know how to preserve the LL(2) grammar in Rust while removing those braces, please explain why, since the answer would revolutionize many fields of computer science.

The braces are redundant because they do not introduce any new information, which is the definition of being redundant.

Whether the resulting grammar is or not LL(2) is orthogonal.

That is the long term plan. In the meantime we also have intentions of making rustc interpret what you want even when the grammar would require the disambiguation so that it can provide the appropriate suggestion in that case.

https://github.com/rust-lang/rust/pull/64700

> C++20 supports enums as non-type template parameters, so I think it'd be possible to do it with enums there. Something like:

Even c++98 supported that already : https://gcc.godbolt.org/z/7xma_u

Good point, I suppose of course it does, since enums are just ints. But C++20 adds support for enum classes (and also variants when they can be defined as value types with a defaulted operator<==>).

> But C++20 adds support for enum classes

It seems to work fine with `enum class` under C++11 ? your code works almost inchanged in g++ 4.7. I don't see anything here : https://en.cppreference.com/w/cpp/language/template_paramete... that adds specific support for that in C++20

Wow it does too, not sure where I got it into my head that it didn't then.

In C++ you can't hide a variable with another of the same name in the same scope. So you'd want to give different names to all the 'state' variables.

I made a rough attempt a little while ago to make something P-like with C++17 constructs, I think it turned out pretty nicely: https://gist.github.com/saltzm/f2acd7f656436dd63c9808ea11738...

There’s one extra validation hop to check valid state transitions that I don’t love, but if I take that feature out then I think it’s pretty low overhead for how readable it is

That example does not work, because declaring `state` multiple times creates an illegal C++ program (redeclaration of local variable - notice that this is not the case in Rust).

You need to declare variables with different names:

    const auto state0 = newState();
    const auto state1 = next(state0);
    const auto state2 = next(state1);
    const auto state3 = next(state); // TYPO -> BOOM use after move

I don't think this can be implemented safely in C++ without creating a "moved from" state that terminates the program on use, because C++ does not have Affine or Linear types.

That is, you can't use an `enum class`, since you can't implement move constructors and destructors for it, so you need to use a `variant` wrapper or similar:

    struct Color {
      struct Green {};
      struct Red {};
      struct Blue {};
      struct MovedFrom {};
      using data_t = variant<Green, Red, Blue, MovedFrom>;
      data_t data; 

      Color(Color&& other) {
        data = other.data;
        other.data = MovedFrom{};
      }
      //... another dozens lines of boilerplate...
    };

and you can't probably use variant either, since using variant would introduce yet another possible state (e.g. if an exception gets thrown..).

So doing this right on C++ probably requires 100s of lines of boiler plate, it probably requires run-time state to keep track of moved-from values to enforce that states that have already been used are not used anymore, etc.

At this point you might as well just write that part of your code in Rust, where `enum Color { Gree, Red, Blue }` just works and will do what you want without any run-time state. If you need to do compile-time computations, you can either use nightly and use const generics, or you can use stable Rust and write a proc macro. Both options are easier for humans to get right than the amount C++ boilerplate that's going to be required to avoid the fact that move operations are not "destructive" / affine.

Another user below was arguing that they preferred to use C++ because there they don't need to use `{ }` to disambiguate const generics, yet they are apparently fine with using `var.template member_fn` to disambiguate all template method calls... I imagine many users will argue that writing all the boilerplate above is "fine" or "not a big deal". To me all this sounds like Stockholm syndrome: somebody must use C++, they have been using it for 10 years already, and having to write all these boilerplate and know all these detail nitpicks of trivia to write a trivial piece of code makes them feel clever and gives them job security. I'm not even going to read your comments so really don't bother replying if that's what you are going to talk about.

> and you can't probably use variant either, since using variant would introduce yet another possible state (e.g. if an exception gets thrown..).

Variants are excellent for a state machine. valueless_by_exception is pretty much irrelevant if your states' relevant constructors and assignments are nothrow.

C++ variants are horrible for state machines, since they are not affine types.

Nobody is using state machines to advance several times through the states with variables named "stateN", so I am not sure what is the point.

There is no "BOOM" either since "use after move" is not a safety concern for those empty types, just a logic bug, which will likely appear at compile-time since your template specialization would not match your expectations.

The redeclaration in Rust always makes me uneasy as a default. It would have been better to require special syntax.

The rest about C++ users looks like flamebait to me.

> Nobody is using state machines to advance several times through the states with variables named "stateN", so I am not sure what is the point.

The point is that in C++ every time you advance the state you "split" the state machine into two - one that can be used by mistake and doing so introduces a bug, and one that is the one that should be used.

In programming languages that proper support state machines (or session types, or any similar pattern), that split is guaranteed to be impossible, so you get the guarantee that users cannot misuse your API, because attempting to do so is a guaranteed compilation error.

> There is no "BOOM" either since "use after move" is not a safety concern for those empty types, just a logic bug, which will likely appear at compile-time since your template specialization would not match your expectations.

This isn't true: even if `state0` and `state1` have different types, as you are proposing, your proposed `next` function accepts both types according to your design without a compilation error.

There is "no" fix for this in C++. Even if you were to introduce `next0`, `next1`, etc. that only accepts one type, the one of `state0`, `state1`, etc. that would create a compilation error here:

    auto state0 = next(initial_state);
    auto state1 = next0(state0); 
    auto state2 = next0(state1); // ct-error: use next1(state1)

but the underlying error is still there, and that is that the user can write

    auto state2 = next0(state0); // use-after-move

that's a logic error that Rust catches at compile-time, but C++ would need to catch at run-time, and catching this at run-time adds overhead, since now you need to store in some run-time data-structure in which state the state machine is, to be able to verify these things (while in Rust, you don't have to track this at run-time at all).

> There is no "BOOM" either since "use after move" is not a safety concern for those empty types, just a logic bug

Rust allows you to assume that this logic bug never happens. C++ code that assumes this can easily have undefined behavior due to the logic bug happening. That is, C++ code cannot assume that the state machine will only go from one state to the next, at least, without the whole state machine library / implementation checking at every step that these bugs do not happen, and, e.g., terminating the program if that's the case That's a valid solution, and probably the best solution that can be implemented in C++, but compared to what Rust and other languages offer, it is a very bad solution and the consequences are quite drastic (state machines, session types, etc. are widely used in Rust to design APIs, while they aren't really used in C++ because they are very boiler plate heavy, complex to implement, and incur a lot of runtime overhead to prevent these errors).

> The redeclaration in Rust always makes me uneasy as a default. It would have been better to require special syntax.

How many years have you been a full-time Rust user ? Or how many of your C++ projects use the "state machine C++ pattern" that you are advocating here ? How many developers are involved in each of those projects ?

You claimed there is a safety issue on "use after free" for empty types which are trivial. I am still waiting to see the proof.

You also keep saying there is no way to fix in C++, you can most definitely make those into compilation errors. And that is if you insist on advancing several states and calling them "stateN" is useful, which I have never done in my life.

Then the last paragraph is another flamebait plus getting into arguments of authority.

> You claimed there is a safety issue on "use after free" for empty types which are trivial. I am still waiting to see the proof.

I claimed that it is trivial to accidentally introduce safety issues when implementing _state_ machines in C++ like you are proposing. The "state" in "state machines" comes from the machine actually having some state. Naive state machines don't store state, and simple state machines can encode all their state in types, but real world state machines rarely do so (e.g. a regex engine).

> You also keep saying there is no way to fix in C++, you can most definitely make those into compilation errors.

Show how to do that then, e.g., for example for a simple file handle wrapper, that only allows reading a file once:

    struct FileHandle {
      static FileHandle open(const char*);
      ~FileHandle(); // closes file
      struct FileRead { ~FileRead(); /* closes file */ };
      static FileRead read(FileHandle);
    };

such that the file is not closed twice:

   auto file = FileHandle::open("foo");
   auto read = FileHandle::read(file);
   //~ read destructor closes file
   //~ file destructor double-closes file

without doing any run-time checks, e.g., in destructors, that check whether the file is closed.

This is easy peasy in Rust.

Advocating for programmer ergonomics is always a good thing. And I think more people should advocate and try to design languages in such a way that the way of programming more closely resembles the actual real thing [1, 2].

As you might recall in cognitive psychology there's a specific idea that translating a problem to a more recognizable problem (or simply changing the symbols) is a good thing [3]. Having less working memory is a good thing.

Reading your post, I believe those principles are behind it.

[1] http://worrydream.com/LearnableProgramming/

[2] Sublime's feature of showing a color when you give a hex value.

[3] Chapter 12 - Cognitive Psychology (3rd edition) by Bruce Goldstein

While I love Bret's work I don't think that's scalable. If you can simulate time axis, it means it can simulate only systems that can are hundreds of times smaller than system resource. E.g. can you simulate a Kubernetes swarm with thousands of different settings?

It's a great learning tool, but not much else.

Bret's work is an example of the principle. Sublime its feature, for example, is scalable.

Depends on the desired level of detail, and how "simulate-able" the system is designed to be. For example if everything uses a central event queue, one can to Discrete Event Simulation by just jumping to the next event. However an exiting Kubernetes swarm is not very simulate, as with most other existing software. And until (or if) simulation becomes a priority, this will continue to be the case.

They link to the `P` language, which I did not know about.

https://github.com/p-org/P

I found the link interesting because I have at times wondered what it would look likes if FSM were first class control flow features, akin to `if` and `while`.

the ping pong program is very easy to read. I don't know if it scales to bigger ones, but this one is really nice.

https://github.com/p-org/P/wiki/PingPong-program for anyone else wondering

Once upon a time I have implemented POP3 server protocol state machine in Clojure. 180 lines in total, of which 40 were FSM declaration, 140 command handling functions. Not sure I'll ever want to approach FSM in any other language, unless no other choice.

Can you perhaps point to it? Sounds interesting to read that code!

Yes. Can't share the whole repo (it's our internal product), but here are two files (FSM macro and FSM itself) you can explore. Let me know it that helps.

https://gist.github.com/juskrey/61148c98bdde871a8d3743f54b82...

https://gist.github.com/juskrey/127cf8456fc527d20ed5e244ce01...

Interesting, thanks a lot for being able to share those examples!

I think you managed to find a bug in the GitHub syntax highlighter, as https://gist.github.com/juskrey/61148c98bdde871a8d3743f54b82... has no colors after line ~108.

Not OP but there is tons of FSM implementations/libs in Clojure scattered around GitHub and GitLab if you search for them.

Some of them:

- https://github.com/ztellman/automat

- https://github.com/metosin/tilakone

- https://github.com/cdorrat/reduce-fsm

Did you iterate to a FSM solution, from many nested conditions, or use it right from the start? I'm fighting the urge to write any FSM without having the absolute certainty that it is needed. There seems no other way than by refactoring to an FSM.

I have started from already existing FSM libs (which did not fit well) and after couple of experiments understood that creating own custom FSM processor is a no-brainer with clojure/core.match

You can invert the box; instead of putting the state inside the struct, put the struct inside the state. So instead of having a Foo with a Yellow state, have a Yellow Foo. You can then call methods on the Yellow state to get a Foo in the next state.

To make it work better, you'd need type-level functions, or some other kind of compile-time function, which can be called when instantiating something with compile-time arguments (like generics). Anything less and you lose the static checking when try and treat your state as a first-class value. The computation of the type (state) needs to happen at compile time. Otherwise you're just back in dynamic land and you might as well put in assertions.

I’ve really enjoyed writing state machines in Swift. The rich enums allow states to be expressed with wrapped data (associated values) and events to also be expressed as rich enums.

I’ve begun using the pattern to represent state in views, navigation, and obviously when modeling processes (like a firmware update or Bluetooth connection).

Just to add more options, if you are willing to eat an allocation per transition, you can achieve a better developer experience by using trait objects.

You can define the trait:

    trait State: std::fmt::Debug {
        fn transition(&self) -> Option<Box<dyn State>>;
    }

Then implement the trait for each struct, and transition:

    #[derive(Debug)]
    struct FirstState {
        foo: u32,
    }
    
    impl State for FirstState {
        fn transition(&self) -> Option<Box<dyn State>> {
            println!("First State Hit {}", self.foo);
            Some(Box::new(SecondState {
                bar: "Hello".to_owned(),
            })) // transition to second state
        }
    }

Can even make an Iterator:

    struct StateIterator {
        curr_state: Option<Box<dyn State>>,
    }
    
    impl StateIterator {
        fn new(curr_state: Option<Box<dyn State>>) -> Self {
            Self { curr_state }
        }
    }
    
    impl Iterator for StateIterator {
        type Item = Box<dyn State>;
        fn next(&mut self) -> Option<Self::Item> {
            let next_state = self
                .curr_state
                .as_ref()
                .and_then(|state| state.transition());
            std::mem::replace(&mut self.curr_state, next_state)
        }
    }

And use it:

    fn main() {
        let first_state = Box::new(FirstState { foo: 0 });
        for state in StateIterator::new(Some(first_state)) {
            println!("{:?}", state);
        }
    }

Which outputs:

    ~ state-machine git:(master)  cargo run
    First State Hit 0
    FirstState { foo: 0 }
    Second State Hit: Hello
    SecondState { bar: "Hello" }

Playground: https://play.rust-lang.org/?version=stable&mode=debug&editio...

You can work-around allocating-per-state by making a hacky enum with an array of pointers, assuming the states themselves are immutable, which gives me an idea for a library.

With generic types, you can also model infinite state machines by instantiating a generic type with anther generic type.

This way you can extend the concept of the presented finite state machine all the way to Turing machines!

See here you can do that with C#:

https://blog.hediet.de/post/how-to-stress-the-csharp-compile... (section "With C# One Can Prove that a Turing Machine Halts")

It turns out, this is much easier to apply to rust than to C#!

Noob question but what about state machines where a given state could transition to more than one other state depending on some outside factors? Or is that no longer considered a state machine?

For a relevant to me example, a VM state. A VM in running state could be transitioned to terminated or stopped or hibernating depending on an admins action.

You might queue up events which cause it to transition to another state. If you hit the hibernate button, it might finish rendering the current frame before checking to see if the button was pressed, then hibernate. So it's the same state machine just with a larger input space.

Sure but how does that work with the provided implementation where all states can only transition to a single state, this is ensured at compile time. What does the code look like that allows a state to transition to one of several other states?

No Rust, but here's a Python implementation that I have built on top of before: https://github.com/pytransitions/transitions

You add the concept of finite "triggers", where [state i] + [trigger result j] always takes you to [new state](which could be the same state if you want)

Triggers are just functions where anything could be happening - coin flip, API call, but they return one of an enumerated set of results so the machine can always use their result to go to another state.

Ah ok. I don't write Rust either but maybe it'd look like:

  impl State<Running> {
    pub fn next(self, Trigger<Hibernate>) -> State<Hibernate> {
        State { _inner: Hibernate {} }
    }

    pub fn next(self, Trigger<Terminate>) -> State<Terminate> {
        State { _inner: Terminate {} }
    }
  }

Usually you would just call your functions hibernate() and terminate(). That way you can call hibernate() on State<Running> but not on State<Terminated> or State<Hibernate>.

that's known as an NFA (Nondeterministic Finite Automaton), a variant of FSMs.

Nondeterminism not needed (or desired I think :D) for an FSM that can turn a VM on or off based on start/stop buttons. Its just multiple possible transitions, guarded by different conditions (the buttons).

But yeah, Nondeterministic FSMs are possible. Ie based on a transition probability.

the "nondeterminism" here doesn't mean we're dealing with probabilities, it's a more discrete kind - it just means that instead of

  S1 --a--> S2

you can have

  S1 --a--> S2
    '--a--> S3
    '--a--> S4

i.e. transition to multiple states "at once"¹. then, instead of being in one state, like an FSM, your NFA is in a set of states, like it had multiple threads, and proceeds "in parallel" from each state. probably not the best explanation, but i'm sure you can find good material about this.

---

¹ this a way to represent nondeterminism in a pure/math-y setting: instead of

  def f():
    b = random_bool()
    if b:
      res = "yes"
    else:
      res = "no"
    return res

you do

  def random_bool2():
    return {True, False}

  def f2():
    res = set()
    for b in random_bool2():
      if b:
        res.add("yes")
      else:
        res.add("no")
    return res

or just:

  def f2():
    return {"yes", "no"}

i.e enumerate all the possible results f() could give depending on what `random_bool()` returns.

Harel's Statecharts (an evolution of state machines) have concurrent states (with branch/fork and merge/wait), which would be one way of solving what you describe.

I believe Harel may have borrowed concurrent (aka orthogonal) states from elsewhere though: state machines have been extended a few different ways over the years.

So you may find similar features elsewhere too.

> A VM in running state could be transitioned to terminated or stopped or hibernating depending on an admins action.

Actually, that doesn't necessarily need concurrency, I misread your question.

Yes, in a state machine, each state can have different conditions (guards) on each outgoing transition. So when running, pushing the stop button would cause transition to the stop/stopping state, pushing the pause button would transition to the pause/pausing state.

Guard conditions are simple boolean decisions, based upon events or other state. And sure, that event/state could be triggered externally to the state machine.

Technically it might not be a 'pure' state machine, but they rarely are outside of toy examples, in my experience — they always have to interact with something, and that thing is often not a state machine. Arguably I'm splitting hairs over philosophical differences here, but hey.

Your example is a standard Finite State Machine. Multiple possible transitions is the norm for an FSM, and each possible transition is guarded by some predicate which decides if it should be followed.

# transition notation: FromState -predicate-> ToState

    Running -stop_button-> Stopped
    Stopped -start_button-> Running
    Running -start_button-> Running # stay running
    Stopped -stop_button-> Stopped # stay stopped

The stop/start_button button here can either be events that come in from the outside (from dedicated click handlers in a GUI), or be functions or properties that are polled when evaluating next().

Since booting a VM can take quite some time, one might want to introduce a Starting state between Stopped and Running.

The example in the original article is just a special case, where there is only one possible transition from each state, and where the predicate always returns true. Although arguably for a real traffic light, there should be a predicate on the transition that checks that enough time has passed! At least I would model that as part of the FSM, instead of on the outside.

EDIT: fix formatting

I disagree with the implementation, State should be a trait with NextState as an associated type. This makes things cumbersome when it can be a set of types, but it makes excellent use of the type system and ownership patterns of Rust. Edit: and the type state pattern http://cliffle.com/blog/rust-typestate/

As an aside, if you want to dive in with FSMs and automata theory (as well as some basic language topics) go read Sipser's book, "Introduction to the Theory of Computation." You'll go from logic to state machines to understanding why Turing Machines are so dope in a few dozen pages. The math isn't bad.

See Nemo157's response to cerebellum42. He explains why having this in runtime is not the best approach for FSMs.

Nothing I suggested implies a runtime penalty. Quite the opposite actually.

the article includes a section on the state as a generic type parameter, though?

in general, state as a type parameter is useful when there's some data that you want for every state (say, unique id, time of event), so those can be normal fields on the State struct, and then each event type can hold event-specific data. You can tie it together with From<T> and TryFrom<T> implementations that enable the specific transitions you want to allow.

Associated types are slightly different than generic types.

    trait State {
        type NextState;
        fn transition(self) -> Self::NextState;
     }

In this example one consumes the current state to yield the next state (one could use From/TryFrom, but I don't think that makes sense semantically, imo).

The advantage of this approach is that if you design your State types such that they can only be constructed by transitioning from a previous state, you cannot write code where your program is accidentally in an invalid state. You also never need to match against an enum.

You should keep going with this and see how ergonomic it is when NextState can be one of many states. I tried implementing State Machines once with this method and ended up wanting to use an `enum` for `State::NextState`. After a while it ended up being pretty unwieldy.

I've had good luck in the past using From<T> and TryFrom<T> to go from State<A> -> State<B>. It's similar to what you propose insofar as there are only some transitions defined, just relying on the built-in traits instead of using your own. Since State::from(prev) is so much more ergonomic than the other ways you could manually construct an illegal transition, it's not much of a problem to prevent that in practice. But I would never use this approach without being able to generate code with macros, otherwise it'd be a pain.

you mention "never have to match against an enum" - I think that's the biggest thing I learned from my experiences, is that generics or traits + associated types are much nicer to use than enums for the same purposes. With an enum, you have to match to pull any data out. It becomes annoying quickly.

Fulcro is the only web framework I'm aware of that uses them throughout

- https://github.com/fulcrologic/fulcro

- https://github.com/fulcro-legacy/fulcro-incubator/blob/devel...

I keep meaning to learn them in the context of a larger web app

Coroutines are another interesting way of expressing state machines. They can make certain classes of state machines easier to read because the flow reads like a normal function. So far I've only used the technique once in Python using generators. There were some ergonomic aspects that were less than ideal but serve as one example of why I look forward to generators being added to Rust.

Async/await in Rust compiles down to a state machine (and to my understanding, uses generators under the hood):

https://rust-lang.github.io/async-book/01_getting_started/04...

Generators are currently unstable, but the crate genawaiter[1] allows you to use them on stable.

We have used that crate at work to replace a very scary and verbose state machine (which was generating a lot more code via procedural macros) with a much more succinct version.

[1]: https://docs.rs/genawaiter/0.2.2/genawaiter/

However one big limitation of this is that this pattern cannot store the state inside another struct; it can only exist on the stack this way. So we cannot do the following:

  struct Foo<S> {
      state: State<S>,
  }

The moment we initialize Foo to take e.g. Green as its parameter, it can now no longer switch to Red in safe Rust. This is what enums are for, and unfortunately we can't use those here.

Couldn't you just declare a trait that S must implement and then declare the member in Foo as State<dyn Trait>? That trait would probably also include the next() method mentioned in the example. Of course you'd be adding dynamic dispatch here, but it should work, right?

I think that the whole point is to do this statically.

The cited post[1] recommends an enum for this job, which avoids the dynamic dispatch and makes it easier to get at a specific state’s data when you have the whole machine.

[1] https://hoverbear.org/blog/rust-state-machine-pattern/

That is probably the way to go, agreed.

I am not a fan of the hoverbear state machine pattern. I find that it makes simple things complicated and hard things impossible. I used it and I had problems with:

  - Reusing code between states.
  - Making callbacks to other APIs during state changes.

I ended up using the standard state pattern described here: https://doc.rust-lang.org/book/ch17-03-oo-design-patterns.ht...

The state pattern is not considered to be idiomatic Rust, but in my experience it works better and is very flexible.

The state pattern has the downside that the type system does not enforce which state changes are allowed.

for reusing code between states, did you try impl blocks that are generic over the state type parameter?

for

    struct State<T> { state: T }

with possible states

    struct A { id: Uuid }
    struct B { id: Uuid }

use a trait

    trait HasId {
        fn id_mut(&mut self) -> &mut Uuid;
    }

now you can impl over both A and B

    impl<T: HasId> for State<T> {
        fn new_id(&mut self) { *self.state.id_mut() = Uuid::new_v4() }
    }

simplistic example but enough to communicate the idea hopefully.

generally, macros makes this kind of thing ergonomic so you can generate the trait implementations and so on. otherwise it's a lot of typing.

don't understand what you mean about making callbacks to other APIs during transitions.

I did not try that -- its a cool technique. Thanks for taking the time to share it.

Of course dynamic dispatch helps, but using it for a state machine is going to raise eyebrows and kill performance.

I think this would depend on the application. Its possibly a problem in a parser of large data, but in a network protocol or business rule its not going make any difference at all.

If you are using a compiled, systems programming language like Rust, you do care about performance to begin with.

Specially in things like parsing or a network protocol!

I think what they're saying is that it literally makes no difference, not negligible difference. At some point you have to do the branching that decides which part of the logic in the state machine runs next. Dynamic dispatch is essentially just a way to do this kind of branching.

Yes, this is basically erasing type invariants by moving them into runtime code. Similar things have been done with things like GPIO pins in embedded code, having the pin numbers carried in the type (`struct Pin1;`) and being able to erase those for collections by moving them to runtime (`struct Pin { id: u8 }`). Unfortunately it comes with a bunch of extra implementation overhead currently, maybe in the future with const-generics it would be possible to reduce this overhead (that would end up being closer to some sort of merge between the first example and the "future directions") .

Wouldn't state machines in a logic programming language or even just a constraint programming DSL be better than doing everything manually?

Slightly OT, but:

> In Germany traffic lights go green -> yellow -> red -> yellow -> green, but let's pretend they're only green -> yellow -> red -> green.

is not correct if I'm not missing something major. Is there any situation where they turn yellow before turning green?

They probably mean "red-yellow", which is an intermediate "wait for it" state in many European countries, including Germany https://de.wikipedia.org/wiki/Ampel#/media/Datei:Traffic_lig...

I think I've never noticed that red-yellow in 40+ years of living in Germany. Interesting. Maybe it's a good thing I never get to drive a car these days.

They go red -> red+yellow -> green when making the red -> green transition.

Couldn't you implement this by consuming `self` on `next()`?

It looks like this is really asking for DataKinds or something similar. Since it's required to lift the enum variant to the type level.

Just have to say what a pretty blog :) More of this please, internet.

I'd have implement a state machine as an enum....

Who is Yoshua Wuyts?

For starters, he's a significant contributor to the Rust community and ecosystem. As you can see, he shares knowledge and experiences, which is a rarety among the more experienced crowd. He actually wants to help others beyond "codeblazing".

Reply on news.ycombinator.com