3 ms·
These are some pretty cool examples, though a little too nitty gritty to communicate the practical importance of state machines. The truth is, state machines ar
by amw-zero 6y ago
These are some pretty cool examples, though a little too nitty gritty to communicate the practical importance of state machines. The truth is, state machines are so fundamental that programmers are not even aware that they are using them. Many, if not most, computer programs can be seen as state machines. In fact, programming can quite literally be seen as state machine creation and management. Programming languages are tools for creating complex state machines without having to manually wire them together.
For example, take the following factorial function in Python:
def factorial(n):
result = 1
while n > 1:
result *= n
n -= 1
return result
Here is a TLA+ spec for the same algorithm, along with the corresponding state diagram for calculating factorial(5): https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c632147 https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c6.... This is a simple example, but the state diagram illustrates an important point that the while loop doesn't: the algorithm is completely linear, meaning it simply builds upon previous states. Even though there is branching in the code, there is no branching in the state diagram.
Of course, we're not so lucky and most state spaces are not linear. Here's the spec and diagram for a user interface that I was building a while back: https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85cb93bd https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85c.... There was a subtle state-based bug where a user had to perform a special sequence of events to experience it. The code seemed simple, but looking at the state diagram directly showed what the bug was immediately.
This was in a React app, and doing this exercise made me realize that React apps trivially translate to state machines as well. Whenever you call `setState` or the corresponding `setHookValue` function when using hooks, you are defining a state transition. The set of all state variables determines the full state space of the application, and bugs arise when we forget to consider that fact within some of our transition functions.
Long story short, you don't need to use a state machine design pattern such as Xstate to actually have a state machine. In fact, unless you are doing some very weird things, your application most likely already is a state machine under it all, but that's only because a state machine is a very simple, general concept that has tons of applications.
- arcbyte 6y agoYup. Basically all enterprise software is just state machine design. Any simple RESTFUL app with a database is just a state machine. Call one end point to create a resource, fetch it later from a second. Calling them out of order yields an error state. Super simple state machine. Of course we've reinvented this wheel so many times. Something like LISP is fun because you can get both the executable and (human AND machine) readable representations of a state machine out of the exact same source code. Thats still the future of programming.
- amw-zero 6y agoWe’ve reinvented the wheel because CS education is really bad at teaching what computation actually is. Then, if you did not study CS (which I did not so I know), you’re really on your own for figuring out what the heck you’re actually doing when you program. There are some very simple and elegant concepts at the bottom of the chain that are really useful to understand, and state machines are for sure one of them. Even with state machines, people often dislike talking about them because they’re seen as impractical since they don’t always have a great correspondence to code. But computation is more than just code.
- the_cat_kittles 6y agoi think this has always subconsciously confused me whenever people talk about state machines, and your comment clarifies what i think ive felt. what would qualify as not a state machine in the broad sense?
- amw-zero 6y agoThat’s a great question. Combinational logic is an example of something that computes that isn’t a state machine. You can compute Boolean algebra operations with no notion of time, they’re essentially pure functions. That’s where it gets slightly confusing though. Just because a function is pure, does not mean that its implementation is not a state machine. For example, an algorithm to compute the greatest common denominator between two numbers is stateful, even if it has a pure functional interface.