51–60 of 119 posts
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")
With 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-compile... (section "With C# One Can Prove that a Turing Machine Halts")
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.
Async/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...
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.
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…
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
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…
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...
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.
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.
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…
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 you want to allow.
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.