8 ms·

Finite State Machines

102 points by adlrocha 6y ago

bjoli 6y ago
I found languages with TCO even easier to implement FSM in: a state is simply a procedure, and going from one state to another is just a procedure call. The difference is small, but once you start getting hairy state machines I have found that it leads to smaller mental overhead for me. The same would be true for something like a recursive descent parser.
- user-the-name 6y ago
  That means you are not able to interrupt your state machine easily, or to serialise its state. That might be OK in a lot of cases, but not all.
  - hderms 6y ago
    Seems like trampolining would be useful to make it interruptible while still mostly preserving the ergonomics of viewing state transitions as procedure calls
  - klibertp 6y ago
    Function objects, including closures, can be serializable - they are in Erlang/Elixir. You can send a lambda/closure over to another node (on another machine) to execute. It's actually one of the basic building blocks of OTP.
    - user-the-name 6y ago
      I assume this only works if the functions are exactly the same. It would break between different versions?
      - rad_gruchalski 6y ago
        It depends. It’s possible to provide a mechanism to switch versions but as it very often is: there are dragons.
  - dragonwriter 6y ago
    Serializable closures (even serializable continuations) are available in a number of languages, including probably most often ones which also have TCO.
- elviejo 6y ago
  What is TCO? what are languages that implement TCO?
  - klibertp 6y ago
    Tail Call Optimization, better called Tail Call Elimination. Haskell, OCaml, Erlang/Elixir, Scala with @tailrec, Scheme, Lua(!), most other functional languages. Basically, if there's a call to a function B at the very end of function A, there's no need to create a new stack frame for the call to B - you can reuse the frame created for call to A. It both saves memory and improves performance. A special case is when A and B are both the same function, in which case we say A is tail-recursive.
bestouff 6y ago
I prefer FSM implemented in Rust. Having valid transitions checked at compile time is a life saver as soon as is gets a bit complex - at least in my case being able to "prove" an embedded system wouldn't trigger its watchdog during operation was very important.
natsch 6y ago
> You are now planning to build your next big system as a state machine, Often people don't actively decide to write a state machine, but do so anyway. I think the big takeaway of FSMs is how to recognize them in an idea or implementation and actively using them as a nice abstraction.
surfsvammel 6y ago
FSMs are great! I’ve worked a lot with state machines, in telecom (to model different parts of 4G connections) as well as in capital markets (to model trades, transactions etc.). My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself. FSMs tend to reflect the business domain very closely, are very easy to reason and talk about with non-tech domain experts but also tend to change often. Therefore we have always implemented the framework for the FSM along with some kind of event kernel, and then left the actual setup and configuration of the FSMs to a configuration layer. It has worked very well and has made it so much easier to talk about how the system works with non-techies.
- tenaciousDaniel 6y ago
  Seems like FSM and DDD would go very well together, although I haven't seen any literature explicitly linking the two.
- jgraettinger1 6y ago
  > My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself. I really love Rust async/await for this. Under the hood, the compiler is simply assembling a big FSM, and polling a Future is equivalent stepping through allowed transitions which are available to it. You can even use this to build FSMs which are designed to be manually driven, by coordinating generator inputs and outputs via RefCell and one-shot channels and calling `poll` yourself.
- youerbt 6y ago
  TLA+ is a great example of a modeling tool that allows you to create FSMs relatively easily. It can also check properties of your model which gives more confidence in the final design.
carlbarrdahl 6y ago
How come there isn't better re-usability in state machines? It seems it would be powerful if they were treated as re-usable lego bricks of state and logic. Apps could then pull these in, connect the wires to any potential backend, and style the interactive components.
- davidkpiano 6y ago
  What makes them reusable is dependent on how you implement them. A state machine that is the simple relation: (state, event) => [state', actions] has a very reusable interface, as long as it doesn't execute the actions (effects, commands, etc.) itself. It's just a pure function that can be used anywhere to get the next state and the actions to execute as a result of receiving an event. Then you can do exactly what you're describing: connect the wires, style the components according to state, etc.
  - carlbarrdahl 6y ago
    Thank you David. Your xstate repo on github brought my attention to state machines and state-charts. Which I guess is why I'm interacting with this thread right now. I often wonder what would happen if we could find ways to build complex applications by creating re-usable blocks using state machines (state, logic), json-schemas (structure, data-model), and React* (presentation). All of these are serializable documents. Imagine being able to search a collective collaboration of components and schemas and piece it together. Could probably be graphical interface like Figma. There are certainly other pieces that could be also used (graphql to describe data-fetching, markdown (mdx) for content). *or similar
    - davidkpiano 6y ago
      I'm currently building this! More info to come soon.
  - dwohnitmok 6y ago
    You probably are already familiar, but if not, this is exactly the entire concept behind Elm (in fact that signature is exactly the update function at the heart of the Elm architecture). And indeed the Elm community has a lot of ideas on how to split that basic idea to make it reusable.
drummojg 6y ago
Is the letter "T" somehow associated with FSMs? I'm taken right back to one of the hardest assignments I ever had, which was learning C in order to write an interpreter for a FSM descriptor language (called "T") our professor had invented.
- ehnto 6y ago
  Perhaps T might describe a transition?
pknerd 6y ago
Anyone implemented in Python or Go for production systems?
- dkarp 6y ago
  I've used https://github.com/pytransitions/transitions https://github.com/pytransitions/transitions in production python systems. It worked great but the system was fairly simple and wasn't changed often. In my opinion, it's nicer when the state machine can be defined as configuration (in XML or whatever) and then generate the code. Unfortunately that's not possible with vanilla pytransitions, but I suppose you could build a layer on top of it.
  - pknerd 6y ago
    Interesting! > Unfortunately that's not possible with vanilla pytransitions Can you elaborate?
  - pknerd 6y ago
    BTW, did you check this? https://github.com/pytransitions/transitions/blob/master/examples/Frequently%20asked%20questions.ipynb https://github.com/pytransitions/transitions/blob/master/exa...
    - dkarp 6y ago
      I did not! I used it last a couple years ago, so maybe that's new. Thanks for sharing!
- davidkpiano 6y ago
  I'm working on XState for Python: https://github.com/davidkpiano/xstate-python https://github.com/davidkpiano/xstate-python Still a work-in-progress, but hope to make this production-ready this year.
  - dzonga 6y ago
    x-state is easily the best js library for modelling state-machines on the front-end. the art is lost to many frontend engineers that UI is a series of states responding to inputs. so yeah, David thanks for your library.
pantulis 6y ago
FSM are the solution to a lot of coding problems that in the beginning just look like bunch of if..thens. Of course, there are a lot of problems that scream "FINITE STATE MACHINE" in their definition, but I'd say that applying FSM early on as a sort of "preemptive optimization" can save a lot of headaches.
- reasonabl_human 6y ago
  Do you have any examples off the top of your head? Haven’t explored this domain
  - slt2021 6y ago
    Actor pattern (akka) is the distributed FSM
    - nahuel0x 6y ago
      Not really, an actor can implement an FSM but it also can have an infinite number of states.
      - slt2021 6y ago
        every non deterministic SM can be converted into FSM: "Using the subset construction algorithm, each NFA can be translated to an equivalent DFA" https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...
        gopiandcode 6y ago
        How is that relevant to the parent's point? Non-determinism has no relation to a system with infinite states, and the NFSM -> FSM construction algorithm provides no help in that case.
  - pantulis 6y ago
    For example an ecommerce order tracking system with different status (in cart, paid, shipped, returned, so on). Spree solves it very elegantly, look at those "events", "transitions". https://github.com/spree/spree/blob/4687e608b49236c2850500b026a9fbbab37dc96c/core/app/models/spree/shipment.rb https://github.com/spree/spree/blob/4687e608b49236c2850500b0... Also, Spree has this nice intro to FSMs https://github.com/Humane-Documentation/Spree/blob/master/related/state_machine.md https://github.com/Humane-Documentation/Spree/blob/master/re...
dragontamer 6y ago
A FSM post without the briefest discussion on Regex? Regex is probably the most common FSM compiler in modern computing. s/find.a.string/replacement/... Yeah, those regex.
andrewla 6y ago
The advice given in the article is to enumerate your states. Since usually when I'm designing an FSM I have an approximate idea of what's required, I find it generally much more instructive to dive right in. Start with the "initial" state and start mapping out transitions -- at each node, list out all the transitions (exhaustively) from that node and assign them states. Walk through the happy path to the terminal state, then start fleshing out the various branches from there. Once you've got the graph, start merging states together as necessary, and since you've been making sure that your transitions are exhaustive at each step, it will be complete. The next step is to step back and look at the entire machine for simplifications, but trying too hard to shoehorn two disparate states into the same state often leads to strange behavior (because transitions from one don't make sense in the other), so it's best to wait until you have some idea of the entire machine before you start combining states.
greenbit 6y ago
Having been both an EE (first) and a software engineer, I have noticed this: as an EE, I would never randomly attack a problem with multiple independent FSMs. Whereas in the s/w realm, I've seen seasoned professionals, without hesitation, do exactly that. I know from University CS training, that s/w engineers most likely all would recognize that any piece of software would, taken as a whole, constitute a single FSM. But as s/w engineers, we usually turn a blind eye toward that fact, seemingly bc there's too much complexity, we perceive the pieces as independent, and need to divide the problems in order to conquer them. This bears some thinking about. For now, just saying, the difference in perspective is interesting
- cube2222 6y ago
  The product of multiple independent state machines is in effect a single state machine.
  - greenbit 6y ago
    Oh absolutely. Part of what I was getting at was that this larger meta-FSM often 'just happens', w/o really being fully intentionally designed. But of course the product that you actually ship is that meta-FSM, so it's the behavior of that thing that matters. Idk, just woolgathering here anyway. One thing that drives me nuts is when people take a linear sequence of code, chop it into little pieces, give each piece to a thread, sometimes give such threads little pieces of other task sequences, then bodge it all back together with various kinds of thread synchronization methods. What you end up with is almost impervious to analysis. So clearly keeping linear sequences of code intact has advantages. Thinking that maybe by thinking about which assemblages of such sequences form relatively independent FSMs, one might, as a s/w developer, be able to make better decisions about how to organize the larger scale structure of software.
- rkangel 6y ago
  I disagree with that - as an EE you almost certainly regularly attack a problem with multiple independent state machines. For example - 3 devices hanging off an I2C bus. Each of those devices will be implementing the I2C state-machine to interpret SCK/SDA. It's a question of what abstraction level you are looking at. In a complex system you need multiple components abstracted from each other and high levels of the system. In those cases, the building blocks will have their own state machine. The same is true in software, although in software it's much easier to reach a high level of complexity. Your average protocol stack (be it IP, LTE, or Bluetooth) is composed of a number of separate layers. These communicate between themselves with messages, and update their internal state-machine. This is a great way to model a system. The same is true in 'closer to hardware' land. An FPGA implementation will often include many explicit state machines, and even more implicit ones.
thangalin 6y ago
I recently released a version of my free and open-source text editor, KeenWrite, that embeds requests to Kroki[0]. Kroki provides a REST API for generating many types of diagrams, including Mermaid diagrams. KeenWrite provides users with the ability to reference variables within the text. Combined, they make it easy to apply the DRY principle to documentation.[1] Even though the request goes over HTTPS, the diagrams are drawn in nearly real-time (and cached). The screenshots show GraphViz diagrams, but changing "graphviz" to "mermaid" at the start of the code block will permit drawing Mermaid diagrams. See the video[2] for more ideas on how to mix variables with documentation. [0]: https://kroki.io/ https://kroki.io/ [1]: https://github.com/DaveJarvis/keenwrite#screenshots https://github.com/DaveJarvis/keenwrite#screenshots [2]: https://www.youtube.com/watch?v=u_dFd6UhdV8 https://www.youtube.com/watch?v=u_dFd6UhdV8

102 points by adlrocha 6y ago

I found languages with TCO even easier to implement FSM in: a state is simply a procedure, and going from one state to another is just a procedure call. The difference is small, but once you start getting hairy state machines I have found that it leads to smaller mental overhead for me. The same would be true for something like a recursive descent parser.

user-the-name 6y ago
That means you are not able to interrupt your state machine easily, or to serialise its state. That might be OK in a lot of cases, but not all.
- hderms 6y ago
  Seems like trampolining would be useful to make it interruptible while still mostly preserving the ergonomics of viewing state transitions as procedure calls
- klibertp 6y ago
  Function objects, including closures, can be serializable - they are in Erlang/Elixir. You can send a lambda/closure over to another node (on another machine) to execute. It's actually one of the basic building blocks of OTP.
  - user-the-name 6y ago
    I assume this only works if the functions are exactly the same. It would break between different versions?
    - rad_gruchalski 6y ago
      It depends. It’s possible to provide a mechanism to switch versions but as it very often is: there are dragons.
- dragonwriter 6y ago
  Serializable closures (even serializable continuations) are available in a number of languages, including probably most often ones which also have TCO.
elviejo 6y ago
What is TCO? what are languages that implement TCO?
- klibertp 6y ago
  Tail Call Optimization, better called Tail Call Elimination. Haskell, OCaml, Erlang/Elixir, Scala with @tailrec, Scheme, Lua(!), most other functional languages. Basically, if there's a call to a function B at the very end of function A, there's no need to create a new stack frame for the call to B - you can reuse the frame created for call to A. It both saves memory and improves performance. A special case is when A and B are both the same function, in which case we say A is tail-recursive.

bestouff 6y ago

I prefer FSM implemented in Rust. Having valid transitions checked at compile time is a life saver as soon as is gets a bit complex - at least in my case being able to "prove" an embedded system wouldn't trigger its watchdog during operation was very important.

natsch 6y ago

> You are now planning to build your next big system as a state machine, Often people don't actively decide to write a state machine, but do so anyway. I think the big takeaway of FSMs is how to recognize them in an idea or implementation and actively using them as a nice abstraction.

surfsvammel 6y ago

FSMs are great! I’ve worked a lot with state machines, in telecom (to model different parts of 4G connections) as well as in capital markets (to model trades, transactions etc.). My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself. FSMs tend to reflect the business domain very closely, are very easy to reason and talk about with non-tech domain experts but also tend to change often. Therefore we have always implemented the framework for the FSM along with some kind of event kernel, and then left the actual setup and configuration of the FSMs to a configuration layer. It has worked very well and has made it so much easier to talk about how the system works with non-techies.

tenaciousDaniel 6y ago
Seems like FSM and DDD would go very well together, although I haven't seen any literature explicitly linking the two.
jgraettinger1 6y ago
> My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself. I really love Rust async/await for this. Under the hood, the compiler is simply assembling a big FSM, and polling a Future is equivalent stepping through allowed transitions which are available to it. You can even use this to build FSMs which are designed to be manually driven, by coordinating generator inputs and outputs via RefCell and one-shot channels and calling `poll` yourself.
youerbt 6y ago
TLA+ is a great example of a modeling tool that allows you to create FSMs relatively easily. It can also check properties of your model which gives more confidence in the final design.

carlbarrdahl 6y ago

How come there isn't better re-usability in state machines? It seems it would be powerful if they were treated as re-usable lego bricks of state and logic. Apps could then pull these in, connect the wires to any potential backend, and style the interactive components.

davidkpiano 6y ago
What makes them reusable is dependent on how you implement them. A state machine that is the simple relation: (state, event) => [state', actions] has a very reusable interface, as long as it doesn't execute the actions (effects, commands, etc.) itself. It's just a pure function that can be used anywhere to get the next state and the actions to execute as a result of receiving an event. Then you can do exactly what you're describing: connect the wires, style the components according to state, etc.
- carlbarrdahl 6y ago
  Thank you David. Your xstate repo on github brought my attention to state machines and state-charts. Which I guess is why I'm interacting with this thread right now. I often wonder what would happen if we could find ways to build complex applications by creating re-usable blocks using state machines (state, logic), json-schemas (structure, data-model), and React* (presentation). All of these are serializable documents. Imagine being able to search a collective collaboration of components and schemas and piece it together. Could probably be graphical interface like Figma. There are certainly other pieces that could be also used (graphql to describe data-fetching, markdown (mdx) for content). *or similar
  - davidkpiano 6y ago
    I'm currently building this! More info to come soon.
- dwohnitmok 6y ago
  You probably are already familiar, but if not, this is exactly the entire concept behind Elm (in fact that signature is exactly the update function at the heart of the Elm architecture). And indeed the Elm community has a lot of ideas on how to split that basic idea to make it reusable.

drummojg 6y ago

Is the letter "T" somehow associated with FSMs? I'm taken right back to one of the hardest assignments I ever had, which was learning C in order to write an interpreter for a FSM descriptor language (called "T") our professor had invented.

ehnto 6y ago
Perhaps T might describe a transition?

pknerd 6y ago

Anyone implemented in Python or Go for production systems?

dkarp 6y ago
I've used https://github.com/pytransitions/transitions https://github.com/pytransitions/transitions in production python systems. It worked great but the system was fairly simple and wasn't changed often. In my opinion, it's nicer when the state machine can be defined as configuration (in XML or whatever) and then generate the code. Unfortunately that's not possible with vanilla pytransitions, but I suppose you could build a layer on top of it.
- pknerd 6y ago
  Interesting! > Unfortunately that's not possible with vanilla pytransitions Can you elaborate?
- pknerd 6y ago
  BTW, did you check this? https://github.com/pytransitions/transitions/blob/master/examples/Frequently%20asked%20questions.ipynb https://github.com/pytransitions/transitions/blob/master/exa...
  - dkarp 6y ago
    I did not! I used it last a couple years ago, so maybe that's new. Thanks for sharing!
davidkpiano 6y ago
I'm working on XState for Python: https://github.com/davidkpiano/xstate-python https://github.com/davidkpiano/xstate-python Still a work-in-progress, but hope to make this production-ready this year.
- dzonga 6y ago
  x-state is easily the best js library for modelling state-machines on the front-end. the art is lost to many frontend engineers that UI is a series of states responding to inputs. so yeah, David thanks for your library.

pantulis 6y ago

FSM are the solution to a lot of coding problems that in the beginning just look like bunch of if..thens. Of course, there are a lot of problems that scream "FINITE STATE MACHINE" in their definition, but I'd say that applying FSM early on as a sort of "preemptive optimization" can save a lot of headaches.

reasonabl_human 6y ago
Do you have any examples off the top of your head? Haven’t explored this domain
- slt2021 6y ago
  Actor pattern (akka) is the distributed FSM
  - nahuel0x 6y ago
    Not really, an actor can implement an FSM but it also can have an infinite number of states.
    - slt2021 6y ago
      every non deterministic SM can be converted into FSM: "Using the subset construction algorithm, each NFA can be translated to an equivalent DFA" https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...
      - gopiandcode 6y ago
        How is that relevant to the parent's point? Non-determinism has no relation to a system with infinite states, and the NFSM -> FSM construction algorithm provides no help in that case.
- pantulis 6y ago
  For example an ecommerce order tracking system with different status (in cart, paid, shipped, returned, so on). Spree solves it very elegantly, look at those "events", "transitions". https://github.com/spree/spree/blob/4687e608b49236c2850500b026a9fbbab37dc96c/core/app/models/spree/shipment.rb https://github.com/spree/spree/blob/4687e608b49236c2850500b0... Also, Spree has this nice intro to FSMs https://github.com/Humane-Documentation/Spree/blob/master/related/state_machine.md https://github.com/Humane-Documentation/Spree/blob/master/re...

dragontamer 6y ago

A FSM post without the briefest discussion on Regex? Regex is probably the most common FSM compiler in modern computing. s/find.a.string/replacement/... Yeah, those regex.

andrewla 6y ago

The advice given in the article is to enumerate your states. Since usually when I'm designing an FSM I have an approximate idea of what's required, I find it generally much more instructive to dive right in. Start with the "initial" state and start mapping out transitions -- at each node, list out all the transitions (exhaustively) from that node and assign them states. Walk through the happy path to the terminal state, then start fleshing out the various branches from there. Once you've got the graph, start merging states together as necessary, and since you've been making sure that your transitions are exhaustive at each step, it will be complete. The next step is to step back and look at the entire machine for simplifications, but trying too hard to shoehorn two disparate states into the same state often leads to strange behavior (because transitions from one don't make sense in the other), so it's best to wait until you have some idea of the entire machine before you start combining states.

greenbit 6y ago

Having been both an EE (first) and a software engineer, I have noticed this: as an EE, I would never randomly attack a problem with multiple independent FSMs. Whereas in the s/w realm, I've seen seasoned professionals, without hesitation, do exactly that. I know from University CS training, that s/w engineers most likely all would recognize that any piece of software would, taken as a whole, constitute a single FSM. But as s/w engineers, we usually turn a blind eye toward that fact, seemingly bc there's too much complexity, we perceive the pieces as independent, and need to divide the problems in order to conquer them. This bears some thinking about. For now, just saying, the difference in perspective is interesting

cube2222 6y ago
The product of multiple independent state machines is in effect a single state machine.
- greenbit 6y ago
  Oh absolutely. Part of what I was getting at was that this larger meta-FSM often 'just happens', w/o really being fully intentionally designed. But of course the product that you actually ship is that meta-FSM, so it's the behavior of that thing that matters. Idk, just woolgathering here anyway. One thing that drives me nuts is when people take a linear sequence of code, chop it into little pieces, give each piece to a thread, sometimes give such threads little pieces of other task sequences, then bodge it all back together with various kinds of thread synchronization methods. What you end up with is almost impervious to analysis. So clearly keeping linear sequences of code intact has advantages. Thinking that maybe by thinking about which assemblages of such sequences form relatively independent FSMs, one might, as a s/w developer, be able to make better decisions about how to organize the larger scale structure of software.
rkangel 6y ago
I disagree with that - as an EE you almost certainly regularly attack a problem with multiple independent state machines. For example - 3 devices hanging off an I2C bus. Each of those devices will be implementing the I2C state-machine to interpret SCK/SDA. It's a question of what abstraction level you are looking at. In a complex system you need multiple components abstracted from each other and high levels of the system. In those cases, the building blocks will have their own state machine. The same is true in software, although in software it's much easier to reach a high level of complexity. Your average protocol stack (be it IP, LTE, or Bluetooth) is composed of a number of separate layers. These communicate between themselves with messages, and update their internal state-machine. This is a great way to model a system. The same is true in 'closer to hardware' land. An FPGA implementation will often include many explicit state machines, and even more implicit ones.

thangalin 6y ago

I recently released a version of my free and open-source text editor, KeenWrite, that embeds requests to Kroki[0]. Kroki provides a REST API for generating many types of diagrams, including Mermaid diagrams. KeenWrite provides users with the ability to reference variables within the text. Combined, they make it easy to apply the DRY principle to documentation.[1] Even though the request goes over HTTPS, the diagrams are drawn in nearly real-time (and cached). The screenshots show GraphViz diagrams, but changing "graphviz" to "mermaid" at the start of the code block will permit drawing Mermaid diagrams. See the video[2] for more ideas on how to mix variables with documentation. [0]: https://kroki.io/ https://kroki.io/ [1]: https://github.com/DaveJarvis/keenwrite#screenshots https://github.com/DaveJarvis/keenwrite#screenshots [2]: https://www.youtube.com/watch?v=u_dFd6UhdV8 https://www.youtube.com/watch?v=u_dFd6UhdV8