Equivalence of State Machines and Coroutines

http://250bpm.com/blog:141

by rumcajz • 8 years ago

84 37 8 years ago

250bpm.com

solidsnack90002• 8 years ago

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

DarkWiiPlayer• 8 years ago

RIP Alderaan

Skunkleton2• 8 years ago

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

JadeNB• 8 years 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.

coldtea2• 8 years ago

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

jpochtar• 8 years ago

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.

jonahx• 8 years ago

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

RossBencina5• 8 years ago

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

millstone• 8 years ago

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?

solidsnack90002• 8 years ago

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

omgtehlion• 8 years ago

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.

GolDDranks• 8 years ago

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

jonsen• 8 years ago

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.

mehrdadn2• 8 years ago

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.

defanor2• 8 years ago

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.

RossBencina5• 8 years ago

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

rumcajz• 8 years ago

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.

mehrdadn2• 8 years ago

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.

defanor2• 8 years ago

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.

edem• 8 years ago

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

discreteevent• 8 years ago

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

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

RossBencina5• 8 years ago

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.

entity345• 8 years ago

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

kitd• 8 years ago

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.

chadcmulligan• 8 years ago

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

emsy2• 8 years ago

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.

xntrk• 8 years ago

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.

emsy2• 8 years ago

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.

RossBencina5• 8 years ago

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.

eliben• 8 years ago

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

kazinator• 8 years ago

I propose Equivalence of state machines and everything that possibly happens in your computer, using any language, any framework, any stack of libraries, ...

meuk• 8 years ago

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)

Equivalence of State Machines and Coroutines

Related Stories