Developers should be force-fed state machines (2011)
shopify.engineering
shopify.engineering
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?
> 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.
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.
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.
We tried for nearly two years to get the status/state of each PR line item to update in real-time as events occurred during follow-on steps, but it was extremely brittle.
We finally added an intermediary queue and centralized all the logic in batch. Anytime something happened that might trigger a state (not verified), we tossed it in the queue. Then, we processed the queue every five minutes through a rules engine that was a classic factory pattern (a favorite anti-pattern). Every time the PR # ran through the rules engine, it would have a deterministic result. Sometimes it would pass through 10-20 times with no state change, but at least it was predictable.
We thought it would be too inefficient, potentially processing the same PRs 100s of times without any actual change to the state. However, the servers handled it fine, and it was real-time "enough" the users didn't notice a lag. We went from fixing issues several times a week to no changes for the remaining two years I was on the project.
That worked fine for us. Also, I have recently (< six months ago) used a SM to build a module in the application I am working on and I am quite happy how it allowed us to quickly adapt to the corner cases that inevitably started cropping up after deploying the module.
I am fairly convinced that a different approach would have make been much more difficult to adapt, and that testing for subtle interactions of different states would have been much more complicated.
I used a SM no more than six months ago to process vouchers and voucher redemption from a third party service and while we had no less than 10 changes after deploying in prod... each one was easy to analyze and the actual fix was like 2-3 lines of code.
I have zero experience (or knowledge) of Kubernetes, but I feel this somehow strengthens my idea that SM can be a very powerful tool indeed when dealing with some specific problem.
If you have a rigid state machine, you better know all the edge cases and states.
Architecturally state machines seem simple but they area computational power beneath stack machines and of course Turing machines.
So next thing you want is a simple rules engine. Well next comes the rete processing rabbit hole, etc.
We want to think computation is just state transition graphs but real computation even just business logic goes off the rails real fast.
Personally I always worked with relatively simple state machines and always wrote actual code to handle new cases or edge conditions that were not in the original design.
As a tool (and at the tactical level), these work fine. Making these an overarching paradigm for your whole system, and especially adding a rule engine is something I never did and I would be wary to try, personally.
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/
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.
Instead of transitioning on multiple parameters you decompose states into respective nested state machines to avoid this explosion
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).
The only feature a language really need to make usable state machines are closures.
https://github.com/apple/swift/blob/main/stdlib/public/Obser...
https://github.com/apple/swift/blob/main/stdlib/public/Obser...
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.
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.
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.
https://en.wikipedia.org/wiki/Halting_problem#Common_pitfall...
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.
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.
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.
Pretty sure that's not what vemv said. Trying to put words in their mouth is very much not cool.
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
In the end I don't pursue an absolute truth. Things are often gradients, one can pick whatever tone seems more reasonable.
It’s like the difference between solving a maze, and solving a maze with constantly moving walls and traps in it.
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.
e.g. one can consider a re-purchased return simply a new purchase, instead of doing a purchased->returned->purchased transition.
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.
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.
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.
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.
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...".
I don’t know why this hasn’t become a standard feature of IDEs and editors.
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.
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)
...
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.
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?
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.
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.
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.
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)
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.
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_...
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.
I wrote this on how to use FSM's in .NET https://www.lloydatkinson.net/posts/2022/modelling-workflows...
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.
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.
Why developers should be force-fed state machines - https://news.ycombinator.com/item?id=2649162 - June 2011 (50 comments)
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.
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;
}
}
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.
Ignoring variable name shadowing a static type system helps a lot
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.
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.
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
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."
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
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.
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.
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
A non-CS grad is much less likely to have. They may not even have a concept that estimating algorithmic complexity is even possible. They may have zero understanding why a massively nested loop structure is slow.
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.
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.
every example I've seen (probably toy examples from articles) felt like way too much abstraction had been applied over the problem.
This works best with languages that have first class support for data literals and maps (or equivalent), such as JS, Clojure, etc.
But if you care a ton about performance you can encode the same with say enums and switch statements or similar. It's just a bit more work and you can't change the machines on the fly or generate them from data, which is a very powerful pattern you can put on top of this. But in many cases that's not needed.
---
You first define a map of states, where each key is the name of the state and each value is a map from event names to state names.
Say you have an on off toggle (very simple example):
On => Toggle => Off
Off => Toggle => On
Where On/Off are state names and Toggle is an event name.
Then, you define a map from two states to a function. We call them transition functions. Like so:
[On Off] => func()...
[Off On] => func()...
Inside the functions you would put side-effects directly (such as activating a light or changing a color, sending an email etc.), or maybe just describe side effects so another part of your program can handle them (which can be useful with larger programs as it makes testing easier).
Lastly, you define a state machine function that runs your program like so:
func(state, event) => if event is handled: trigger transition function and return new state, else: return current state
In many cases you want to simply ignore events that aren't handled in the current state of your state machine (like described above).
Sometimes though, you want to buffer events that are currently not handled in a queue and handle them later; that's a niche use-case in order to manage async events in a specific order.
Agreed, though. We need to stop pretending 12 weeks of JavaScript is at all equivalent to four years of rigorous theory and practice.
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.
I mean, should they at least acknowledge the change of header?