1. 36

  2. 10

    State machines are kinda a huge pain in any language, as far as I can tell. Either you try to make them checked at compile time, like the first example does, and run into issues, or you do lots of checking at runtime and end up asking yourself things like “how did I get into this state?” and “why is it trying to transition into the wrong one?”, or you make a table of transitions and states and altering/updating it becomes error prone. Annoying for such a fundamental pattern.

    1. 6

      in Rust you can have both strongly-typed transitions and runtime dynamism. This kind of simulates session types, like what Idris is really nice for encoding in a lower boiler-plate way.

      1. 4

        State machines are kinda a huge pain in any language

        I’ve found state machines in dependently typed languages to be wicked cool, and much less painful. You can encode the state transitions into the types, which guarantee that your program is in a given state during compile time. The flexibility of the dependent type system allow you to encode state machines of arbitrary complexity.

        For example, in idris, you can do things like ensure that a file handle is open when you call read:

        -- legal 
        do f <- open "file.txt"
           content <- read f
           close f
        -- illegal 
        do f <- open "file.txt"
           close f
           content <- read f   -- won't compile because the file is closed!

        Some documentation on idris state machines, and an example of stateful socket programming

        1. 3

          I think it’s partially from a mismatch between conceptual model and language semantics, but a lot of it seems to come from people half-assing it, either by generating code that can get into a bad state, or not being explicit on what happens when receiving a message unsupported by the current state, things of that nature. I don’t think any of these issues are fundamental to the model of state machines though, or the semantics of the languages we use. Being more careful about generated code, and probably doing a lot more design-time / compile-time verification of the definitions would make it much more pleasant to use, in which case it would actually be used a lot more often, almost certainly to the improvement of software in general.

        2. 8

          I’ve been thinking about state machines in the last couple days. Specifically, I think Erlang’s gen_statem pattern (from OTP) is the 8th wonder of the world. The author of this behavior tackled a huge problem and I’ll be damned, hit it out of the park, considering how muddled one can get when thinking about state machines, let alone coding them up. I did a shallow dive into it a good while back (http://blog.snailtext.com/posts/bend-it-like-gen-statem.html), which isn’t bad. OK, not Rust related, but gen_statem certainly is something to marvel at in this space.

          1. 1

            Hey thanks to much for the link to your post! I’m an Elixir fellow myself, so I’ll happily digest what you’ve written.

            1. 1

              Nice blog post, and also a v. nice website design!

              If you’d enjoy it, could you spend a few words gushing about the things that gen_statem gets right that other state machine implementations get wrong, or don’t get at all? I love reading enthusiastic praises, and also I’m curious about the design space of the interfaces of state machine libraries.

              1. 1

                I regularly tell Rust people to learn about FUCRS, since this blog really got me thinking a lot about techniques for combating rightward pressure when I was working more with Erlang :) gen_statem and generally all of the behaviors are particularly nice IMO because they push all of their state in your face during transitions, and they keep the reality of the system more on your mind. For a dynamic language, erlang is able to specify so many beautiful properties that can be tested in a way that kind of approaches a much more usable dependent type system in some cases, with the features of dialyzer and general amenability to model-based testing that gets bugs to fall out of a system so quickly. Working in erlang has significantly impacted how I write Rust, and especially how I try to lean into state machine-based approaches for anything distributed-systems related.

              2. 6

                Using this simple typestate is useful for things like setting configuration up in a misuse-resistant (but often with confusing errors for users) way. Embedded people like to lean into this stuff a lot, but it can be really challenging to write it in a way that doesn’t turn your code into a maintenance nightmare. It’s one of many sharp tools in Rust that should be used with extreme care. Leaning too hard into typestates makes code difficult to wield, understand, change, basically everything from a human perspective gets worse other than strictly preventing misuse. So you want the misuse that it prevents to be really bad, usually, to justify this pricetag on a codebase.

                There are some nicer ways of writing state machines for the cases where strongly-typed transitions are worth the relatively high complexity pricetag, like in replication state machines etc… The 2 properties you want are:

                • strongly-typed transitions
                • uses an enum so that it can be contained in a single concrete type, so it can transition in orderings that are not crystallized in your specific code, as the simple typestate

                You can get this through something like this which is totally ugly, but you can start to see how you can start to do these strongly-typed events + input -> output transitions. The effect is what matters. Rust can encode more constraints than P if you’re willing to go down this path. P will just throw UnhandledEvent exceptions if you trigger invalid transitions at runtime. Rust can prevent coding those transitions in the first place if you embrace the style.

                An example where most of this boilerplate is hidden is https://github.com/fitzgen/state_machine_future which might be nice for some use cases.

                By far the biggest productivity gains associated with heavy reliance on state machine-oriented engineering is the ability to apply deterministic testing techniques, as discussed here and here. If you’re building correctness-critical stateful systems, this style of architecture lets you root out bugs literally millions of times faster than if you were relying on something like jepsen.

                1. 4

                  The way the author uses structs and then specifying each type in the State type…it doesn’t feel natural at all. It seems to be very unidiomatic way to do this.Very convoluted and hard to follow. (Which is I guess their point).

                  A more natural way to do this and keeping to the whole “you must be explicit about your values/transitions” is to use pattern matching / switching statement. Then you can do next(value) etc.

                  Their suggestion at the end though feels no better. It’s a form of pattern matching here really. To which I say: just use damn pattern matching and stop shoehorning :) Defining functions that take one specific value and output one specific value still requires a decision tree to pick which function to use.

                  Good article to incite some conversation and experiments.

                  I wish they would’ve called it “Some thoughts on doing simple state machines in Rust”.

                  Edit: I made my own experiment here https://lobste.rs/s/anu6c6/some_thoughts_on_simple_state_machines