Equivalence of State Machines and Coroutines | Hacker News Reader

Equivalence of State Machines and Coroutines

250bpm.com

84 pointsrumcajz37 comments

One 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.

Coroutines are software constructs like subroutines or threads. They are not more related to state machines than those constructs are.

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.

In addition to state, coroutines can also have side effects. So you kinda need effectful, stateful "finite" state machines to get started.

What is the difference between a side effect and a state transition?

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.

"almost every object that computes is naturally viewed as a state machine" - Leslie Lamport

https://lamport.azurewebsites.net/pubs/state-machine.pdf

It's as if millions of voices of state machine libraries suddenly cried out in terror and were suddenly silenced.

RIP Alderaan

On the same topic, from 2009: https://eli.thegreenplace.net/2009/08/29/co-routines-as-an-a...

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.

What 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.

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.

This doesn't ring 100% true to me; goroutines have stack so they can't be fully equal to (finite) state machines!

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.

Co-routines as an alternative to state machines https://news.ycombinator.com/item?id=793140

This 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.

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?

With coroutines, only one routine is executing at a time. If you simulate that with threads (using locks) it is also coroutines.

This explanation is so succinct and natural you might miss how well done it is.

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).

Interesting coincidence that Kotlin coroutines use state machines internally: https://youtu.be/YrrUCSi72E8?t=432

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.

Further evidence: coroutines are often implemented as state machines under the hood.

> 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.

Well, state machines can also be implemented as coroutines, so...

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 CPU is a state machine. Therefore all software is a state machine. Take that functional programming.

There's nothing in FP that's against state machines.

Even if we say that FP = purity, you can have state machines with immutable state.

Reply on news.ycombinator.com