[HN Gopher] Finite State Machines
___________________________________________________________________
Finite State Machines
Author : adlrocha
Score : 95 points
Date : 2021-02-21 11:31 UTC (1 days ago)
(HTM) web link (adlrocha.substack.com)
(TXT) w3m dump (adlrocha.substack.com)
| drummojg wrote:
| Is the letter "T" somehow associated with FSMs? I'm taken right
| back to one of the hardest assignments I ever had, which was
| learning C in order to write an interpreter for a FSM descriptor
| language (called "T") our professor had invented.
| ehnto wrote:
| Perhaps T might describe a transition?
| bestouff wrote:
| I prefer FSM implemented in Rust. Having valid transitions
| checked at compile time is a life saver as soon as is gets a bit
| complex - at least in my case being able to "prove" an embedded
| system wouldn't trigger its watchdog during operation was very
| important.
| surfsvammel wrote:
| FSMs are great! I've worked a lot with state machines, in telecom
| (to model different parts of 4G connections) as well as in
| capital markets (to model trades, transactions etc.).
|
| My opinion is that FSMs are best implemented on a higher
| abstraction layer than directly in code itself. FSMs tend to
| reflect the business domain very closely, are very easy to reason
| and talk about with non-tech domain experts but also tend to
| change often. Therefore we have always implemented the framework
| for the FSM along with some kind of event kernel, and then left
| the actual setup and configuration of the FSMs to a configuration
| layer.
|
| It has worked very well and has made it so much easier to talk
| about how the system works with non-techies.
| jgraettinger1 wrote:
| > My opinion is that FSMs are best implemented on a higher
| abstraction layer than directly in code itself.
|
| I really love Rust async/await for this. Under the hood, the
| compiler is simply assembling a big FSM, and polling a Future
| is equivalent stepping through allowed transitions which are
| available to it.
|
| You can even use this to build FSMs which are designed to be
| manually driven, by coordinating generator inputs and outputs
| via RefCell and one-shot channels and calling `poll` yourself.
| youerbt wrote:
| TLA+ is a great example of a modeling tool that allows you to
| create FSMs relatively easily. It can also check properties of
| your model which gives more confidence in the final design.
| tenaciousDaniel wrote:
| Seems like FSM and DDD would go very well together, although I
| haven't seen any literature explicitly linking the two.
| pknerd wrote:
| Anyone implemented in Python or Go for production systems?
| rad_gruchalski wrote:
| Protoactor for golang:
| https://github.com/AsynkronIT/protoactor-go#state-
| machines--....
| dkarp wrote:
| I've used https://github.com/pytransitions/transitions in
| production python systems.
|
| It worked great but the system was fairly simple and wasn't
| changed often. In my opinion, it's nicer when the state machine
| can be defined as configuration (in XML or whatever) and then
| generate the code. Unfortunately that's not possible with
| vanilla pytransitions, but I suppose you could build a layer on
| top of it.
| pknerd wrote:
| Interesting!
|
| > Unfortunately that's not possible with vanilla
| pytransitions
|
| Can you elaborate?
| pknerd wrote:
| BTW, did you check this?
|
| https://github.com/pytransitions/transitions/blob/master/exa.
| ..
| davidkpiano wrote:
| I'm working on XState for Python:
| https://github.com/davidkpiano/xstate-python
|
| Still a work-in-progress, but hope to make this production-
| ready this year.
| dragontamer wrote:
| A FSM post without the briefest discussion on Regex?
|
| Regex is probably the most common FSM compiler in modern
| computing. s/find.a.string/replacement/... Yeah, those regex.
| pantulis wrote:
| FSM are the solution to a lot of coding problems that in the
| beginning just look like bunch of if..thens. Of course, there are
| a lot of problems that scream "FINITE STATE MACHINE" in their
| definition, but I'd say that applying FSM early on as a sort of
| "preemptive optimization" can save a lot of headaches.
| reasonabl_human wrote:
| Do you have any examples off the top of your head? Haven't
| explored this domain
| slt2021 wrote:
| Actor pattern (akka) is the distributed FSM
| nahuel0x wrote:
| Not really, an actor can implement an FSM but it also can
| have an infinite number of states.
| slt2021 wrote:
| every non deterministic SM can be converted into FSM:
| "Using the subset construction algorithm, each NFA can be
| translated to an equivalent DFA" https://en.wikipedia.org
| /wiki/Nondeterministic_finite_automa...
| pantulis wrote:
| For example an ecommerce order tracking system with different
| status (in cart, paid, shipped, returned, so on). Spree
| solves it very elegantly, look at those "events",
| "transitions".
|
| https://github.com/spree/spree/blob/4687e608b49236c2850500b0.
| ..
|
| Also, Spree has this nice intro to FSMs
|
| https://github.com/Humane-
| Documentation/Spree/blob/master/re...
| pantulis wrote:
| I also happened to work in a very huge C++ project for the
| business logic component of a call center, using CORBA and
| the Reactor pattern from ACE to integrate different parts
| of the user / ACD / 1st agent / specialist / CTI combo.
|
| But it was a telco project, so the "let's use a FSM" was
| well thought from the beginning. Turns out you could easily
| know what the system would do just by reading a huge
| Smartdraw document, and this also allowed for reasoning on
| new use case scenarios. It did not matter that the main
| file was a horrendous 40kLOC C++ class because the
| Smartdraw diagram _was_ the documentation and everything
| else was just trivial code.
| greenbit wrote:
| Having been both an EE (first) and a software engineer, I have
| noticed this: as an EE, I would _never_ randomly attack a problem
| with multiple independent FSMs. Whereas in the s /w realm, I've
| seen seasoned professionals, without hesitation, do exactly that.
|
| I know from University CS training, that s/w engineers most
| likely all would recognize that any piece of software would,
| taken as a whole, constitute a single FSM. But as s/w engineers,
| we usually turn a blind eye toward that fact, seemingly bc
| there's too much complexity, we perceive the pieces as
| independent, and need to divide the problems in order to conquer
| them.
|
| This bears some thinking about. For now, just saying, the
| difference in perspective is interesting
| cube2222 wrote:
| The product of multiple independent state machines is in effect
| a single state machine.
| greenbit wrote:
| Oh absolutely. Part of what I was getting at was that this
| larger meta-FSM often 'just happens', w/o really being fully
| intentionally designed. But of course the product that you
| actually ship _is_ that meta-FSM, so it 's the behavior of
| that thing that matters.
|
| Idk, just woolgathering here anyway. One thing that drives me
| nuts is when people take a linear sequence of code, chop it
| into little pieces, give each piece to a thread, sometimes
| give such threads little pieces of _other_ task sequences,
| then bodge it all back together with various kinds of thread
| synchronization methods. What you end up with is almost
| impervious to analysis. So clearly keeping linear sequences
| of code intact has advantages. Thinking that maybe by
| thinking about which assemblages of such sequences form
| relatively independent FSMs, one might, as a s /w developer,
| be able to make better decisions about how to organize the
| larger scale structure of software.
| rkangel wrote:
| I disagree with that - as an EE you almost certainly regularly
| attack a problem with multiple independent state machines. For
| example - 3 devices hanging off an I2C bus. Each of those
| devices will be implementing the I2C state-machine to interpret
| SCK/SDA.
|
| It's a question of what abstraction level you are looking at.
| In a complex system you need multiple components abstracted
| from each other and high levels of the system. In those cases,
| the building blocks will have their own state machine.
|
| The same is true in software, although in software it's much
| easier to reach a high level of complexity. Your average
| protocol stack (be it IP, LTE, or Bluetooth) is composed of a
| number of separate layers. These communicate between themselves
| with messages, and update their internal state-machine. This is
| a great way to model a system.
|
| The same is true in 'closer to hardware' land. An FPGA
| implementation will often include many explicit state machines,
| and even more implicit ones.
| greenbit wrote:
| Yeah, from that angle, yes, you'd do that. But within any one
| of those devices, would you carve the insides into
| independent FSMs? Probably a 'yes' qualifed with 'if they
| were very independent problems anyway'.
|
| I did say I needed to think about it more. Guess if there
| were to eventually be a point I'd try to make, it would be
| that s/w seems to have a tendency to be structured more like
| an entire complex system, than like nice tight clean self
| contained state machines.
|
| Idk if this has to be so or not, but in recent years with the
| rise of multicore processing, I've seen a huge gravitation
| toward splintering s/w into threads, without, seemingly, well
| planned combination of those threads. It's sort of like if,
| as an EE you were going to build a whole computer, declared
| "I'm going to need counters and adders and registers (etc)",
| and then set about designing great counters and adders etc,
| but then just lashed them together somewhat haphazardly and
| kind of just hoped to get the system you wanted.
| rkangel wrote:
| Modern software development is about management of
| complexity. That's why you have abstraction, that's why you
| have CI, that's why you have automated tests.
|
| Having multiple independent state machines isn't
| necessarily a failure of system thinking. To extend your
| processor argument, do you think there is only one state
| machine in (each core of) an x86 processor?
| natsch wrote:
| > You are now planning to build your next big system as a state
| machine,
|
| Often people don't actively decide to write a state machine, but
| do so anyway. I think the big takeaway of FSMs is how to
| recognize them in an idea or implementation and actively using
| them as a nice abstraction.
| bjoli wrote:
| I found languages with TCO even easier to implement FSM in: a
| state is simply a procedure, and going from one state to another
| is just a procedure call.
|
| The difference is small, but once you start getting hairy state
| machines I have found that it leads to smaller mental overhead
| for me.
|
| The same would be true for something like a recursive descent
| parser.
| elviejo wrote:
| What is TCO? what are languages that implement TCO?
| klibertp wrote:
| Tail Call Optimization, better called Tail Call Elimination.
| Haskell, OCaml, Erlang/Elixir, Scala with @tailrec, Scheme,
| Lua(!), most other functional languages.
|
| Basically, if there's a call to a function B at the very end
| of function A, there's no need to create a new stack frame
| for the call to B - you can reuse the frame created for call
| to A. It both saves memory and improves performance. A
| special case is when A and B are both the same function, in
| which case we say A is tail-recursive.
| user-the-name wrote:
| That means you are not able to interrupt your state machine
| easily, or to serialise its state. That might be OK in a lot of
| cases, but not all.
| dragonwriter wrote:
| Serializable closures (even serializable continuations) are
| available in a number of languages, including probably most
| often ones which also have TCO.
| klibertp wrote:
| Function objects, including closures, can be serializable -
| they are in Erlang/Elixir. You can send a lambda/closure over
| to another node (on another machine) to execute. It's
| actually one of the basic building blocks of OTP.
| user-the-name wrote:
| I assume this only works if the functions are exactly the
| same. It would break between different versions?
| rad_gruchalski wrote:
| It depends. It's possible to provide a mechanism to
| switch versions but as it very often is: there are
| dragons.
| hderms wrote:
| Seems like trampolining would be useful to make it
| interruptible while still mostly preserving the ergonomics of
| viewing state transitions as procedure calls
| andrewla wrote:
| The advice given in the article is to enumerate your states.
| Since usually when I'm designing an FSM I have an approximate
| idea of what's required, I find it generally much more
| instructive to dive right in.
|
| Start with the "initial" state and start mapping out transitions
| -- at each node, list out all the transitions (exhaustively) from
| that node and assign them states. Walk through the happy path to
| the terminal state, then start fleshing out the various branches
| from there. Once you've got the graph, start merging states
| together as necessary, and since you've been making sure that
| your transitions are exhaustive at each step, it will be
| complete.
|
| The next step is to step back and look at the entire machine for
| simplifications, but trying too hard to shoehorn two disparate
| states into the same state often leads to strange behavior
| (because transitions from one don't make sense in the other), so
| it's best to wait until you have some idea of the entire machine
| before you start combining states.
| thangalin wrote:
| I recently released a version of my free and open-source text
| editor, KeenWrite, that embeds requests to Kroki[0]. Kroki
| provides a REST API for generating many types of diagrams,
| including Mermaid diagrams. KeenWrite provides users with the
| ability to reference variables within the text. Combined, they
| make it easy to apply the DRY principle to documentation.[1] Even
| though the request goes over HTTPS, the diagrams are drawn in
| nearly real-time (and cached).
|
| The screenshots show GraphViz diagrams, but changing "graphviz"
| to "mermaid" at the start of the code block will permit drawing
| Mermaid diagrams. See the video[2] for more ideas on how to mix
| variables with documentation.
|
| [0]: https://kroki.io/
|
| [1]: https://github.com/DaveJarvis/keenwrite#screenshots
|
| [2]: https://www.youtube.com/watch?v=u_dFd6UhdV8
| carlbarrdahl wrote:
| How come there isn't better re-usability in state machines?
|
| It seems it would be powerful if they were treated as re-usable
| lego bricks of state and logic.
|
| Apps could then pull these in, connect the wires to any potential
| backend, and style the interactive components.
| davidkpiano wrote:
| What makes them reusable is dependent on how you implement
| them.
|
| A state machine that is the simple relation:
|
| (state, event) => [state', actions]
|
| has a very reusable interface, as long as it doesn't execute
| the actions (effects, commands, etc.) itself. It's just a pure
| function that can be used anywhere to get the next state and
| the actions to execute as a result of receiving an event.
|
| Then you can do exactly what you're describing: connect the
| wires, style the components according to state, etc.
| carlbarrdahl wrote:
| Thank you David. Your xstate repo on github brought my
| attention to state machines and state-charts. Which I guess
| is why I'm interacting with this thread right now.
|
| I often wonder what would happen if we could find ways to
| build complex applications by creating re-usable blocks using
| state machines (state, logic), json-schemas (structure, data-
| model), and React* (presentation).
|
| All of these are serializable documents. Imagine being able
| to search a collective collaboration of components and
| schemas and piece it together. Could probably be graphical
| interface like Figma.
|
| There are certainly other pieces that could be also used
| (graphql to describe data-fetching, markdown (mdx) for
| content).
|
| *or similar
| davidkpiano wrote:
| I'm currently building this! More info to come soon.
| dwohnitmok wrote:
| You probably are already familiar, but if not, this is
| exactly the entire concept behind Elm (in fact that signature
| is exactly the update function at the heart of the Elm
| architecture). And indeed the Elm community has a lot of
| ideas on how to split that basic idea to make it reusable.
| MarkSweep wrote:
| At a previous company we used statemachines to debounce
| signals, implement protocols, and sequence robot moves. While
| they were designed so that the actions executed on state entry
| were pluggable (i.e. all action were executed by calling
| through a C# interfaxe), in practice we did not use it. Instead
| were abstracted at a slightly higher level: components that
| wrapped statemachines with some extra logic and nice APIs. The
| inputs for the statemachines were also pluggable, so different
| sources of digital inputs or motor control could be used.
___________________________________________________________________
(page generated 2021-02-22 23:02 UTC)