There's a lot of truth to this statement in my experience. I just finished rewriting my homework for my operating systems course and the first version looks awful compared to when I rewrote a chunk of it as a state machine
Life cycle management, process synchronization, lockfree data structure, user-space networking... I can't remember the last time I didn't use a state machine.
Or control systems (which is remarkably similar to game programming, really). Basically anything that needs to model on control a system which changes state over time. Sometimes it gets a bit too much, though, and people start seeing every task as a nail for a state-machine hammer.
Any such state model is not the actual thing it models (which is almost always stateless continuous time) therefore extremely annoying to work with. Also a source of bugs and concurrency issues.
> I am the only kind of developer there is and so therefore I will speak with authority as to what all developers do.
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.
Traditional programming languages and imperative thinking don't lend themselves to writing state machines, so its not really that surprising that they're under utilized.
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.
Similarly with embedded development. We use them for just about everything from communications to scheduling. I think the subtext here is that state machines are just rarely used for web/mobile...
One simplistic state machine in web/mobile is mouse/swipe motion handling – mousedown transitions into "in motion" state, mousemove tracks that state, mouseup transitions into "finished motion" state, runs event handlers, and transitions again into "idle" state.
Definitely true for gamedev in my experience. I don't think I've worked in a game code base of nontrivial size without seeing some implementation of state machines.
The "some implementation" probably is part of the problem - if there was a good generic implementation included in the standard library so that it could and would be used in language tutorials (especially in languages where rolling nice state machine code is tricky), then developers would use them much more.
The problem with that is each system has slightly different requirements. Scripting state machines vs animation state machines are going to have very different constraints and end-goals.
[edit]
For example here is UE3's anim tree[1] editor vs Kismet[2].
> State machines are super commonly used in languages where you can (easily) construct ADTs and pattern match on them.
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?
Unfortunately no -- NDA / work-for-hire. Customer requested .NET but didn't care which language. We usually write Python, F# felt friendlier than C#. State classes looked like:
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
And transition functions:
let initialize (args : string list) (s:UninitializedState) : State =
// create an initial state from args, not actually like this
InitialState {a= 5; b="hello"}
I probably put too many types into my function signatures, but I'm new to this style.
In 's4vi0r’s defense, “FP” usually means ML-style FP, which does happen to be pretty biased towards creating stack-based FSMs since it has literal syntax for stacks (list literals), states (discriminated unions + tuples), and transitions (pattern matching).
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.
This comment reminds me of something I read recently on Yaron Minsky's twitter:
"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)
This might be, but state machines are so common in imperative code, you could say they are common idiom there also. Pattern matching over ADTs only drives transitions; different representation of transitions can lead to different constructs being more convenient (e.g. if your transitions are just based on a finite set of values, you can use just dictionaries).
> Traditional programming languages and imperative thinking don't lend themselves to writing state machines
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...........
Traditional programming languages and imperative thinking don't lend themselves to writing state machines.
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.
>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
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?
Heh, very often their problem domain is also an issue.
"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?
Haskell code for that looks quite nice as well - however, it's less about a language per se but rather about availability of libraries and how mature / well-built their API is.
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.
> It's less about a language per se but rather about availability of libraries and how mature / well-built their API is.
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.
I agree. For me what matters most is language implementation (compiler/VM quality, GC quality, etc) and important libraries (and whether they are good). Language itself is not very important. I can write boilerplate, but I can't write GC implementation. So while I don't like Go language, for example, its implementation is very good and I can live with it.
> Haskell code for that looks quite nice as well - however, it's less about a language per se but rather about availability of libraries and how mature / well-built their API is.
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.
In my experience, that's really not an argument against Haskell. I find it easier to make large changes in my representation of the world in Haskell than in any other language I've worked in.
As much as I love haskell and want to say I've had those same experiences, that hasn't been my experience. Haskell forces me to write better code so often that it's painful when bad code will do just as fine.
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
Well, despite what we tell ourselves, I think that most code we write is actually short lived. As in, it is only used for a short time. It might be in a zombie state for many years and even be revived, if it's an Open Source project, but that's not the common scenario.
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 agree with most of that, but I find that when my code is changing drastically is when I get the most help from my type checking, and find it most conspicuously absent when I use "less strict" languages.
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.
The erlang tutorial is pretty effective at that, IMO. The biggest problem with it is that erlang syntax is so foreign to most programmers you're going to spend enough mental effort understanding that to detract from the brainpower available for understanding the functional paradigms.
I don't think 'three haskell tutorials' is ever enough to teach you a completely new programming language/paradigm. You wouldn't learn C in 'three C tutorials' either, would you?
Perhaps a Haskell book with a project or two would be a better alternative?
No, but if well done, it could be enough for me to say, "I get why this is worth pursuing further." I've had the same experience as the person above: Haskell tutorials seem to say, "Look what I can do!" and not, "See how you can do this?"
Well, after a few tutorials you should have noticed that it's a high-level language with clean syntax and a compiler that produces relatively fast binaries. That's a start. What else were you expecting?
Something that shows me how this is worth spending the time learning, when I could just as easily use another high-level language with clean syntax and a compiler that produces relatively fast binaries - but that are not functional - minus the learning curve.
Well shit. I guess teaching languages designed by academicians aren't for you. Same goes for blog posts written by random amateurs on the internet. A whole three tutorials, too! You should ask for a refund.
Currently just started myself on http://haskellbook.com/, their philosophy seems to be just something for you, teaching functional programming with haskell from well defined fundamentals to make sure everything clicks. If they deliver on the promise I am yet to find out!
What's worked for me is using Scala on real production projects and just taking it slow. First year or two I was writing Scala that looked like Java, last year or two I've been writing Scala that looks like Haskell, but because the language supports both styles I was able to learn one piece at a time and stay productive the whole time.
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.
> 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.
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.
I'm following along with Learn You A Haskell[0] and it's the only Haskell tutorial I've found that's enjoyable to read and is super easy to follow and understand. I definitely recommend it.
State machines are still and by far most commonly used in C, where, lo and behold, most low-level and embedded programming is still done.
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.
> Traditional programming languages and imperative thinking don't lend themselves to writing state machines,
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.
I don't think there is a conflict between imperative thinking and state machines, but I do agree that lots of programming languages neither provide built-in features for expressing state machines nor support expressing them particularly elegantly, and that the superior support for general abstraction in certain functional languages reduce the friction of use.
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.)
State machines are one of the most traditional programming constructs there is, and most people I've seen champion or use them are the types who would rather program in assembly than Haskell. Heck, some "imperative thinking" programmers consider state machines only slightly more exotic than a for loop, and would be similarly dismayed if a colleague didn't know how to write one.
You could even go as far as saying that a class in some forms is a state machine. Networking is a huge application of state machines. Microcontrollers usually have a small state and step through a switch statement in an infinite loop. OpenGL is a state machine. If you write a state machine, it's easier to implement it "perfectly" than other methods, and other parts of your program are able to interact with it in more straightforward ways.
State machines are essential for a lot of programming tasks -- I wish they were more explicit more often, because there always is an implicit state machine lurking in there somewhere, and code would be cleaner with the state machine made explicit.
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.
A reducer store is not a state machine since both the transitions and states are loosely defined. That said, at this point I think it's actually better for UI, despite the verbosity and lack of formal correctness.
Of course developers whose last experience with state machines was in a college course won’t use them. Just read some of the comments below the article on storks.com. Labview developers use state machines extensively, because the implementation is graphical, beautiful, and prevents loose ends.
I used to do VHDL for FPGAs, where you basically have to use state machines. LabView is that way too, being a dataflow language. But I don't know how much LabView I've seen that I would call beautiful. Maybe if one considers spaghetti beautiful. ;)
One of my go-to interview questions is "Can you tell me about a time when you've used an explicitly-modeled state machine in your programming?" Our work, heavy in embedded devices, network protocols, and parsing, is so full of state machines that I wouldn't want to hire someone who wasn't comfortable using them.
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.
I had to do it to implement a 16-instruction loop for the TI RM4's High-End Timers, which are programmable timers that you can offload arbitrary pulse-train generation to, among other things.
For equipment automation i am using end-state player which accelerate our development at least in 3 times. Why? There are three levels of hierarchy: conception level, detail, gui. All of these levels are independant to earch others, for example, arhitector can invented new conception with some fake elements which will be substituted in some future stages. Software developers who are making new elements (with parsers, new libraries and so on), regarding to conception above, are not intersected with conception and gui levels. In its turn gui developers use only state schema with all defined properties or data which are belong to every state.
I really don't like state machines because if you need to add a new event, each of the states need to be updated to handle that event. If you add a new state, you have to figure out how to handle each of the transitions from other states. So as your states grow, the maintenance on the developer's side grows faster than linear.
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.
I don't understand the issue very well... If you have a new event, you either have to handle it in the state machine or some other way. Any place where the event doesn't apply should cause an appropriate failure. Same with new states - you have to write those transitions in some way. You can use macros/abstractions/whatever for simplifying many cases. But none of that code really disappears when you don't use SM.
I think the concern is that the update is across the code -dispersed in the code base. But this only applies to legal events in all states else the default behavior should be invoked. If a new event that is legal in many states is created then you have to handle it everywhere anyway, and my experience that if then structures fill with bugs fast in this case
> if you need to add a new event, each of the states need to be updated to handle that event
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.
This idea of defining a hard error for a transition which makes no sense is a nice way to deal with the OPs problem. You must still explicitly handle the situation, but it minimizes the "unwind/undo" code.
For the life of me, I can't read your complaints as actual complaints, but endorsements of the idea.
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).
That faster than linear maintenance growth is exactly why you need SMs.
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.
What's wrong with drawing the state machine diagram?
And generally, what's wrong with drawing your code structure?
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.
>I really don't like state machines because if you need to add a new event, each of the states need to be updated to handle that event. If you add a new state, you have to figure out how to handle each of the transitions from other states. So as your states grow, the maintenance on the developer's side grows faster than linear.
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 really don't like state machines because if you need to add a new event, each of the states need to be updated to handle that event. If you add a new state, you have to figure out how to handle each of the transitions from other states
You still have to do all this without state machines, but likely in a less organized and harder to maintain way.
>I really don't like state machines because if you need to add a new event, each of the states need to be updated to handle that event
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 would hazard a guess that there are decent state machine libraries for most languages that you can use
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.
Agreed. When I worked on last years Advent of Code problems (amazingly good problems btw) I ended up writing many solutions as small FSMs.
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.
We tend to use state machines for massively asynchronous operations like order management (with days between updates), as well as a home-built library for handling the task. It's incredibly fault tolerant and offers really easy abstraction and automation.
State machines are not a first-class concept in most currently popular high-level programming languages, so when you implement one, you're merely adhering to a design pattern.
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.
lol, interesting read. I used to work on a graphics project with a state machine at its core, and user actions are defined to trigger state transitions
Using (explicit) state machines in Rails is so easy, thanks to the gem of the same name(1), that we use them very often, with good results. I think that ease of setting them up and integrating them in whatever framework/language you use is a very important factor in their adoption.
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".
Quite a lot of software developers were never CS students. In fact in some industries engineers are very much desired as programmers. In others, math and physics majors are desirable. And even when we exhaust all of those, I don't think there is any need to look down our noses at those who took an apprenticeship style approach to the industry. In fact, in my career I have met many CS graduates who dismissed grammars and automata as irrelevant and insisted on writing that parser for a context sensitive language using regular expressions and about 400 global variables (and they still can't understand why it doesn't always work). Besides some of us "web application developers" actually have CS degrees and have worked in half a dozen other industries besides "web application development". Programming is programming and a programmer is a programmer. There's a lot to learn and you have to stay humble your whole career. Not everybody manages it easily.
The ECMAScript standard actually has a section on "Context- Free Grammars". In that section and subsequent sections there is discussion of tokens, terminals, nonterminals and productions. If a web application developer using Javascript read these sections of the language specification and became curious enough to do a little outside research on the terminology, then perhaps it is forseeable she might encounter the notion of a "state machine".
163 comments
[ 3.0 ms ] story [ 209 ms ] threadI got over both of these and now use state machines in production where they make sense as a model.
I've been using state machines for Javascript UI elements.. really simplifies things.
https://news.ycombinator.com/item?id=2949543
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.
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.
[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
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?
State machines are also intrinsically stateful, that should be obvious.
So are lots of data types, but those are still useful in FP.
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.
"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)
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...........
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.
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.
http://haskell-servant.readthedocs.io/en/stable/tutorial/
http://happstack.com/docs/crashcourse/index.html
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.
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.
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.
[0]: http://learnyouahaskell.com/
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.
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.
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.)
many of "the older FP guys" actually think "it's cool, it's mathematical. But it's not practical."
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 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.
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.
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.
(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.
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.
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.
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.
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 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.
https://adventofcode.com/2017
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.
Mind you however, the immutable nature of variables really helps.
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.
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.
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
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.