[OT] Stackless fibers/coroutines

[Nick Sabalausky via Digitalmars-d]

On 09/24/2016 10:20 AM, Jacob Carlborg wrote:
> On 2016-09-24 15:12, Nick Sabalausky wrote:
>
>> +1.
>>
>> Although I haven't given it too much thought, I'd bet that could also be
>> used to provide, in library, my #1 most wanted missing D feature: Input
>> ranges (maybe even forward, too) written as stackless coroutines
>> (C#-style, heck, even C can do it in lib). So we could write input
>> ranges without turning the whole freaking algorithm completely
>> inside-out, or requiring the overhead of a full fiber.
>
> Yeah, I've been thinking of that as well. It should be fairly easy to
> implement something like Protothreads [1]. Not sure about stackless
> coroutines though, if they need to save the state of the function on
> suspension and restore the state when the function resumes.
>
> [1] http://dunkels.com/adam/pt/
>

"Protothreads"! I've been trying to remember the name of that lib and 
couldn't find it. I used that the last time I was working on a C/C++ 
thing, and it was very helpful.

AIUI though, that IS stackless coroutines, same thing AFAIK. The 
Protothreads lib refers to itself as "extremely lightweight stackless 
threads". And the way it's used is definitely what I'd consider a coroutine.

Protothreads solves the problem of saving/restoring state by doing two 
things:

1. You put all your locals (at least, any that need preserved across 
save/restore) in a struct, together with the appropriate jump label to 
be jumped to upon resume. Then when yielding, this struct gets passed 
out, and when resuming you pass it back in.

2. Yielding can ONLY be done by a coroutine, itself, NOT by any 
functions it calls (unless those are also coroutines and return some 
flag signaling the first coroutine to also yield). This is the one big 
key that makes stackless fibers/coroutines/etc possible in the first place.

My understanding is that C#'s coroutines, under the hood, work the same 
way as C's Protothreads library:

First, only C#'s coroutines can yield, not regular functions called by a 
coroutine. Then, the C# compiler "lowers" the coroutine function into a 
big switch statement, with the current state (values of the locals and 
the hidden "case" target to jump to) passed in and out as a hidden argument.

Since the compiler does the conversion, it can safely deal with 
saving/restoring the locals, and crossing scope boundaries and such 
(which C is just plain not concerned with at all).

So really, C#'s coroutines (AIUI) are just like C's Protothreads, but 
with nicer sugar.

But about implementing it in D:

I'm not so sure that's realistic right now. I mean, I think something 
like it is *technically* possible, and I would have done so myself long 
ago, except that I see two major problems:

1. You'd have to write the entire coroutine as a string, which would 
really mess with IDE/editor features and the compiler's error reporting. 
And I'm not sure I see any way to do this in D without writing the 
coroutine as a string (or, you know, using AST macros ;) ).

2. Compared to C, D has much stricter rules about where a switch's 
"case" labels can do. Ie, they can't really cross scope boundaries. So 
*all* the coroutine's "yield" statements would have to be within the 
same scope *and* at the same nesting-level (or at the very least, 
there'd be some big annoying restrictions). Otherwise, when it gets 
converted to a "case:", the resulting code would be invalid.

We could use "goto" instead of case, but that has many of the same 
issues, plus (IIRC) the issue of goto-ing past a variable declaration 
(which IIRC is disallowed, or maybe had some other problem).

I'm not sure how you could get around problem #1 without AST macros or 
just implementing the whole feature in the compiler, like C#.

Even if you solved that, the only way I see to get around #2 would 
require very careful manual adjustments to the coroutine via a CTFE D 
AST, which (for right now) would be all kinds of bother, and at that 
point you may as well just add the feature built-into the compiler (like 
C#) because it would be more efficient than CTFE, AND it would solve 
problem #1.