The Rise of the State Machines | Hacker News Reader

The Rise of the State Machines

smashingmagazine.com

57 pointsmpweiher15 comments

In case the author reads this, the distinction between Mealy and Moore machines is wrong. Both use the current state and the current input as arguments for the transition function but while Mealy machines also use those two as arguments for the output function Moore machines only use the current state. They are equally powerful but Mealy machines can sometimes get away with fewer states at the price of the current state no longer uniquely determining the output.

Especially in hardware implementations there are also Medvedev machines where the output is the state vector or part of it, i.e. the output function is the identity function. As far as I can tell that is also where the distinction originated from because they have different critical paths resulting in differing maximum clock frequencies. For software implementations the distinction seems not really relevant.

Another similar article: https://css-tricks.com/robust-react-user-interfaces-with-fin... (full disclosure, I wrote this)

There is definitely a learning curve to state machines, and even more so with statecharts/UML. It's much, _much_ easier to start coding an application from a bottom-up approach (start coding, colocate app logic wherever it's needed, refactor later) than a top-down approach (systematically plan the entire higher-level behavior of your app's various parts before writing a single line of code). That's why it's slow to catch on in the application development (web + native) part of the tech world.

However, in game development, hardware development, etc. state machines and statecharts are more commonly used. To me, the ability to declaratively structure your program's behavior as a directed graph opens the door to the possibility of being able to automate integrated tests (simple path/shortest path/etc. algorithms), statically analyze logic (are all states reachable? are all events handled?), optimize paths, add and remove features without worrying about if some other part of the application will be adversely affected, have smarter analytics, visualize app state, and much much more.

I know there's critics to FSMs where other more idiomatic language-oriented approaches would suffice (I myself absolutely detest the OOP state pattern - it's a needlessly imperative, hard-to-analyze state machine), but I think if developers further understood and saw benefits to functional, declarative, reactive programming and statecharts (a huge improvement over conventional FSMs), application development as a whole could reach a new level of efficiency and robustness.

>There is definitely a learning curve to state machines,

In my view, the concept of a finite state machine is a simple one with essentially no learning curve. It is a straightforward concept. I would never hire anyone that described experiencing a learning curve for this concept.

A surprising number of developers (especially in the web/native app dev world) are unfamiliar with state machines, especially in regard to UI development.

The idea of "when an event occurs, the state changes" might be a natural one, but there's many things about FSMs that are somewhat of a learning curve: self-transitions, sink states, Mealy vs. Moore machines (and their equivalence), non-deterministic FSMs (and converting to deterministic FSMs), optimization algorithms, path-finding algorithms, implementation (imperative, functional, regex-based, etc.)

Personally I no longer use pure state machines, as they can become beasts and end up being a royal pain to maintain.

Instead, I use 'duff devices' variations of it (in C) which breaks down the machine into code that looks 'linear' enough, but is in fact, a state machine without the drawbacks.

I've implemented quite a few protocol stacks using that 'trick' and it's still very nice to read/maintain -- the good thing is that it roughtly looks like a coroutine/thread, without any runtime requirements, so will work just fine on embedded systems as well. Same as coroutine/state machines, don't make your 'states' too 'long' or CPU intensive, you'll have the same consequences.

There's an implementation floating around called 'protothreads' [0], but you can really do pretty much the same with a handful of macros.

[0]: http://dunkels.com/adam/pt/

State machines are wonderful for testing as well. Any time you have a bug, just record the events that got you into the buggy state, and replay it in a test.

State machines are wonderful in general. I'm sure most people were taught it, but somehow it always seems more complicated than just to code some if-statements... until you have some spaghetti logic with many transitions which is magically made maintainable and less buggy by refactoring it into a state machine.

That's how state machines first clicked for me, and it blew my mind. And this keeps happening, when somebody mentions it in code review, somebody's mind is usually blown.

So the more people read about this "boring" subject the better. Although the (non)deterministic finite automata (DFA/NFA) regex engines are a super interesting read IMO: https://swtch.com/~rsc/regexp/regexp1.html

Lol, i have been thinking about implementing this for the ordering logic in my own shop platform ( handling, opening, refunding, partial delivery, paid, ...).

But this article also describes how the data handling is processed, which seems to be totally different from what i was thinking about

Couple of questions/comments/nitpicks about the article:

- does the turnstile example in the article actually need a state machine? When you insert a coin it unlocks, when you push it locks. No need to remember the state you are in.

- in the data-fetching example, it says that in the "fetching" state it is not /accepting/ any clicks. But then shouldn't this be explicitly specified in the state machine, by having the click event loop back into the fetching state? I think it would be less error-prone and more systematic to account for all the events in all the states.

You would need to remember the state of the turnstile when someone attempts to go through it. If it's locked, you can't pass. If it's unlocked, you can.

Whether or not this situation needs a "state machine" is debatable, but you do need to remember the state. In this case, a simple boolean "isLocked" could suffice.

I remember wondering if foregoing the front end frameworks and using a simple state machine - such as the type I remember making for compsci assignments - would actually make things easier. But then I thought "well I'm new to front end, surely if this was a good solution to the problem everyone would be doing this and there wouldn't be a cambrian framework explosion".

I'd love to hear if others have tried using a state machine.

If you google "finite state machine javascript", you'll see that lots of people have given it some thought, but it never seems to catch on. My theory is that state machines aren't a natural way to think about most problems nor are they a natural solution to most UI/frontend dev problems. Button states are a natural fit for state machines because they have a finite, well defined and well understood number of states. But, because of that, we already have the equivalent state machine built directly into CSS3 in the form of selectors (:hover, :disabled, :focused, etc).

I suspect people just write buggy code that ignores corner cases. For example, what should the UI look like if you press a button and the RPC takes a long time or times out? Or suppose an RPC returns really late, when the user went to a different screen, or already started another RPC?

I wrote a game for mobile devices in JavaScript that used a state machine and it worked far better than I could have imagined. It surprises me that there isn't a good web framework that does something similar, though Angular's notion of states comes somewhat close.

Elements of Software Construction [1] (MIT OCW 6.005 2008) has an excellent practical introduction to programming with the State Machine paradigm.

It uses Java but is applicable to any language because it's a design centric approach. In particular, lectures [2] [3] [4] [5].

It relies on a very lightweight notation and presents a choice of 4 design patterns (not just GoF State) to synthesise the code directly from the design [3].

[4] shows how to apply invariant reasoning to State Machine design, which is an extremely powerful reasoning tool.

[5] is very interesting because it explains how to deal with structured traces, which are modelled as streams using a regular grammar. This turns out to be a very simple but powerful design approach that is applicable to many situations, and very straightforward to implement using JSP (nothing to do with Java, stands for Jackson Structured Programming). Because this is basically a parser (at a very abstract level), the course then follows naturally to the FP paradigm.

It also includes a couple of very cool hands-on exercises:

Multipart file transfer [6] [7]

Midi piano player [8]

In fact, the whole course is outstanding.

[1] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[2] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[3] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[4] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[5] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[6] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[7] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[8] https://ocw.mit.edu/courses/electrical-engineering-and-compu...