5 ms·

In software, it’s rare that two states can be transitioned between synchronously. Or at least, modeling a problem in terms of states that have synchronous trans

by rcme 4y ago

In software, it’s rare that two states can be transitioned between synchronously. Or at least, modeling a problem in terms of states that have synchronous transitions is hard. Waiting for user input, making a network request, disk IO, etc. are all asynchronous. This makes it annoying to design a state machine. Just as an example, imagine you have two states you want to model, A and B. Let’s say the transition between A and B requires 3 async operations. You then need 8 total states: A, A_before_step_1, A_before_step_2, A_before_step3, B, B_before_step_1, B_before_step_2, and B_before_step_3. It just becomes totally unmanageable.

AgentOrange1234 4y ago
Can’t you still just model A and B, and have your transitioning logic compute and wait for whatever is necessary to make the full transition? If you keep the ephemeral stuff in aux memory, you can have keep your number of states more manageable.
- rcme 4y ago
  No, because resources are limited. Like if a user indicates they want to go from A to B, and then half way thorough the transition decides they want to go back to A, then you need to cancel and clean up everything for the transition to B. Otherwise you’re wasting battery, network bandwidth, main thread cycles, etc. on useless work.
ericmcer 4y ago
I would just consider all those intermediary states as one “loading” state. It is pretty simple to have a “loading” and “error” state in addition to your other ones.
- jayd16 4y ago
  If you do that then you can't pipeline the response handling and you can't show loaded data until you fully transition to B. Any error would equate to every error. You could have your loading state handle every little detail but then what was the point of the state machine anyway?
ratorx 4y ago
Surely only if you need to name each state and define every transition. However a sparse representation would be useful here right? If there are fundamentally transitions that are impossible (or errors) then just only define the transitions that make sense and have the rest map to a error condition if they ever come up. Also, if the state space is factorisable (like in your example) then it is easy to represent. You never need to name every state separately if e.g. you use 2 enums (or more generally a GADT) instead of trying to fit it all into 1 variable for every possible state.
- rcme 4y ago
  No, you need to represent every state. Like let’s say there are two async operations: a disk read, then a network request. When you transition, you need to know: did I start the disk read? If yes, cancel the disk read if it’s pending. Did the network request start? If it started but didn’t finish, then cancel it. So you can see that there is a huge amount of state you need to operate on that’s not directly captured by states A and B.
  - dustingetz 4y ago
    now add concurrency, the system state is a superposition of concurrent transitions
    - funcDropShadow 4y ago
      Finite state machines are an ideal mechanism to with concurrency if you put a concurrent queue in front of them. Such a program is easily coded with Akka's FSM trait. It even adds the possibility to trigger transition based on timer. As soon as you are in the realm of time sensitive programs, i.e. because of network requests, this is a very powerful and easy to understand way to program complicated parts of programs.
      - dustingetz 4y ago
        for others: https://doc.akka.io/docs/akka/current/typed/fsm.html https://doc.akka.io/docs/akka/current/typed/fsm.html https://doc.akka.io/docs/akka/current/typed/persistence-fsm.html#eventsourced-behaviors-as-finite-state-machines https://doc.akka.io/docs/akka/current/typed/persistence-fsm.... Is ^ demonstrating the equivalence between FSMs and event streams? or are they not quite identical just closely related?
jjtheblunt 4y ago
Those regexes that are ubiquitous are called regular expressions because they describe “regular languages” (qv), which are recognized by nondeterministic finite automata, which are converted to deterministic finite automata by fun with powersets, which are compiled into software state machines behind the abstraction of the regex libraries. So they are not at all rare but not exposed to programmers explicitly.
- lmm 4y ago
  Almost all "regexes" in programming languages are not actually regular expressions and do not have the properties you describe. (I'd argue that this is one of the clearest demonstrations that programmers do not put a lot of value of state machines)
  - jjtheblunt 4y ago
    Yes definitely a different thing when talking about ‘extended regex’ libraries, wrt to the regular languages (language class) and associates recognizers. That said, even modern pcre uses state machines https://github.com/rurban/pcre/blob/master/src/pcre2_dfa_match.c https://github.com/rurban/pcre/blob/master/src/pcre2_dfa_mat...
_gabe_ 4y ago
> This makes it annoying to design a state machine. Annoying sure, but necessary right? With or without a state machine you have to handle all the states, and if you don't bother quantifying all possible states of your model and just winging it, it's not like those extra transition states magically disappear. Instead you just run into weird multithreading bugs and after banging your head against the wall for 5 hours you realize you forgot about a transitory state And just to clarify, I don't mean handling every single state possible, because that's most likely infinite. But if you specify a finite number of states your app can be in, and then mark the invalid transitions to take you to an invalid state, then you can figure out when your app is in an invalid state immediately instead of having the weird bugs crop up randomly.
- rcme 4y ago
  > Annoying sure, but necessary right? No, not necessary. The key insight here is that the transitions are the hard part. One way to solve this is to write your transitions as a series of asynchronous steps that feed into each other. The end result is an asynchronous chain of operations. E.g. if you have a video app, playing a video might look like: 1) Read the user metadata from disk. 2) Use the user metadata to make a network request for the video metadata. 3) Deserialize the video metadata on a background thread. 4) Present the video player with the video metadata on the main thread. You compose each step into a chain of operations. Each step in the chain contains async work as well as logic that “cleans up” the work. So when you want to play a video, your code says “start the complicated video chain.” When you want to stop the video, your code says “stop the video chain.” The chains are a generic sequence of steps, so they can be stopped in the middle. Each step contains its own cleanup logic, so the cleanup of any pending work can happen automatically upon stopping the chain. tldr: “state” the user is in at any given time is so complex that it’s impossible model with a state machine. It’s easier to think of cascading asynchronous steps instead. A good library for writing this kind of code is called Rx.
  - joshka 4y ago
    It's been a while since I wrote any Rx in earnest, but when I did, it was useful to look at it as almost exactly what you'd end up if you incorporated time (via ordered streams/publishers/observers/etc.) into a model that represents a state machine model. That is to say, you can kinda both be right here. ;)
osigurdson 4y ago
>> transition between A and B requires 3 async operations Couldn't you do the equivalent of a join to transition to B?
taeric 4y ago
This is one that you can actually get a lot better mileage by introducing a new state machine, oddly. You have the states A and B, but you also have the state machine for the transition that is T1, T2, and T3. In this world, you have 5 things you need to be able to render/model. A, B, T1, T2, and T3. That the T things will be modeled/rendered inside either A or B can usually be irrelevant. Even better, if you picked the right abstraction for the T state machine, that same set of modeling can be used elsewhere. (Note, no panacea. You can still pick the wrong abstractions here. Or one that just doesn't help you later, even if it isn't wrong.) And this is exactly how it is in the physical world. The "payment acceptor" state machine of a vending machine is independent of the vending aspect of the vending machine. It is there solely to create the signal of "payment received" to the machine. Whether that comes from coins, credit cards, phone taps, whatever.

by rcme 4y ago

AgentOrange1234 4y ago

Can’t you still just model A and B, and have your transitioning logic compute and wait for whatever is necessary to make the full transition? If you keep the ephemeral stuff in aux memory, you can have keep your number of states more manageable.

rcme 4y ago
No, because resources are limited. Like if a user indicates they want to go from A to B, and then half way thorough the transition decides they want to go back to A, then you need to cancel and clean up everything for the transition to B. Otherwise you’re wasting battery, network bandwidth, main thread cycles, etc. on useless work.

ericmcer 4y ago

I would just consider all those intermediary states as one “loading” state. It is pretty simple to have a “loading” and “error” state in addition to your other ones.

jayd16 4y ago
If you do that then you can't pipeline the response handling and you can't show loaded data until you fully transition to B. Any error would equate to every error. You could have your loading state handle every little detail but then what was the point of the state machine anyway?

ratorx 4y ago

Surely only if you need to name each state and define every transition. However a sparse representation would be useful here right? If there are fundamentally transitions that are impossible (or errors) then just only define the transitions that make sense and have the rest map to a error condition if they ever come up. Also, if the state space is factorisable (like in your example) then it is easy to represent. You never need to name every state separately if e.g. you use 2 enums (or more generally a GADT) instead of trying to fit it all into 1 variable for every possible state.

rcme 4y ago
No, you need to represent every state. Like let’s say there are two async operations: a disk read, then a network request. When you transition, you need to know: did I start the disk read? If yes, cancel the disk read if it’s pending. Did the network request start? If it started but didn’t finish, then cancel it. So you can see that there is a huge amount of state you need to operate on that’s not directly captured by states A and B.
- dustingetz 4y ago
  now add concurrency, the system state is a superposition of concurrent transitions
  - funcDropShadow 4y ago
    Finite state machines are an ideal mechanism to with concurrency if you put a concurrent queue in front of them. Such a program is easily coded with Akka's FSM trait. It even adds the possibility to trigger transition based on timer. As soon as you are in the realm of time sensitive programs, i.e. because of network requests, this is a very powerful and easy to understand way to program complicated parts of programs.
    - dustingetz 4y ago
      for others: https://doc.akka.io/docs/akka/current/typed/fsm.html https://doc.akka.io/docs/akka/current/typed/fsm.html https://doc.akka.io/docs/akka/current/typed/persistence-fsm.html#eventsourced-behaviors-as-finite-state-machines https://doc.akka.io/docs/akka/current/typed/persistence-fsm.... Is ^ demonstrating the equivalence between FSMs and event streams? or are they not quite identical just closely related?

jjtheblunt 4y ago

Those regexes that are ubiquitous are called regular expressions because they describe “regular languages” (qv), which are recognized by nondeterministic finite automata, which are converted to deterministic finite automata by fun with powersets, which are compiled into software state machines behind the abstraction of the regex libraries. So they are not at all rare but not exposed to programmers explicitly.

lmm 4y ago
Almost all "regexes" in programming languages are not actually regular expressions and do not have the properties you describe. (I'd argue that this is one of the clearest demonstrations that programmers do not put a lot of value of state machines)
- jjtheblunt 4y ago
  Yes definitely a different thing when talking about ‘extended regex’ libraries, wrt to the regular languages (language class) and associates recognizers. That said, even modern pcre uses state machines https://github.com/rurban/pcre/blob/master/src/pcre2_dfa_match.c https://github.com/rurban/pcre/blob/master/src/pcre2_dfa_mat...

_gabe_ 4y ago

> This makes it annoying to design a state machine. Annoying sure, but necessary right? With or without a state machine you have to handle all the states, and if you don't bother quantifying all possible states of your model and just winging it, it's not like those extra transition states magically disappear. Instead you just run into weird multithreading bugs and after banging your head against the wall for 5 hours you realize you forgot about a transitory state And just to clarify, I don't mean handling every single state possible, because that's most likely infinite. But if you specify a finite number of states your app can be in, and then mark the invalid transitions to take you to an invalid state, then you can figure out when your app is in an invalid state immediately instead of having the weird bugs crop up randomly.

rcme 4y ago
> Annoying sure, but necessary right? No, not necessary. The key insight here is that the transitions are the hard part. One way to solve this is to write your transitions as a series of asynchronous steps that feed into each other. The end result is an asynchronous chain of operations. E.g. if you have a video app, playing a video might look like: 1) Read the user metadata from disk. 2) Use the user metadata to make a network request for the video metadata. 3) Deserialize the video metadata on a background thread. 4) Present the video player with the video metadata on the main thread. You compose each step into a chain of operations. Each step in the chain contains async work as well as logic that “cleans up” the work. So when you want to play a video, your code says “start the complicated video chain.” When you want to stop the video, your code says “stop the video chain.” The chains are a generic sequence of steps, so they can be stopped in the middle. Each step contains its own cleanup logic, so the cleanup of any pending work can happen automatically upon stopping the chain. tldr: “state” the user is in at any given time is so complex that it’s impossible model with a state machine. It’s easier to think of cascading asynchronous steps instead. A good library for writing this kind of code is called Rx.
- joshka 4y ago
  It's been a while since I wrote any Rx in earnest, but when I did, it was useful to look at it as almost exactly what you'd end up if you incorporated time (via ordered streams/publishers/observers/etc.) into a model that represents a state machine model. That is to say, you can kinda both be right here. ;)

osigurdson 4y ago

>> transition between A and B requires 3 async operations Couldn't you do the equivalent of a join to transition to B?

taeric 4y ago

This is one that you can actually get a lot better mileage by introducing a new state machine, oddly. You have the states A and B, but you also have the state machine for the transition that is T1, T2, and T3. In this world, you have 5 things you need to be able to render/model. A, B, T1, T2, and T3. That the T things will be modeled/rendered inside either A or B can usually be irrelevant. Even better, if you picked the right abstraction for the T state machine, that same set of modeling can be used elsewhere. (Note, no panacea. You can still pick the wrong abstractions here. Or one that just doesn't help you later, even if it isn't wrong.) And this is exactly how it is in the physical world. The "payment acceptor" state machine of a vending machine is independent of the vending aspect of the vending machine. It is there solely to create the signal of "payment received" to the machine. Whether that comes from coins, credit cards, phone taps, whatever.