Why Developers Never Use State Machines (2011)
skorks.com
skorks.com
Its kind of frustrating constantly reading posts where people shit on functional programm(ers|ing) for being too ivory tower-y or whatever, when its kind of hard not to be when a lot of the older FP guys have spent the last like 20-30 years going "yo this is dope you guys should really be doing this" and getting largely ignored. State machines are super commonly used in languages where you can (easily) construct ADTs and pattern match on them.
I've not been ignoring them. I tried at least three different Haskell tutorials and articles explaining how cool it is. The problem was the author would show some code sand say 'see how easy it is to do this, and this, and this!', but I'd look at the code and have no idea whatever what it was doing or how it was doing it, and the guide/tutorial wouldn't tell me. After a few tries, I just gave up.
Maybe there's a canonical newbie's tutorial that takes you through the shift from imperative/procedural thinking?
"We're going to write a compiler in our shiny FP language".
"We're going to implement a Fourier transform".
Nah, thanks, could you show me instead how I can get the Employee record from an XML file, stick it in a PostgreSQL database and also send it down the wire through a REST API as JSON?
For quite a few FP languages the ecosystem is there and you can do all these problem domains nicely, they just tend to be skipped in tutorials as they rely on non-core third party libraries (sometimes with multiple nice but very different alternatives). Perhaps a "batteries-included" stance of Ruby(+Rails) and Python would simplify that, but it's more of a political issue.
In the real world, those matter just as much as the language. They usually matter even more :)
Look at what Rust is doing - I think at least half of their effort is spent towards building up a large collection of high quality, well maintained (i.e. feature requests implemented, bugs fixed quickly) and well documented libraries.
That might be the case, but you simply never see tutorials for writing a CRUD-like web application in Haskell. Maybe they exist, but they don't seem to show up very often here or on reddit or whatever.
I'm always surprised how often bad code is the solution too.. And when I say the solution, I mean to all the points along the path that I may take to get to the final destination. And I'm not saying this because you can't write this type of code in haskell but because haskell makes it more difficult and that's not always a good thing
As a result, if most of the code written by most programmers is short lived and during that short life changes drastically, super-strict languages actually slow you down a lot.
The real problem is: sometimes certain parts of our code live very long and intense lives. But we never know which parts and at which moments. If we knew, we'd just write those parts in Rust/Haskell and the rest in Javascript or Visual Basic and live merrily ever after.
To paraphrase P.T. Barnum: I know that 10% of my code needs to be extremely fast, easy to refactor and readable, I just don't know which 10% :D
I've no doubt this depends on context, on habits and approach, on skill with the languages in question, and on skill with effectively using static typing in general, so I'm not surprised that others' experiences differ.
You're better off learning OCaml or F# for a small project or two, honestly. The jump from pure procedural to pure functional is big enough without also dragging in laziness, type classes, and monads.
Perhaps a Haskell book with a project or two would be a better alternative?
There's the shift to functional thinking, which should not be underestimated. Next up is learning the target language syntax. Then there is the issue of gaining familiarity with the tools & libraries available.
That's probably not the problem - imperative development can start off from a level of complexity where state machines don't look relevant.
Six weeks down the line, the whole codebase has overtaken the complexity of a state machine, though each of the development bugs were simple fixes to the original branching code.
The standard web-app wizard is where I've run into this again and again.
Every web-app is stateful enough to maintain DB state sync'd & ticking over from a user-click, which makes it really easy to work out whether all clicks go somewhere useful.
However this makes sense only when you have around 7+ states and transitions between them (particularly the "go back" one).
Until then, the regular if/else branch scenarios work out just fine ... but then when you're near the 20-30 state range, it all falls apart.
Holy shit, once I built a web app for some biologists that wanted a "designer wizard." First I implemented a really shitty buggy wizard. Then I refactored it all into a state machine...........
I had the opportunity to use F# for the first time last month, and I experienced this first hand -- it was far easier to write a procedure as a sum type with transition functions than it would have been to write it procedurally. And with all the advantages of having the states of the system and their transitions laid out explicitly, why fight it?
type InitialState = {a : int; b : string}
type IntermediateState = {a : int; b: string; c: string list}
type FinishedState = {a: int; b: string}
type ErrorState = {a: int; b: string; message: string}
type State =
| UninitializedState
| InitialState of InitialState
| IntermediateState of IntermediateState
| FinishedState of FinishedState
| ErrorState of ErrorState
| FinalState
let initialize (args : string list) (s:UninitializedState) : State =
// create an initial state from args, not actually like this
InitialState {a= 5; b="hello"}
[edit]
For example here is UE3's anim tree[1] editor vs Kismet[2].
[1] https://docs.unrealengine.com/udk/Three/AnimTreeEditorUserGu...
[2] https://docs.unrealengine.com/udk/Three/KismetUserGuide.html
State machines are also intrinsically stateful, that should be obvious.
So are lots of data types, but those are still useful in FP.
"An odd habit of functional programmers: when confronted with a nice, but clearly imperative way of structuring a program, they will often declare that this technique is in fact functional." (https://twitter.com/yminsky/status/950883335324225541)
and then
"Case in point: structuring a program as an imperative, deterministic state machine, where the state is determined fully by the state machine logic plus the sequence of transactions." (https://twitter.com/yminsky/status/950883598189686784)
Only after sometime around 2010. Before that it was mostly Lisp and Scheme. Sometime around then, the trend around Haskell, purity, and co overtook them as what people mean when they talk about FP.
Linden Scripting Language, used for Second Life, has explicit state machines as a first-class programming construct. Programs are divided into state sections, using a keyword "state". Each state has its own local functions.
And function pointers make up for pretty much the only fundamentally useful aspect of FPs regarding FSMs which is functions as first-class objects.
Everything else pretty much just substitutes one convenience for another. A pretty good case can be made about how the State Pattern makes traditional OOP indispensable in FSM design, and I'm sure that in OO languages with functions as first class objects (like Python, Lua or Javascript) people can showcase elegant designs that to them far surpass both classically OO or classically FP designs etc. etc.
I'd argue sums and pattern matching are almost as important given the simplicity of expression.
It's pretty easy to imagine, though, a class based OOP language where each class was also an HSM, with methods defined per state and identifying transitions (as well as states and their entry and exit behavior being explicitly defined.)
pretty sure most C introduction books cover various implementations of state machines. In "traditional" desktop WIMP GUI software it's a fairly common paradgim ; a bunch of frameworks such as StateCharts with SCXML even allow you to design the state machine graphically and have it compiled to C++ or Java code.
many of "the older FP guys" actually think "it's cool, it's mathematical. But it's not practical."
I think this is already part of the problem of complexity --- when I think "state machine", what comes to mind is a loop and a switch with some gotos in the cases. Definitely not a library. If you think "I need to use a state machine" and your next thought is "I need to find a library for that", then IMHO you're definitely doing it wrong.
Typically you read a token, moved to a new position and then acted based on the current state and the token, position. You don't need a library since the code is just a few switch statements.
Though that is preventable, mostly because the code you run is inbetween transitions and that will return very nice stack traces.
Otherwise, you don't need a trace of a state machine, the state you're in and the current transition should tell you exactly where it's breaking.
If it doesn't, chances are you're breaking state machine definitions by storing wildly complex state outside the machine.
Additionally, I find that I cannot understand how the program works without actually drawing out the state machine diagram if I come across it the first time, so there is a bit of a learning curve. It's also a nightmare to test because of all of the states that need to be tested.
So in summary, not a fan. Like recursion... if it feels natural then use it, but I don't go and try and turn stuff that isn't a SM into one or turn something that can be done as loops into recursive function for fun.
State machines have been designed to neatly capture and componentize exactly that.
Anything else is less explicit, and even more error prone.
That new even and those new transitions you've mentioned? You still need to handle them anyway -- only you do it in an informal manner without a SM.
I haven't done it, yet, but I am tempted to make everyone I work with draft out the state machine of everything we are working with in our systems. I'm half convinced the worst bugs we have, are when folks didn't realize that the change they were doing required modifications because of how far reaching they were in the state of the system.
I take a simple vending machine as a good thought exercise. If you are just changing the system that recognizes coins, you can easily localize your changes. If you are changing the system that accepts coins...
How much of the anti-formalism attitude is about real difficulties of the method, and how much is about "I don't know this method, so it must be bad".
Code, regardless of what it does, is a state machine. That does not change whether you do it intentionally or not. And if you don't use state machine design tools to design them ... then your state machine becomes a huge mess with transitions going from everywhere to everywhere and very surprising connections in many places (and most/all of those will be bugs, bugs that no unit test ever is going to find).
Which seems to be acceptable for a lot of people.
(haven't used this yet)
Depends on your formalism. I never use state machines of that form for exactly the reason you say. Rather, each state defines the conditions which cause a transition from it. Receiving an event in a state in which it is not expected (say, an I/O completion in a state which should not have outstanding I/O) is a straight-up hard error.
You don't need to test every scenario - only the critical positive/negative ones.
If you abstract out all the generic SM logic you can have a neat source file per SM that contains only the allowed transition mappings or do something like https://github.com/pluginaweek/state_machine where the transitions are contained behind methods.
My experience with recursion has been the reverse - the more recursion in use the less predictable the code behaves (at least initially) - but even just a little bit of SM usage can increase stability from the start and also forces you to think about all the states required.
You may be able to keep it all in your head when you write it the first time... try again when you're doing maintenance after 6 months of not touching it though.
You still have to do all this without state machines, but likely in a less organized and harder to maintain way.
Depends but usually no. An event in a state which has no transition from it would be an error. The state becomes undefined and you produce a crash.
>If you add a new state, you have to figure out how to handle each of the transitions from other states.
Yes but only states that transition to this new state which is easily formalized.
>Additionally, I find that I cannot understand how the program works without actually drawing out the state machine diagram if I come across it the first time, so there is a bit of a learning curve
SM diagrams are fairly easy, they were mandatory course material in my second semester at university.
>It's also a nightmare to test because of all of the states that need to be tested.
In fact, the opposite is usually true. You can mathematically verify that your state machine will always behave exactly as expected or crash. The coffee machine won't dispense coffee and return the cash put in; the state machine in it does not allow it, even better, such a series of events becomes utterly impossible. Once the coffee has been dispensed, the machines has only one way forward: initial state.
Additionally, SMs allow you to verify that your specific implementation is the most optimal one. And if it isn't, you can easily derive it. And you can test if two independent SM implementations are equivalent to eachother with 100% certainty.
Sadly, since their state is very limited, they are usually not very useful once you want to do something that can't be expressed in a finite state machine (basically anything with threads, ever, to start with).
I've been using state machines for Javascript UI elements.. really simplifies things.
While a design pattern is a perfectly legitimate strategy to organize code, it's a manual exercise with no help from the compiler: it's a workaround for the language of choice not being high-level enough for the concepts you're coding.
This is why frameworks useful: they intentionally constrain the problem space, so one can focus on just unique behavior. When one reaches for a framework, they're often using someone else's state machine. Game loops, GUI event loops, or network protocol states are applications of this same pattern.
In some greenfield development, frameworks have a poor reputation for removing developer control. This stems from a misunderstanding: that having a large amount of choices in organizing code is a desirable goal. It very rarely is.
https://shopifyengineering.myshopify.com/blogs/engineering/1...
I always thought all computer science students had to take a compilers course, or some course on theory of computation that required some level of competency in lexing/scanning/tokenizing and parsing. This blog post appears to be directed at "web application developers" who lack "awareness about state machines".
I've worked with lots of programmers over the years and a CS degree has been a very poor indicator of their ability to program in the large.
* A quarter-century ago I implemented a cluster membership protocol and coordination system as a state machine. This provided great benefits in terms of verifiability, extensibility, etc. but some developers complained while the current state was explicit the history of how we got there was not. Adding a history mechanism helped, but frankly it still wasn't as good as the stack traces we'd had before. While the benefits far outweighed the drawbacks, this drawback was quite real.
* On my current project, a critical component (not dissimilar to the the one in the previous example) was implemented by someone else as a state machine. Besides the fact that the semantics of that state machine are unusual and undocumented, and that this state machine also lacks a history mechanism, developers over the years have been wildly inconsistent about which actions occur on which state transitions and how other information is saved/restored "off to the side" between transitions. The result is worse than spaghetti. It's like a chunky goulash that nobody can digest, which is why we're rewriting that component from scratch.
Based on these experiences, I suggest a few rules for implementing a successful state machine.
* Make sure the state machine is properly documented - what the states mean, what the events mean, how a transition is selected when multiple might apply, etc.
* Make the control flow discoverable by providing a history mechanism.
* Make the data discoverable by capturing all relevant flags and secondary state in a structure that's passed to the code implementing transitions.
* Verify the heck out of your state machine every time it changes. Make sure that every path terminates, using timeout events as needed, and that termination includes proper resource cleanup. If appropriate, verify that multiple concurrent invocations can't race with one another and violate the invariants you've checked within each. This verification is much easier to do with state machines than with other approaches, and you should take advantage of that.
Let's say you have a music playback control component you wish to reuse across a feature rich player, as well as a mini playback controller.
You COULD just use the full state machine to power the mini player, but most of the transitions would be unused. It would be unclear to the next maintainer which aspects were needed for each use case, thus making the state machine brittle.
Instead, you can write an independent playback progress/state class, and reuse it in both players via composition and proper layering of functionality.
By hiding the playback state from the rest of the player and exposing control of it's state via an interface, you've gained functional reuse.
Reapply the same pattern for all components of your players and you'll find that your product is safer to change and easier to understand than if you had built a complicated formal state machine covering all possible music player use cases.
Any class managing state exclusively is an implicit state machine, no?
function transitionsTo (stateName, fn) {
return function (...args) {
const returnValue = fn.apply(this, args);
this[STATE] = this[STATES][stateName];
return returnValue;
};
}
I'd argue that you are building a separate state machine for the two players, but there is some reuse possible in this approach.
However, specifically in web development, it is discouraged because the nature of the application itself. Think hard how states are managed in a typical service, the real states live in a DB. Which makes state machine less useful because the ground truth is stored elsewhere, and should be updated by DB's own primitives. And in a distributed settings, failure is something you have to put into consideration. Making your service stateful is a red herring that brings all kinds of operational troubles. That is why the dominant approach people seems to agree upon is to keep application stateless while delegate all dirty work to DB.
So realistically I think state machine is useful to write certain helper routines in a non-persistent, single-thread scenario, for the ease of reasoning, but really should be limited within the lifecycle of a single API call.
That means we have to resort to hacks to store state (databases, cookies) - and like most hacks, those are fragile (such as assuming a single instance of state and then breaking when the user opens another copy of the site in a tab).
With the rise of single page apps, there's a more coherent concept of state on the front end, but that doesn't fix the fragility of the server side portions.
In principle, there's nothing fragile about the types of state you describe, but most web frameworks don't impose enough restrictions to ensure this state is used correctly [1].
[1] something like this would work, but it's not the only option: http://cs.brown.edu/~sk/Publications/Papers/Published/mk-int...
https://github.com/nhatminhle/cofoja for example
http://www.ti.com/general/docs/litabsmultiplefilelist.tsp?li...
Every instruction was a state and I had to model each of the transitions between instructions to understand the program flow.
It basically just means that you define states for your program to be in and you define from what state to what other state your program can go to under what conditions.
For example, let's say you have a program that takes user input and once everything is entered correctly, then you move on to the next thing.
That would mean you have a state "user_input" (or whatever you want to call it). Then you'd have a event "User clicks OK-button", with which you'd do a state transition. And then there's two possible state transitions, one which loops back onto user_input, for when the user enters something that's not correct, and one that points to the state of that next thing, with a condition of the user input being correct.
You could also directly specify here what "correct" user input looks like. That's your choice. It's a design tool, use it to whatever depth you need it.
There's a relatively intuitive notation standard, which you'll want to learn, as writing it all down is what gets you to actually think through all the states, events and conditions that there are.
Implementation-wise, you'll usually have a variable that holds your state and then methods to do state transitions. You can also implement a check into those methods to ensure you're in a state that's allowed to transition to the state that this method transitions to.
It basically just means that you define states for your program to be in and you define from what state to what other state your program can go to under what conditions.
For example, let's say you have a program that takes user input and once everything is entered correctly, then you move on to the next thing.
That would mean you have a state "user_input" (or whatever you want to call it). Then you'd have a event "User clicks OK-button", with which you'd do a state transition. And then there's two possible state transitions, one which loops back onto user_input, for when the user enters something that's not correct, and one that points to the state of that next thing, with a condition of the user input being correct.
You could also directly specify here what "correct" user input looks like. That's your choice. It's a design tool, use it to whatever depth you need it.
There's a relatively intuitive notation standard, which you'll want to learn, as writing it all down is what gets you to actually think through all the states, events and conditions that there are.
Implementation-wise, you'll usually have a variable that holds your state and then methods to do state transitions. You can also implement a check into those methods to ensure you're in a state that's allowed to transition to the state that this method transitions to.
And even if you never end up using it, it is a nice mindset to get yourself into.
Mind you however, the immutable nature of variables really helps.
I use state machines regularly when producing performance statistics where I need to individually isolate many history dependent outcomes in a large sample space. I tried doing it without them and ended up with unreadable and thus unmaintainable buggy code. Never again.
Maybe you meant to say that only competent developers use state machines. But that would place you outside their august company, leaving us little reason to credit your observation. In that world, the absence of state machines in one's code would reliably indicate incompetence.
But in fact, by definition, there is no computer program on God's green Earth that is not a state machine. Programming languages were created specifically to make the state machines they compile down to look more intuitive and less like, you know, state machines.
So the observation is really that our programs usually look the way they were intended to look, except when we abuse our language in pursuit of performance, elegance, or other consensual delusion.
1 current version: https://github.com/pluginaweek/state_machine
1a original unmaintained version: https://github.com/pluginaweek/state_machine
I spent too much time on HN today
For example ...
I was brought on to work at a startup a few years ago by an old-time acquaintance that was CEO of a startup ... the company's proposed product sounded interesting, and I believed in her skills and background and had decent rapport with her. I was wary of the VP Engineering and a few others, but it was to be my first post-move-out-of-SF-Bay-Area remote startup job and I thought I could make it work.
I show up in Santa Clara, CA to make sure I really want to do this ... and after joining we spend the next few days going over architecture, implementation-so-far, etc. Part of the product's job is to discover and categorize servers and networking devices, the basic software deployed on them, etc. Apparently this aspect has been in design/implementation for several months, but it's not working very well, and the problem and approach aren't articulated very well. I have a chance to look at the code a bit.
I eat lunch with the CEO and she asks me how I'd approach the problem, and I advocate breaking everything down into state machines with well-defined transitions ... both for interacting with the environment, and for storing info in the back end -- there's ample opportunity for things to go wrong, to require retries, etc., and tracking these interactions with state machines makes it much easier to efficiently and quickly deal with the environment and back end in asynchronous fashion, and to separate different levels of discovery (network / IP; finding credentials that work; OS determination; software inventory; storage inventory; etc.) much easier.
In the next day's architecture discussion I then hear the VP Engineering use a few of my words and draw a few poorly formulated diagrams that don't do the task much justice ... it's apparent the CEO has discussed the problem with him and urged a new look. I had to start work on my piece so I didn't follow their developments much, but I heard later they actually purchased and licensed for significant money a "finite state machine package" of some kind. All they needed were ENUMs, (preferably async-result) functions to try something out, and then transitions between enums based on the results. That discovery code was always buggy, never did work right.
That was one of many fiascos. There were so many other fiascos, and they all cost me lots of sleep, some of my sanity, and some self-respect. I lasted almost three years there (some early players were pushed out but the product never really got better). I would have been happier quitting the first week, or better yet never joining.
It is still shared state, a thing to minimize. Usually message passing (current buzzword: reactive) approaches work much better.
One of the classic ways of architectural a concurrent system is as a collection of sequential processes implementing message processing loops as state machines.
If you mean that state machines can't deal with internal concurrency, that's not true either. Leaving out concerns about unmanaged state (mutable data not reflected in the state of the machine), a state machine provides a clear framework for managing concurrency:
(1) an unlimited number of events that produce self-transitions can be processed simultaneously;
(2) an event that would be processed the same in the start and end states of all currently running events and whose end state would not alter the processing of any currently running event can be processed concurrently,
(3) an event that would not be valid in the end state of any currently running event is invalid,
(4) any other event cannot be run concurrently, blocks new events entering processing, and must be evaluated for validity after each running event completes (it may become either runnable or invalid).
The last is a kind of bottleneck, but it's usually not introduced by the state machine so much as a feature of the domain.
I got over both of these and now use state machines in production where they make sense as a model.
Bonus: Pages written by developers who don't know/care about graceful degradation appear blank, so you don't have to waste time reading them.