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.
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]
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...
> 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
Even invented my own DSL and compiler a while back, but never really had the time to get it good enough to be useful.
Also known as hierarchical state machines. (web searches) Oh, which are also called state charts. So yes, those!
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.
>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.
Just, please, don't implement them in Oracle stored procedures.
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
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.
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.
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).
Generators are essentially similar to automatic CPS transformation.
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.
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...
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
}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());
}
[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 impl State<Color::Green> {
fn next(self) -> State<Color::Yellow> { ... }
}Even c++98 supported that already : https://gcc.godbolt.org/z/7xma_u
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
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
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...
};
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.
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.
Variants are excellent for a state machine. valueless_by_exception is pretty much irrelevant if your states' relevant constructors and assignments are nothrow.
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
It's a great learning tool, but not much else.
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`.
https://gist.github.com/juskrey/61148c98bdde871a8d3743f54b82...
https://gist.github.com/juskrey/127cf8456fc527d20ed5e244ce01...
Some of them:
- https://github.com/ztellman/automat
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 begun using the pattern to represent state in views, navigation, and obviously when modeling processes (like a firmware update or Bluetooth connection).
You can define the trait:
trait State: std::fmt::Debug {
fn transition(&self) -> Option<Box<dyn State>>;
}
#[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
}
}
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)
}
}
fn main() {
let first_state = Box::new(FirstState { foo: 0 });
for state in StateIterator::new(Some(first_state)) {
println!("{:?}", state);
}
}
~ state-machine git:(master) cargo run
First State Hit 0
FirstState { foo: 0 }
Second State Hit: Hello
SecondState { bar: "Hello" }
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.
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")
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.
# 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
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 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.
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.
But yeah, Nondeterministic FSMs are possible. Ie based on a transition probability.
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.
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.
trait State {
type NextState;
fn transition(self) -> Self::NextState;
}
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.
- 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
https://rust-lang.github.io/async-book/01_getting_started/04...
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.
struct Foo<S> {
state: State<S>,
}
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?
- Reusing code between states.
- Making callbacks to other APIs during state changes.
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.
> 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?
