One helpful hint for dealing with state machines isn't listed (arguably because it's not state machine specific).
The most common way to abstractly describe state machines is the directed graph, but (like nearly all graph problems) it's often just as illuminating if not more to decompose the graph into a matrix as well. So rows are states, columns are events, and the intersections are transitions. Being able to run down a column and see what happens in each of the states when a certain event is processed has made a lot of bugs much more obvious for me.
Now when documentating a state machine enough to actually draw out the graph, I always include a matrix representation as well for that reason.
This is the way to go. I have taught teams to use state machines a couple of times, and it is so useful to just write down a list of all the events that could possibly happen. The user types something, they click on something, an api response arrives, and so on. Figuring out the list of states can be harder, so I usually start with the most obvious and draw the graph as we fill out the matrix. Usually answering the question of what goes in any particular cell is easy, and with the graph it is often easier to see when you have to add a state rather than go back to an existing one.
The best result was the time we spent an hour at the whiteboard, then the team split up and we each re–wrote part of the code (there was message–passing between components involved, so we just each took one component; I had cleverly used the events between components in the state machine in addition to external events). We all committed by the end of the day, and the next day QA said it was perfect. (Eventually I think some automated tests got written, but whatever.) Compare that to the prior months where QA would find some weird problem, someone would debug it, write a patch, and declare it fixed without realizing that they had broken some other edge case. There were never any bugs found in that thing ever again.
I find myself drawing graphs of state machines a lot and they can help, but I have never considered doing a matrix representation. I have a problem I am working on with a very bad state machine at work and I think maybe putting in a matrix may help me untangle the madness way better, so I will give it a shot. Thanks!
It can also be useful for other reasons, the one that I think of is the interview question involving the knight jumping on the telephone keypad. Using the matrix instead of the graph, you can leverage matrix maths. Multiply the matrix by itself and miraculously you can see where the knight can go in two jumps. Use the power of 7 and sum the rows and you can count how many valid phone numbers are possible from any starting position!
> Now when documentating a state machine enough to actually draw out the graph, I always include a matrix representation as well for that reason.
Incidence matrices[1] might be an effective way to represent graphs, but the sparse nature of state machines combined with large numbers of input events and states end up making it hard to represent non-trivial state machines.
Also, state machines are often organized into sub-state machines, which are not adequately represented with incidence matrices.
Definitely. The graph is great for checking that all you specified is implemented. The matrix or complete table of possible transitions is great for checking there are no unwanted ones.
I wrote a tool at work for this. Using python to read in an Excel workbook with states and events in rows and columns that outputs a PlantUML state machine description. Worked really nicely, but not available for open sourcing at the moment.
Using python it's quite straightforward to convert between numpy arrays and sparse arrays, which are basically the graph represtation of the same data.
> State machines and finite automata are two different things
Author says that SMs and "finite automata" are different things, and links to Wikipedia to prove it. But Wikipedia says "A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation."
Author seems to take the view that something like a compiler is a "state machine", or at least can be modeled as one. I suspect that his definition (which he doesn't actually set out) translates roughly to "machine".
Finite state machines are equivalent to finite automaton, but non finite state machines are not.
The most obvious difference is that a state machine can have infinite transitions and infinite states. The most obvious example is a counter machine that simply keep tracks of how many events it received.
Such state machines can be Turing complete, but also allow to add restrictions to limit their expressiveness
Edit: to add more context Turing machines are essentially finite state machines with an unlimited memory attached and specific input events (the alphabet of the memory eg bits) and output states (move left/right, write, halt; with possibly multiple state for each output)
Function pointers as state machines has been a favorite trick of mine for very embedded C stuff. Each function sets the next state function. I actually prefer this in some cases over a switch machine. I find that big switches don’t scale/self document well.
I'm not super familiar with it, but I seem to remember using the `ucontext` library in my college OS class in a way pretty similar to this. If I recall correctly (and was using it correctly at the time, which is itself potentially an unlikely assumption), it entailed instantiating a struct that would be available as memory to each "state", and then doing basically what you describe with function pointers for state transitions. I remember being vaguely aware that I was essentially creating a directed graph that would be used to determine what to run next, but looking back, I don't think I made the final logical step from there to realizing that this was just an implementation of state machines (which I knew about from my more theory-oriented classes); at the time, I remember thinking that it was a rather cumbersome way to specify what code to run next instead of just writing out everything I wanted in order. I hope my TAs were as amused reading what must have been a giant heap of spaghetti code as I am thinking about it now, but I probably wouldn't be amused actually having it in front of me and having to read it along side a few dozen other project submissions that were written similarly.
For people developing on Apple platforms don’t miss the state machines that are part of Gameplay Kit. It’s pretty simple to use them for anything, not just games.
I'm not too familiar with Sketch (have seen the name, maybe visited the site previously) but is the focus comparable, and how so?
Independently of XState's visualizer and more recent IDE/plugin offerings, XState allows you to declaratively specify statecharts and fsms (vanilla JS object notation), define handlers (functions) for transitions and services, and then instantiate those machines via an interpreter provided by XState. It might not be fun to do all that, say, in a Node.js REPL, but you could.
State machines are cool but they don't compose well out of the box. Behavior Graph let's you build a composable network of them so they become a practical software architecture. (Disclaimer, I am a coauthor) https://github.com/yahoo/bgjs
Hi. Thanks for the reply. (Pardon my drawn out response. I can nerd out on this all day.)
I'm not aware of sub-state-machines as a standard concept. There are State Charts which are a superset of state machines and have their own notions of composition (XState is an implementation).
A sub-state-machine may feel like an intuitive concept but it does lead to a number of design decisions and related tradeoffs.
For example:
- We can have "State Machine A" influences "State Machine B". In order to make that happen there needs to be code in A that notifies B. Perhaps we do this with an explicit function call B. That's not too bad, but we are introducing a tight coupling between them.
- We can also have "State Machine A" influences a number of downstream state machines. Now we need many function calls or instead implement some observable or event protocol. That's also not too bad but its certainly not out of the box.
- Or we can have "State Machine A" and "State Machine B" both influence "State Machine C". In order to avoid updating C twice (glitches) we need some coordinating code that understand the dependency graph. I know from experience that is definitely not easy or obvious.
- And additionally we can address what it means for state machines to come and go over time which changes the dependency graph.
Behavior Graph is our implementation of those ideas in a slightly more general sense (we aren't restricted to _finite_ state machines and we have a generalized notion of events and observers).
I know talking about things this abstractly can make people's eye's glaze over so I won't belabor it too much, but that's what I mean by "don't compose easily out of the box".
That’s interesting conceptually. Coming from a games background we don’t tend to think about the state machine as the primary element but wrap them inside other concepts. So an Entity might contain multiple state machines but communication and update is mediated by entities rather than between the state machines themselves. So I’m nodding along to the issues you raise but also feel like they get solved quite neatly with the game approach.
Sub-state machines or hierarchical state machines have been a thing in games for quite a long time. It’s a natural extension particularly for AI although IMO it’s mostly reducing a cognitive burden.
The folks behind the SCXML spec were trying to address some of those concerns, albeit in the abstract manner required of platform-independent spec authors:
Work on that goes back to the early 2000s, when XML was on the rise. One of the more important and lasting contributions of that work is likely Appendix D, "Algorithm for SCXML Interpretation":
I suggest ignoring the XML-specific aspects of it; consider that such tree-shaped data structures can as readily be encoded in JS objects (including stringified JSON). Also consider the larger spec's notions of `send` and `invoke` for "External communications":
Sub-state machines have been around since at least 1970. They were used in NLP, where they were coined Augmented Transition Networks. Those were FSA with a stack (and variables), but when you don't do recursion, it's substituting an edge with another FSA.
We live in a post UML landscape, nevertheless diagramming methods like state machines, activity and sequence diagrams, class and component diagrams are used everywhere. And the ones not using them miss out.
We should start respecting these standards again just not treat them religiously like we did in the 2000s.
Can someone recommend a good primer on _implementing state machines_? I’ve only really encountered the theory and the diagrams, but have had a harder time finding examples of actual implementations in code.
There're different ways to implement a state machine, table-driven, object-driven, function pointer driven, callback based, etc. If you just want a simple and hard coded sate machine, nothing beats switch statements. You can do something like the following.
enum State { S1, S2, S3, S4, ... , END }
State transition(State current_state, int input) {
switch current_state
case S1:
switch input
case 100: new_state = S3
do_action1()
case 101: new_state = S4
do_action2()
default: error()
case S2:
switch input
case 100: new_state = S3
do_action3()
case 206: new_state = S11
do_action4()
case 207: new_state = S12
do_action5()
case 208: new_state = S19
do_action6()
default: error()
case S3:
switch input
...
...
return new_state
}
run_state_machine(int[] inputs) {
State state = S1
foreach input in inputs
state = transition(state, input)
}
That's it. It's simple to understand and it's clear what the legal transitions are from each state based on the input. You can attach actions and data update on each state transition to do something useful.
The primer is simple: if you notice that your code is using too many if statements, especially nested ones, and you are starting to wonder if you are covering all alternatives and cases, then using the rigor of a state machine may help.
Stop and write a proper case statement (aka a state machine). You may discover that combinations of booleans (in my example, stopped & !jumping) deserve to be their own state. The insight is that the resulting code should be one clean case statement, with no nested ifs allowed. Then you know you cover all the states/cases.
“If” conditions and state machines are not mutually exclusive. You can implement a proper State machine with “If” conditions.
That switch-case alternative you’re suggesting? That’s just another manifestation of the same concept behind “If” conditions. So, really, with case statements, you’re still implementing nested conditions, just in mixed ways (a mix of case statements and “If” conditions)
The distinguishing characteristic between state machine and bad logic is that the top level conditions are the states, rather than the inputs.
I had a job interview question: "In Python, write a class to implement a state machine."
Me: So, each instance should represent a state, and include a list of states it could transition to, and methods to transition to them? Is that what you had in mind?
Them: Well, if that's what you think a state machine is, then sure.
Me: There are a million ways I could implement this. What context will this be used in? I can make sure I write something that meets those requirements.
Them: Do you not know what a state machine is?
Me: Of course. But how are you planning to use it?
Them: I can't believe you don't know what a state machine is.
So as far as I can tell, I have no idea how to implement one.
Or they realized in that moment they didn't feel confident enough in their own understanding of state machines to critique anyone who might take the opportunity to cut them down to size. It is a stupid reaction to a sensible request for clarification, there are tons of equally valid ways to implement a state machine in an object oriented python script - especially when there are zero constraints on expected use. If I'd asked such a question, and got no sense of pushback, I'd be a little nervous about hiring that person and having them need close supervision - because they were to scared to point out ambiguity in direction.
there are tons of equally valid ways to implement a state machine in an object oriented python script
...and chances are that the interviewer would be fine with any of them, or ask questions after you've shown a solution.
If I'd asked such a question, and got no sense of pushback, I'd be a little nervous about hiring that person and having them need close supervision - because they were to scared to point out ambiguity in direction.
That's the exact opposite impression I have; someone who doesn't need to ask many questions, as long as they can justify their decisions well, is definitely more preferable to someone who constantly asks and needs to be lead every little step of the way.
> ...definitely more preferable to someone who constantly asks and needs to be lead every little step of the way.
Asking for clarification before starting isn't anywhere close to "needs to be lead every little step". If you are hiring a work crew for roadside ditch digging than your interview method might be a good idea, but for a job where implementation details matter - bad idea. One of my more difficult professional experiences was fighting the urge to displace blame for a wasted week of work, which would have been avoided had I asked for the tasking to be described back to me - or had he spoken up and said "Do you mean this or that?"
the question was about a state machine. could there be a more general task to give a programmer? certainly no task would ever be assigned to them on the job that would be anywhere near that general.
questions like that don't show you how they'll be on the job, they're an opportunity to see their thought process, but you won't get that without talking to them.
The first reply is passive-aggressive and is inappropriate in the context of an interview (assuming that's word for word what has been said).
A better answer would be either "Yep sounds good to me" or something along the lines of "Let's step back and first define what a state machine should do".
Even if GP was not getting the job it is the responsibility of a good interviewer that GP leaves the room having learned something. If GP left this interview still not knowing what a state machine is (or what the interviewer thinks a state machine is) or no closer to an implementation of a state machine then the interviewer has failed as much as the candidate.
it is the responsibility of a good interviewer that GP leaves the room having learned something. If GP left this interview still not knowing what a state machine is (or what the interviewer thinks a state machine is) or no closer to an implementation of a state machine then the interviewer has failed as much as the candidate.
I strongly disagree. An interview is an assessment, not a tutorial.
I’m a staff-level engineer with thousands of LoC on GitHub, and many times that inside my employers’ repos. I know how to program. I wasn’t asking them to teach me what a state machine is or how to write one. Instead, I was trying to narrow down a thousand possibilities to the ones that would meet their requirements. You know, like I’d be doing on the job if they’d hired me.
When the CTO says “we need a thing”, I don’t sit down and start writing. I try to learn what we’ll need so I can build something that satisfies my stakeholders’ needs.
If I were interviewing you, and said “hey userbinator, make a paragraph”, and you did that without asking WTF I was talking about, the rest of the session may not go well.
i'm not so sure the first reply was, "go ahead and do what you think is right", it could've just as easily been, "guess what i'm thinking." actually, their refusal to talk about what they were asking for makes it more probable that it was the second one.
they may be glad they didn't hire them, it's hard to say how they feel, but i bet they're one of those companies out their complaining they can't seem to hire anyone at any price.
That sounds to me as if the interviewer had said "write a program". It seems rather natural to ask "OK. What do you want the program to do? Shall I write a program that takes some input, and outputs it reversed? Would that do?", and they said "If that's what you think a program is, then sure."
At that point, it's probably best to stop arguing, and code. They probably want to argue with you about your code, not their spec.
But when I got the reply "Do you not know what a state machine is?", I think I might have thanked them for their time, and left. I would have been sorely tempted to come back with "Yes, a state machine is an abstraction, and you seem to want a concrete implementation, but you don't seem to want to fill in the details of your requirement. Is it a good use of our time together for me to complete your spec, so there's something for me to code up?"
It sounds like they didn't want you; perhaps your face didn't fit. They say most interviews are decided in the first couple of minutes.
I recently did an interview that went something like this too. The questions weren’t state machines. But like your experience, they boiled down to “I have some interesting experiences that feel kind of unique to me, is it possible you’ve had them too?” It was a mid level relatively seasoned person, but they admitted interviewing was kinda new. So it really came back to that “do you think we could experience a sort of cohort chemistry here” vetted by a pretty arbitrary set of “let’s find some geeky things to get connect about.” And like you, I’m not disappointed they chose to keep looking.
def next_state(state):
if state == 90000:
return 0
return state + 1
But more seriously; once I was asked to implement offsetof in an interview for an entry level C++ position. I didn't quite remember that this was impossible during the heat of the interview, but I did remember enough to not produce an incorrect solution that relies on undefined behavior. I didn't get that job.
For one possibility, look up the State design pattern.
Basically, you have a variable that holds an (immutable) object representing the current state. All states that can be assigned to that variable (all abstract states the system can be in) implement a common interface (the static type of the variable), which in particular includes a method (or methods) for asking the state what the next state is given a particular event. The method then returns the new state. Whenever an event occurs, you ask the current state stored in the variable (call its respective method) to compute the next state given the current event, and then you assign that new state returned by the method to your state variable.
The common interface usually comprises further methods that define/implement the behavior of the system in the given state. For example, if the states correspond to the different modes of an editor, there could be a method that implements what happens when a key is pressed in the specific state.
There are two different types of state machines that behave differently. Moore machines have actions (or outputs) determined by the state while Mealy machines have actions determined by the specific transitions (or state + inputs).
Depending on the system and implementation constraints one type works better than the other (e.g. Mealy machines can implement Moore machine behavior with one less state, which may save hardware).
I'm not sure "assign reviewer" would fit either in Draft.exit() or InReview.entry(). I guess you'd implement something like "ensure reviewer assigned" in InReview.entry() instead. Which would work, but would itself contain the sort of state-dependent logic that a state machine is meant to surface.
Putting it in the entry is probably what I’d do, or I’d split the “InReview” state into its own sub state machine. It’s hard to reason exactly with imaginary scenarios though.
I think two states is probably a bad idea. Obviously the use case is hypothetical, but I'm assuming the set of transitions available from the In Review state does not depend on the path you took to get there.
It really depends on your programming language. In C it's not much more then a switch case over an enum where every enum value is a concrete state. It languages with pattern matching and ADTs it's much more ergonomic since a state machine then is just a function from a state and an input to a new state and an output.
For large state machines sure. For smaller ones no. My point wasn't that enum is the only way to do it in C. Just a simple representation that is used in practice that I could explain in a single sentence.
>"In C it's not much more then a switch case over an enum where every enum value is a concrete state."
This is but stupidly primitive representation / implementation of SM (yes it is useful in very simple cases). You can do way better in C. Somebody else already presented more advanced design.
There are some good state chart compilers like http://www.colm.net/open-source/ragel/ (disclaimer - haven't used it in years) that you can look at the output of.
It really depends on what you want in terms of implementation. On one hand, a big chunk of digital logic is about implementing large, high-speed state machines using circuits.
On the other hand, regular expressions and things like lexers are largely based on finite-state machines so there is a ton of information related to those, but they often implement things more complex than finite-state machines in order to be more expressive.
In terms of manually implementing them yourself, I think the naive implementation based on the mathematical definition of a deterministic finite automata is pretty good for a small number of states for things like tracking program state. In particular, explicitly listing the total set of expected inputs/transition criteria, explicitly listing the states, and having a single function that takes the current state and current transition-relevant data and produces a new state.
This representation is nice because it makes the behavior inspectable in one location. This makes it easier to notice the edge cases and prevent the state representation and possible transitions from getting spread all over code. The transition function can be a switch statement or a table. Really any way of writing a two-input function with a finite number of inputs and outputs will work. Many people have also explored strongly-typed versions of this, which are worth a look as well.
There is also a DOT file (and SVG image) of the resulting state graph (the code to generate the DOT file directly from the FSM dict is at the bottom of the mousebindings.py file.)
Game Programming Patterns by Robert Nystrom has a chapter on state machines. It’s both freely available online or for purchase if you really like it and want to support him.
Context just holds the global stuff of the process, data is the new input into the machine and state is the current state.
A simple example is an SMTP server. State is the current command (or idle), context is email message being built, and data is the line read from the socket.
Context context = new Context();
sendSMTPBanner();
State state = new IdleState();
while (!state.isFinished) {
String data = readLine();
state = state.next(context, data);
}
I am also in search for a elegant way to teach such implementations in Python. I do not want students to confuse this with OO, not sure if they see the value in functional programming so soon. My best idea so far is to teach the concept of state and state machines with Python generators…
Svelte + FSM turned one of the most convoluted UXes I've every dealt with into something manageable and almost pleasant.
This is a complex sales kiosk that must operate work limited or flapping network connectivity entire handling huge spikes in usage.
Svelte itself jusy gets out of the way, you don't fight it. The FSM makes your mental model explicit.
Something like "ok, we're halfway through the complex terminal registration process, the last network request timed out and the user pressed the back button, we have half the necessary data cached in indexeddb, now what?"
What nobody seems to understand is that all software and all digital hardware are state machines. So thinking in state machines makes it possible to clearly think about software. TLA+ is an example of this thinking applied to modelling software.
I really struggle with the value of simple state machine diagrams. For example, I get very little out of the Unix process state machine diagram. I've also seen designs involving just two states. What am I missing?
State machine diagrams illuminate system semantics without code: “when an API returns 403, go to REQUEST_AUTH state.” The transitions/states can then be observed by outside code to trigger UI/side effects.
Done correctly, you can disentangle the decision-making code from the side effecting code to maximize reasoning ability.
I think the simplest one I ever did was basically a reimplementation of setTimeout in Javascript. It was really only intended as a demonstration, because of course setTimeout is right there, but with only a very slight extension you can save the time you’re supposed to activate to permanent storage so that you can set long timeouts (hours or days) and they still fire correctly if the user leaves the page and returns later. And the code is clear and obviously correct, and now the reader has some idea of how to use the code to create more interesting state machines.
You might be missing Prof. Harel's innovations in the 1980s, which have seen and do continue to see use in a number of hardware/software engineering fields, but still seem to be mostly under appreciated:
Not sure I necessarily agree with all these. Its common in game programming to use a form of state machine that defines a character's animation. Characters can be in an idle state, an attacking state, a hit-react state. Because its desirable to have the animations blend, the state machines transitions are not atomic.
Now, you could argue that this design is not a state machine but I think its more useful to understand that such a thing that is VERY similar to a state machine but has non-atomic transitions does exist and is commonly used.
Think about the following: The transitions from one state to another are triggered by specific events. What happens in the game when such an event occurs during the transition? Unless the event is outright ignored during transitions, the object (character) is in some state which defines how it reacts to that event. Maybe it’s a separate “transitioning” state, or maybe the character is logically already in the target state, even though the transition animation is still playing out.
The bottom line is: States are defined by how the system reacts to events. Insofar as the system always reacts to events in some way, it is always in a specific state.
I really have no idea what you're trying to say here. If a system responds to events it's in a state? Is anything not a state machine by this definition?
Anyway, my point was that these are all just conceptual models and another conceptual model that's useful is one with non-atomic transitions.
A state is a (mathematical) function from events to the next state. There is a set of events that can potentially occur, and the function tells you what the next state will be given that event. That’s the mathematical definition of a state machine. You can reverse-engineer what states a system can be in by considering what those possible functions are.
For example, consider a state A of some object in your game. For event E (say, the player presses some specific button), the object may transition to state B. For a different event F (say, the object collides with a particular type of other object), it may transition to state C. For yet another event G, the object may remain in state A. Thus the function corresponding to A is { E -> B, F -> C, G -> A } (assuming that E, F, G are the only possible events).
Now, you’re saying that the object can be within the transition from (say) A to B. The question is, if one of the possible events occurs during that transition, what does the corresponding function look like? For example, if event F occurs, does the object still continue to go to B, or does it maybe now go to C, or to yet another state? You can write down the corresponding function. If that function is the same as the A function, then that means that the object is actually still in state A. If the function is the B function, then it means the object is actually already in state B. If the function is different from both the A and the B function, then it means the object is actually in a third separate state.
Note that an event can also be “the transition animation has finished playing”.
The point is, using that functional definition of states (which is the usual definition of state machines or FSAs), for any system with non-atomic transitions there is an equivalent state machine with atomic transitions, and that latter one is what is normally understood to constitute a proper state machine.
One thing to add: A major benefit of state machines is that you can clearly reason about its behavior. If, however, you have non-atomic state transitions, the behavior during a transition, i.e. how it reacts to events occurring during a transition, is unclear. The reason why state transitions are normally considered to be atomic is so that the system is in a well-defined state at every point in time, so that in turn the behavior of the system is well-defined at every point in time.
Thank you for good article. I've used SM extensively since the 90s. I've even written a software product once which was enterprise grade SM visual designer and runner. It was used in real life to facilitate interactions between various subsystems between multiple Telecom companies. Later on much bigger company came with their business process middleware (basically the same thing) and us being very familiar with the tech has brought very fruitful partnership.
I wish there was some tools like Unity animation panel or Behavior Tree plugin in Unity.
Tools that would integrate well with any code in JS. Maybe you would define blocks with code, and wire the things up in the IDE but with a graphical interface. Kind of like how draw.io is integrated in Jetbrains IDE (and certainly in VSCode too).
Unrelated to javascript, but in the robotics industry there is a trend towards Behaviour Trees. https://www.behaviortree.dev/ is a C++ library that was originally designed for controlling robots via ROS, but it appears to be decoupled from the ROS ecosystem so it could be used for other projects.
The most common way to abstractly describe state machines is the directed graph, but (like nearly all graph problems) it's often just as illuminating if not more to decompose the graph into a matrix as well. So rows are states, columns are events, and the intersections are transitions. Being able to run down a column and see what happens in each of the states when a certain event is processed has made a lot of bugs much more obvious for me.
Now when documentating a state machine enough to actually draw out the graph, I always include a matrix representation as well for that reason.