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.
The 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.
Coroutines 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.
I'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.
A 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.
While 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.
In the article he says "finite state machines", not merely "state machines". The distinction is not negligible. FSMs have important properties (and corresponding algorithms) that rely on the fact that their state spaces are finite.
The article's aim is said to be to clarify the meaning of that, but it still seems confusing: if it's rather informal, perhaps it is worth linking the mentioned examples that refer to this equivalence. Sounds like it makes sense in some context, but evidently it may be hard to make sense of it otherwise.
I propose Equivalence of state machines and everything that possibly happens in your computer, using any language, any framework, any stack of libraries, ...
To 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)
I 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.
I 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.
I 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.
It 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.
The 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?
Equivalence 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).
Another 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.
I 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...
The following are formally defined mathematical structures:
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.