12 ms·
State Machines in Rust
- Phlogistique 7y agoThey link to the `P` language, which I did not know about. https://github.com/p-org/P 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`.
- juskrey 7y agoOnce 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.
- harperlee 7y agoCan you perhaps point to it? Sounds interesting to read that code!
- juskrey 7y agoYes. 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/61148c98bdde871a8d3743f54b822ae5 https://gist.github.com/juskrey/61148c98bdde871a8d3743f54b82... https://gist.github.com/juskrey/127cf8456fc527d20ed5e244ce01e312 https://gist.github.com/juskrey/127cf8456fc527d20ed5e244ce01...
- diggan 7y agoInteresting, 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/61148c98bdde871a8d3743f54b822ae5 https://gist.github.com/juskrey/61148c98bdde871a8d3743f54b82... has no colors after line ~108.
- diggan 7y agoNot 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/ztellman/automat - https://github.com/metosin/tilakone https://github.com/metosin/tilakone - https://github.com/cdorrat/reduce-fsm https://github.com/cdorrat/reduce-fsm
- Dowwie 7y agoDid 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.
- deleted 7y ago[deleted]
- juskrey 7y agoI 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
- cerebellum42 7y agoHowever 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?
- tunnuz 7y agoI think that the whole point is to do this statically.
- kd5bjo 7y agoThe 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/ https://hoverbear.org/blog/rust-state-machine-pattern/
- cerebellum42 7y agoThat is probably the way to go, agreed.
- papaf 7y agoI 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.html 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.
- mettamage 7y agoAdvocating 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/ 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
- Ygg2 7y agoWhile 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.
- mettamage 7y agoBret's work is an example of the principle. Sublime its feature, for example, is scalable.
- jononor 7y agoDepends 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.
- unlinked_dll 7y agoI 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/ 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.
- grenoire 7y agoSee Nemo157's response to cerebellum42. He explains why having this in runtime is not the best approach for FSMs.
- unlinked_dll 7y agoNothing I suggested implies a runtime penalty. Quite the opposite actually.
- deleted 7y ago[deleted]
- jstrong 7y agothe 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.
- unlinked_dll 7y agoAssociated 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.
- baybal2 7y agoWho is Yoshua Wuyts?
- Dowwie 7y agoFor 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".
- logicchains 7y agoC++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 }
- alvarelle 7y agoIn 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.
- Arnavion 7y agoRust 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&edition=2018&gist=7cf04999dd6d093fc34da5c022a04b8f 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
- m90 7y agoSlightly 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?
- derkha 7y agoThey 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_lights_4_states.svg https://de.wikipedia.org/wiki/Ampel#/media/Datei:Traffic_lig...
- m90 7y agoI 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.
- TimNN 7y agoThey go red -> red+yellow -> green when making the red -> green transition.
- diggan 7y agoFor 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/resources/statecharts.pdf https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res... Website with lots of info and resources: https://statecharts.github.io/ 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 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=18483704 - https://news.ycombinator.com/item?id=15835005 https://news.ycombinator.com/item?id=15835005 - https://news.ycombinator.com/item?id=21867990 https://news.ycombinator.com/item?id=21867990 - https://news.ycombinator.com/item?id=16606379 https://news.ycombinator.com/item?id=16606379 - https://news.ycombinator.com/item?id=22093176 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.
- deleted 7y ago[deleted]
- taneq 7y ago> (nested state machines!) Also known as hierarchical state machines. (web searches) Oh, which are also called state charts. So yes, those!
- bobbiechen 7y agoThanks 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.com/en/us/archive/paxos_made_live.pdf http://static.googleusercontent.com/media/research.google.co...
- slifin 7y agoFulcro is the only web framework I'm aware of that uses them throughout - https://github.com/fulcrologic/fulcro https://github.com/fulcrologic/fulcro - https://github.com/fulcro-legacy/fulcro-incubator/blob/develop/state-machine-docs.adoc https://github.com/fulcro-legacy/fulcro-incubator/blob/devel... I keep meaning to learn them in the context of a larger web app
- epage 7y agoCoroutines 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.
- trevyn 7y agoAsync/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_async_await_primer.html https://rust-lang.github.io/async-book/01_getting_started/04...
- luckysori 7y agoGenerators 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/ https://docs.rs/genawaiter/0.2.2/genawaiter/
- Gehinnn 7y agoWith 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-compiler https://blog.hediet.de/post/how-to-stress-the-csharp-compile... (section "With C# One Can Prove that a Turing Machine Halts")
- Gehinnn 7y agoIt turns out, this is much easier to apply to rust than to C#!
- leshow 7y agoIt looks like this is really asking for DataKinds or something similar. Since it's required to lift the enum variant to the type level.
- ones_and_zeros 7y agoNoob 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.
- Tyr42 7y agoYou 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.
- ones_and_zeros 7y agoSure 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?
- skrtskrt 7y agoNo Rust, but here's a Python implementation that I have built on top of before: https://github.com/pytransitions/transitions 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.
- ones_and_zeros 7y agoAh 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 {} } } }
- barrkel 7y agoYou 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.
- oflannabhra 7y agoI’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).
- deleted 7y ago[deleted]
- RcouF1uZ4gsC 7y agoIn 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-features/generators.html 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.
- klysm 7y agoState 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.
- jfkebwjsbx 7y agoResource 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).
- wahern 7y ago> 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.
- nwmcsween 7y agoWouldn't state machines in a logic programming language or even just a constraint programming DSL be better than doing everything manually?
- superlopuh 7y agoCouldn't you implement this by consuming `self` on `next()`?
- djtriptych 7y agoJust have to say what a pretty blog :) More of this please, internet.
- dpbriggs 7y agoJust 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&edition=2018&gist=534a16753f5001ae2e3f814dc24f540e 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.
- richardwhiuk 7y agoI'd have implement a state machine as an enum....