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!<p>Here is the initial paper from David Harel: STATECHARTS: A VISUAL FORMALISM FOR COMPLEX SYSTEMS (1987) - <a href="https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf" rel="nofollow">https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res...</a><p>Website with lots of info and resources: <a href="https://statecharts.github.io/" rel="nofollow">https://statecharts.github.io/</a><p>And finally a very well made JS library by David Khourshid
that gives you lots of power leveraging statecharts: <a href="https://github.com/davidkpiano" rel="nofollow">https://github.com/davidkpiano</a><p>While we're at it, here are some links to previous submissions on HN regarding statecharts with lots of useful and interesting information/experiences:<p>- <a href="https://news.ycombinator.com/item?id=18483704" rel="nofollow">https://news.ycombinator.com/item?id=18483704</a><p>- <a href="https://news.ycombinator.com/item?id=15835005" rel="nofollow">https://news.ycombinator.com/item?id=15835005</a><p>- <a href="https://news.ycombinator.com/item?id=21867990" rel="nofollow">https://news.ycombinator.com/item?id=21867990</a><p>- <a href="https://news.ycombinator.com/item?id=16606379" rel="nofollow">https://news.ycombinator.com/item?id=16606379</a><p>- <a href="https://news.ycombinator.com/item?id=22093176" rel="nofollow">https://news.ycombinator.com/item?id=22093176</a><p>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.
In my experience, state machines are very nice in theory, but in practice, over time, they devolve into a mess of spaghetti code.<p>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.<p>In Rust, if you want a state machine, generators are probably the long term way to go.<p><a href="https://doc.rust-lang.org/nightly/unstable-book/language-features/generators.html" rel="nofollow">https://doc.rust-lang.org/nightly/unstable-book/language-fea...</a><p>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.
C++20 supports enums as non-type template parameters, so I think it'd be possible to do it with enums there. Something like:<p><pre><code> 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
}</code></pre>
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].<p>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.<p>Reading your post, I believe those principles are behind it.<p>[1] <a href="http://worrydream.com/LearnableProgramming/" rel="nofollow">http://worrydream.com/LearnableProgramming/</a><p>[2] Sublime's feature of showing a color when you give a hex value.<p>[3] Chapter 12 - Cognitive Psychology (3rd edition) by Bruce Goldstein
They link to the `P` language, which I did not know about.<p><a href="https://github.com/p-org/P" rel="nofollow">https://github.com/p-org/P</a><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`.
Once upon a time I have implemented POP3 <i>server</i> 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.
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.<p>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.<p>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.<p>You can define the trait:<p><pre><code> trait State: std::fmt::Debug {
fn transition(&self) -> Option<Box<dyn State>>;
}
</code></pre>
Then implement the trait for each struct, and transition:<p><pre><code> #[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
}
}
</code></pre>
Can even make an Iterator:<p><pre><code> 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)
}
}
</code></pre>
And use it:<p><pre><code> fn main() {
let first_state = Box::new(FirstState { foo: 0 });
for state in StateIterator::new(Some(first_state)) {
println!("{:?}", state);
}
}
</code></pre>
Which outputs:<p><pre><code> ~ state-machine git:(master) cargo run
First State Hit 0
FirstState { foo: 0 }
Second State Hit: Hello
SecondState { bar: "Hello" }
</code></pre>
Playground: <a href="https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=534a16753f5001ae2e3f814dc24f540e" rel="nofollow">https://play.rust-lang.org/?version=stable&mode=debug&editio...</a><p>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.<p>This way you can extend the concept of the presented finite state machine all the way to Turing machines!<p>See here you can do that with C#:<p><a href="https://blog.hediet.de/post/how-to-stress-the-csharp-compiler" rel="nofollow">https://blog.hediet.de/post/how-to-stress-the-csharp-compile...</a>
(section "With C# One Can Prove that a Turing Machine Halts")
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?<p>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.
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 <a href="http://cliffle.com/blog/rust-typestate/" rel="nofollow">http://cliffle.com/blog/rust-typestate/</a><p>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.
Fulcro is the only web framework I'm aware of that uses them throughout<p>- <a href="https://github.com/fulcrologic/fulcro" rel="nofollow">https://github.com/fulcrologic/fulcro</a><p>- <a href="https://github.com/fulcro-legacy/fulcro-incubator/blob/develop/state-machine-docs.adoc" rel="nofollow">https://github.com/fulcro-legacy/fulcro-incubator/blob/devel...</a><p>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.
<i>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:</i><p><pre><code> struct Foo<S> {
state: State<S>,
}
</code></pre>
<i>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.</i><p>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?
Slightly OT, but:<p>> In Germany traffic lights go green -> yellow -> red -> yellow -> green, but let's pretend they're only green -> yellow -> red -> green.<p>is not correct if I'm not missing something major. Is there any situation where they turn yellow before turning green?