3 ms·

I love state machines and every time I use one my workers think I invented it because they’ve never seen them before. The data for state machine in this articl

I love state machines and every time I use one my workers think I invented it because they’ve never seen them before. The data for state machine in this article might be best prepared by generating it from a program. That generator program doesn’t need to care (too much) about performance since it is run during the build process. I like the idea of doing a lot of work now to save time in the future.

pletnes 2y ago
Do you have any accessible references on state machines? I’ve just read about them a bit but never coded one in a project. Seems like a useful concept for testable, reliable code.
- GrantMoyer 2y ago
  The video Finite State Machines explained by Abelardo Pardo[1] seems like a good introduction (I'm not familiar with the author; I just searched Finite State machine on youtube and found the first result which wasn't a jumbled mess of abstract or misused jargon). It may seem simple, but that's truely all there is to finite state machines, a set of finite states and a set of events which cause transitions between states. Their specific applications to various domains is a much larger topic, but with a basic understanding, any application should be clear whenever it comes up. There's no one way to implement a state machine, and you've probably used them all the time, even if you haven't thought about them formally. For example, a simple but common 2-state machine takes the form: running = true while running: … if <some condition>: running = false [1]: https://www.youtube.com/watch?v=hJIST1cEf6A https://www.youtube.com/watch?v=hJIST1cEf6A
  - d0mine 2y ago
    It could be written as: while True: ... if <exit condition>: break
- trealira 2y ago
  A finite state machine has a set of input symbols, a set of states, and a transition function, which maps the current state and current input to the next state (and, when programming it, it doesn't have to be a literal function; for example, it could be a 2D array). It also has a start state, and a set of accept states. It's also common for state machines to have some sort of output; otherwise, all an FSM can do is recognize whether an input string is "good." So, there's also an output function, so that the FSM actually does something while processing the input string. There are two types of FSMs: a Mealy Machine, and a Moore machine. In a Mealy machine, the output function maps the current state and the current input to an output; so, one state could be associated with multiple outputs. In a Moore machine, the output is purely a function of the current state, no matter the input. Usually, a Moore machine has more states than the equivalent Mealy machine. In practice, Moore machines are a lot rarer than Mealy machines. You can model FSMs in a variety of ways. You could use the state pattern [0]. You could have a table-based state machine; examples in C here [1] [2]. It's also common to model them using a loop and a switch statement with integers to represent the current state - or just use "goto" to go to the next state, if it's available in your language. Also, this is tangential, but something nice about coroutines is that they save can you from writing an explicit state machine, as the state is implicit in your code. One example of this is how it's easier to write iterators as coroutines that yield results as they run, rather than as structures that update themselves based on their current state, transition to the next state, and yield a result. So far, what I've covered is basically a deterministic finite automaton (DFA). There are also non-deterministic finite automata (NDFAs), which are used to implement regular expressions (at least when regular expressions aren't extended to require more powerful recognizers) [3], as well as pushdown automata (PDAs), which are basically finite automata with a stack, and can parse e.g. programming languages. Finally, there are Turing machines. For theory on that, I'd recommend reading Sipser's Introduction to the Theory of Computation. If you look up the book on Google, it's not difficult to find a PDF of it. [0]: https://refactoring.guru/design-patterns/state https://refactoring.guru/design-patterns/state [1]: https://nullprogram.com/blog/2020/12/31 https://nullprogram.com/blog/2020/12/31 [2]: https://ideone.com/94U6aJ https://ideone.com/94U6aJ (this one removes C-style comments from source code - I didn't make it) [3]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
SoftTalker 2y ago
I agree, and I raised an eyebrow at the "The algorithm is known as an "asynchronous state-machine parser". It's a technique for parsing that you don't learn in college." I certainly learned about state machines in college. Not sure we ever studied this particular algorithm but the concept was definitely covered. And I also agree that when you are dealing with a known, finite set of values, pre-computing lookup or index tables for techniques like this can be a big win.
FroshKiller 2y ago
I'm a little surprised to hear this. Writing a state machine to simulate an alarm clock used to be an introductory project for first-year computer science undergraduates.

pletnes 2y ago

Do you have any accessible references on state machines? I’ve just read about them a bit but never coded one in a project. Seems like a useful concept for testable, reliable code.

GrantMoyer 2y ago
The video Finite State Machines explained by Abelardo Pardo[1] seems like a good introduction (I'm not familiar with the author; I just searched Finite State machine on youtube and found the first result which wasn't a jumbled mess of abstract or misused jargon). It may seem simple, but that's truely all there is to finite state machines, a set of finite states and a set of events which cause transitions between states. Their specific applications to various domains is a much larger topic, but with a basic understanding, any application should be clear whenever it comes up. There's no one way to implement a state machine, and you've probably used them all the time, even if you haven't thought about them formally. For example, a simple but common 2-state machine takes the form: running = true while running: … if <some condition>: running = false [1]: https://www.youtube.com/watch?v=hJIST1cEf6A https://www.youtube.com/watch?v=hJIST1cEf6A
- d0mine 2y ago
  It could be written as: while True: ... if <exit condition>: break
trealira 2y ago
A finite state machine has a set of input symbols, a set of states, and a transition function, which maps the current state and current input to the next state (and, when programming it, it doesn't have to be a literal function; for example, it could be a 2D array). It also has a start state, and a set of accept states. It's also common for state machines to have some sort of output; otherwise, all an FSM can do is recognize whether an input string is "good." So, there's also an output function, so that the FSM actually does something while processing the input string. There are two types of FSMs: a Mealy Machine, and a Moore machine. In a Mealy machine, the output function maps the current state and the current input to an output; so, one state could be associated with multiple outputs. In a Moore machine, the output is purely a function of the current state, no matter the input. Usually, a Moore machine has more states than the equivalent Mealy machine. In practice, Moore machines are a lot rarer than Mealy machines. You can model FSMs in a variety of ways. You could use the state pattern [0]. You could have a table-based state machine; examples in C here [1] [2]. It's also common to model them using a loop and a switch statement with integers to represent the current state - or just use "goto" to go to the next state, if it's available in your language. Also, this is tangential, but something nice about coroutines is that they save can you from writing an explicit state machine, as the state is implicit in your code. One example of this is how it's easier to write iterators as coroutines that yield results as they run, rather than as structures that update themselves based on their current state, transition to the next state, and yield a result. So far, what I've covered is basically a deterministic finite automaton (DFA). There are also non-deterministic finite automata (NDFAs), which are used to implement regular expressions (at least when regular expressions aren't extended to require more powerful recognizers) [3], as well as pushdown automata (PDAs), which are basically finite automata with a stack, and can parse e.g. programming languages. Finally, there are Turing machines. For theory on that, I'd recommend reading Sipser's Introduction to the Theory of Computation. If you look up the book on Google, it's not difficult to find a PDF of it. [0]: https://refactoring.guru/design-patterns/state https://refactoring.guru/design-patterns/state [1]: https://nullprogram.com/blog/2020/12/31 https://nullprogram.com/blog/2020/12/31 [2]: https://ideone.com/94U6aJ https://ideone.com/94U6aJ (this one removes C-style comments from source code - I didn't make it) [3]: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

SoftTalker 2y ago

I agree, and I raised an eyebrow at the "The algorithm is known as an "asynchronous state-machine parser". It's a technique for parsing that you don't learn in college." I certainly learned about state machines in college. Not sure we ever studied this particular algorithm but the concept was definitely covered. And I also agree that when you are dealing with a known, finite set of values, pre-computing lookup or index tables for techniques like this can be a big win.

FroshKiller 2y ago

I'm a little surprised to hear this. Writing a state machine to simulate an alarm clock used to be an introductory project for first-year computer science undergraduates.