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?
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)
Sorry, seen this only now.
Yep, I do consider these states, and yes, I am aware that trying to scale up to a "simple" rule engine is a huge effort.
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.
These is analogous to kubernetes conditions in the old-debate between explicit state machines with phases/transitions and events/conditions for k8s resources.
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.
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.
I worked on a highly complex, high-volume automated procurement sourcing system many years ago. Each Purchase Requisition (PR) -> RFQ -> Bid Response -> Purchase Order could have many-to-many relationships, splitting & bundling at each line item (even the arrows above don't give the right idea, as things could go to re-bid, long-term contract with task orders, etc.).
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.
Not sure about the specifics but yes, in cases like the one I described in my oriignal post, the "header" state will not change immediately but some kind of service thread would periodically revisit the active headers (i.e. anything that had not reached the final stable state) and check all the items in order to update the header state.
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 agree on the fact that you may have edge cases cropping up in production... still, in my experience this approach makes adjusting (either by introducing new States, or by altering the logic that guides a State Transition) much easier because you can reason about the problem in terms of a specific item and a specific State Transition at the time, even if this happens to 10k records at the same time, and there are another 10M records of different type and in different states.
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.
> 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.
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.
Um... No? Parallel (though hierarchical/recursive would be more fitting term) states are literally designed to fight combinatorial explosion of transitions. Qt docs provide nice, concise summary: https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-...
Instead of transitioning on multiple parameters you decompose states into respective nested state machines to avoid this explosion
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.
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).
Just take the product of the two independent states. If you had 5 + 5 states, now you have 25 superstates each representing a potentially unique situation. As long as the sub-states are enumerable, the superstates will be enumerable too.
One could argue this is exactly where state machines shine, because they allow you to methodically consider every condition.
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.
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).
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
> 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.
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
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.
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.
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...".
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:)
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
> 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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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
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.
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."
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?
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.
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.
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
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.
This response is a bit late sorry. I fully agree. Most programming languages already give you enough tools to write very simple and powerful state machines.
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.
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.
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.
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.
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.
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
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.
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.
One example I can think of: A CS major is likely to have at least been exposed to the idea of Big-O estimating algorithmic complexity.
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.
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.
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.
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 :-)...
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.
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?