14 ms·

How I Learned to Stop Worrying and Love the State Machine

• epx 9y ago
  Coincidence, I've written something about it two weeks ago (in Portuguese, unfortunately: https://epxx.co/logbook/entries/sm.html https://epxx.co/logbook/entries/sm.html). About Petri Nets as well. It is difficult to understand why so many junior programmers use a dozen boolean state variables instead of a state machine, given that they learn it in CS or similar courses. My guess is they are taught in an overly scientific fashion, so they go to the same dusty corner where so many other CS topics that are never used in practice lie already.
  • stcredzero 9y ago
    go to the same dusty corner where so many other CS topics that are never used in practice lie already I've been meaning to write a letter to the CS department of one UC school: What the hell are they teaching in CS nowadays? If presented with a situation where the user can create circular references, there's one UC school that produces graduates with high 3.8+ GPAs, virtually none of whom I've interviewed can give you an implementable description of how to detect circular references. As a general pattern, they also tend to say silly things, like that a null pointer member of a structure uses up no data. I can go on and on. It seems to me they are being taught by TAs who would also flub such points in an interview.
    • hateduser2 9y ago
      How is being able to detect circular references a useful skill?
      • stcredzero 9y ago
        > How is being able to detect circular references a useful skill? For all kinds of systems, where there are references input by users as data, one needs to be able to contend with this. Systems which crawl webpages have to contend with this. Parser-transformation systems need to detect these. Such detection could be useful in memory management. It's not just the ability to detect a circular reference. It's the ability to contend with problems of that type. Furthermore, two of those UC system CS grads had eerily similar responses, consisting of, "Oh, is that a graph algorithm?" plus a literal handwave. Is there some pool of TAs somewhere that has that attitude towards graph algorithms?
        • westoncb 9y ago
          Hmm, this seems like a kind of understandable attitude if I'm reading it correctly. Hearing that it's a (standard) graph algorithm means it's a solved problem so you don't need to worry about it: pick up a text book or Google and compare the available options—easy.
    • bschwindHN 9y ago
      Detecting circular references is one of those "tricks" which end up being a bad interview question because you either know the trick or you don't.
    • seanmcdirmid 9y ago
      GPAs are not normalized across universities. The higher the average GPA for the school's graduates, the more likely grade inflation is at work.
  • schoen 9y ago
    > O autômato mais poderoso é a Máquina de Turing, a que equivale todo computador de uso geral. It's the most powerful realizable automaton (although it's not even fully physically realizable because of the infinite tape), but people have studied far more powerful automata: https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Arithmetical_hierarchy https://en.wikipedia.org/wiki/Arithmetical_hierarchy In these models the oracle is so called by analogy to prophetic oracles of antiquity, who were believed to obtain reliable information from an incomprehensible and supernatural source. :-)
  • braythwayt 9y ago
    > they go to the same dusty corner where so many other CS > topics that are never used in practice lie already. https://www.skorks.com/2011/09/why-developers-never-use-state-machines/ https://www.skorks.com/2011/09/why-developers-never-use-stat...
  • HumanDrivenDev 9y ago
    > It is difficult to understand why so many junior programmers use a dozen boolean state variables instead of a state machine, given that they learn it in CS or similar courses. If you think that's a head-scratcher, the fact that senior developers consistently do the exact same thing must really confuse you!
  • westoncb 9y ago
    It makes sense to me that junior programmers would not jump to state machines for something like, e.g., handling complex UI state. I see the reasons as twofold: 1) How would you describe the reason for using state machines over handling the state and transitions through if-statements and sprinklings of booleans? The best I can come up with is that it allows you to be explicit about which states exist, how they can be moved between, and what other code should execute when transitioning. It basically comes down to the architectural principle of 'cohesion': put related things nearby one another. This is pretty fuzzy until you've actually had concrete experience getting bitten by the lack of cohesion and attendant unmanageable complexity. To sum up, it's something you need to learn through experience—especially because another aspect of the problem is identifying situations where it really make sense rather than some simplistic heuristic about using state machines is better than not. 2) The way they're taught in school is generally about theory of automata, or they're used to diagram the behavior of some simple little system. Using them to control state transitions in applications is unlikely taught at all, and isn't really directly implied by the seemingly related things which are taught.
  • deckard1 9y ago
    > It is difficult to understand why so many junior programmers use a dozen boolean state variables instead of a state machine It's not just juniors. The only times I've encountered state machines in the wild are almost exclusively games and virtual machines/interpreters. The reason, to me at least, is pretty clear. In both games and VMs, you mostly know the rules ahead of time. You have a clear picture of the opcodes you want to implement (add, mul, call, jump, etc.) or the game rules you need. But for most development, especially with multiple stakeholders or customers and multiple developers working independently, the rules aren't known at the start. In fact, the majority of requirements are brought up months or years after the first line of code is even written. It's like the parable of the blind men and the elephant (https://en.wikipedia.org/wiki/Blind_men_and_an_elephant https://en.wikipedia.org/wiki/Blind_men_and_an_elephant). Each person, working separately, has a different idea of what this thing is that you're creating. Communication being an incredibly difficult thing, the requirements are never fully rendered coherent by the entire team at the moment where it would benefit them most (i.e. the beginning).
    • braythwayt 9y ago
      In my experience, this is when you need the skill to know to refactor to a state machine and/or refactor to some other form of composition (strategy objects, has-a, or whatever). As taught in school, State Machines are formalisms that fit well when everything can be formally specified. As I have learnt, State Machines in programming help to reorganize things that have evolved haphazardly.
• sktrdie 9y ago
  I've been studying state machines and specifically statecharts (which are essentially state-machines with hierarchy) for a while now. Here's a great resource to learn more https://statecharts.github.io/ https://statecharts.github.io/ I absolutely fell in love with them and haven't looked back ever since I learned more about how they work. As the author explains in this post we're implicitly writing state-machines all the times in the form of code. The idea of making them explicit, rather than implicit, helps us visualize the behavior which would've otherwise been hidden in code. I'd highly suggest to also read this paper by David Harel, the creator of statecharts, On Visual Formalisms: http://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/VisualFormalisms.pdf http://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Visua... If you're a frontend developer checkout my post on the subject related to React and Redux specifically: https://medium.freecodecamp.org/how-to-model-the-behavior-of-redux-apps-using-statecharts-5e342aad8f66 https://medium.freecodecamp.org/how-to-model-the-behavior-of...
  • nrclark 9y ago
    Is there much in the way of FOSS statechart implementations? It's been a while since I looked into the ecosystem. I remember that the canonical one was always the Quantum framework, but I never wanted to deal with the licensing aspect of it.
    • Serow225 9y ago
      Definitely not FOSS, but Stateflow is used a ton in scientific computing (Automotive, Control Systems, etc): https://www.mathworks.com/products/stateflow.html https://www.mathworks.com/products/stateflow.html
    • davidkpiano 9y ago
      Hey! I'm the creator of xstate: https://github.com/davidkpiano/xstate https://github.com/davidkpiano/xstate - a pure, functional, declarative implementation of statecharts in TypeScript. It has zero dependencies, is frameworkless, and fast (O(n) state and transition look-up time for most cases). I have some important updates to announce at JSConf Iceland, including the ability to translate to/from SCXML, and an improved visualizer. Let me know what you think!
• nickpsecurity 9y ago
  And once you're confortable with FSM's, you might try Abstract, State Machines (ASM's) for formally specifying or verifying software: http://www.di.unipi.it/~boerger/Papers/Methodology/BcsFacs07.pdf http://www.di.unipi.it/~boerger/Papers/Methodology/BcsFacs07... Microsoft even had a gool, AsmL, for this method. TLA's PlusCal specs look similar to some Ive seen in ASM's, too.
  • metalliqaz 9y ago
    Microsoft has the best gools.
    • mcguire 9y ago
      Microsoft has the only gools.
• wyldfire 9y ago
  The state machine is a powerful/clear metaphor to align your design. IMO hierarchical state machines (aka Harel statecharts) are a superior variant that makes behavior yet clearer and easier to design.
  • stcredzero 9y ago
    Harel statecharts I wonder how those map to "Behavior Trees" in game development?
    • meheleventyone 9y ago
      A behaviour tree is sort of a hierarchical state machine but one in which the states are not explicit. They fall out of how you arrange the nodes in the tree. Actual hierarchical state machines are pretty common for driving a variety of things. Probably most commonly animation but also driving game state.
      • stcredzero 9y ago
        Actual hierarchical state machines are pretty common for driving a variety of things. My understanding of hierarchical state machines, is that they're equivalent to Context Free Languages in terms of computational power.
    • dahart 9y ago
      FWIW, I wrote one for a game engine, and I'm aware of several others. I can safely say they map cleanly enough that the names are more or less synonymous, at least as far as the underlying concept goes.
• braythwayt 9y ago
  A colleague raised the point that state machines (or their richer variations) work best in models with low cohesion. Anybody here have some thoughts/experience with this point of view?
  • tonyarkles 9y ago
    My (admittedly limited) experience had some high-cohesion models and it worked ok, with the caveat that they often didn't change independently. It was basically one FSM for a cluster of high-cohesion objects, and the events would mutate some subset. I agree with your colleague somewhat. If you have a system where every domain object is inextricably linked to every other domain object, then you're going to have a state explosion trying to capture the states and transitions. My gut reaction looking at a system like that is to start decomposing it, looking for accidental coupling that doesn't need to be there.
  • ahartmetz 9y ago
    I have related experience with QStateMachine versus hand-written (state variable(s) + switch + some freeform manipulation): if your state machine is "pure", using the framework is nice. If your state machine needs certain interesting transitions such as undo which don't fit in, you may be better off writing it yourself. If it fits at all, a funny state machine is better than no concept for your state variables. You still get most of the benefits. I guess domain-specific transitions like undo and cohesion mean similar things to state machines: requirements that don't cleanly fit into conventional state machine models.
• craigkerstiens 9y ago
  Love seeing more about this. It's a great design pattern for many systems. We used this approach back at Heroku to power Heroku Postgres and follow the same to power our database as a service at Citus as well (https://www.citusdata.com/blog/2016/08/12/state-machines-to-run-databases/ https://www.citusdata.com/blog/2016/08/12/state-machines-to-...). The approach has scaled extremely well due to us following a few key principles (most importantly that we don't change the state of a running database, rather we failover to some new one with the new state).
• jstimpfle 9y ago
  This is another important argument against class-based object oriented programming. There are only very few "objects" so small as the ones conventionally created in OOP. If money is withdrawn from a bank account, it's going to be put somewhere else. Withdrawing money from an account is not an operation on an account, but on a larger system that includes the account. So making an "account" class with a "widthdraw" method is a bad idea. Very often a program has only one or very few meaningful state machines, and pretty much always they are "global", i.e. there is only one of its kind in a process. Just use global state, it has the best possible syntax for OOP :-)
  • braythwayt 9y ago
    Having worked on actual banking software, I agree that an Account object with a "withdraw" method is not a real-world thing. But having also blogged for a while... There are no good examples that are complex enough to be realistic and yet simple enough that we can concentrate on the programming principle and not be distracted by the thing being modelled :-D Now as to one or two state machines... This has not been my experience. I have worked on some systems that had dozens of state machines, nearly every domain model was a state machine of some kind.
    • jstimpfle 9y ago
      Yep - The only useful explicitly coded state machines I have seen are the massive, generated ones. Like DFAs representing regular expressions.
  • dnomad 9y ago
    In the real world nobody would ever create an Account class with a 'withdraw' method. Withdrawals are always first class entities that unique IDs and states of their own. Every Withdrawal is itself a request with a lifecycle that, only if completed successfully, results in an event and changes to the system. This example is very reductive. In a rich and constantly changing domain like banking using a state machine to model core entities like an Account almost always ends in disaster. It simply doesn't work because businesses are complex and ever-changing. Virtually every time I've seen a 'STATE' property in a core entity, especially if it's a public property, it has evolved over time to become a horrendous thing that nobody really understands but it is now integrated throughout so many codebases that people have no choice but to continue supporting it. Ugh. The real point here is that state machines are mathematical, highly specified constructs. They do not change well. If you are working on a protocol that can be specified precisely, sure use a state machine. If you're working on a business entity think long and hard about whether these requirements are truly fundamental and will never change. And if you really do think you have a state machine at least don't make it public.
• notduncansmith 9y ago
  Shameless plug: I’ve been working on some open-ended state-machine-like constructs in Clojure and JavaScript - https://github.com/notduncansmith/factfold https://github.com/notduncansmith/factfold The idea is to capture the useful properties of state machines without being constrained to enumerable states. I’m currently working on a program to edit these machines visually.
• hprotagonist 9y ago
  Eric Lippert's "Wizards and Warriors" blog posts seem appropriate here, especially as an example of how tracking state and OO can clash pretty badly. A common problem I see in object-oriented design is: A wizard is a kind of player. A warrior is a kind of player. A staff is a kind of weapon. A sword is a kind of weapon. A player has a weapon. But before we get into the details, I just want to point out that I am not really talking about anything specific to the fantasy RPG genre here. Everything in this series applies equally well to Papers and Paychecks, but wizards and warriors are more fun to write about, so there you go. OK, great, we have five bullet points so let’s write some classes without thinking about it! What could possibly go wrong? https://ericlippert.com/2015/04/27/wizards-and-warriors-part-one/ https://ericlippert.com/2015/04/27/wizards-and-warriors-part... https://ericlippert.com/2015/04/30/wizards-and-warriors-part-two/ https://ericlippert.com/2015/04/30/wizards-and-warriors-part... https://ericlippert.com/2015/05/04/wizards-and-warriors-part-three/ https://ericlippert.com/2015/05/04/wizards-and-warriors-part... https://ericlippert.com/2015/05/07/wizards-and-warriors-part-four/ https://ericlippert.com/2015/05/07/wizards-and-warriors-part... https://ericlippert.com/2015/05/11/wizards-and-warriors-part-five/ https://ericlippert.com/2015/05/11/wizards-and-warriors-part...
  • jacquesm 9y ago
    That's mixing up properties, ownership and state. Those are very different concepts.
    • bdjewkes 9y ago
      That's effectively the conclusion that the series comes to in the end.
    • mehrdadn 9y ago
      It may be obvious to you but it's very hard to see this without a fair bit of experience.
    • CPAhem 9y ago
      Indeed. Whether you use OO or state machines depends on the architecture of your problem. There is unlikely to be a one-size fits all solution to every class of problem. State machines are used extensively by HDL hardware design tools, and are easier to debug.
• syats 9y ago
  Another in the series "Show HN what is it that people actually learn in their first two years of undegrad CS"
  • archagon 9y ago
    700 points, 200 comments. Clearly, you've been misinformed. (Also, I did my CS undergrad at UC Berkeley and I don't recall ever studying state machines. All the useful engineering bits and design patterns I picked up after getting my first job.)
  • Jtsummers 9y ago
    Sadly, while many people learn about state machines in their first two years (to varying degrees of formality), they often don't learn how to design code using them. I think the only course where I explicitly designed programs using state machines was compilers (other than writing things to simulate state machines in my theory courses).
  • tonyarkles 9y ago
    You'd think that... I did both EE and CS undergrad (we didn't have Computer Engineering at the time). In EE we started talking about FSMs very early on, in quite a bit of depth. In CS though, we didn't really talk about them until the Computability course in 3rd or 4th year, and even then it was in the very theoretical Finite Automata sense; applying FSMs to software design wasn't really a thing that was ever covered. From the EE material, I started loosely applying those concepts to software design, but it wasn't until my first job in industry where I was lucky enough to be exposed to a system that was very deliberately designed as a system of FSMs. We based the design of ours off of a pretty famous paper, whose name is entirely escaping me at the moment. Damn.
    • matthewwiese 9y ago
      Are you thinking of Harel's paper "On Visual Formalisms"? http://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/VisualFormalisms.pdf http://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Visua... I'm curious to know what famous paper it is so that I can go and read it!
• topaxi 9y ago
  xstate is a nice javascript library which even generates charts out of your defined states in your app: https://github.com/davidkpiano/xstate https://github.com/davidkpiano/xstate
  • restore24 9y ago
    Similarly, I have a early-stage JS library for hierarchical statecharts. It revolves around nested contexts and an explicit message passing interface for controlling states between parent/child/sibling. Example: https://github.com/jdque/royal/blob/master/test.js https://github.com/jdque/royal/blob/master/test.js
    • mpfundstein 9y ago
      off-topic but why do you use 'let' instead of 'const'? In royal.ts you do that all the time even though you variables don't change! Is there a reason for that?
      • braythwayt 9y ago
        I have no idea why they did it, but I have argued for quite some time that const has very little practical value, because its effect is always lexical and local. To demonstrate that this is so, I suggest that we can write a processor that converts all lets to consts where possible. I also demonstrate that this is so by asking, "What bug will const catch that our tests will not catch?" _Immutable Data_, on the other hand, is marvellous. Immutability has nonlocal effects, and it is not something that can be trivially verified.
        • mpfundstein 9y ago
          I agree with your assessment, but for me it is a message from the programmer to the reader. Hey this value will not be re-assigned during the following scope block. If I see a let, I know I must be careful. Of course this doesn't apply to properties of objects ... which is a pity!
  • 9y ago
• jonasvp 9y ago
  I distinctly remember the first time I looked at a overly long and complicated model class and thought: "OMG, this is a state machine!" - a shortish refactor later and it was much simpler to read and debug. However, now I'm at a loss on how to teach the junior programmers at my company how to recognize which patterns scream "turn me into a state machine!" Several booleans triggering certain code paths in several methods is a pretty sure sign. Are there more?
  • bsder 9y ago
    The word "protocol" is a big red flag that you should be using a state machine. The words "event loop" probably mean you need a state machine. If "time" is an input variable, you probably have a state machine.
    • disease 9y ago
      Your second and third points are why I love having state machines in the games I develop.
    • criddell 9y ago
      I've also found the presence of a mode variable a good indicator that a FSM should at least be considered.
  • yen223 9y ago
    If you have a "status" field in your object, chances are you can represent it as a state machine
• skybrian 9y ago
  I find the original example to be much clearer. If you want to know about all the valid transitions from the 'held' state, search for all usages of 'held'. Adding complicated dispatching doesn't help readability. This seems a lot like the expression problem [1]. There are no perfect solutions. A problem can be split along multiple dimensions, but not all at once, or at least not as code saved in a text file. Whether you split the problem first by method or by state, you will have code that's located far away from closely related code. [1] https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem
• richdougherty 9y ago
  Here's a tip for state machines. If you've got a transition that takes some time then you often actually need another state to represent the state that the system is in during the "transition". This is usually modeled better on backend systems (a state while waiting for a network response to arrive) but is often modeled poorly in front-end systems (a state while waiting for an animation to finish).
  • Klathmon 9y ago
    This is one of the reasons why I love ReactJS. You quickly realize that it just won't work unless you model all of those states in your component. And the act of "forcing" you to model all of those states often catches logic bugs or issues that wouldn't have been found until much later in the process.
    • blaqkangel 9y ago
      And that's exactly why I'm loving Elm right now. The compiler is also incredibly helpful in finding out where you might have missed a state.
  • HeyLaughingBoy 9y ago
    This is something I had to deal with pretty recently. The sequence I needed to model was: Operator pushes Start Turn motor on Motion triggers switch to ON state Motion triggers switch to OFF state Turn motor off Machine changes state to RUNNING The time between pushing Start and RUNNING is only a couple seconds, but there's a chance that something could jam, the switches could fail, or something I have no knowledge of could go wrong. Question becomes, do I now need an intermediate "In Motion" state for the six or so cases where this happens? In the end, I decided no, because there was no other transition out of that state than the expected behaviors, so modeling the intermediate state didn't offer me any benefit[1]. Failure to get to OFF state within a certain time puts the system into a global error condition that required manual intervention to fix. I don't have a real comment here :-) other than to back up your point that modeling isn't as obvious as it first appears to be. [1] I would have created this intermediate state if this was a complex controller that was likely to have new rules added later. However, knowing it was a simple one-off, I'd just be giving myself extra work for no benefit if I did it now.
• deleted 9y ago
  [deleted]
• madhadron 9y ago
  This reminds me of my old mentor Julian Noble's Forth code that makes state machine transition tables valid code: http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm....
• rdtsc 9y ago
  Erlang, which traditionally deals with concurrency and parsing protocol has had a built-in standard FSM module for a long while: http://learnyousomeerlang.com/finite-state-machines http://learnyousomeerlang.com/finite-state-machines It even got a recent re-write and the new one is called gen_statem: http://erlang.org/doc/man/gen_statem.html http://erlang.org/doc/man/gen_statem.html This new version is already is used to handle some of the TLS and SSH stuff from what I've heard. Here is TLS connection code: https://github.com/erlang/otp/blob/11cd0f1d000be5849bba2466b3b54daa7727af22/lib/ssl/src/tls_connection.erl https://github.com/erlang/otp/blob/11cd0f1d000be5849bba2466b... I've done them in C and Python before as well. In C I the like the table + function pointers approach when possible. Here is an example: https://stackoverflow.com/questions/133214/is-there-a-typical-state-machine-implementation-pattern?answertab=active#tab-top https://stackoverflow.com/questions/133214/is-there-a-typica...
  • tonyarkles 9y ago
    Even without the framework, Erlang/Elixir processes very naturally lend themselves to statemachine-like behaviour. Unless you're doing something really weird, the messaging behaviour is basically: new state = old state + message
    • rdtsc 9y ago
      Indeed. In Erlang I had never actually used any of the FSM modules in practice because in my case a simple gen_server works just as well.
  • jedimastert 9y ago
    > I've done them in C and Python before as well. In C I the like the table + function pointers approach when possible. Here is an example: https://stackoverflow.com/questions/133214/is-there-a-typica.. https://stackoverflow.com/questions/133214/is-there-a-typica.... In that particular example, I'd just like to point out how super clever it is to put `NUM_STATES` at the end of the enum in the first line. I'm fairly comfortable in C, but I never really used it with/around people who have been using it forever, so I love seeing these little tricks.
• rs86 9y ago
  How much of developers do not know what a state machine is?
  • aidenn0 9y ago
    At least 90% by my observation.
    • billysielu 9y ago
      This is the key point IMO. Putting stuff in your code that developers don't understand is a RISK.
      • deleted 9y ago
        [deleted]
• CamperBob2 9y ago
  TIL that VHDL can be more readable than Javascript.
  • marcosdumay 9y ago
    Just wait until you start connecting things with different types by mistake and watch the weird results you'll get.
  • jxub 9y ago
    And JavaScript is eating software... :sob:
• pron 9y ago
  It's unfortunate that the article (and Wikipedia, too), use "state machine" to refer to a finite state machines. In program semantics and formal verification, the term state machine is a common term of art, but it refers to either a finite- or an infinite- state machine, with infinite being the presumed default unless otherwise stated. If people come to associate the concept of a state machine with the useful but more limited narrowly applicable concept of a finite state machine, they may miss out on this important and general concept. In program semantics and formal verification, a state machine is a mathematical mechanism for describing an often nondeterministic discrete (software or hardware) system as a mathematical relation, →, on states, where if `s → t` (i.e., the pair <s,t> is in the relation), then a transition from state `s` to state `t` is possible. For example, both Turing machines and the lambda calculus are often naturally described as state machines. A finite state machine is just a state machine with a finite number of states.
  • braythwayt 9y ago
    There are more generalized concepts of great interest, including infinite state machines and (as mentioned elsewhere in this discussion) hierarchal state machines. However... A blog post with the stated aim of alerting programmers to the opportunities for refactoring a convoluted domain model into something with more structure has to start somewhere, and leave something out. The great thing about discussions like this is that more experienced programmers such as yourself can chime in with exactly this kind of observation. I invite you to post a link or two for others to read. I'm sure the community will appreciate it.
    • pron 9y ago
      Oh, I was merely commenting on the use of the unqualified "state machines" as referring only to finite state machines. Wikipedia indeed claims this is the default meaning (i.e., finite unless stated otherwise), but I am not familiar with it being the default, and, in any event, don't think it should be, as that would be confusing.
      • braythwayt 9y ago
• 3pt14159 9y ago
  Eh. State machines have their place, and I find them especially helpful for simultaneous code of all kinds, but for run of the mill business logic I find they just get in the way of the code. My rough rule of thumb is this: 1. Can simultaneous actions hurt here? 2. Would a database transactions work instead? Iff the answer is "yes" to the first and "no" to the second then consider state machines. Make sure the answer to #1 is really "yes" though. For example, things like animations consider libraries like Ember Concurrency which give you fine grain control over queuing and restarting things without the muck of a bunch of states and transitions.
• KaoruAoiShiho 9y ago
  Font on this website is so thin that it's unreadable.
• HumanDrivenDev 9y ago
  When people talk about state machines, do they mean deterministic finite automatons? Because i can see a lot of ubiquity in state transition tables in code, but less use in deciding whether to reject or accept a sequence of states which is essentially what a DFA does.
  • twtw 9y ago
    Not usually. "State machine" is typically used to refer to the more general concept of a finite state machine, which includes Mealy and Moore automatons. DFAs typically are not viewed as having an output (or arguably a single bit for the whole input sequence that represents acceptance), while FSMs can have outputs on each transition or in each state, which means it can induce some action.
    • HumanDrivenDev 9y ago
      So people basically mean a transition table/function, but without the start state or accepting states?
      • twtw 9y ago
        No. They mean a set of states, a set of input symbols, a set of output symbols, an initial state, a transition function, and an output function. The output function maps from the state to the set of output symbols (or sometimes from the state and input to the output).
        • HumanDrivenDev 9y ago
          Is there a formal name for this?
          • twtw 9y ago
            It's probably closest to a finite state transducer. No guarantees that what I described above is exactly the definition, though.
• kazinator 9y ago
  When state machines are finite, and are well-formalized, they are fairly easy to understand and debug. State machines descriptions can lie. For instance, suppose that the implementation of a state machine grows hair that is not folded back into the specification. For instance, originally, the outputs of state transitions were just pure outputs. Now they are secretly fed back into the machine and give rise to additional states. Or, originally, the state machine just consumed input events and changed state. Now, without it being clear in the diagrams and documentation, the machine can push back any number of events into the event stream to process again, including rearranged and edited versions of the events. This is just modeled as an "output" of certain transitions. Oops! (Why, it must be an output, because it's coded in some "output handler" function in the state machine implementation).
• deleted 9y ago
  [deleted]
• emodendroket 9y ago
  I'll admit it: I always had a kind of murky idea of how you might use state machines in a real program. This article gave me some idea. Good stuff.
• michelpp 9y ago
  State machines also make excellent database constraints. Trigger based enforcement removes the need to implement machines in application languages and prevents bad code from inserting bogus states. This only matters if you're storing state data in a DB. For example I wrote a simple trigger based fsm extension for postgres: https://github.com/michelp/sqlfsm https://github.com/michelp/sqlfsm
• dstalli 9y ago
  Check out statechart.js. It is a implementation of a Harel Statechart and it has worked out well for my company. https://github.com/burrows/statechart.js/tree/master https://github.com/burrows/statechart.js/tree/master
• nateroling 9y ago
  After playing around with some state machine libraries, I find a simple switch statement against a State enum to be the most straightforward approach. Especially if your language can guarantee an exhaustive switch.
  • ensiferum 9y ago
    Indeed.
• zengid 9y ago
  I remember reading about a language from Microsoft called P that compiles to state machines in C. Its for complex and asynchronous state changes, like programming a protocol for an automated drone. https://www.microsoft.com/en-us/research/blog/p-programming-language-asynchrony/ https://www.microsoft.com/en-us/research/blog/p-programming-...
  • JoachimS 9y ago
    I'm slightly surprised that nobody (as far as I've seen) have mentioned SDL: https://en.wikipedia.org/wiki/Specification_and_Description_Language https://en.wikipedia.org/wiki/Specification_and_Description_... SDL is widely used in telecom and datacom systems to develop the control plane. Most tools are of the draw your code-type, which ends up being a unmanagable mess in direct contrast to what management thinks. But the tools will generate state machines that pass messages between eachother and to controlling interfaces based on states an inputs. The point being made for SDL is that you can easily simulate the whole system and watch/test that the control plane will work as intended before the HW has been built.
• Timothycquinn 9y ago
  I spent a majority of my programming career developing business process automation solutions on top of a graph database that incorporated state management in the middleware layer as a first come citizen. State transitions were triggered and it had strict schema. It was amazing the amount of features we could push out with great stability and scalability using this middleware. We build huge systems that just ran like clockwork and was easy to explain and reason about. Sad part of this is that the middleware is not commercially available without buying they vendors domain specific products.
  • Timothycquinn 9y ago
    Typo: ...first class citizen...
• jonahx 9y ago
  Fun fact: The J language implements general finite state machines as a language primitive -- `;:` http://www.jsoftware.com/help/dictionary/d332.htm http://www.jsoftware.com/help/dictionary/d332.htm
• manmal 9y ago
  State machines are my #1 „magic trick“ for writing reliable code in Swift. In Swift you can attach values to enum cases, so you have implicit data stored with each state. UI states are very well suited for this (Eg .loading, .success(value), .error(error, cached)), or API request states (.initial, .fetching(isRetrying), .success(value), .error(error)). Each can cycle through each state, and each state translation can be handled and animated or ignored. I cannot stress enough how much this improves the resulting code. Most bugs I get now are almost „intended“ as I chose a certain behaviour for a certain state, but that decision was wrong (rather than the code flying in my face unexpectedly).
• JoachimS 9y ago
  Talking to some programmers the last year I was surprised that state machines was unknown. In embedded systems, and esp in HW design (FPGAs and ASICs) you have state machines everywhere controlling the behaviour of the data processing (the data plane) part of the design. I first started to really learn about finite state machines (FSMs) during compiler class. The parser in a compiler for example is a FSM. Tools like Bison generates FSMs based on state rules. And in general as programmers we write code to parse stuff all the time. So how can FSMs be unknown? I'm a bit baffled.
• joveian 9y ago
  No JavaScript support but for nice finite state machines in C, C++, C#, D, Go, Java, and Ruby there is Ragel: https://www.colm.net/open-source/ragel/ https://www.colm.net/open-source/ragel/
  • rurounijones 9y ago
    Worth pointing out that the ragel parser was used to create a pretty bulletproof HTTP parsing implementation in the mongrel webserver. I think that implementation is still used in other http servers.
• vijucat 9y ago
  The last time I looked at this (when having to deal with spaghetti-like execution flows through an Actor-based code base), I really liked the ideas of model checking with Colored Petri Nets and code generation (http://cpntools.org/ http://cpntools.org/), and the TLA+ language.
• pknerd 9y ago
  Interesting.. wonder whether there's any Python implementation ?
  • mogsie 9y ago
    Two: * https://aleph2c.github.io/miros/ https://aleph2c.github.io/miros/ * https://github.com/AlexandreDecan/sismic https://github.com/AlexandreDecan/sismic
• CRConrad 9y ago
  Horrible propaganda, pure "1984 Newspeak"! Just because the State is a big horrid Machine is no reason to "love" it!
• brentjanderson 9y ago
  The sample code is fine for JavaScript, but it begs to be written using pattern matching, like that in Elixir/Erlang. If you have the current state and an event to apply to that state (similar to Redux), you can pattern match on pieces of the current state and the event to apply to that state. Your event handler could look like: ``` def handle(%{state: "open", balance: balance},%Deposit{amount: amount}) do {:ok, %{state: "open", balance: (balance + amount)}} end def handle(%{state: "closed"}, %Deposit{}) do {:error, "invalid action: account closed"} end ``` Every state/event pairing is explicitly defined as a variation of the `handle` method. There are countless ways to build a state machine like this, but the basic pattern matching primitive seems to simplify this a lot. An extension to javascript to support this has been proposed, I'm hopeful that it gets considered seriously: https://github.com/tc39/proposal-pattern-matching https://github.com/tc39/proposal-pattern-matching