Hacker News Reader

That's one of the reasons I love ADTs and pattern matching in systems code so much.

For instance in rust where both self and Event are enums

  fn on_event(&mut self, event: Event) {
    *self = match (self, event) {
       (State1(data), Event1(args)) => {
           .... processing event1
           State2(new_data)
       }
       // All other events in State1 are ignored
       (State1(data), _) => State1(data),

       (State2(data), Event1(args)) => {
          .... processing event2
          State3(new_dat)
       }
       ..... pattern match the rest of the matrix
     }
   }

will do a great job highlighting missing transitions of the state machine's transition matrix.

My favorite rust state-machine-ism is consuming self by value when you transition. In combination with generics and From, this allows you to ensure that states are only ever entered into via the transitions you encode by implementing the trait, and because the previous state is totally consumed it makes the transitions super clear.

I'd love to read a blog post detailing exactly how is this done.

Here! https://hoverbear.org/blog/rust-state-machine-pattern/

Much appreciated, thank you!

Could you explain a little more? That sounds really cool.

Here's a good blog on the topic: https://hoverbear.org/blog/rust-state-machine-pattern/. The last implementation of Raft uses this pattern.

I started off by doing that, but ultimately didn't like it for my use cases.

* It didn't seem to grant a lot of benefits over pattern matching (errors were pushed to compile time checks in both cases).

* It had larger cognitive overhead since the allowed transitions were either all over the place in the source instead of in one match statement or weren't colocated with their structs.

* It didn't seem nearly as good at attacking the combinatorial complexity you see in these matrices as pattern matching is.

It's definitely not a great fit if you have a ton of different state transitions, since the From impls add a lot of boiler plate. But I've found it perfect for situations where there's only a few very well defined transitions, like the Raft implementation suggested in the blog post I linked in parent reply.

Not Rust but I often find with ADT's + Pattern matching I end up with a state machine without even attempting to write a state machine.

ADT's + pattern matching make it a very easy pattern to implement. If your language supports exhaustive pattern matching it's also a very easy way to leverage the compiler to find bugs in your logic.

I'm certainly not an expert in this, but the big issues when not using a "real" state machine but e.g. a bunch of separate booleans representing various parts of the state (isLoading, isError, ...) are the following:

- you can be in an inconsistent state that should not exist, e.g. isLoading and isError at the same time

- state transitions that should not be possible can be performed if you make a mistake

The first one you can easily fix without a library by using a state enum instead of a bunch of booleans. The second one is probably better handled by a library that implements a declared state machine or state chart. In Javascript that would be e.g. xstate (https://xstate.js.org/).

I found that simply thinking about the states and writing them down as a state machine is already very helpful in avoiding certain kinds of issues that arise when you just do this on the fly.

This gets greatly compounded when you have a lot of states. As an easy example, consider the "state machine" for a rubik's cube. All told, this isn't insurmountable, but you are almost certainly not going to write down all of the allowed states with all of the possible transitions.

Which is not to say you can't make a program to reason about what the allowed states are. I started a probably bad attempt at that a while back at https://taeric.github.io/cube-permutations-1.html. (And, I just noticed the mathjax included on that page isn't loading. Almost certainly my fault... :( )

State charts avoid that problem to some extent, you don't explode the number of state like in a simple finite state machine. But that's a point where you certainly want to use a library.

Right. My assertion would then be that many things are modeled on a ton of possible states.

Granted. In context of this story, I'm in complete agreement with you.

Might be worth reposting that link, it's an interesting topic on its own. Rubik's cube transformations as permutations is one of those "obvious" things that had never occurred to me before, plus the neat interactive demo at the bottom.

Would love to see feedback on it. I posted back when I wrote it. I think it was mostly lost to the noise.

I think your answer boils down to "pick the right tool for the job". Of course state machines are cumbersome for systems with loads of different states and transitions.

But state machines are really useful when designing safety-critical systemsfor aeronautical, automotive or train components, especially if one uses timed automata for modelling.

It's possible to either generate the code from the model or use the model to automatically generate a complete test suite for the modelled system. Very useful for verification purposes.

Completely agree. I did not mean my post as an argument against state machines.

The permutations you're getting are Cayley's Theorem in action: https://en.wikipedia.org/wiki/Cayley%27s_theorem

Basically, there's a finite group that acts on the Rubik's cube, and every finite group is a subgroup of a permutation group if you squint at it right. (what's a 'finite group action?' The 'group' is a set of composable and reversible "moves." The 'action' means that the group moves are effectively state transitions acting on a set of states, and that the action is nice and associative: g(hs) = (gh)s. And 'finite' just says that there's only so many states possible...)

Really nice demo, by the way! Very fun to see the squares go flying.

I'll have to read up on Cayley's Theorem. Thanks for the link!

Glad others found the squares flying as much fun to watch as I did. :D

If you implement your favourite variant of the state pattern, state machines get a lot nicer to work with also - depending on the task at least. You wouldn’t bother with it to track a button press state in embedded but it’s nice when the state is complex, has some sort of “on tick” aspect, or there are a lot of states

https://gameprogrammingpatterns.com/state.html

On a few occasions in C++ I have found few boolean flags are superior to enum in code that evolves. What happens was that code changes effectively turned deterministic state machine into nondeterministic one. Modeling the relevant parallel states with bits is very natural then.

Ragel is a good tool for this: http://www.colm.net/open-source/ragel/

This can be built into languages as "typestate" but noone ever seems to get around to doing it. It's unfortunate because I think it's the only acceptable way to do OOP.

Heh, I mentioned Ragel in that other thread I linked to, although I see I messed up the link and linked to GraphViz instead.

I have to admit I've only very briefly dabbled with Ragel but yes it does seem a pity that this approach is so rarely used.

One of those code-generative tools is Ragel[1], which was in the middle of an issue at CloudFlare[2]. Though CF did note that it was a bug in how they used Ragel, not Ragel itself.

[1] https://www.colm.net/open-source/ragel/

[2] https://blog.cloudflare.com/incident-report-on-memory-leak-c...

This is what Interana does. You define the states and the transition rules, and what you want to compute (eg how many times was this pattern matched, what was the p50 duration between steps 2 and 5, etc.) It then compiles this into machine code to actually scan the column store using llvm.

To be honest I wouldn't bother with an existing code generator. However I would definitely consider modelling your state machine and generating code from that. Also model your state machine hierarchically, especially if it has any kind of complexity. We did that with our NBD client, which has 96 states in 17 groups, generating C code: https://github.com/libguestfs/libnbd/tree/master/generator

> code-generative tools out there that help make state machines very explicit: you describe the state machine, and the system generates the code.

J's sequential machine builtin[0] implements something similar to this. It doesn't generate code, but it executes a state machine based purely on descriptions of states and transitions.

0. https://www.jsoftware.com/help/dictionary/d332.htm

tl;dr Software programmers continue to fail to grasp that "protocol" means "state machine". News at 11.

Even beyond just "use an actual state machine", programmers don't grasp that you need to think about:

1) What is my state now?

2) What are my inputs now?

3) What are my outputs now?

4) What is my state next?

5) Where/when do I transition from state now to state next and does it need to be atomic?

Conflating any of these results in bugs. And not using state machines explicitly always results in conflating these.

One of the most important overlooked concepts in protocols is that "time" is an input (interestingly, Carmack talks about this in game development, too). Timeouts and errors are a state like anything else.

> And not using state machines explicitly always results in conflating these.

Not true - (pure) functional programming also enforces that you do exactly that. Even more, its rule-set also enforces that time must be an input.

Most pure functional idioms for handling a protocol are state machines, some of them in disguises, others plain ones.

The ones that aren't state machines are very limited and often enough way too verbose.

In particular, FRP is worth noticing as being exactly a set of states that change by means of events. It's a nice idiom for composing very complex state machines, but isn't even disguised.

I think it is the other way around.

FRP goes further than state machines, in that it forbids any side effects.

E.g. you could build a state machine that, when in a certain state and getting a certain event, responds or acts by printing the current time. A classical state machine will thus behave different, depending when it receives the event. However, in FRP you _must_ either parametrize the event with the current time, or you need to have something _outside_ of the statemachine (such as an effect interpreter) which handles effects such as printing the current time. A classic state machine does not have these restrictions.

General state machines are useless as an abstraction: they're fundamentally noncompositional, which makes them impossible to reason about as soon as they get big enough. Many things can be represented as state machines, just as any program can be represented as a sequence of machine instructions; that doesn't mean that's a useful representation for working with.