6 ms·

Developers should be force-fed state machines (2011)

92 points by signa11 4y ago

awelxtr 4y ago
Have you noticed that the article from 2011 is sporting an image of vscode released on 2015? I mean, should they at least acknowledge the change of header?
giovannibonetti 4y ago
Many popular computer languages in use make state machines unergonomic. The problem is solved with native enumerated types or, even better, tagged unions, like Rust and functional languages from the ML family (Haskell, Ocaml, Elm). It is a joy working with state machines when you have a compiler that can verify exhaustively wheter all states and state transitions are handled.
- cal85 4y ago
  I've only really used state machines in TypeScript via xstate, and I've been meaning to try Rust for a while, so your comment interests me. Got any tips or advice on further reading or specific libs that you can recommend for working with FSMs in Rust?
  - giovannibonetti 4y ago
    I don't have much Rust-specific experience, but I wonder if you need a library for this when the language/compiler is doing all the heavy lifting. When working with Elm, for example, that uses that a lot for the Model-View-Update framework, you just define your model states and pattern match them to build the view and update functions.
  - giraffe_lady 4y ago
    Look at how you'd do it in f#, ocaml, or elm first imo. The type systems of those languages allow for a very tight approach with no confounding factors. The way rust does it is the same, but with more details leaked in from the constraints rust imposes. Which is fine, but I think it's valuable to see the "pure" stripped back form in a language almost perfectly suited to it first.
- orwin 4y ago
  Symbolic languages make it trivial. The only really complex state machine i ever wrote was in lisp (it was an IA for a game). Not the most intelligent IA, but a breath to write. The only feature a language really need to make usable state machines are closures.
- andrewjl 4y ago
  There are some interesting approaches in Swift: https://github.com/apple/swift/blob/main/stdlib/public/Observation/Sources/Observation/ObservationRegistrarStateMachine.swift https://github.com/apple/swift/blob/main/stdlib/public/Obser... https://github.com/apple/swift/blob/main/stdlib/public/Observation/Sources/Observation/ObservationRegistrar.swift https://github.com/apple/swift/blob/main/stdlib/public/Obser...
lloydatkinson 4y ago
I strongly agree with this. So many parts of systems are just poorly implemented finite state machines without knowing it. I wrote this on how to use FSM's in .NET https://www.lloydatkinson.net/posts/2022/modelling-workflows-with-finite-state-machines-in-dotnet/ https://www.lloydatkinson.net/posts/2022/modelling-workflows...
winstonprivacy 4y ago
State machines are a good solution when you have a typical transactional business process (order fulfillment, inventory management, etc). But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. For instance, let's say that are trying to execute a complex spread in the market. You might be partially filled on one leg (the timing of which is completely out of your control, if it happens at all). Then this needs to spawn an offsetting trade (or two), both of which may or may not be completely filled over multiple tickets. Super messy. A naive state machine simply doesn't work for this, as the overall unit of work (a "trade") can have multiple sub-states all operating more or less independently of one another. Are there well-known patterns to handle such situations?
- Bjartr 4y ago
  In terms of specific implementation I'm not sure, but it may be possible to use a formal modeling tool like TLA+ to prove a particular approach only results in outcomes you consider correct. So you could try to model the trade and all the sub states you mention in a naive state machine way, then check if that super messy tangle works as intended or if it has incorrect behavior.
- rubyfan 4y ago
  Can you share what your current solution looks like for something like that? > But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. Your comment resonated with me relative to regulated financial services where a relationship with a customer has many states can can be independent or intertwined depending on regulatory environment and subject matter i.e. status and renewal of terms of a contract/agreement, billing/payment, different pricing revisions, etc.
  - winstonprivacy 4y ago
    Basically, lots of if...else statements combined with coroutines. Refactoring out as many big blocks of code helps a bit, but there's always yet another exception lurking in the shadows, waiting to show up at the least opportune time (such as when the system is under stress).
goodpoint 4y ago
"force-fed" is a bit distasteful tho.
jasfi 4y ago
The gem they link to hasn't been updated for the last 10 years. State machines get a lot of praise, but seem scarce in practice. Perhaps there are practical problems with using them in the long term?
- Pamar 4y ago
  Not that I am aware of, apart from the problem of implementation and design/documentation starting to drift apart ... but as you surely know this is not a problem with SM per se.
  - jasfi 4y ago
    I was thinking of more along the lines of specialized framework and libraries for state machines. Perhaps those aren't necessary.
- JohnFen 4y ago
  I don't think so. About half of the programs (both new and old) I've worked with have used state machines, and I haven't noticed any long-term problems with them aside from the usual long-term problems with code generally.
muhehe 4y ago
I keep seeing "use statemachine", but it all seems very abstract to me. How would you "use statemachine" in, let's say python? Is there some library, or is more of a conceptual thing for code organization? This is probably stupid question but I can't really grasp what I should do. I'd like to because I'm currently tasked to create something like order system, which could benefit from this, but I don't know where to start.
- Balladeer 4y ago
  For typical use cases, you're probably persisting the data, so I'll assume your use case is "Python with a database ORM like Django or SQLAlchemy". The really short version of "use statemachine" is: store a single, explicit state for every 'thing' and create a log row every time that state changes. - Make a python model / database table to represent "the things whose state can change" (like an Order or a Task). - Give each a unique id and a 'state' column that is either a text field or an enumerated type (or a foreign key to a 'valid_states' table if you want to get fancy). Do this _instead_ of adding boolean columns like 'is_completed' or 'is_deleted'. - Create a log table with the same columns as your Order table -- whenever you update an Order's state (or create a new one), add a new row to the log table with the new state and a timestamp. Now your 'Order' table shows the current state of every Order, while your log table shows every state that every Order has ever been in, which will come in _super_ handy for analytics later. Everything else can be built on top of the above: - defining valid states and their transitions (aka formalizing the state machine) - preventing 'invalid' transitions if you want - creating analytics tables to show the 'typical' flow of an Order (e.g. columns like 'creation_date', 'payment_date', 'ship_date', 'return_date') - triggering other systems when Orders enter or leave a given state - etc
- JohnFen 4y ago
  A state machine is a technique. It is not language-dependent. There might be libraries to encapsulate the mechanics of state machines -- I don't know, though, because I find the mechanics of creating them easy enough that I never felt the need to seek out a library to support them. I'd recommend reading up about them on the web. Here's a reasonable start: https://www.freecodecamp.org/news/state-machines-basics-of-computer-science-d42855debc66/ https://www.freecodecamp.org/news/state-machines-basics-of-c... In their purest form, though, state machines are very simple. You have a conceptual "state" represented by a variable, then what amounts to a series of if-then statements (or a switch statement like in C/C++). The state machine consists of a loop, each iteration checking the current state (1, 2, 3, etc.) and performing the actions associated with that state. Then the state is changed as appropriate and the loop continues. So you have something like "If the state is "Starting", then do initialization things and change the state variable to "Running". If the state is "Running", do some business logic. If it's time to quit, change the state to "Stopping". If the state is "Stopping", free up resources and stop execution."
GuB-42 4y ago
Like the GoF design patterns, knowing about state machines is important, but whether or not you should use them in their "pure" form depends on the problem at hand. State machine make for some the least readable code I have written and an ad-hoc solution could have been more appropriate. The difficulties I have with state machines is, as usual, side effects. That is, implementing the state transition logic is usually straightforward, but more often than not, there is something you want to do between these states, typically I/O. In a pure framework, it manifests as a hidden, extra state, for witch the "right" thing to do is to make it explicit, and you may end up with a monster state and transitions all over the place. I have written a few of these monsters, and while I think it is partly the result of inherent complexity, I must say it is not the code I am the most proud of. In other situations, state machines were a perfect match, but like everything else, just because the problem can be modeled with a state machine doesn't mean it should.
- Cthulhu_ 4y ago
  One great example of state machines being used in the wild is in video games, e.g. playable and non-playable characters; for a simple 2D game, a player could be in a state "moving left", "right", "jumping", "falling", etc. Although it might quickly become a case where two states can be active (jumping & shooting), or there's different states for different things (e.g. animation state separate from movement state).
- giraffe_lady 4y ago
  I do some work in ocaml where state machines are popular I think because of how cleanly they map onto the language constructs. One common approach is the elm-ish move of having the machine fn return a pair of (new state, action). Then you have an intermediate fn run the side effects, but you can implement that somewhere else and mostly pretend it's not there. React reducers are kind of like this too. When doing this though like you said you always either find there are more states than you initially thought, or you end up having pseudostates only for their effects. I pretty much only reach for state machines when I know the inputs will never change and I'll never have to modify the implementation. Even in a language almost perfectly suited for them they are hard to understand once they're doing all the edge cases and side effects and edge cases of the side effects and error handling etc etc.
jnmandal 4y ago
A lot of this comes down to the clunkiness in high level programming languages. We will have all sorts of abstractions over enumeration and collections yet for some reason few languages seek to include niceties for state machines in their stdlibs.
JohnFen 4y ago
I'm genuinely surprised and more than a little shocked and concerned that there are developers out there who are unfamiliar with state machines and their use. I think of state machines as being foundational knowledge, like sorting algorithms, b-trees, etc.
- knsv 4y ago
  I fully agree! When designing solving a problem it great to take a step back and think through the states you can end up in. Although it is easy to make the machine overly complex when you have "multi-dimensional" states unless to are a little bit carful with how you model it.
- physicles 4y ago
  I’d argue they’re more foundational. If some code could use a b-tree but the dev doesn’t know about them, they can’t do much damage — they’ll use a less optimal tree. If some code needs a state machine but the dev doesn’t know about them, that code will have so many bugs.
dang 4y ago
Discussed at the time: Why developers should be force-fed state machines - https://news.ycombinator.com/item?id=2649162 https://news.ycombinator.com/item?id=2649162 - June 2011 (50 comments)
deterministic 4y ago
Game developers use state machines all the time.
AstixAndBelix 4y ago
Developers should be force fed nothing, because they "chose" to not follow a formal education. Almost everything I see in these blog posts is stuff I was already taught at college (or very adjacent). If you want developers to know about this stuff stop encouraging people to go to code bootcamps and start making SWE curricula more palatable and end this idea that college is a scam that teaches you nothing
- gpderetta 4y ago
  If you can learn this stuff in college it is great, but you can also learn it on your own.
- redeux 4y ago
  I’m glad this was your experience, but your school’s CS curriculum isn’t universal. I was once chatting with a jr sw engineer that had recently graduated from a respectable state university with a CS degree about which database would be optimal for our upcoming project. He confided in me that he hadn’t taken the DB course in school because he heard bad things about the professor who taught it. I was absolutely blown away. The moral of the story is that your shouldn’t assume that just because someone has a CS degree that they have knowledge of all the fundamental areas.
  - lightbendover 4y ago
    Databases were not part of my CS curriculum until I took an elective web development course at the very end. People struggled. I had been doing hobbyist web development since I was quite young so the whole class was a breeze for me, but I understand that for those who are only taught the fundamentals and theory, anything pragmatic can feel daunting. I'm sure curriculums have changed greatly since I went through (KV/graph stores were not yet adopted, distributed DBs were merely a thought), but it still doesn't feel quite right for faulting a student for choosing certain classes or not being perfectly suited for learning a given domain instantly.
    - redeux 4y ago
Manfred 4y ago
I do have a pet peeve related to this and some observations. Sometimes developers call their variable or method state_machine, that's akin to calling your variable variable. You should be descriptive in what you are modeling as a state machine. I have also seen developers attempt to track external state using a state machine when they had no way to guarantee that the external state actually behaved that way. It becomes a really big mess. Especially when you are interested in the time of a change (or the person making the change), it's very often useful log the state transitions in a separate database table.
- prettyStandard 4y ago
  My rule of thumb is if you think the variable type may be useful to others reading your code, append it to the end. This is generally useful if you have the same data going through different forms. Let's see if I can write something, that others understand with no context. //For this example let's ignore the nuances of names. function (nameUserinput) { if(isValidName(nameUserinput)) { return processName(nameUserinput)) } else { return { first: '', middle: '', last: '' } } } function isValidName () { return (containsAtLeastOneSpace(nameUserinput) && containsLessThanThreeSpaces(nameUserinput) && hasThreeOrMoreCharacters(nameUserinput) && noSpacesOnEnd(nameUserinput)) } function processName (nameUserinput) { const nameObj = { middle: '' }; const nameUserinputArray = nameUserinput.split(' '); if(nameUserinputArray.length = 2) { [nameObj.first, nameObj.last] = nameUserinputArray; } else if(nameUserinputArray.length = 3) { [nameObj.first, nameObj.middle, nameObj.last] = nameUserinputArray; } } nameObj and nameUserinput and nameUserinputArray are all the same data in different forms. I think it's helpful to start them with the same prefixes, but change the suffix with the type to communicate that. You could imagine taking this a step further, with nameStatemachine. You might chart a person's course through life, do they go to law school, medical school, get married etc. I've been meaning to write a blog post on this. But this does follow my most important words first rule. You'll see a lot of similarities there, just not on this exact topic. https://soft-wa.re/naming-conventions/ https://soft-wa.re/naming-conventions/
  - 4y ago
samsquire 4y ago
When I think that you can see the memory of a program and the execution of instructions as a state machine just a very large one. I am trying to design a state machine representation/notation that handles the transitions of multiple complicated objects over time and between threads and machines. I want a good notation for state machines that is similar to EBNF. I think rule engines become relevant when you think about complicated transitions of business processes. I settled on this, it is inspired by prolog. It represents the state progression of an async/await thread pool and parallel state machines and forking and joining state machines. A and B is a task variable and 1 is a thread number. The pipe symbol represents a transition from a group of states, all previous facts must match before progressing. next_free_thread = 2 task(A) thread(1) assignment(A, 1) = running_on(A, 1) | paused(A, 1) running_on(A, 1) thread(1) assignment(A, 1) thread_free(next_free_thread) = fork(A, B) | send_task_to_thread(B, next_free_thread) | running_on(B, 2) paused(B, 1) running_on(A, 1) | { yield(B, returnvalue) | paused(B, 2) } { await(A, B, returnvalue) | paused(A, 1) } | send_returnvalue(B, A, returnvalue) I actually worked on a BPMN project once. The idea of this syntax is that your code would be reactive and you would have an API to retract or publish facts. The state machine handles scheduling.
- discarded1023 4y ago
  > I want a good notation for state machines that is similar to EBNF. If this isn't a firm requirement, perhaps you can dig into the venerable state machine notations of yesteryear. For instance ARGOS [1] and StateCharts [2]. The latter got incorporated into UML somehow [3] IIRC. Esterel [4] is a bit mind blowing. Other people prefer dataflow, in which case Lustre [5] might be worth a look. These make a strong synchrony hypothesis which may or may not apply to your situation. But if it does you're in clover. And if you're not you can still try to use this stuff in a GALS [6] architecture. [1] https://dl.acm.org/doi/10.1016/S0096-0551%2801%2900016-9 https://dl.acm.org/doi/10.1016/S0096-0551%2801%2900016-9 (and google some more) [2] https://statecharts.dev/ https://statecharts.dev/ [3] https://en.wikipedia.org/wiki/UML_state_machine https://en.wikipedia.org/wiki/UML_state_machine [4] https://en.wikipedia.org/wiki/Esterel https://en.wikipedia.org/wiki/Esterel [5] https://en.wikipedia.org/wiki/Lustre_(programming_language) https://en.wikipedia.org/wiki/Lustre_(programming_language) [6] https://en.wikipedia.org/wiki/Globally_asynchronous_locally_synchronous https://en.wikipedia.org/wiki/Globally_asynchronous_locally_...
probably_wrong 4y ago
I have exactly one negative thing to say about state machines: they are difficult to understand when all you have is the implementation, which makes them difficult to update. My solution is typically to include an ASCII drawing of the state diagram in the comments, which I never really liked as a solution for reasons I can't explain. But I also think that this is a fair price to pay when the alternative is a jungle of "if condition1 and not condition2...".
- stinos 4y ago
  they are difficult to understand when all you have is the implementation, which makes them difficult to update I don't really have that issue, could you give an example? I typically write them with a helper like (not web app, but shouldn't matter) fsm.In(State.Idle).When(Command.SomeStuffHappened).GoTo(State.Foo).WithTransition(InitiateRun); fsm.In(State.Idle).When(Command.OtherStuffHappened).GoTo(State.Bar).WithTransition(InitiateRun); ... fsm.In(State.Foo).When(Command.FooAborted).GoTo(State.Idle) ... which for me is a lot easier to reason about than reasoning about state generally is (i.e, very hard especially if you have to look at the combination of a couple of state variables and then also have to take preconditions into account, god forbid other threads, well, you know the drill probably:)
  - giraffe_lady 4y ago
    I think there is kind of a figure/ground effect where there's two ways of looking at a given state machine but it's impossible to hold both in your mind at the same time. You're either thinking about the "path through" and the effects along the way, or you're looking at a single state and its valid transitions. Both are both, obviously, but to make a change to an existing machine you need to start somewhere. The helper fns, or named types, or whatever approach, will have to commit to one of those "views" leaving you on your own for the other one. Your example clearly shows the "paths through" eg the start, end, and effects. But to modify it you need to focus on a single state, and figure out which other states and transitions are available from there, which it doesn't help with. You could phrase the helpers instead to make the transition map clearer, but then you obscure the start/end/effects view. I'm maybe not explaining this well but it's a problem I've run into in some way with every state machine after its implementation. They are like regex they make sense when you're building it and have all the context but later it's hard to put it back together.
DanielVZ 4y ago
Somewhat unrelated, but I think coding a state machine is a much better interview question than typical leetcode questions. I’ve suffered way too much from ad-hoc written code with state being distributed all over the place in several functions, where one or two state machines would’ve kept everything tidily. I’m saying this as a self taught that tried to do his due diligence before looking for a job and fucking over all my colleagues work.
- qikInNdOutReply 4y ago
  How do you check, that your state-machine is not stuck. Its still shocking how much software can "hang", as if there is no way to detect that and reset to a "controllable" state via watchdog and error message. Its a disgrace, that such software engineering basic functionality has to be performed by the operating system.
  - govolckurself 4y ago
    Pretty sure this is equivalent to solving the Halting Problem, which is... difficult, to say the least. But why should the OS try to stop you from making logic errors? Test your state machines. Test every transition you're interested in. In practice, it's not that big of an issue, and programs hang for more mundane reasons.
    - qikInNdOutReply 4y ago
      Im confused. We argue for the same point. The program must know. And it can know. It can perform regular check ins and the watchdog in the program internals should reset it properly out of an error state. With an error message and the ability to save previously done work. I totally agree with you. Its very strange that the Operating System has to do basic controll flow jobs, as in Windows with the basic regular check ins by programs with the os. It should be part of every executable.
      - anongraddebt 4y ago
        The Redmond philosophy views running Windows update as basic control flow for any executable whatsoever.
vemv 4y ago
I've never seen a production FSM that I liked. Although admittedly they're better than many ad-hoc alternatives. My problems with them being that they cram together pieces of information that could be considered separatedly. For instance you could write a FSM that transitions from "paid" to "delivered"... or you could have two columns, paid_at and delivered_at, and consider those two columns orthogonal. As I see it, it scales better for humans - it's easier for us to consider 10 or 20 things separately than as part of an intrincate, bespoke rule system. You can still have some simple validation rules e.g. "delivered_at can't be set if paid_at hasn't been set". Which probably, if you squint is like a FSM in some mathematical sense, but in practice much complexity is avoided.
- DanielVZ 4y ago
  I think the issue most of the time is that you only start with two states, and you can avoid complexity by not implementing a FSM. But suddenly requirements change, and you have 4 or 5 new states that could go back and forth. The original approach ends up being way more complex than implementing a FSM in the first place; or even, than implementing the FSM when you add a third state.
  - vemv 4y ago
    When they seemingly need go "back and forth" I typically consider it good timing to create a new instance (object, or DB row) instead of keeping mutating the same instance. e.g. one can consider a re-purchased return simply a new purchase, instead of doing a purchased->returned->purchased transition.
  - Balladeer 4y ago
    This "suddenly requirements change" is why I get instantly wary whenever I see a boolean column like `completed` in a design. Sure, you start with two explicit states. But then you add `deleted` and now you have four states, whether you know it or not. Then there's talk of adding a third boolean column, and folks are wondering what it _means_ to be "deleted" but not "completed" and whether that is a valid state, and pretty soon the team is reinventing the concept of a state machine without any of the vocabulary that makes it straightforward.
quickthrower2 4y ago
A good way to think is that all code is a state machine, and you want to pick the right abstractions for that state to suit your task. Sometime the status field is enough. Sometimes you need something more complex. And developers are forcefed state machines. It is called JIRA, when it won't let you close the ticket and you need to hunt down someone who is an admin to fix it :-)...
- Swizec 4y ago
  > all code is a state machine Not true. At least not a finite state machine, which is what people usually mean by “state machine”. Most problems aren’t modelable as a state machine because they need contextual memory. But a state machine + stack, now we’re talking. That can do almost everything. State machine + “infinite” tape – yessss now we can solve everything.

92 points by signa11 4y ago

Have you noticed that the article from 2011 is sporting an image of vscode released on 2015? I mean, should they at least acknowledge the change of header?

giovannibonetti 4y ago

Many popular computer languages in use make state machines unergonomic. The problem is solved with native enumerated types or, even better, tagged unions, like Rust and functional languages from the ML family (Haskell, Ocaml, Elm). It is a joy working with state machines when you have a compiler that can verify exhaustively wheter all states and state transitions are handled.

cal85 4y ago
I've only really used state machines in TypeScript via xstate, and I've been meaning to try Rust for a while, so your comment interests me. Got any tips or advice on further reading or specific libs that you can recommend for working with FSMs in Rust?
- giovannibonetti 4y ago
  I don't have much Rust-specific experience, but I wonder if you need a library for this when the language/compiler is doing all the heavy lifting. When working with Elm, for example, that uses that a lot for the Model-View-Update framework, you just define your model states and pattern match them to build the view and update functions.
- giraffe_lady 4y ago
  Look at how you'd do it in f#, ocaml, or elm first imo. The type systems of those languages allow for a very tight approach with no confounding factors. The way rust does it is the same, but with more details leaked in from the constraints rust imposes. Which is fine, but I think it's valuable to see the "pure" stripped back form in a language almost perfectly suited to it first.
orwin 4y ago
Symbolic languages make it trivial. The only really complex state machine i ever wrote was in lisp (it was an IA for a game). Not the most intelligent IA, but a breath to write. The only feature a language really need to make usable state machines are closures.
andrewjl 4y ago
There are some interesting approaches in Swift: https://github.com/apple/swift/blob/main/stdlib/public/Observation/Sources/Observation/ObservationRegistrarStateMachine.swift https://github.com/apple/swift/blob/main/stdlib/public/Obser... https://github.com/apple/swift/blob/main/stdlib/public/Observation/Sources/Observation/ObservationRegistrar.swift https://github.com/apple/swift/blob/main/stdlib/public/Obser...

lloydatkinson 4y ago

I strongly agree with this. So many parts of systems are just poorly implemented finite state machines without knowing it. I wrote this on how to use FSM's in .NET https://www.lloydatkinson.net/posts/2022/modelling-workflows-with-finite-state-machines-in-dotnet/ https://www.lloydatkinson.net/posts/2022/modelling-workflows...

winstonprivacy 4y ago

State machines are a good solution when you have a typical transactional business process (order fulfillment, inventory management, etc). But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. For instance, let's say that are trying to execute a complex spread in the market. You might be partially filled on one leg (the timing of which is completely out of your control, if it happens at all). Then this needs to spawn an offsetting trade (or two), both of which may or may not be completely filled over multiple tickets. Super messy. A naive state machine simply doesn't work for this, as the overall unit of work (a "trade") can have multiple sub-states all operating more or less independently of one another. Are there well-known patterns to handle such situations?

Bjartr 4y ago
In terms of specific implementation I'm not sure, but it may be possible to use a formal modeling tool like TLA+ to prove a particular approach only results in outcomes you consider correct. So you could try to model the trade and all the sub states you mention in a naive state machine way, then check if that super messy tangle works as intended or if it has incorrect behavior.
rubyfan 4y ago
Can you share what your current solution looks like for something like that? > But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. Your comment resonated with me relative to regulated financial services where a relationship with a customer has many states can can be independent or intertwined depending on regulatory environment and subject matter i.e. status and renewal of terms of a contract/agreement, billing/payment, different pricing revisions, etc.
- winstonprivacy 4y ago
  Basically, lots of if...else statements combined with coroutines. Refactoring out as many big blocks of code helps a bit, but there's always yet another exception lurking in the shadows, waiting to show up at the least opportune time (such as when the system is under stress).

goodpoint 4y ago

"force-fed" is a bit distasteful tho.

jasfi 4y ago

The gem they link to hasn't been updated for the last 10 years. State machines get a lot of praise, but seem scarce in practice. Perhaps there are practical problems with using them in the long term?

Pamar 4y ago
Not that I am aware of, apart from the problem of implementation and design/documentation starting to drift apart ... but as you surely know this is not a problem with SM per se.
- jasfi 4y ago
  I was thinking of more along the lines of specialized framework and libraries for state machines. Perhaps those aren't necessary.
JohnFen 4y ago
I don't think so. About half of the programs (both new and old) I've worked with have used state machines, and I haven't noticed any long-term problems with them aside from the usual long-term problems with code generally.

muhehe 4y ago

I keep seeing "use statemachine", but it all seems very abstract to me. How would you "use statemachine" in, let's say python? Is there some library, or is more of a conceptual thing for code organization? This is probably stupid question but I can't really grasp what I should do. I'd like to because I'm currently tasked to create something like order system, which could benefit from this, but I don't know where to start.

Balladeer 4y ago
For typical use cases, you're probably persisting the data, so I'll assume your use case is "Python with a database ORM like Django or SQLAlchemy". The really short version of "use statemachine" is: store a single, explicit state for every 'thing' and create a log row every time that state changes. - Make a python model / database table to represent "the things whose state can change" (like an Order or a Task). - Give each a unique id and a 'state' column that is either a text field or an enumerated type (or a foreign key to a 'valid_states' table if you want to get fancy). Do this _instead_ of adding boolean columns like 'is_completed' or 'is_deleted'. - Create a log table with the same columns as your Order table -- whenever you update an Order's state (or create a new one), add a new row to the log table with the new state and a timestamp. Now your 'Order' table shows the current state of every Order, while your log table shows every state that every Order has ever been in, which will come in _super_ handy for analytics later. Everything else can be built on top of the above: - defining valid states and their transitions (aka formalizing the state machine) - preventing 'invalid' transitions if you want - creating analytics tables to show the 'typical' flow of an Order (e.g. columns like 'creation_date', 'payment_date', 'ship_date', 'return_date') - triggering other systems when Orders enter or leave a given state - etc
JohnFen 4y ago
A state machine is a technique. It is not language-dependent. There might be libraries to encapsulate the mechanics of state machines -- I don't know, though, because I find the mechanics of creating them easy enough that I never felt the need to seek out a library to support them. I'd recommend reading up about them on the web. Here's a reasonable start: https://www.freecodecamp.org/news/state-machines-basics-of-computer-science-d42855debc66/ https://www.freecodecamp.org/news/state-machines-basics-of-c... In their purest form, though, state machines are very simple. You have a conceptual "state" represented by a variable, then what amounts to a series of if-then statements (or a switch statement like in C/C++). The state machine consists of a loop, each iteration checking the current state (1, 2, 3, etc.) and performing the actions associated with that state. Then the state is changed as appropriate and the loop continues. So you have something like "If the state is "Starting", then do initialization things and change the state variable to "Running". If the state is "Running", do some business logic. If it's time to quit, change the state to "Stopping". If the state is "Stopping", free up resources and stop execution."

GuB-42 4y ago

Like the GoF design patterns, knowing about state machines is important, but whether or not you should use them in their "pure" form depends on the problem at hand. State machine make for some the least readable code I have written and an ad-hoc solution could have been more appropriate. The difficulties I have with state machines is, as usual, side effects. That is, implementing the state transition logic is usually straightforward, but more often than not, there is something you want to do between these states, typically I/O. In a pure framework, it manifests as a hidden, extra state, for witch the "right" thing to do is to make it explicit, and you may end up with a monster state and transitions all over the place. I have written a few of these monsters, and while I think it is partly the result of inherent complexity, I must say it is not the code I am the most proud of. In other situations, state machines were a perfect match, but like everything else, just because the problem can be modeled with a state machine doesn't mean it should.

Cthulhu_ 4y ago
One great example of state machines being used in the wild is in video games, e.g. playable and non-playable characters; for a simple 2D game, a player could be in a state "moving left", "right", "jumping", "falling", etc. Although it might quickly become a case where two states can be active (jumping & shooting), or there's different states for different things (e.g. animation state separate from movement state).
giraffe_lady 4y ago
I do some work in ocaml where state machines are popular I think because of how cleanly they map onto the language constructs. One common approach is the elm-ish move of having the machine fn return a pair of (new state, action). Then you have an intermediate fn run the side effects, but you can implement that somewhere else and mostly pretend it's not there. React reducers are kind of like this too. When doing this though like you said you always either find there are more states than you initially thought, or you end up having pseudostates only for their effects. I pretty much only reach for state machines when I know the inputs will never change and I'll never have to modify the implementation. Even in a language almost perfectly suited for them they are hard to understand once they're doing all the edge cases and side effects and edge cases of the side effects and error handling etc etc.

jnmandal 4y ago

A lot of this comes down to the clunkiness in high level programming languages. We will have all sorts of abstractions over enumeration and collections yet for some reason few languages seek to include niceties for state machines in their stdlibs.

JohnFen 4y ago

I'm genuinely surprised and more than a little shocked and concerned that there are developers out there who are unfamiliar with state machines and their use. I think of state machines as being foundational knowledge, like sorting algorithms, b-trees, etc.

knsv 4y ago
I fully agree! When designing solving a problem it great to take a step back and think through the states you can end up in. Although it is easy to make the machine overly complex when you have "multi-dimensional" states unless to are a little bit carful with how you model it.
physicles 4y ago
I’d argue they’re more foundational. If some code could use a b-tree but the dev doesn’t know about them, they can’t do much damage — they’ll use a less optimal tree. If some code needs a state machine but the dev doesn’t know about them, that code will have so many bugs.

dang 4y ago

Discussed at the time: Why developers should be force-fed state machines - https://news.ycombinator.com/item?id=2649162 https://news.ycombinator.com/item?id=2649162 - June 2011 (50 comments)

deterministic 4y ago

Game developers use state machines all the time.

AstixAndBelix 4y ago

Developers should be force fed nothing, because they "chose" to not follow a formal education. Almost everything I see in these blog posts is stuff I was already taught at college (or very adjacent). If you want developers to know about this stuff stop encouraging people to go to code bootcamps and start making SWE curricula more palatable and end this idea that college is a scam that teaches you nothing

gpderetta 4y ago
If you can learn this stuff in college it is great, but you can also learn it on your own.
redeux 4y ago
I’m glad this was your experience, but your school’s CS curriculum isn’t universal. I was once chatting with a jr sw engineer that had recently graduated from a respectable state university with a CS degree about which database would be optimal for our upcoming project. He confided in me that he hadn’t taken the DB course in school because he heard bad things about the professor who taught it. I was absolutely blown away. The moral of the story is that your shouldn’t assume that just because someone has a CS degree that they have knowledge of all the fundamental areas.
- lightbendover 4y ago
  Databases were not part of my CS curriculum until I took an elective web development course at the very end. People struggled. I had been doing hobbyist web development since I was quite young so the whole class was a breeze for me, but I understand that for those who are only taught the fundamentals and theory, anything pragmatic can feel daunting. I'm sure curriculums have changed greatly since I went through (KV/graph stores were not yet adopted, distributed DBs were merely a thought), but it still doesn't feel quite right for faulting a student for choosing certain classes or not being perfectly suited for learning a given domain instantly.
  - redeux 4y ago

Manfred 4y ago

I do have a pet peeve related to this and some observations. Sometimes developers call their variable or method state_machine, that's akin to calling your variable variable. You should be descriptive in what you are modeling as a state machine. I have also seen developers attempt to track external state using a state machine when they had no way to guarantee that the external state actually behaved that way. It becomes a really big mess. Especially when you are interested in the time of a change (or the person making the change), it's very often useful log the state transitions in a separate database table.

prettyStandard 4y ago
My rule of thumb is if you think the variable type may be useful to others reading your code, append it to the end. This is generally useful if you have the same data going through different forms. Let's see if I can write something, that others understand with no context. //For this example let's ignore the nuances of names. function (nameUserinput) { if(isValidName(nameUserinput)) { return processName(nameUserinput)) } else { return { first: '', middle: '', last: '' } } } function isValidName () { return (containsAtLeastOneSpace(nameUserinput) && containsLessThanThreeSpaces(nameUserinput) && hasThreeOrMoreCharacters(nameUserinput) && noSpacesOnEnd(nameUserinput)) } function processName (nameUserinput) { const nameObj = { middle: '' }; const nameUserinputArray = nameUserinput.split(' '); if(nameUserinputArray.length = 2) { [nameObj.first, nameObj.last] = nameUserinputArray; } else if(nameUserinputArray.length = 3) { [nameObj.first, nameObj.middle, nameObj.last] = nameUserinputArray; } } nameObj and nameUserinput and nameUserinputArray are all the same data in different forms. I think it's helpful to start them with the same prefixes, but change the suffix with the type to communicate that. You could imagine taking this a step further, with nameStatemachine. You might chart a person's course through life, do they go to law school, medical school, get married etc. I've been meaning to write a blog post on this. But this does follow my most important words first rule. You'll see a lot of similarities there, just not on this exact topic. https://soft-wa.re/naming-conventions/ https://soft-wa.re/naming-conventions/
- 4y ago

samsquire 4y ago

When I think that you can see the memory of a program and the execution of instructions as a state machine just a very large one. I am trying to design a state machine representation/notation that handles the transitions of multiple complicated objects over time and between threads and machines. I want a good notation for state machines that is similar to EBNF. I think rule engines become relevant when you think about complicated transitions of business processes. I settled on this, it is inspired by prolog. It represents the state progression of an async/await thread pool and parallel state machines and forking and joining state machines. A and B is a task variable and 1 is a thread number. The pipe symbol represents a transition from a group of states, all previous facts must match before progressing. next_free_thread = 2 task(A) thread(1) assignment(A, 1) = running_on(A, 1) | paused(A, 1) running_on(A, 1) thread(1) assignment(A, 1) thread_free(next_free_thread) = fork(A, B) | send_task_to_thread(B, next_free_thread) | running_on(B, 2) paused(B, 1) running_on(A, 1) | { yield(B, returnvalue) | paused(B, 2) } { await(A, B, returnvalue) | paused(A, 1) } | send_returnvalue(B, A, returnvalue) I actually worked on a BPMN project once. The idea of this syntax is that your code would be reactive and you would have an API to retract or publish facts. The state machine handles scheduling.

discarded1023 4y ago
> I want a good notation for state machines that is similar to EBNF. If this isn't a firm requirement, perhaps you can dig into the venerable state machine notations of yesteryear. For instance ARGOS [1] and StateCharts [2]. The latter got incorporated into UML somehow [3] IIRC. Esterel [4] is a bit mind blowing. Other people prefer dataflow, in which case Lustre [5] might be worth a look. These make a strong synchrony hypothesis which may or may not apply to your situation. But if it does you're in clover. And if you're not you can still try to use this stuff in a GALS [6] architecture. [1] https://dl.acm.org/doi/10.1016/S0096-0551%2801%2900016-9 https://dl.acm.org/doi/10.1016/S0096-0551%2801%2900016-9 (and google some more) [2] https://statecharts.dev/ https://statecharts.dev/ [3] https://en.wikipedia.org/wiki/UML_state_machine https://en.wikipedia.org/wiki/UML_state_machine [4] https://en.wikipedia.org/wiki/Esterel https://en.wikipedia.org/wiki/Esterel [5] https://en.wikipedia.org/wiki/Lustre_(programming_language) https://en.wikipedia.org/wiki/Lustre_(programming_language) [6] https://en.wikipedia.org/wiki/Globally_asynchronous_locally_synchronous https://en.wikipedia.org/wiki/Globally_asynchronous_locally_...

probably_wrong 4y ago

I have exactly one negative thing to say about state machines: they are difficult to understand when all you have is the implementation, which makes them difficult to update. My solution is typically to include an ASCII drawing of the state diagram in the comments, which I never really liked as a solution for reasons I can't explain. But I also think that this is a fair price to pay when the alternative is a jungle of "if condition1 and not condition2...".

stinos 4y ago
they are difficult to understand when all you have is the implementation, which makes them difficult to update I don't really have that issue, could you give an example? I typically write them with a helper like (not web app, but shouldn't matter) fsm.In(State.Idle).When(Command.SomeStuffHappened).GoTo(State.Foo).WithTransition(InitiateRun); fsm.In(State.Idle).When(Command.OtherStuffHappened).GoTo(State.Bar).WithTransition(InitiateRun); ... fsm.In(State.Foo).When(Command.FooAborted).GoTo(State.Idle) ... which for me is a lot easier to reason about than reasoning about state generally is (i.e, very hard especially if you have to look at the combination of a couple of state variables and then also have to take preconditions into account, god forbid other threads, well, you know the drill probably:)
- giraffe_lady 4y ago
  I think there is kind of a figure/ground effect where there's two ways of looking at a given state machine but it's impossible to hold both in your mind at the same time. You're either thinking about the "path through" and the effects along the way, or you're looking at a single state and its valid transitions. Both are both, obviously, but to make a change to an existing machine you need to start somewhere. The helper fns, or named types, or whatever approach, will have to commit to one of those "views" leaving you on your own for the other one. Your example clearly shows the "paths through" eg the start, end, and effects. But to modify it you need to focus on a single state, and figure out which other states and transitions are available from there, which it doesn't help with. You could phrase the helpers instead to make the transition map clearer, but then you obscure the start/end/effects view. I'm maybe not explaining this well but it's a problem I've run into in some way with every state machine after its implementation. They are like regex they make sense when you're building it and have all the context but later it's hard to put it back together.

DanielVZ 4y ago

Somewhat unrelated, but I think coding a state machine is a much better interview question than typical leetcode questions. I’ve suffered way too much from ad-hoc written code with state being distributed all over the place in several functions, where one or two state machines would’ve kept everything tidily. I’m saying this as a self taught that tried to do his due diligence before looking for a job and fucking over all my colleagues work.

qikInNdOutReply 4y ago
How do you check, that your state-machine is not stuck. Its still shocking how much software can "hang", as if there is no way to detect that and reset to a "controllable" state via watchdog and error message. Its a disgrace, that such software engineering basic functionality has to be performed by the operating system.
- govolckurself 4y ago
  Pretty sure this is equivalent to solving the Halting Problem, which is... difficult, to say the least. But why should the OS try to stop you from making logic errors? Test your state machines. Test every transition you're interested in. In practice, it's not that big of an issue, and programs hang for more mundane reasons.
  - qikInNdOutReply 4y ago
    Im confused. We argue for the same point. The program must know. And it can know. It can perform regular check ins and the watchdog in the program internals should reset it properly out of an error state. With an error message and the ability to save previously done work. I totally agree with you. Its very strange that the Operating System has to do basic controll flow jobs, as in Windows with the basic regular check ins by programs with the os. It should be part of every executable.
    - anongraddebt 4y ago
      The Redmond philosophy views running Windows update as basic control flow for any executable whatsoever.

vemv 4y ago

I've never seen a production FSM that I liked. Although admittedly they're better than many ad-hoc alternatives. My problems with them being that they cram together pieces of information that could be considered separatedly. For instance you could write a FSM that transitions from "paid" to "delivered"... or you could have two columns, paid_at and delivered_at, and consider those two columns orthogonal. As I see it, it scales better for humans - it's easier for us to consider 10 or 20 things separately than as part of an intrincate, bespoke rule system. You can still have some simple validation rules e.g. "delivered_at can't be set if paid_at hasn't been set". Which probably, if you squint is like a FSM in some mathematical sense, but in practice much complexity is avoided.

DanielVZ 4y ago
I think the issue most of the time is that you only start with two states, and you can avoid complexity by not implementing a FSM. But suddenly requirements change, and you have 4 or 5 new states that could go back and forth. The original approach ends up being way more complex than implementing a FSM in the first place; or even, than implementing the FSM when you add a third state.
- vemv 4y ago
  When they seemingly need go "back and forth" I typically consider it good timing to create a new instance (object, or DB row) instead of keeping mutating the same instance. e.g. one can consider a re-purchased return simply a new purchase, instead of doing a purchased->returned->purchased transition.
- Balladeer 4y ago
  This "suddenly requirements change" is why I get instantly wary whenever I see a boolean column like `completed` in a design. Sure, you start with two explicit states. But then you add `deleted` and now you have four states, whether you know it or not. Then there's talk of adding a third boolean column, and folks are wondering what it _means_ to be "deleted" but not "completed" and whether that is a valid state, and pretty soon the team is reinventing the concept of a state machine without any of the vocabulary that makes it straightforward.

quickthrower2 4y ago

A good way to think is that all code is a state machine, and you want to pick the right abstractions for that state to suit your task. Sometime the status field is enough. Sometimes you need something more complex. And developers are forcefed state machines. It is called JIRA, when it won't let you close the ticket and you need to hunt down someone who is an admin to fix it :-)...

Swizec 4y ago
> all code is a state machine Not true. At least not a finite state machine, which is what people usually mean by “state machine”. Most problems aren’t modelable as a state machine because they need contextual memory. But a state machine + stack, now we’re talking. That can do almost everything. State machine + “infinite” tape – yessss now we can solve everything.