Live data from Hacker News

State Machines in Rust

blog.yoshuawuyts.com

71–80 of 119 posts

Re: State Machines in Rust

#71
post #68
post #50

Earlier quoted context omitted.

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)…

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 ; let y: RectangularArray ; 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?…

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

Re: State Machines in Rust

#72

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.

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.

Re: State Machines in Rust

#73

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 struct State{}; auto newState() -> State {...}; auto next(State ) -> State {...} auto next(State ) -> State {...} auto next(State ) -> State {...} int main(){ const auto state = newState(); // Green const auto state = next(state); // Yellow const a…

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

Re: State Machines in Rust

#74

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.

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.

Re: State Machines in Rust

#75
post #28

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 fi…

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/

Re: State Machines in Rust

#76
post #59

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 re…

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 and TryFrom implementations that enable the specific transitions…

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.

Re: State Machines in Rust

#78
post #28

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 fi…

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

Re: State Machines in Rust

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

Re: State Machines in Rust

#80

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.

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

Post reply on HN