9 ms·
Facts about State Machines
- dqpb 4y agoThis is an excellent write up! > Combinatorial explosion can be mitigated through nesting and parallelizing You can also add an intermediary state to handle this. Instead of NxN you can have Nx2 by doing N->I->N.
- michaelsbradley 4y agoStatecharts (hierarchical state machines) for the modern web: https://github.com/statelyai/xstate#readme https://github.com/statelyai/xstate#readme https://xstate.js.org/ https://xstate.js.org/ Interactive visualizer: https://stately.ai/viz https://stately.ai/viz
- Jtsummers 4y agoIn a similar vein: https://sketch.systems https://sketch.systems
- michaelsbradley 4y agoI'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.
- slevcom 4y agoState 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 https://github.com/yahoo/bgjs
- jayd16 4y agoWhy not? Don't they compose easily with sub-state-machines?
- slevcom 4y agoHi. 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".
- dqpb 4y ago> I'm not aware of sub-state-machines as a standard concept. Hierarchical State Machine.
- michaelsbradley 4y agoThe folks behind the SCXML spec were trying to address some of those concerns, albeit in the abstract manner required of platform-independent spec authors: https://www.w3.org/TR/scxml/ https://www.w3.org/TR/scxml/ https://en.wikipedia.org/wiki/SCXML https://en.wikipedia.org/wiki/SCXML 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": https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation https://www.w3.org/TR/scxml/#AlgorithmforSCXMLInterpretation 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": https://www.w3.org/TR/scxml/#external-module https://www.w3.org/TR/scxml/#external-module
- renlo 4y agoCan 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.
- jen729w 4y agoThe XState (JS framework) docs and community are great. Spend a bit of time hanging out there and you'll get the idea. I'm a big fan. https://xstate.js.org https://xstate.js.org
- rowanG077 4y agoIt 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.
- Joker_vD 4y agotypedef struct State State, *StateMachine; typedef void (*Event)(StateMachine *sm); struct State { Event TurnOn; Event TurnOff; Event MakeStuck; }; void IdleTransition(StateMachine *sm); void BecomeOn(StateMachine *sm); void BecomeOff(StateMachine *sm); void BecomeStuck(StateMachine *sm); const State StateOn = { .TurnOn = IdleTransition, .TurnOff = BecomeOff, .MakeStuck = BecomeStuck }; const State StateOff = { .TurnOn = BecomeOn, .TurnOff = IdleTransition, .MakeStuck = BecomeStuck }; const State StateStuck = { .TurnOn = IdleTransition, .TurnOff = IdleTransition, .MakeStuck = IdleTransition }; void IdleTransition(StateMachine *sm) { } void BecomeOn(StateMachine *sm) { *sm = &StateOn; } void BecomeOff(StateMachine *sm) { *sm = &StateOff; } void BecomeStuck(StateMachine *sm) { *sm = &StateStuck; } StateMachine sm = &StateOff; It's still C but arguably much more concise than a switch, wouldn't you agree?
- 4y ago
- jayd16 4y agoNot 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.
- murderfs 4y agoThat just means that the actual state machine has intermediate states for each transition.
- jayd16 4y agoYou can look at it this way but it's much more useful to treat them as conceptually non-atomic.
- layer8 4y agoThink 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.
- jayd16 4y agoI 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.
- FpUser 4y agoThank 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.
- monocasa 4y agoOne 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.
- flir 4y agoHmm. I wonder if the dot language (which is how I draw state machines) can be turned into a matrix as easily as it can a graph. Don't see why not.
- Multicomp 4y agoPotentially you could see about adapting the https://graphviz.org/docs/layouts/patchwork/ https://graphviz.org/docs/layouts/patchwork/ layout?
- emmelaich 4y agoDo you know of a tool to draw a graph from a matrix or vice-versa. It doesn't sound too hard but I'm sure there are wrinkles.
- kejaed 4y agoI 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.
- viraptor 4y agoJust write one yourself. It's really trivial to do. Foreach node Foreach node.transition Matrix(node, transition.event) = transition.destination And the other way: Foreach node Foreach event Destination = matrix(node, event) Graph(node).add(event, destination)
- gumby 4y ago> I hold the opinion that state machines are often misunderstood and under-applied An excellent starting point for this post. I couldn't agree more.
- mikessoft_gmail 4y ago
- abnry 4y agoI 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?
- michaelsbradley 4y agoYou 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: https://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Statecharts.pdf https://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Stat...
- drhodes 4y agoHere's a one that tracks the state of a button with mouse interactions https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/button-fsm/ https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/b...
- db48x 4y agoI 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.
- mikessoft_gmail 4y ago
- travisgriggs 4y agoFunction 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.
- saghm 4y agoI'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.
- arinlen 4y ago> Function pointers as state machines has been a favorite trick of mine for very embedded C stuff. Each function sets the next state function. This is the basis of OO's State pattern. https://en.wikipedia.org/wiki/State_pattern https://en.wikipedia.org/wiki/State_pattern
- mbrodersen 4y agoWhat 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.
- a4isms 4y agoTwo discussions about state machines on HN from 2018: 1. "How I Learned to Stop Worrying and Love the State Machine" link: http://raganwald.com/2018/02/23/forde.html http://raganwald.com/2018/02/23/forde.html comments: https://news.ycombinator.com/item?id=16468280 https://news.ycombinator.com/item?id=16468280 2. "More State Machine Love: From Reflection to Statecharts" link: http://raganwald.com/2018/03/03/reflections.html http://raganwald.com/2018/03/03/reflections.html comments: https://news.ycombinator.com/item?id=16606379 https://news.ycombinator.com/item?id=16606379
- macshome 4y agoFor 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. https://developer.apple.com/documentation/gameplaykit https://developer.apple.com/documentation/gameplaykit
- infogulch 4y agoCan CRDTs be modeled as state machines? Maybe state machines with rules on how you are allowed to transition between states?
- aj7 4y agoIan Horrocks Book https://cloudflare-ipfs.com/ipfs/bafykbzaceaffaddwzzdbdu57rg5evfc7uj7rp5f5hgfbftijxyt25dagjsnsm?filename=Ian%20Horrocks%20-%20Constructing%20the%20User%20Interface%20with%20Statecharts-Addison-Wesley%20Professional%20%281999%29.pdf https://cloudflare-ipfs.com/ipfs/bafykbzaceaffaddwzzdbdu57rg...
- ColinWright 4y agoState machines are a brilliant tool, and turn up more often than you expect once you have the background and experience to see them. Some time ago I wrote up a particularly simple but elegant example I came across. The write-up is here: https://www.solipsys.co.uk/new/StateMachineInRealLife.html?vj01hn https://www.solipsys.co.uk/new/StateMachineInRealLife.html?v... In case people would like to discuss that specifically, I've (re-)submitted it here: https://news.ycombinator.com/item?id=33045211 https://news.ycombinator.com/item?id=33045211
- arinlen 4y ago> State machines are a brilliant tool, and turn up more often than you expect once you have the background and experience to see them. "A Computer is a state machine. Threads are for people who can't program state machines." - Alan Cox
- jibbit 4y agoParaphrasing Joe Armstrong: "What's the worst order to handle events in? The order they arrive!"
- denton-scratch 4y ago> 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." https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine 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".
- comfypotato 4y agoGood catch. The author directly contradicts themselves here. Can’t help but wonder if the rest is worth reading now.
- afiori 4y agoFinite 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 https://en.m.wikipedia.org/wiki/Pushdown_automaton https://en.m.wikipedia.org/wiki/Pushdown_automaton 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)
- oaiey 4y agoWe 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.
- pragmatic 4y agoA great use case (as mentioned in the article) is complex UI state. I've used this library very succesfully in such a situation: https://github.com/kenkunz/svelte-fsm https://github.com/kenkunz/svelte-fsm 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?" With boolean flags its a mess.
- pragmatic 4y agoOn this scenerio each page has a starter machine and some components might as well. So you can in fact nest state machines. Totally undeused concept I've been trying to implement since the VB6 days.
- Heyso 4y agoI 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).
- dhon_ 4y agoUnrelated to javascript, but in the robotics industry there is a trend towards Behaviour Trees. https://www.behaviortree.dev/ 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. There is a basic UI available for editing the tree https://github.com/BehaviorTree/Groot https://github.com/BehaviorTree/Groot