5 ms·

Good analyses, but I was expecting more discussion of how best to work with (conceptual) state machines when writing code. I'm no expert on the matter, but the

• fabian2k 6y ago
  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/ 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.
  • taeric 6y ago
    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 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... :( )
    • fabian2k 6y ago
      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.
      • taeric 6y ago
        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.
    • Jtsummers 6y ago
      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.
      • taeric 6y ago
        Would love to see feedback on it. I posted back when I wrote it. I think it was mostly lost to the noise.
    • madpata 6y ago
      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.
      • taeric 6y ago
        Completely agree. I did not mean my post as an argument against state machines.
  • hertzrat 6y ago
    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 https://gameprogrammingpatterns.com/state.html
  • fpoling 6y ago
    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.
• monocasa 6y ago
  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.
  • __jem 6y ago
    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.
    • monocasa 6y ago
      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.
      • __jem 6y ago
        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.
      • deleted 6y ago
• minitoar 6y ago
  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.
• tyingq 6y ago
  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/ https://www.colm.net/open-source/ragel/ [2] https://blog.cloudflare.com/incident-report-on-memory-leak-caused-by-cloudflare-parser-bug/ https://blog.cloudflare.com/incident-report-on-memory-leak-c...
• rwmj 6y ago
  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 https://github.com/libguestfs/libnbd/tree/master/generator
• astrange 6y ago
  Ragel is a good tool for this: http://www.colm.net/open-source/ragel/ 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.
  • MaxBarraclough 6y ago
    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.
• bsder 6y ago
  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.
  • valenterry 6y ago
    > 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.
    • marcosdumay 6y ago
      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.
      • valenterry 6y ago
        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.
• moonchild 6y ago
  > 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 https://www.jsoftware.com/help/dictionary/d332.htm