12 ms·

State machines are wonderful tools

338 points by chmaynard 6y ago

zevv 6y ago
Encoding parser FSMs by hand can be tedious and error prone, there's some nice tools to help you with that; I'm a huge fan of Ragel: http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/
- 082349872349872 6y ago
  I sometimes wonder if replacing the hand-coded FSMs of UI ravioli callbacks with a more parser-generator-like declaration would be a cleaner approach. (or maybe it's already been done? I haven't done UI code since last century...)
grandinj 6y ago
FSM are fun to write but horrible to modify especially if you’re not the one who wrote it.
- amw-zero 6y ago
  This is only true when considering a specific software design that implements the state machine. I'd say the most popular way to define a state machine in code is how Xstate does it: https://github.com/davidkpiano/xstate https://github.com/davidkpiano/xstate. You define your states, and then you define your inputs, and then you map out every single transition between states. This is probably the most inefficient way to design a state machine. There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible transitions (that's the definition of a completely connected graph). This means there's a large space of possible transitions relative to the number of states, which means there's a high probability that you will have to modify lots of transitions when modifying the state machine itself. In this article, this author is sharing several alternative designs for state machines, which don't look like they suffer from exactly the same problem. I'm most familiar with TLA+, where you describe a state machine simply with one logical predicate: the "Next" state relation. This is the most powerful way I've found to define state machines, and modifying one function to entirely change the behavior of the state machine is very easy in practice.
  - teacpde 6y ago
    Mind elaborate on the next state predicate approach? By next, I imagine the focus is on transition rather than state; however, if you have multiple transitions arriving at the same state, what makes the next approach better? At the end of day, the state machine is the same regardless how it is implemented.
    - nitrogen 6y ago
      Edit: looks like they're talking about this: https://en.wikipedia.org/wiki/TLA%2B https://en.wikipedia.org/wiki/TLA%2B What I describe below is not related. ---- Not the OP, but here's a stab at it... In state machines commonly used in embedded C code, each state is represented either by a function or by a struct that contains a function pointer. The state machine calls the current state function in a loop or whenever relevant events happen, and that function returns a pointer to the next state, calculated based on inputs. If there is no state transition, then the function returns NULL or returns its own state.
    - amw-zero 6y ago
      See the above reply where I gave an example with both representations. Agreed, the machine representation is independent of the machine itself, it's the same mathematical object. So what I was talking about was how to represent using only a relation which describes the possible next states given the current one. This is the most common definition of a state machine, and for me, it's a cleaner representation since you avoid referring to each edge in the state graph explicitly.
  - JadeNB 6y ago
    > There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible transitions (that's the definition of a completely connected graph). A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels. (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.)
- lmilcin 6y ago
  The problem with modifying FSM is if you start with modifying the code. This is wrong approach. The FSM is not a code but a model and the code is just an implementation of the model. What you want to do is to recreate the process of modelling (or modify existing model) and then recreate the code based on that. What I do is to have an implementation-agnostic model of the FSM that gets translated to code. That code is never modified, it only is called from external modules or calls external modules. There are some cases where I would just hardcode the FSM without the model. Those cases are when I do not expect the state machine to change because it follows from the fundamental description of the problem. For example, I might have some communication protocol and the state machine describes the state of that communication channel. If I do my job well the state machine maps 1:1 to the problem and will never need to change even as the rest of the application changes.
  - teacpde 6y ago
    In your example, what happens if changes need to be made to the protocol? It is less frequent than business/application changes, but definitely can happen.
    - lmilcin 6y ago
      Good protocols are usually made in layers. You would typically want to have some state machine describing lower part of application protocol on which you build higher level of your application protocol, composed of specific functions. This way you can modify functionality without necessarily touching low level implementation. I can give an example. I have worked with credit card terminals and I have implemented entire application from scratch. There is a protocol to communicate between the terminal and the acquirer's system (ISO 8583). This protocol specifies a flow and format of messages. For example, if you send a transaction request, you will get a response. If you don't get a response you may or may not retry it, etc. If you send a transaction advice (ie. transaction has already happened) you must be retrying sending it until you get a response, but every retransmission after first must include a bit that says it is retransmission. If the request or advice has been sent and transaction was cancelled, you need to be sending cancellations until you get an acknowledgement. Now, all those messages have a huge amount of fields that change regularly as requirements change, but the basic flow of the protocol is fairly constant and has been constant for many years. I have implemented the protocol as a tree of state machines telling the application what to do based on events and I believe the code has not been touched in over 10 years even though the application was in constant development.
- rualca 6y ago
  > FSM are fun to write but horrible to modify especially if you’re not the one who wrote it. It really depends on the tooling you're using. For example, Qt's support for SCXML[¹] eliminates much of the pain of using state machines. [1] https://doc.qt.io/qt-5/qtscxml-overview.html https://doc.qt.io/qt-5/qtscxml-overview.html
- jarirajari 6y ago
  FSMs should be "written" visually, and they should have either hierarchical sub-states or some sort of a grouping scheme to keep complexity at a reasonable level. FSM examples are usually too simplified, and they don't show how to manage the complexities of a real, more complex state machine.
- blunte 6y ago
  It also depends on how you implement the state machine. If you're constrained by memory or performance (or playing golf), then you may end up with code like TFA. But if you're implementing in a typical app, you can obviously organize and write that is very understandable. I find the title of TFA misleading in its generality in comparison to the content of the article.
- xondono 6y ago
  The general issue is that FSM require a lot of naming, since you want to give every state a significant name, and naming is hard. When the states are clear enough, modifying FSMs is very nice.
  - teacpde 6y ago
    That isn’t necessarily a state machine problem, a state is an abstraction that maps to part of your business semantics. Naming becomes hard when your state abstraction isn’t clear, which in turn is probably due to how business semantics are modeled. One the most important things in implementing state machines is to draw it up and make sure every state and transition has clear meanings before actually implementing them. There usually will be multiple iterations of modeling before arriving at a good design.
    - spacemanmatt 6y ago
      Nomenclature challenges are a negative code smell
- masterofmisc 6y ago
  Yeah, i find that using a library (like Stateless for C#) where it makes you "spell-out, upfront" each of the states and the transitions that are permitted from this state, it makes it easier to reason about the code.
- threatofrain 6y ago
  But for many this is just React with Redux, and the community buzz around that has been that teamwork is made easier. You’d have a state machine if the problem called for it anyway, but with redux everything is now explicit and teammates come prepared.
loopz 6y ago
Isn't FSM more like writing a program consisting only of GOTO's? I call this the "loopz-effect", where any single state may have effect in any other state of the program.
- ajuc 6y ago
  It's the opposite. In a FSM you have clearly defined states and all possible transitions between them. If you write the same code as normal imperative code that modifies some variables - to understand what it does you have to "run it" in your brain and reverse engineer the states and transitions yourself.
- davemp 6y ago
  It's more like having a switch statement inside of a loop. The variable you switch on is the next state and the case you're in is the current state.
- retrac 6y ago
  Strictly speaking, yes. But you should think of it as a formalized abstraction over that; a way to reason about something you can easily translate into a bunch of goto statements. It's just like how all if/then and function call constructs compile down to goto, as well. Some languages will offer more abstraction over this, but you can still do such constructs in assembly language if you want to by hand-holding the machine through every step. If you do find yourself writing assembly language (or C, for that matter!) then you should do just that; implement high-level constructs at the low level with a bunch of jump statements. The resulting code is verbose and superficially seems gnarly, but will also be far more scalable and robust. But there are compilers for a reason! There are some examples of automatic FSM to C compilers elsewhere in this thread. Some very high-level languages have embedded domain languages for FSM generation as well.
- garethrowlands 6y ago
  Yes. And not only that, but GOTOs are the normal recommended way of implementing an FSM.
  - 6y ago
vesinisa 6y ago
Cool trickery, but should I ever encounter one of those hex tables in a program I am maintaining, I would certainly hope to see at least the state graph of the encoded machine as documentation.
deleted 6y ago
[deleted]
hyperpallium2 6y ago
Now you equivalently have two problems.
psykotic 6y ago
Some random fun things you can do with DFAs/NFAs: 1. From two machines you can build a single machine that corresponds to running them in lockstep/parallel. Most language classes are closed under unions but regular languages stand out by being closed under intersections, and that relies on this construction. You can't replicate this construction with pushdown automata to show that context-free languages are closed under intersection because the product automata would require two stacks. But in fact the intersection of a context-free language with a regular language is context-free via this construction. 2. You can run them backwards. Usually works best with NFAs since reversing a DFA can seriously inflate the state space. E.g. if you're trying to match a regular expression of the form '<re1> string <re2>' you can search for 'string' and then match re1 backward and re2 forward. Running machines backwards can also be used for computing capture groups after a match has been found since the fastest methods for matching don't let you compute capture groups on the fly. Decoupling the re1 and re2 machines also means you end up with two independent machines with smaller state spaces, which means smaller, cache-friendlier lookup tables. See the next item for a less conventional example of what you can do with small state spaces. 3. While DFA execution seems inherently serial, it can actually be parallelized very effectively if the state space is small enough, through speculative execution. Suppose you want to lex a string in parallel by chopping it in half. You don't know what state the DFA will be in when it reaches the halfway point, but you can process the second half for all possible states at that point. Then when both halves are finished you throw away all but one of the speculative answers for the second half based on the final state for the first half. This is extremely fast and practical with PSHUFB/TBL-like instructions if your state space is small enough, at most 16 states for PSHUFB. You can mux together multiple PSHUFBs to go beyond that limit but the cost increases substantially. (This is a parallel prefix algorithm when applied recursively. As far as I know the application to parallel lexing goes back to the Hillis-Steele paper on data-parallel algorithms from 1986.) 4. There's a critical optimization for the last algorithm which is sometimes applicable. A log file processor might have numerous internal states while processing a line, so you'd rather not speculate on all of them. Instead you can chop the file in half and from the second half seek forward to the next newline and start there. This avoids speculation entirely if there's a unique state following a newline character regardless of what state you were in before the newline.
- 6y ago
dqpb 6y ago
Every program is fundamentally states and state transitions. You can be explicit about it or not, but the states and transitions are there regardless.
- amw-zero 6y ago
  Absolutely. This is the definition of what computation is. Even in the lambda calculus, where everything is defined with pure functions, we build up state sequentially over time, based on previous values of the state. The fact that there’s no mutation under the hood is inconsequential.
ColinWright 6y ago
I'm reminded of a thing I wrote about seeing a state machine implemented in real life: https://www.solipsys.co.uk/new/StateMachineInRealLife.html?UA01HN https://www.solipsys.co.uk/new/StateMachineInRealLife.html?U...
- skrebbel 6y ago
  That was a delightful little read, thanks!
- pardner 6y ago
  Great little story!
- deleted 6y ago
  [deleted]
amw-zero 6y ago
These are some pretty cool examples, though a little too nitty gritty to communicate the practical importance of state machines. The truth is, state machines are so fundamental that programmers are not even aware that they are using them. Many, if not most, computer programs can be seen as state machines. In fact, programming can quite literally be seen as state machine creation and management. Programming languages are tools for creating complex state machines without having to manually wire them together. For example, take the following factorial function in Python: def factorial(n): result = 1 while n > 1: result *= n n -= 1 return result Here is a TLA+ spec for the same algorithm, along with the corresponding state diagram for calculating factorial(5): https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c632147 https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c6.... This is a simple example, but the state diagram illustrates an important point that the while loop doesn't: the algorithm is completely linear, meaning it simply builds upon previous states. Even though there is branching in the code, there is no branching in the state diagram. Of course, we're not so lucky and most state spaces are not linear. Here's the spec and diagram for a user interface that I was building a while back: https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85cb93bd https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85c.... There was a subtle state-based bug where a user had to perform a special sequence of events to experience it. The code seemed simple, but looking at the state diagram directly showed what the bug was immediately. This was in a React app, and doing this exercise made me realize that React apps trivially translate to state machines as well. Whenever you call `setState` or the corresponding `setHookValue` function when using hooks, you are defining a state transition. The set of all state variables determines the full state space of the application, and bugs arise when we forget to consider that fact within some of our transition functions. Long story short, you don't need to use a state machine design pattern such as Xstate to actually have a state machine. In fact, unless you are doing some very weird things, your application most likely already is a state machine under it all, but that's only because a state machine is a very simple, general concept that has tons of applications.
- arcbyte 6y ago
  Yup. Basically all enterprise software is just state machine design. Any simple RESTFUL app with a database is just a state machine. Call one end point to create a resource, fetch it later from a second. Calling them out of order yields an error state. Super simple state machine. Of course we've reinvented this wheel so many times. Something like LISP is fun because you can get both the executable and (human AND machine) readable representations of a state machine out of the exact same source code. Thats still the future of programming.
sovietmudkipz 6y ago
It’s humbling to see a state machine implemented using coroutines. I program professionally since about 6 years ago but have only recently appreciated generators and coroutines. I’m working through learn.unity.com for fun and because, in my estimation, there is an upcoming boom in real time interfaces for real work. All the people playing video games have mastered skills that aren’t being taken full advantage of. Anyways, coroutines in Unity can be used to do interesting things over time while attached to the game loop. My point, despite my digression, is just how there are still basic/intermediate topics I have only been able to appreciate recently. Humbling.
- sali0 6y ago
  100% agreed on the increasing importance of video game interfaces. Nice to see I am not alone in that thought.
  - sovietmudkipz 6y ago
    Every now and again as I play RTS (and other) games I imagine how the interface could be used in for business, engineering or marketing. There’s potential, IMO. The test (as I imagine it now) is making work fun enough that my 13 year old self would want to do work. At any rate, ideas are cheap. Prototypes and implementation are what matters. We’re speaking publically but I would like to know what you imagine about when you think about this topic?
    - jodrellblank 6y ago
      I sometimes wonder what it would take to visualise the state of a system in a game engine such as OpenTTD[1]. Then I remember the video of VMware's VMWorld 2017 event keynote speech[2] where they did such a poor example of VR - cubes representing virtual machines which you could virtually throw into the trash to delete them, or pick them up and move them to another host to use VMotion. It was a poor combination of low quality uninspired use of graphics and 3D space, and individually managing servers one at a time for things VMware DRS will do (load balancing moving of VMs between hosts) and things you don't want to be doing by hand (individually provisioning and removing servers). I'm not convinced that a game engine is capable of showing enough information compared to flat text, tables of numbers, graphs, and things made as web pages or documents where you can scroll down several pages. In a game engine, the things you aren't looking at end up far away, smaller, easier to miss. Text usually has to be bigger to be readable. How do you bring things to attention without just replicating a web browser showing a page of stats in a game engine? How do you make "work" possible without replicating a right click menu in-game, or a popup Quake style command line? How do you envisage an RTS game interface doing work - what kind of work, and how does the interface help with it? > "The test (as I imagine it now) is making work fun enough that my 13 year old self would want to do work." A game you have to play for 6+ hours continuously, cannot quit, cannot pause, cannot undo/retry, almost cannot die or lose, has no story, no end to get to, and is a repetitive grind? [1] Isometric world map full of moving parts, metrics and graphs https://linuxhint.com/wp-content/uploads/2020/01/OpenTTD.jpg https://linuxhint.com/wp-content/uploads/2020/01/OpenTTD.jpg [1] which has overlays for things like cargo pressure in two directions https://www.openttd.org/screenshots/1.4-cargodist.png https://www.openttd.org/screenshots/1.4-cargodist.png that could be displaying network link load, etc. [2] https://lukaswinnnet.files.wordpress.com/2017/09/vmworldeu2017_d1keynotepatalan.jpg https://lukaswinnnet.files.wordpress.com/2017/09/vmworldeu20... [2] https://i.ytimg.com/vi/EiKyR4X5kxs/maxresdefault.jpg https://i.ytimg.com/vi/EiKyR4X5kxs/maxresdefault.jpg
carapace 6y ago
FWIW, here's an example I wrote in Python "that imitates what “compiled” FSM code might look like in an “unrolled” form. Most FSM code uses a little driver loop and a table datastructure, the code below instead acts like JMP instructions (“jump”, or GOTO in higher-level-but-still-low-level languages) to hard-code the information in the table into a little patch of branches." https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html#drive-a-fsm https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expre... It's part of an (incomplete. slightly broken) notebook on Brzozowski’s derivatives of regular expressions.
ci5er 6y ago
A long time ago I used to auto gen http and smtp servers and message queues (similar to RabbitMQ) from very compact descriptions. My in-house I infrastructure build-out productivity went up ~30x, but all the downstream teams hated it.
strenholme 6y ago
I ended up using one in MaraDNS 2.0 to parse configuration files, since the C code for parsing MaraDNS 1.0 configurations files was a lot more error-prone and hard to maintain. The state machine’s grammar is embedded in the Deadwood (MaraDNS 2 recursor) binary. Here is a full explanation of the finite state machine, along with the actual embedded code: https://github.com/samboy/MaraDNS/blob/master/deadwood-github/doc/internals/MARARC.parser https://github.com/samboy/MaraDNS/blob/master/deadwood-githu...
sixdimensional 6y ago
No post on state machines would be complete without mention of the superset concept of Petri nets [1]. I have used Petri nets to build my own workflow engine previously. Building a workflow engine is one of those things... nearly every enterprise app has one, and normally you shouldn’t need to build one if you can source one... but it is an exercise that makes you a stronger engineer/developer too, deepening understanding of the patterns that lie beneath most systems. Back when I was building, openly available workflow engines, BPML, BPEL etc. were not really a thing yet, so it made a little more sense to be building one. [1] https://en.wikipedia.org/wiki/Petri_net https://en.wikipedia.org/wiki/Petri_net
- mikewarot 6y ago
  This is my first encounter with the Petri nets, and at first I thought they were just like state machines, in that you're only concerned with flow of control... boy was I wrong. Its going to take a while to fully grok, but it seems impressively powerful in what it can do. Thanks!
- nudpiedo 6y ago
  Do you have more information on how to build workflow systems, and why is it good to do so with Petri nets rather than abstract the processes with classes or whatever else? Any information is welcome
  - sixdimensional 6y ago
    There are two components to your question - the practical side, "how do I build a workflow system?" and then, "why Petri nets?". If you really want to build a generic workflow engine, I think the way is to identify the pattern they follow and implement that. Build classes, attributes and methods that abstract away automating a process in a generic sense (e.g. turn workflow into one or more services) and then integrate those service(s) into your application as the glue that holds together complex processes. It's obviously harder than that one sentence, of course there are lots of nuances, but that's probably the simplest way I can think of to explain the high-level hand-wavy approach to doing this if you want to build it yourself, without going into all the details. If you understand the pattern, and would rather not build, but buy or obtain an open source workflow engine/management system, many exist [1][2]. Most enterprise applications (e.g. Oracle, SAP, Salesforce, etc. etc.) have such workflow tools built in already. Regarding the second part of your question, "why Petri nets?", well, one could argue that any system that automates a process in any way is a kind of workflow management system/engine or could be modelled as a "Petri net". I guess you could say, "why care about patterns in software engineering" then? The difference is, like many patterns, Petri nets give you a tried/tested technique for conceptualizing and modelling the system/process, validating its correctness, and in some cases, tools/engines that implement these concepts can even give you the executable framework for building too. You know, standing on the shoulders of giants and that kind of thing. Technically, Petri nets are a superset for modelling/designing/visualizing/validating what you can do in a workflow system. Also, to be clear, the concept of Petri nets is in every way compatible with/related to object oriented design, and even functional and procedural programming paradigms. Perhaps I can try to answer your question in this way.. by relating Petri nets to design patterns in software engineering (think, Gang of Four, Patterns of Enterprise Architecture, etc.). You know how, when you're developing software - over the years, you start to see patterns emerge? The best way to understand Petri nets and how they relate is to see what problem they solve in work you might have done yourself. If you have ever implemented a large chunk of any information system, you start to realize, that even though it might be comprised of many smaller components working together, ultimately, it had to enable some kind of overall process to function. And how, there were certain core components that you realize are more infrastructural in nature and are re-usable? For example, logging, security (AAA, authentication, authorization, access control), etc.? I was exposed to workflow systems when I first started working on case management systems (for example, legal cases). Case management is a scenario that includes, coordinating multiple child processes to build a "case", which is an instance of a process that is being executed. Think.. Case ID #123 is an instance of a distributed process, which results in a case file, but may have many independent and ancillary sub-processes, approvals, communications, notes, reviews, etc. that must come together to "complete" the case. You might diagram the flow of that legal process in a "flow chart". Business people love flowcharts right? The next logical step is to think of.. what if these flow charts could represent/become computable models (e.g. math/validity/correctness) and perhaps even a shell of executable code? You could construct an entire monolithic case management system, that handled all the work related to legal cases - by learning the business process, hard-coding the logic from that flow chart (classes with attributes and methods that define the full behavior of the system, interactions, etc. if we were doing OOP), and so on. If you did that, and you did that reasonably well, that system would certainly work for its designated scenario (legal cases). In the midst of doing that, you might have realized that, the IT ticketing system you bought for your organization, had a similar process (for example, case management in ITIL). You might notice.. startling similarities between the basic design of that system and the legal case management one.. to the point where you start asking.. is there a pattern here? Sure enough, there is one. The basis for that pattern is what some call workflow patterns - Professor Wil van der Aalst and Professor Arthur ter Hofstede being two influential thinkers in the area [3]. If we follow this thread, we find one helpful paper: "The Application of Petri Nets to Workflow Management" [4] ,which I think would be of interest. Then we start to realize that, some processes don't happen in a monolithic way. They need to be "consistent", but the underlying code and execution could be distributed in different services or different systems and yet our process needs to pull it altogether to carry out the work of the process. We might see that even though distributed, these processes and systems could be represented holistically. Petri nets help in this situation. I think one thing people might have missed when we got into this whole world of federated, independent teams, service-oriented architecture and now microservices, was that - ultimately, systematic behavior and processes must still function, and function well enough for organizations to fulfill their purpose. While self-emergent behaviors are entirely possible and arise all the time, in complex systems.. when you absolutely must make your system/process work, you need a way to engineer that and Petri nets give you a way to think about, model, and validate/reason about that. For a current very relevant example, consider microservices today. On their own, they provide little value - but when orchestrated and working together to compose a larger system, to enable human and machine processes to execute and thrive, it would be nice to have ways to think about and model those processes that live on top. Petri nets are one way to conceptualize and visualize those processes, where that conceptual model can be proven to be sound mathematically, and even turned in some cases directly into an executable framework within which to plug in your own code. That's what workflow systems often do, for example. Another relevant and recent case - event sourcing.. and event-driven mechanisms, and event handling, and the processing that goes along with it to essentially create a "directed process" - these are all directly related too. Also, there's a reason that data workflow automations such as Apache Spark or Airflow, for example, chose directed acyclic graphs (DAG) as models for complex, reliable, distributed process execution - and you can represent those as Petri nets too. What I always liked about Petri nets when I discovered them, was it gave me a way to link together strict state management, with process control, based in logical/provable theory - but also gave me a way to bridge between the "human" side of process ("flow charts") and the technical side of things. It gave me a framework to "plug in" my different systems, functions, services, objects and behaviors into something that coordinated complex process both in theory and in practice. I do not believe that one must implement monolithic process in code - as there is also emergent behavior - but, Petri nets and workflow management systems give you a way to think conceptually about how your system works.. and even potentially to build the "glue" that puts your system together, if you chose. By the way, one interesting thing I saw that came out of this work, was simulation software where you could use Petri nets to essentially "run" a process in a simulated way and see if there were any natural bottlenecks in the process that you could optimize in advance - before building any code at all. Process simulation [5] is another whole related rabbit hole to go down, but a fascinating one! [1] https://en.wikipedia.org/wiki/Workflow_management_system https://en.wikipedia.org/wiki/Workflow_management_system [2] https://github.com/meirwah/awesome-workflow-engines https://github.com/meirwah/awesome-workflow-engines [3] http://www.workflowpatterns.com/ http://www.workflowpatterns.com/ [4] https://www.semanticscholar.org/paper/The-Application-of-Petri-Nets-to-Workflow-Aalst/c79ac9d26d3246488fe4c9ebadffe3088ba16b83 https://www.semanticscholar.org/paper/The-Application-of-Pet... [5] https://en.wikipedia.org/wiki/Process_simulation https://en.wikipedia.org/wiki/Process_simulation
allenu 6y ago
State machines are incredibly useful and I use them all the time when I write UI code. There are a couple benefits that come to mind with respect to writing UI. First, it forces you think through all the potential "inputs" on your system, be they button presses from users or network request responses. You have to be explicit about what could have an effect on the system. Secondly, it makes your business logic easier to reason about because you essentially turn your UI code into a bunch of functional statements. All your transitions are just pure functions where the input is the previous state and some input, and the output is the new state. A lot of UI frameworks do it this way today, of course, but I picked up from reading about how Elm works. Whenever I write new UI from scratch, I always end up falling back on the state machine for guidance.
blargmaster42_8 6y ago
And this is news? Duuu
pupdogg 6y ago
I don’t mind being reminded every 2-3 years how great State Machines are. I was first introduced to the concept back in 2002 and my mind was blown. At that time, I was in my 20s...now I’m pushing past 40 and I’m starting to think my life is a state stuck in an event loop.

338 points by chmaynard 6y ago

zevv 6y ago

Encoding parser FSMs by hand can be tedious and error prone, there's some nice tools to help you with that; I'm a huge fan of Ragel: http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/

082349872349872 6y ago
I sometimes wonder if replacing the hand-coded FSMs of UI ravioli callbacks with a more parser-generator-like declaration would be a cleaner approach. (or maybe it's already been done? I haven't done UI code since last century...)

grandinj 6y ago

FSM are fun to write but horrible to modify especially if you’re not the one who wrote it.

amw-zero 6y ago
This is only true when considering a specific software design that implements the state machine. I'd say the most popular way to define a state machine in code is how Xstate does it: https://github.com/davidkpiano/xstate https://github.com/davidkpiano/xstate. You define your states, and then you define your inputs, and then you map out every single transition between states. This is probably the most inefficient way to design a state machine. There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible transitions (that's the definition of a completely connected graph). This means there's a large space of possible transitions relative to the number of states, which means there's a high probability that you will have to modify lots of transitions when modifying the state machine itself. In this article, this author is sharing several alternative designs for state machines, which don't look like they suffer from exactly the same problem. I'm most familiar with TLA+, where you describe a state machine simply with one logical predicate: the "Next" state relation. This is the most powerful way I've found to define state machines, and modifying one function to entirely change the behavior of the state machine is very easy in practice.
- teacpde 6y ago
  Mind elaborate on the next state predicate approach? By next, I imagine the focus is on transition rather than state; however, if you have multiple transitions arriving at the same state, what makes the next approach better? At the end of day, the state machine is the same regardless how it is implemented.
  - nitrogen 6y ago
    Edit: looks like they're talking about this: https://en.wikipedia.org/wiki/TLA%2B https://en.wikipedia.org/wiki/TLA%2B What I describe below is not related. ---- Not the OP, but here's a stab at it... In state machines commonly used in embedded C code, each state is represented either by a function or by a struct that contains a function pointer. The state machine calls the current state function in a loop or whenever relevant events happen, and that function returns a pointer to the next state, calculated based on inputs. If there is no state transition, then the function returns NULL or returns its own state.
  - amw-zero 6y ago
    See the above reply where I gave an example with both representations. Agreed, the machine representation is independent of the machine itself, it's the same mathematical object. So what I was talking about was how to represent using only a relation which describes the possible next states given the current one. This is the most common definition of a state machine, and for me, it's a cleaner representation since you avoid referring to each edge in the state graph explicitly.
- JadeNB 6y ago
  > There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible transitions (that's the definition of a completely connected graph). A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels. (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.)
lmilcin 6y ago
The problem with modifying FSM is if you start with modifying the code. This is wrong approach. The FSM is not a code but a model and the code is just an implementation of the model. What you want to do is to recreate the process of modelling (or modify existing model) and then recreate the code based on that. What I do is to have an implementation-agnostic model of the FSM that gets translated to code. That code is never modified, it only is called from external modules or calls external modules. There are some cases where I would just hardcode the FSM without the model. Those cases are when I do not expect the state machine to change because it follows from the fundamental description of the problem. For example, I might have some communication protocol and the state machine describes the state of that communication channel. If I do my job well the state machine maps 1:1 to the problem and will never need to change even as the rest of the application changes.
- teacpde 6y ago
  In your example, what happens if changes need to be made to the protocol? It is less frequent than business/application changes, but definitely can happen.
  - lmilcin 6y ago
    Good protocols are usually made in layers. You would typically want to have some state machine describing lower part of application protocol on which you build higher level of your application protocol, composed of specific functions. This way you can modify functionality without necessarily touching low level implementation. I can give an example. I have worked with credit card terminals and I have implemented entire application from scratch. There is a protocol to communicate between the terminal and the acquirer's system (ISO 8583). This protocol specifies a flow and format of messages. For example, if you send a transaction request, you will get a response. If you don't get a response you may or may not retry it, etc. If you send a transaction advice (ie. transaction has already happened) you must be retrying sending it until you get a response, but every retransmission after first must include a bit that says it is retransmission. If the request or advice has been sent and transaction was cancelled, you need to be sending cancellations until you get an acknowledgement. Now, all those messages have a huge amount of fields that change regularly as requirements change, but the basic flow of the protocol is fairly constant and has been constant for many years. I have implemented the protocol as a tree of state machines telling the application what to do based on events and I believe the code has not been touched in over 10 years even though the application was in constant development.
rualca 6y ago
> FSM are fun to write but horrible to modify especially if you’re not the one who wrote it. It really depends on the tooling you're using. For example, Qt's support for SCXML[¹] eliminates much of the pain of using state machines. [1] https://doc.qt.io/qt-5/qtscxml-overview.html https://doc.qt.io/qt-5/qtscxml-overview.html
jarirajari 6y ago
FSMs should be "written" visually, and they should have either hierarchical sub-states or some sort of a grouping scheme to keep complexity at a reasonable level. FSM examples are usually too simplified, and they don't show how to manage the complexities of a real, more complex state machine.
blunte 6y ago
It also depends on how you implement the state machine. If you're constrained by memory or performance (or playing golf), then you may end up with code like TFA. But if you're implementing in a typical app, you can obviously organize and write that is very understandable. I find the title of TFA misleading in its generality in comparison to the content of the article.
xondono 6y ago
The general issue is that FSM require a lot of naming, since you want to give every state a significant name, and naming is hard. When the states are clear enough, modifying FSMs is very nice.
- teacpde 6y ago
  That isn’t necessarily a state machine problem, a state is an abstraction that maps to part of your business semantics. Naming becomes hard when your state abstraction isn’t clear, which in turn is probably due to how business semantics are modeled. One the most important things in implementing state machines is to draw it up and make sure every state and transition has clear meanings before actually implementing them. There usually will be multiple iterations of modeling before arriving at a good design.
  - spacemanmatt 6y ago
    Nomenclature challenges are a negative code smell
masterofmisc 6y ago
Yeah, i find that using a library (like Stateless for C#) where it makes you "spell-out, upfront" each of the states and the transitions that are permitted from this state, it makes it easier to reason about the code.
threatofrain 6y ago
But for many this is just React with Redux, and the community buzz around that has been that teamwork is made easier. You’d have a state machine if the problem called for it anyway, but with redux everything is now explicit and teammates come prepared.

loopz 6y ago

Isn't FSM more like writing a program consisting only of GOTO's? I call this the "loopz-effect", where any single state may have effect in any other state of the program.

ajuc 6y ago
It's the opposite. In a FSM you have clearly defined states and all possible transitions between them. If you write the same code as normal imperative code that modifies some variables - to understand what it does you have to "run it" in your brain and reverse engineer the states and transitions yourself.
davemp 6y ago
It's more like having a switch statement inside of a loop. The variable you switch on is the next state and the case you're in is the current state.
retrac 6y ago
Strictly speaking, yes. But you should think of it as a formalized abstraction over that; a way to reason about something you can easily translate into a bunch of goto statements. It's just like how all if/then and function call constructs compile down to goto, as well. Some languages will offer more abstraction over this, but you can still do such constructs in assembly language if you want to by hand-holding the machine through every step. If you do find yourself writing assembly language (or C, for that matter!) then you should do just that; implement high-level constructs at the low level with a bunch of jump statements. The resulting code is verbose and superficially seems gnarly, but will also be far more scalable and robust. But there are compilers for a reason! There are some examples of automatic FSM to C compilers elsewhere in this thread. Some very high-level languages have embedded domain languages for FSM generation as well.
garethrowlands 6y ago
Yes. And not only that, but GOTOs are the normal recommended way of implementing an FSM.
- 6y ago

vesinisa 6y ago

Cool trickery, but should I ever encounter one of those hex tables in a program I am maintaining, I would certainly hope to see at least the state graph of the encoded machine as documentation.

deleted 6y ago

[deleted]

hyperpallium2 6y ago

Now you equivalently have two problems.

psykotic 6y ago

Some random fun things you can do with DFAs/NFAs: 1. From two machines you can build a single machine that corresponds to running them in lockstep/parallel. Most language classes are closed under unions but regular languages stand out by being closed under intersections, and that relies on this construction. You can't replicate this construction with pushdown automata to show that context-free languages are closed under intersection because the product automata would require two stacks. But in fact the intersection of a context-free language with a regular language is context-free via this construction. 2. You can run them backwards. Usually works best with NFAs since reversing a DFA can seriously inflate the state space. E.g. if you're trying to match a regular expression of the form '<re1> string <re2>' you can search for 'string' and then match re1 backward and re2 forward. Running machines backwards can also be used for computing capture groups after a match has been found since the fastest methods for matching don't let you compute capture groups on the fly. Decoupling the re1 and re2 machines also means you end up with two independent machines with smaller state spaces, which means smaller, cache-friendlier lookup tables. See the next item for a less conventional example of what you can do with small state spaces. 3. While DFA execution seems inherently serial, it can actually be parallelized very effectively if the state space is small enough, through speculative execution. Suppose you want to lex a string in parallel by chopping it in half. You don't know what state the DFA will be in when it reaches the halfway point, but you can process the second half for all possible states at that point. Then when both halves are finished you throw away all but one of the speculative answers for the second half based on the final state for the first half. This is extremely fast and practical with PSHUFB/TBL-like instructions if your state space is small enough, at most 16 states for PSHUFB. You can mux together multiple PSHUFBs to go beyond that limit but the cost increases substantially. (This is a parallel prefix algorithm when applied recursively. As far as I know the application to parallel lexing goes back to the Hillis-Steele paper on data-parallel algorithms from 1986.) 4. There's a critical optimization for the last algorithm which is sometimes applicable. A log file processor might have numerous internal states while processing a line, so you'd rather not speculate on all of them. Instead you can chop the file in half and from the second half seek forward to the next newline and start there. This avoids speculation entirely if there's a unique state following a newline character regardless of what state you were in before the newline.

6y ago

dqpb 6y ago

Every program is fundamentally states and state transitions. You can be explicit about it or not, but the states and transitions are there regardless.

amw-zero 6y ago
Absolutely. This is the definition of what computation is. Even in the lambda calculus, where everything is defined with pure functions, we build up state sequentially over time, based on previous values of the state. The fact that there’s no mutation under the hood is inconsequential.

ColinWright 6y ago

I'm reminded of a thing I wrote about seeing a state machine implemented in real life: https://www.solipsys.co.uk/new/StateMachineInRealLife.html?UA01HN https://www.solipsys.co.uk/new/StateMachineInRealLife.html?U...

skrebbel 6y ago
That was a delightful little read, thanks!
pardner 6y ago
Great little story!
deleted 6y ago
[deleted]

amw-zero 6y ago

These are some pretty cool examples, though a little too nitty gritty to communicate the practical importance of state machines. The truth is, state machines are so fundamental that programmers are not even aware that they are using them. Many, if not most, computer programs can be seen as state machines. In fact, programming can quite literally be seen as state machine creation and management. Programming languages are tools for creating complex state machines without having to manually wire them together. For example, take the following factorial function in Python: def factorial(n): result = 1 while n > 1: result *= n n -= 1 return result Here is a TLA+ spec for the same algorithm, along with the corresponding state diagram for calculating factorial(5): https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c632147 https://gist.github.com/amw-zero/c604f4dfd2d98e0d77fffe602c6.... This is a simple example, but the state diagram illustrates an important point that the while loop doesn't: the algorithm is completely linear, meaning it simply builds upon previous states. Even though there is branching in the code, there is no branching in the state diagram. Of course, we're not so lucky and most state spaces are not linear. Here's the spec and diagram for a user interface that I was building a while back: https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85cb93bd https://gist.github.com/amw-zero/4dc16cbf8e578d9be9e68b0a85c.... There was a subtle state-based bug where a user had to perform a special sequence of events to experience it. The code seemed simple, but looking at the state diagram directly showed what the bug was immediately. This was in a React app, and doing this exercise made me realize that React apps trivially translate to state machines as well. Whenever you call `setState` or the corresponding `setHookValue` function when using hooks, you are defining a state transition. The set of all state variables determines the full state space of the application, and bugs arise when we forget to consider that fact within some of our transition functions. Long story short, you don't need to use a state machine design pattern such as Xstate to actually have a state machine. In fact, unless you are doing some very weird things, your application most likely already is a state machine under it all, but that's only because a state machine is a very simple, general concept that has tons of applications.

arcbyte 6y ago
Yup. Basically all enterprise software is just state machine design. Any simple RESTFUL app with a database is just a state machine. Call one end point to create a resource, fetch it later from a second. Calling them out of order yields an error state. Super simple state machine. Of course we've reinvented this wheel so many times. Something like LISP is fun because you can get both the executable and (human AND machine) readable representations of a state machine out of the exact same source code. Thats still the future of programming.

sovietmudkipz 6y ago

It’s humbling to see a state machine implemented using coroutines. I program professionally since about 6 years ago but have only recently appreciated generators and coroutines. I’m working through learn.unity.com for fun and because, in my estimation, there is an upcoming boom in real time interfaces for real work. All the people playing video games have mastered skills that aren’t being taken full advantage of. Anyways, coroutines in Unity can be used to do interesting things over time while attached to the game loop. My point, despite my digression, is just how there are still basic/intermediate topics I have only been able to appreciate recently. Humbling.

sali0 6y ago
100% agreed on the increasing importance of video game interfaces. Nice to see I am not alone in that thought.
- sovietmudkipz 6y ago
  Every now and again as I play RTS (and other) games I imagine how the interface could be used in for business, engineering or marketing. There’s potential, IMO. The test (as I imagine it now) is making work fun enough that my 13 year old self would want to do work. At any rate, ideas are cheap. Prototypes and implementation are what matters. We’re speaking publically but I would like to know what you imagine about when you think about this topic?
  - jodrellblank 6y ago
    I sometimes wonder what it would take to visualise the state of a system in a game engine such as OpenTTD[1]. Then I remember the video of VMware's VMWorld 2017 event keynote speech[2] where they did such a poor example of VR - cubes representing virtual machines which you could virtually throw into the trash to delete them, or pick them up and move them to another host to use VMotion. It was a poor combination of low quality uninspired use of graphics and 3D space, and individually managing servers one at a time for things VMware DRS will do (load balancing moving of VMs between hosts) and things you don't want to be doing by hand (individually provisioning and removing servers). I'm not convinced that a game engine is capable of showing enough information compared to flat text, tables of numbers, graphs, and things made as web pages or documents where you can scroll down several pages. In a game engine, the things you aren't looking at end up far away, smaller, easier to miss. Text usually has to be bigger to be readable. How do you bring things to attention without just replicating a web browser showing a page of stats in a game engine? How do you make "work" possible without replicating a right click menu in-game, or a popup Quake style command line? How do you envisage an RTS game interface doing work - what kind of work, and how does the interface help with it? > "The test (as I imagine it now) is making work fun enough that my 13 year old self would want to do work." A game you have to play for 6+ hours continuously, cannot quit, cannot pause, cannot undo/retry, almost cannot die or lose, has no story, no end to get to, and is a repetitive grind? [1] Isometric world map full of moving parts, metrics and graphs https://linuxhint.com/wp-content/uploads/2020/01/OpenTTD.jpg https://linuxhint.com/wp-content/uploads/2020/01/OpenTTD.jpg [1] which has overlays for things like cargo pressure in two directions https://www.openttd.org/screenshots/1.4-cargodist.png https://www.openttd.org/screenshots/1.4-cargodist.png that could be displaying network link load, etc. [2] https://lukaswinnnet.files.wordpress.com/2017/09/vmworldeu2017_d1keynotepatalan.jpg https://lukaswinnnet.files.wordpress.com/2017/09/vmworldeu20... [2] https://i.ytimg.com/vi/EiKyR4X5kxs/maxresdefault.jpg https://i.ytimg.com/vi/EiKyR4X5kxs/maxresdefault.jpg

carapace 6y ago

FWIW, here's an example I wrote in Python "that imitates what “compiled” FSM code might look like in an “unrolled” form. Most FSM code uses a little driver loop and a table datastructure, the code below instead acts like JMP instructions (“jump”, or GOTO in higher-level-but-still-low-level languages) to hard-code the information in the table into a little patch of branches." https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html#drive-a-fsm https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expre... It's part of an (incomplete. slightly broken) notebook on Brzozowski’s derivatives of regular expressions.

ci5er 6y ago

A long time ago I used to auto gen http and smtp servers and message queues (similar to RabbitMQ) from very compact descriptions. My in-house I infrastructure build-out productivity went up ~30x, but all the downstream teams hated it.

strenholme 6y ago

I ended up using one in MaraDNS 2.0 to parse configuration files, since the C code for parsing MaraDNS 1.0 configurations files was a lot more error-prone and hard to maintain. The state machine’s grammar is embedded in the Deadwood (MaraDNS 2 recursor) binary. Here is a full explanation of the finite state machine, along with the actual embedded code: https://github.com/samboy/MaraDNS/blob/master/deadwood-github/doc/internals/MARARC.parser https://github.com/samboy/MaraDNS/blob/master/deadwood-githu...

sixdimensional 6y ago

No post on state machines would be complete without mention of the superset concept of Petri nets [1]. I have used Petri nets to build my own workflow engine previously. Building a workflow engine is one of those things... nearly every enterprise app has one, and normally you shouldn’t need to build one if you can source one... but it is an exercise that makes you a stronger engineer/developer too, deepening understanding of the patterns that lie beneath most systems. Back when I was building, openly available workflow engines, BPML, BPEL etc. were not really a thing yet, so it made a little more sense to be building one. [1] https://en.wikipedia.org/wiki/Petri_net https://en.wikipedia.org/wiki/Petri_net

mikewarot 6y ago
This is my first encounter with the Petri nets, and at first I thought they were just like state machines, in that you're only concerned with flow of control... boy was I wrong. Its going to take a while to fully grok, but it seems impressively powerful in what it can do. Thanks!
nudpiedo 6y ago
Do you have more information on how to build workflow systems, and why is it good to do so with Petri nets rather than abstract the processes with classes or whatever else? Any information is welcome
- sixdimensional 6y ago
  There are two components to your question - the practical side, "how do I build a workflow system?" and then, "why Petri nets?". If you really want to build a generic workflow engine, I think the way is to identify the pattern they follow and implement that. Build classes, attributes and methods that abstract away automating a process in a generic sense (e.g. turn workflow into one or more services) and then integrate those service(s) into your application as the glue that holds together complex processes. It's obviously harder than that one sentence, of course there are lots of nuances, but that's probably the simplest way I can think of to explain the high-level hand-wavy approach to doing this if you want to build it yourself, without going into all the details. If you understand the pattern, and would rather not build, but buy or obtain an open source workflow engine/management system, many exist [1][2]. Most enterprise applications (e.g. Oracle, SAP, Salesforce, etc. etc.) have such workflow tools built in already. Regarding the second part of your question, "why Petri nets?", well, one could argue that any system that automates a process in any way is a kind of workflow management system/engine or could be modelled as a "Petri net". I guess you could say, "why care about patterns in software engineering" then? The difference is, like many patterns, Petri nets give you a tried/tested technique for conceptualizing and modelling the system/process, validating its correctness, and in some cases, tools/engines that implement these concepts can even give you the executable framework for building too. You know, standing on the shoulders of giants and that kind of thing. Technically, Petri nets are a superset for modelling/designing/visualizing/validating what you can do in a workflow system. Also, to be clear, the concept of Petri nets is in every way compatible with/related to object oriented design, and even functional and procedural programming paradigms. Perhaps I can try to answer your question in this way.. by relating Petri nets to design patterns in software engineering (think, Gang of Four, Patterns of Enterprise Architecture, etc.). You know how, when you're developing software - over the years, you start to see patterns emerge? The best way to understand Petri nets and how they relate is to see what problem they solve in work you might have done yourself. If you have ever implemented a large chunk of any information system, you start to realize, that even though it might be comprised of many smaller components working together, ultimately, it had to enable some kind of overall process to function. And how, there were certain core components that you realize are more infrastructural in nature and are re-usable? For example, logging, security (AAA, authentication, authorization, access control), etc.? I was exposed to workflow systems when I first started working on case management systems (for example, legal cases). Case management is a scenario that includes, coordinating multiple child processes to build a "case", which is an instance of a process that is being executed. Think.. Case ID #123 is an instance of a distributed process, which results in a case file, but may have many independent and ancillary sub-processes, approvals, communications, notes, reviews, etc. that must come together to "complete" the case. You might diagram the flow of that legal process in a "flow chart". Business people love flowcharts right? The next logical step is to think of.. what if these flow charts could represent/become computable models (e.g. math/validity/correctness) and perhaps even a shell of executable code? You could construct an entire monolithic case management system, that handled all the work related to legal cases - by learning the business process, hard-coding the logic from that flow chart (classes with attributes and methods that define the full behavior of the system, interactions, etc. if we were doing OOP), and so on. If you did that, and you did that reasonably well, that system would certainly work for its designated scenario (legal cases). In the midst of doing that, you might have realized that, the IT ticketing system you bought for your organization, had a similar process (for example, case management in ITIL). You might notice.. startling similarities between the basic design of that system and the legal case management one.. to the point where you start asking.. is there a pattern here? Sure enough, there is one. The basis for that pattern is what some call workflow patterns - Professor Wil van der Aalst and Professor Arthur ter Hofstede being two influential thinkers in the area [3]. If we follow this thread, we find one helpful paper: "The Application of Petri Nets to Workflow Management" [4] ,which I think would be of interest. Then we start to realize that, some processes don't happen in a monolithic way. They need to be "consistent", but the underlying code and execution could be distributed in different services or different systems and yet our process needs to pull it altogether to carry out the work of the process. We might see that even though distributed, these processes and systems could be represented holistically. Petri nets help in this situation. I think one thing people might have missed when we got into this whole world of federated, independent teams, service-oriented architecture and now microservices, was that - ultimately, systematic behavior and processes must still function, and function well enough for organizations to fulfill their purpose. While self-emergent behaviors are entirely possible and arise all the time, in complex systems.. when you absolutely must make your system/process work, you need a way to engineer that and Petri nets give you a way to think about, model, and validate/reason about that. For a current very relevant example, consider microservices today. On their own, they provide little value - but when orchestrated and working together to compose a larger system, to enable human and machine processes to execute and thrive, it would be nice to have ways to think about and model those processes that live on top. Petri nets are one way to conceptualize and visualize those processes, where that conceptual model can be proven to be sound mathematically, and even turned in some cases directly into an executable framework within which to plug in your own code. That's what workflow systems often do, for example. Another relevant and recent case - event sourcing.. and event-driven mechanisms, and event handling, and the processing that goes along with it to essentially create a "directed process" - these are all directly related too. Also, there's a reason that data workflow automations such as Apache Spark or Airflow, for example, chose directed acyclic graphs (DAG) as models for complex, reliable, distributed process execution - and you can represent those as Petri nets too. What I always liked about Petri nets when I discovered them, was it gave me a way to link together strict state management, with process control, based in logical/provable theory - but also gave me a way to bridge between the "human" side of process ("flow charts") and the technical side of things. It gave me a framework to "plug in" my different systems, functions, services, objects and behaviors into something that coordinated complex process both in theory and in practice. I do not believe that one must implement monolithic process in code - as there is also emergent behavior - but, Petri nets and workflow management systems give you a way to think conceptually about how your system works.. and even potentially to build the "glue" that puts your system together, if you chose. By the way, one interesting thing I saw that came out of this work, was simulation software where you could use Petri nets to essentially "run" a process in a simulated way and see if there were any natural bottlenecks in the process that you could optimize in advance - before building any code at all. Process simulation [5] is another whole related rabbit hole to go down, but a fascinating one! [1] https://en.wikipedia.org/wiki/Workflow_management_system https://en.wikipedia.org/wiki/Workflow_management_system [2] https://github.com/meirwah/awesome-workflow-engines https://github.com/meirwah/awesome-workflow-engines [3] http://www.workflowpatterns.com/ http://www.workflowpatterns.com/ [4] https://www.semanticscholar.org/paper/The-Application-of-Petri-Nets-to-Workflow-Aalst/c79ac9d26d3246488fe4c9ebadffe3088ba16b83 https://www.semanticscholar.org/paper/The-Application-of-Pet... [5] https://en.wikipedia.org/wiki/Process_simulation https://en.wikipedia.org/wiki/Process_simulation

allenu 6y ago

State machines are incredibly useful and I use them all the time when I write UI code. There are a couple benefits that come to mind with respect to writing UI. First, it forces you think through all the potential "inputs" on your system, be they button presses from users or network request responses. You have to be explicit about what could have an effect on the system. Secondly, it makes your business logic easier to reason about because you essentially turn your UI code into a bunch of functional statements. All your transitions are just pure functions where the input is the previous state and some input, and the output is the new state. A lot of UI frameworks do it this way today, of course, but I picked up from reading about how Elm works. Whenever I write new UI from scratch, I always end up falling back on the state machine for guidance.

blargmaster42_8 6y ago

And this is news? Duuu

pupdogg 6y ago

I don’t mind being reminded every 2-3 years how great State Machines are. I was first introduced to the concept back in 2002 and my mind was blown. At that time, I was in my 20s...now I’m pushing past 40 and I’m starting to think my life is a state stuck in an event loop.