7 ms·
Equivalence of State Machines and Coroutines
- chadcmulligan 8y agoCo-routines as an alternative to state machines https://news.ycombinator.com/item?id=793140 https://news.ycombinator.com/item?id=793140
- solidsnack9000 8y agoIt's as if millions of voices of state machine libraries suddenly cried out in terror and were suddenly silenced.
- DarkWiiPlayer 8y agoRIP Alderaan
- Skunkleton 8y agoFurther evidence: coroutines are often implemented as state machines under the hood.
- JadeNB 8y ago> Further evidence: coroutines are often implemented as state machines under the hood. Of course you just said "further evidence", not "proof", but naturally this just proves simulability, not bisimulability.
- coldtea 8y agoWell, state machines can also be implemented as coroutines, so...
- ectospheno 8y agoI enjoy when in discussions like this the person saying the things can’t simulate each other proceed to prove their point by writing two computer programs and running them on the same physical machine...
- Skunkleton 8y agoThe CPU is a state machine. Therefore all software is a state machine. Take that functional programming.
- coldtea 8y agoThere's nothing in FP that's against state machines. Even if we say that FP = purity, you can have state machines with immutable state.
- jpochtar 8y agoThe Program Counter (PC) register is some of our most important state! Ever since Gotos were considered harmful, we've forgotten that it's just another register.
- jonahx 8y agoThis explanation is so succinct and natural you might miss how well done it is.
- RossBencina 8y agoEquivalence is a symmetric relation. The article presents an example of a goroutine implementing an FSM. Even if you thought a single example constituted a proof, to show equivalence you'd also need to show how an arbitrary coroutine can be implemented using an FSM; and as others have observed, the ability to dynamically allocate memory distinguishes a coroutine from an FSM. That said, in practice, often we don't program with FSMs, we program with structures that are FSMs augmented with additional state such as counters and storage (collections/stacks/queues).
- millstone 8y agoThe article casts this as a coroutine, but it's straightforward to translate this Go code into any language that supports multiple threads. Is this actually a coroutine?
- solidsnack9000 8y agoWith coroutines, only one routine is executing at a time. If you simulate that with threads (using locks) it is also coroutines.
- omgtehlion 8y agoThis is what c# compiler does for async/await behind the scenes. And I bet every other compiler out there does too. In the end (in machine code) you will have pretty much your original state machine.
- GolDDranks 8y agoThis doesn't ring 100% true to me; goroutines have stack so they can't be fully equal to (finite) state machines!
- jonsen 8y agoIt depends on perspective. Having a finite stack is just a way of organizing a state machine. In practice all computer software is state machines. A computer is nothing but a big state machine. A very big finite state machine. Running some software on a computer is just commanding that state machine. In computing theory we have som ideal abstractions, such as nondeterministic finite state machines, and others which are not state machines. These abstractions are just tools we use to make the design of our very big state machine programs manageable. The point of the article is that the interoperation of two or more coroutines can be modeled as an abstract state machine.
- mehrdadn 8y agoCoroutines are potentially-infinite state machines, not finite state machines. While their instruction pointers belong in a finite state space, their usable memory space is infinite.
- defanor 8y agoI've spent some time thinking how to put it, but it indeed doesn't seem like equivalence -- perhaps more of an inclusion. Or coroutines should be limited to stateless ones, but then a similar statement could be made about regular subroutines. Though not even sure what would be a proper way to compare state machines to coroutines, maybe some context is missing.
- deleted 8y ago[deleted]
- RossBencina 8y agoIn addition to state, coroutines can also have side effects. So you kinda need effectful, stateful "finite" state machines to get started.
- raxxorrax 8y agoWhat is the difference between a side effect and a state transition?
- RossBencina 8y agoA side effect would do something external to the state machine, such as transmit something on the network, or perform disk i/o. Or it might emit an event that is received by another concurrent state machine.
- rumcajz 8y agoWhile that's true in theoretical sense, what we call "state machines" in the real world do have additional state. For example, TCP state machine has CWND. The same way, coroutines allow for additional state.
- edem 8y agoInteresting coincidence that Kotlin coroutines use state machines internally: https://youtu.be/YrrUCSi72E8?t=432 https://youtu.be/YrrUCSi72E8?t=432
- discreteevent 8y ago"almost every object that computes is naturally viewed as a state machine" - Leslie Lamport https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf
- RossBencina 8y agoOne thing that bugs me is this: The following are formally defined mathematical structures: - Moore Machine - Mealy Machine - Deterministic Finite Automata There are also (multiple) formal semantics for Harel State Charts. But there is no single precise formal definition of what a coroutine is. And when we talk about programming with (finite) state machines, we are often not strictly referring to any of the above formalisms. To claim that two ill-defined notions are equivalent is not particularly meaningful.
- entity345 8y agoCoroutines are software constructs like subroutines or threads. They are not more related to state machines than those constructs are.
- kitd 8y agoAnother interesting problem is how one can simulate a general state machine, eg a Petri net that aggregates states, using coroutines. I suspect states would need to be defined and handled explicitly.
- emsy 8y agoI probably wouldn't use coroutines as state machines, because most state machine DSLs are very easy to read. I'm curious though, if I could ditch state machines altogether if the coroutine equivalent was more readable. Most state machine libs also allow things like on-enter/on-exit state callbacks, which would look awkward using only coroutines.
- xntrk 8y agoWhat are you using state machines for now? just wondering. I have been looking into JS state machines (mostly xstate) in order to model UIs better.
- emsy 8y agoI recently programmed an application for a test bench of electric motors, where I could basically translate the flow chart I was given by the engineers to a state machine. Out of the state machine I handled all concerns like UI, hardware controlling and persistence via events.
- RossBencina 8y agoI agree. I also would prefer not to use state machines if I wanted coroutines (i.e. algorithmic code with traditional control structures interspersed with coroutine yields). Ideally you need both.
- eliben 8y agoOn the same topic, from 2009: https://eli.thegreenplace.net/2009/08/29/co-routines-as-an-alternative-to-state-machines https://eli.thegreenplace.net/2009/08/29/co-routines-as-an-a...
- kazinator 8y agoI propose Equivalence of state machines and everything that possibly happens in your computer, using any language, any framework, any stack of libraries, ...
- meuk 8y agoTo show equivalence, you should show that any state machine can be implemented as a coroutine and vice versa. The author here implements one example with coroutines and with a state machine, which shows exactly nothing. (As a metaphore, it's like saying that being green and being a frog is equivalent, because there exists a green frog)