3 ms·
This does reflect very sadly on schools, and shows up when trying to explain things to programmers used to conventional languages, especially if you're trying t
by Yttrill 14y ago
This does reflect very sadly on schools, and shows up when trying to explain things to programmers used to conventional languages, especially if you're trying to explain why C is fundamentally broken.
Roughly there are three fundamental control transfer operations: conditional jumps, subroutine calls, and coroutine calls. A subroutine is a slave, the caller is a master. With coroutines, the caller and callee are peers.
Coroutine calling is more fundamental and easier to program, but it isn't available in C.
The theory is about continuations. A continuation is just "the rest of the program". You can think of it as the program counter (PC). Subroutine calling works by passing a continuation to a routine, when the routine is finished it invokes the continuation. This is done by pushing the program counter on the stack, and the subroutine popping it with a return statement.
Coroutines work by exchange of control. When you call a coroutine you give it your current continuation to call when its ready. But also you do not call the coroutine at the beginning. You call it where it last left off: at its last continuation point.
A set of coroutines are usually called fibres. They represent interleaving of control. You can emulate them with pre-emptive threads and locks, but coroutines are synchronous and non-premptive.
Felix and Go both make heavy use of coroutines (called fthreads and goroutines). Iterators as in Python are a special case.
In general on today's badly designed CPU's you have to think of coroutines as requiring stack swapping. Threads do this which is why you can emulate coroutines with threads.
By far the most well known coroutine scheduler is .. the Operating System. Its basically a coroutine of applications. This is why you can read and write to files: the real world is event driven but callbacks are impossible to program with. So the operating control inverts the events by stack swapping so your application can be written as a master.
You think you're calling the OS, and the OS thinks its calling you. You're both masters. That's coroutines.
Python (and Felix) both have yield, but that's a special case. In general the model is reading and writing channels: yielding is just writing the "sole" channel and getting a function result is just reading it. A channel is basically a "place to swap stacks".
- csense 14y ago> Coroutine calling is more fundamental and easier to program Citation needed. For coroutines, each coroutine needs its own stack. That means you have to have a dynamic memory system baked into the language. And maybe garbage collection too. > on today's badly designed CPU's you have to think of coroutines as requiring stack swapping I can't think of an implementation of yield (let alone general coroutines) that doesn't require a separate stack for each coroutine. I admit that I haven't learned very many of the stranger forgotten architectures that are out there, so I might be blinded by the limitations of a somewhat conventional experience. But I'm also thinking it might even be provable that each coroutine needs its own stack: Think of a program that has m generator functions, where f_1 calls f_2, f_2 calls f_3, ..., f_{m-1} calls f_m. Each of these subroutines creates n copies of its next-level generator, and steps those generators and yields to the parent unpredictably (for example, depending on input from a user-supplied file). It seems like if m and n are large enough, you'll have no choice but to resort to swapping stacks.
- eru 14y ago> For coroutines, each coroutine needs its own stack. That means you have to have a dynamic memory system baked into the language. And maybe garbage collection too. Why? Just statically give every co-routine it's own stack.
- csense 14y agoThe number of coroutine invocations, and the order in which they're cleaned up, could depend on user input. The former could be unbounded. More formally, I'm pretty sure you can write a program that always halts, but for every pair of large numbers N, K > 0, there are at least K different input values that result in (1) at least N coroutine invocations being simultaneously active, and (2) for each of those K different input values, those invocations finish in a different order.