[HN Gopher] Developers should be force-fed state machines (2011)
___________________________________________________________________
Developers should be force-fed state machines (2011)
Author : signa11
Score : 72 points
Date : 2023-04-19 08:46 UTC (1 days ago)
(HTM) web link (shopify.engineering)
(TXT) w3m dump (shopify.engineering)
| vemv wrote:
| 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.
| mannykannot wrote:
| > 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.
|
| The first seems to imply that delivery cannot occur until the
| state 'paid' has been reached, while the second contains no
| such implication. Either might be correct, depending on how the
| business operates, and modeling the states and the allowable
| transitions between them is an excellent way to find out what
| questions need to be answered before you can produce a correct
| implementation - better in every way than implementing what
| seems right intuitively, and then seeing what happens.
| omeid2 wrote:
| As you say, state machines are the best thing around.
|
| As for the "paid" and "delivered" _states_ in relation to
| paid_at and delivered_at timestamps. You can have your cake and
| eat it too.
| AnimalMuppet wrote:
| > As you say, state machines are the best thing around.
|
| Pretty sure that's _not_ what vemv said. Trying to put words
| in their mouth is very much not cool.
| mustardo wrote:
| 100% this! One of the worst projects to reason about I have
| ever worked on (and I have worked on a lot of trash) was when a
| colleague insisted on implementing a state machine in a system
| that tracked voucher (offer) redemptions. State machines do
| have their place but coordinating business logic with one is a
| bad idea IMHO
|
| This same colleague had implemented a similar FSM (flying
| spaghetti monster as known by the team) in an FX (foreign
| exchange) platform at a previous company. Which after a job
| change I got the pleasure of experiencing, nobody in the team
| knew how it worked and everyone was petrified of making changes
| smallpipe wrote:
| You realise you're allowed to use more than one state machine
| right ?
| jameshart wrote:
| Sure, but as soon as you create linkage between them - if the
| state of machine A affects what transitions are possible when
| in machine B and vice versa - then you don't really have two
| state machines, you have a single Cartesian state machine
| combining both. Or you have a pair of metastatemachines which
| aren't able to be analyzed in the same way as an independent
| state machine.
|
| It's like the difference between solving a maze, and solving
| a maze with constantly moving walls and traps in it.
| worthless-trash wrote:
| This was my thought too, I hear most people get a bit jumpy
| when they see two state machines, like its too many moving
| parts.
| vemv wrote:
| Yes. From intuition I'd say that getting the right
| granularity is just as hard as getting other granularities
| right (e.g. how "micro" or "macro" your services should be).
|
| In the end I don't pursue an absolute truth. Things are often
| gradients, one can pick whatever tone seems more reasonable.
| DanielVZ wrote:
| 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.
| giraffe_lady wrote:
| Yeah or even more insidious when a new state looks like, and
| so is modeled as, just a special case of one of the original
| two. As a mentor said to me early in my career "every
| functioning business system is a state machine, but the only
| ones that are easy to work on are where they knew that from
| the beginning."
|
| Most systems I've worked on end up with one of the "original"
| states being a catchall or misc type entity that could carry
| any number of other meanings depending on timing and context.
| A lot of legacy code work in my experience is actually a game
| of "find and name the states" when they're spread out across
| multiple systems, written at different times and with
| different understandings of the broader system, and with
| different methods to track and modify them.
| Balladeer wrote:
| 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.
| vemv wrote:
| 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.
| Tangurena2 wrote:
| I worked for a department of motor vehicles (it also included
| what other states would call "the highway department"). I
| argued that the vehicle registration process needed to be
| implemented as a state machine. Other folks started "getting
| it" when I compared it to traffic lights. Certain steps had to
| be done in legally mandated sequences which were governed by
| state & federal laws as well as federal regulations. Like, the
| VIN must be checked with NCIC to ensure that it isn't stolen.
|
| This used to be one of the states where dishonest people would
| "launder" salvage titles to remove the brand. If a vehicle is
| totaled (flood damage also counts), the title gets branded with
| the word SALVAGE. Every subsequent title for that vehicle
| should also have SALVAGE written on it. Before you can get a
| license plate for such a vehicle, it needs to be inspected for
| safety.
|
| The human-readable diagram took up an 11"x17" piece of paper.
| giovannibonetti wrote:
| 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.
| orwin wrote:
| 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.
| cal85 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| lloydatkinson wrote:
| 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...
| winstonprivacy wrote:
| 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?
| sesteel wrote:
| Look up HSMs.
| winstonprivacy wrote:
| I've looked into HSMs and I don't think they are intended to
| handle this scenario due to the needed to be in multiple
| states at once.
|
| For instance, you partially fill one trade. This spawns a
| process which must then enter an offsetting trade for that
| partial amount.
|
| While this is going on, you may partially fill more of your
| initial trade, which then must spawn an offsetting trade for
| that amount (and so on).
|
| This quickly escalates out of control when you consider all
| of the possibilities which can happen at each state along the
| way (partial fills, cancels, connection issues, circuit
| breakers).
| Bjartr wrote:
| 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 wrote:
| 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 wrote:
| 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).
| Pamar wrote:
| Not that I know of (so I'd like to see if someone can suggest
| anything).
|
| In practice, what I have always done is to decompose the
| "object" into a set of components. Each of these components can
| be in a number of states, and there are rules to set the header
| state depending on what the substates are.
|
| Practical example:
|
| ------------
|
| Business order #2849 State: PSH (Partially shipped)
|
| Item 2849.01 State ONO (Ordered, not confirmed)
|
| Item 2849.02 State STR (Received, stored)
|
| Item 2849.03 State SSH (Shipped by supplier)
|
| Item 2849.04 State STR (Received, stored)
|
| -------------
|
| Where the "business rules" are something like:
|
| * "If all items are SSH or better, status=SSH"
|
| * "If at leat one item is ONO, status=POR" (on order, not fully
| confirmed)
|
| ... Etc.
| winstonprivacy wrote:
| That is precisely what I'm doing now and it's the best
| solution I've found so far. However it is brittle and it
| takes quite a long time to iron out the edge cases where
| things can happen that you didn't anticipate.
|
| I have one system that has been more or less stable for two
| months and once a week, it fails inexplicably (dumping no
| logs either). Whenever this happens, I find myself writing a
| ton of debug code hoping to catch it.
| mcphage wrote:
| > But I rarely see mention of messier problems which consist of
| overlapping and perhaps hierarchical states.
|
| That's what State Charts were designed for:
| https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res...
|
| It's used as the basis for a number of state machine / state
| chart libraries, for instance XState:
| https://xstate.js.org/docs/
| friendzis wrote:
| > Are there well-known patterns to handle such situations?
|
| I'm not familiar with algorithmic trading so may be way off,
| but if I understand your problem correctly, it sounds like you
| need what is called parallel states: state machine where a
| "state" is in itself a state machine. The trick here is that
| transition of one "leg" can be transition trigger for another
| leg. In your example you would have 4 states: "Executing trade
| leg A/B" and "Executing balancing trade". Suppose trade A fills
| first (a complex machine in itself), it triggers leg B to
| terminate and transition to balancing trade state while leg A
| would transition to completion state.
| bheadmaster wrote:
| I think the problem with parallel states is the combinatorial
| explosion of the number of transitions - instead of having
| O(n) transitions, now you have O(n_1*n_2*...*n_k) transitions
| between all possible k-tuples of parallel states.
| jnmandal wrote:
| 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.
| goodpoint wrote:
| "force-fed" is a bit distasteful tho.
| AstixAndBelix wrote:
| 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 wrote:
| If you can learn this stuff in college it is great, but you can
| also learn it on your own.
| redeux wrote:
| 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.
| Version467 wrote:
| Were you asking him about what kind of db would be best
| suited for your project (i.e. relational, document based,
| graph, etc.), or were you asking about specific products,
| like Postgres vs. Mariadb?
|
| If it was the latter, then I doubt he could have answered
| that even if he had taken the db course at his college. And
| that's probably fine, I don't think the differences between
| specific db products counts as the sort of fundamental
| knowledge that should be taught at a university.
| redeux wrote:
| We were talking about kinds of DBs, not specific products.
| Version467 wrote:
| Oh okay, yeah that makes more sense then.
| rs999gti wrote:
| I would take a CS degree with no experience over a boot camp
| or for profit school's fresh graduate.
|
| At least I know the CS degree has standards and academic
| rigor, with mathematics and some problem solving, which to me
| means they can think and adapt.
|
| Once both groups get experience though they are pretty much
| the same resume wise. Then it is up to the interview process
| and probation period to shake them out
| redeux wrote:
| I don't think this is a very controversial take, and I'm
| not arguing against the value of a CS degree. You just
| can't assume that someone knows even foundational topics
| because they have one.
| govolckurself wrote:
| No, but it makes it fairly likely that they were exposed
| to the fundamentals, like a lack of a degree makes it
| likely they weren't. "Well, actually, not EVERY CS major
| knows their fundamentals!" is not nearly as strong of an
| argument as people seem to think.
| lightbendover wrote:
| 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 wrote:
| My point is about not assuming people know specific topics
| in CS just because they have a CS degree. So, I feel like
| we agree here. There were no problems with his attitude,
| and it was a quick fix. I just assumed he knew, having
| recently gotten a CS degree and I was wrong.
| ly3xqhl8g9 wrote:
| Certainly doesn't help that colleges that aren't at the
| MIT/Stanford level have as specified purposes only to provide
| employment and generate profit through state subsidies,
| education is a side effect, if at all. It is just luck if at
| one of these colleges you find a passionate
| teacher/professor/mentor who has enough time to pay attention
| to you.
|
| The future of education will be the personal artificial mentor,
| such as GPT10+ will be able to provide, and then the question
| becomes: how do you generate internal motivation for the
| children/people to be interested in knowledge and power over
| nature instead of being mindlessly entertained by whatever the
| ad-driven feed displays.
| dgb23 wrote:
| I'm an autodidact and a big fan of state machines (specifically
| mealy machines).
|
| They can easily be expressed as plain data structures of three
| layers that map the name of a state to possible inputs/events
| to the appropriate name of the subsequent state. Then you only
| need code / functions for each transition (from state, to
| state) to generate effects. This data driven pattern is very
| straight forward to implement and easy to reason about.
|
| I learned it from hobby game programming, especially its
| application and usefulness. It comes up in lectures/books,
| sure, but generally people tend to vastly underestimate its
| applicability and instead smear state control all over their
| code, regardless of their education.
| govolckurself wrote:
| Vegetables aren't as great as ice cream, but you need
| vegetables, even if they aren't "palatable". Let's end the
| notion that everything in computer science is easy and hip and
| fun. No, recurrence relations probably aren't the most
| exciting, but they're important fundamentals. I expect
| developers to be adults and learn difficult things, even if
| they're not "palatable".
|
| Agreed, though. We need to stop pretending 12 weeks of
| JavaScript is at all equivalent to four years of rigorous
| theory and practice.
| jasfi wrote:
| 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?
| JohnFen wrote:
| 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.
| Pamar wrote:
| 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.
| Manfred wrote:
| 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 wrote:
| 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/
| mustardo wrote:
| A Hungarian notation but as a suffix?
|
| Ignoring variable name shadowing a static type system helps a
| lot
|
| https://en.m.wikipedia.org/wiki/Hungarian_notation
| prettyStandard wrote:
| > Hungarian notation but as a suffix
|
| Yeah, but only when it adds to the readability. I avoid
| mentioning Hungarian notation because I don't like it
| either. I think many criticisms still apply, so I suggest
| the use case before, where you have the same data passing
| through multiple types. There may be other good use cases,
| but I am not sure what those are. This is why my general
| rule, is "most important words first", I think that
| technically covers this use case.
| quickthrower2 wrote:
| 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 wrote:
| > 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.
| samsquire wrote:
| 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 wrote:
| > 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
| (and google some more) [2] https://statecharts.dev/ [3]
| https://en.wikipedia.org/wiki/UML_state_machine [4]
| https://en.wikipedia.org/wiki/Esterel [5]
| https://en.wikipedia.org/wiki/Lustre_(programming_language) [6]
| https://en.wikipedia.org/wiki/Globally_asynchronous_locally_...
| muhehe wrote:
| 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.
| JohnFen wrote:
| 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-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."
| Balladeer wrote:
| 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
| GuB-42 wrote:
| 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.
| giraffe_lady wrote:
| 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.
| Cthulhu_ wrote:
| 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).
| probably_wrong wrote:
| 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...".
| Xenoamorphous wrote:
| I don't think I'd ever 100% trust a diagram (of a state machine
| or anything else, really). They become out of sync way too
| easily.
| criddell wrote:
| I use a plugin for Visual Studio that lets me add an image to
| comments and it's wonderful even if it is a bit janky. If you
| don't have the plugin, you still see a reference to an image
| file that you can click on to load in an external viewer and
| this a decent fallback.
|
| I don't know why this hasn't become a standard feature of IDEs
| and editors.
| JohnFen wrote:
| I would hate this so much!
|
| I can see how an actual image is useful in certain
| circumstances, but I wouldn't want it to appear in the code
| itself. Just include the image in the documentation folder
| and refer to it in the code by name.
| criddell wrote:
| It's been invaluable to me in a few circumstances. A common
| one is when there is a diagram of a physical object with
| dimensions and the dimensions are used in the code. For
| example, say you are doing a volume calculation of a
| complex enclosed space that uses quantities like length,
| height, clearance, diameter, etc... A diagram illustrating
| what those dimensions are can aid immensely in
| understanding the code.
| JohnFen wrote:
| Oh, sure, it can be extremely helpful. A picture is worth
| a thousand words and all of that. I just don't want that
| picture in-line with the code. It bulks up the view of
| the code and I'd want the picture in a separate window
| anyway, to refer to it as I'm scrolling through the code
| itself.
| govolckurself wrote:
| graphviz on a dot file to PNG, and then slap that bad boy in
| the README. Boom. Done.
| stinos wrote:
| _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(Comma
| nd.SomeStuffHappened).GoTo(State.Foo).WithTransition(InitiateRu
| n); fsm.In(State.Idle).When(Command.OtherStuffHappened).G
| oTo(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:)
| jsmith45 wrote:
| That's not bad.
|
| One limitation is that is probably a builder pattern,
| creating an object that runs an arbitrary state machine. (I
| suppose it _could_ be a method repeated rerun, where fsm is a
| wrapper around the current state, and method calls that don
| 't apply return a null object singleton, but that seems less
| likely).
|
| If so it will have a few downsides, like extra memory needed
| to build up the transition table(s), and possibly being less
| efficient in executing than a hard coded implementation,
| simply because the FSM type would need to implement code for
| arbitrary FSMs, meaning potentially less efficient than
| scenario specific implementation.
|
| In many scenarios this additional overhead is probably not a
| big concern, and the increased maintainability vs some other
| styles of coding FSMs may be well worth it.
|
| I'd guess the built up data structure data structure would be
| something like a dictionary that maps from the current state
| to a dictionary that maps from trigger conditions (or
| commands in the code above), to a struct that contains the
| new state, and optionally a transition action function
| pointer (or delegate, or whatever your language calls them).
|
| One of the interesting things about FSMs is that there are
| many ways to code them. I've also seen an thin wrapper around
| state object with methods for all transition actions, said
| methods being mostly a switch statement (or if/else chain)
| around the current state, setting the new one and possibly
| calling an transition action.
|
| Plus of course there are plenty of ways to code an FSM such
| that its existence is more implicit than explicit, where the
| main hint that an FSM exists at all the existence of a
| variable named state.
| stinos wrote:
| _I 'd guess the built up data structure data structure
| would be something like a dictionary that maps from the
| current state to a dictionary that maps from trigger
| conditions (or commands in the code above), to a struct
| that contains the new state, and optionally a transition
| action function pointer (or delegate, or whatever your
| language calls them)._
|
| That's about right yes. This particular thing was in C# in
| a fairly large desktop application, and the little extra
| memory needed for this or potential performance overhead of
| a dict wasn't a concern at all in the greater scheme of
| things.
| giraffe_lady wrote:
| 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.
| mistrial9 wrote:
| Moore Machine or Mealy Machine ?
|
| https://en.wikipedia.org/wiki/State_diagram
| stinos wrote:
| _figure out which other states and transitions are
| available from there_
|
| I think I see what you mean (for me this is just another
| manifestation of 'reasoning about state is hard - like
| possibly the hardest thing in programming), and in a case
| like the example shown you start by looking that up by
| looking at the definition; it's bascially also why I left
| the newline between the Idle and Foo states: want to know
| what states are available from Idle? Look at all lines
| starting with In(State.Idle). Now, I assume you also
| figured that out so perhaps the state machines I've used
| have never been big enough (largest would be like 100 of
| these lines) to really see the problem you're facing. Or
| maybe you've been often looking at machines where states
| aren't very well defined meaning a state isn't 'small'
| enough making it really hard to figure out where to go from
| there (state machine inside another one could potentially
| be a solution there)? Or perhaps a state machine wasn't the
| right solution after all?
| skywal_l wrote:
| The problem is that the code and the diagram will eventually
| diverge, especially if multiple people are working on the same
| code base (which is why you have a diagram in the first place).
|
| There used to be software like Rational Rose were you would
| draw your state machine and then have the code generated but
| the code generated is hard to maintain and debug and ends up
| drifting away anyway.
| tourgen wrote:
| [dead]
| DanielVZ wrote:
| 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 wrote:
| 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 wrote:
| 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.
| yccs27 wrote:
| The Halting Problem is undecidable only for Turing
| machines, but we are restricting ourselves to finite state
| machines - and with a finite number of states it must
| eventually either halt or repeat a previous configuration.
|
| https://en.wikipedia.org/wiki/Halting_problem#Common_pitfal
| l...
|
| I'd go so far to say that this is a key advantage of FSMs -
| without Turing completeness you get much better options for
| theoretical analysis.
| qikInNdOutReply wrote:
| 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 wrote:
| The Redmond philosophy views running Windows update as
| basic control flow for any executable whatsoever.
| qikInNdOutReply wrote:
| Which still is by all means a externalized watchdog,
| which in addition is deactivated, if its not properly
| implemented and still working. So the philosophy itself
| is brokken by the programers and the users are used as
| sensor to find out wether the program executed properly.
|
| A proper implementation would be, that windows for
| example during the installation could "starve" the
| process in a API or somewhere else into a internal
| timeout and expect that error to come up, to proof
| worthiness.
| awelxtr wrote:
| 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?
| dang wrote:
| Discussed at the time:
|
| _Why developers should be force-fed state machines_ -
| https://news.ycombinator.com/item?id=2649162 - June 2011 (50
| comments)
| JohnFen wrote:
| 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 wrote:
| 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 wrote:
| 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.
___________________________________________________________________
(page generated 2023-04-20 23:03 UTC)