www.digitalmars.com         C & C++   DMDScript  

digitalmars.dip.development - First Draft: Coroutines

reply Richard (Rikki) Andrew Cattermole <richard cattermole.co.nz> writes:
Coroutines is a stack machine transformed representation for a 
function. It enables storing the state of a function externally 
to the stack to allow for high throughput event handling.

Latest: 
https://gist.github.com/rikkimax/fe2578e1dfbf66346201fd191db4bdd4

Current: 
https://gist.github.com/rikkimax/fe2578e1dfbf66346201fd191db4bdd4/0bb4442c092e061d520c35a43278f0819666f26f

It uses the `` async`` attribute to transform into a type that is 
used to describe the function, with the help of implicit 
conversions using knowable library types and a hook for 
construction to produce a library object that represents the 
function.

There is support for such UDA's as `` Route`` to make the 
function automatically marked as `` async`` to prevent explicit 
annotation requirement.

An example usage of one:

```d
void clientCO(Socket socket)  async {
	writeln("Connection has been made");

	socket.write("GET / HTTP/1.1\r\n");
	socket.write("Accept-Encoding: identity\r\n");
	socket.write("\r\n");

	while(Future!string readLine = socket.readUntil("\n")) {
		if (!readLine.isComplete) {
			writeln("Not alive and did not get a result");
			return;
		}
		
		string result = readLine.result;
		writeln(result);

		if (result == "</html>") {
			writeln("Saw end of expected input");
			return;
		}
	}
}
```
Aug 04
next sibling parent reply ryuukk_ <ryuukk.dev gmail.com> writes:
On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 Coroutines is a stack machine transformed representation for a 
 function. It enables storing the state of a function externally 
 to the stack to allow for high throughput event handling.

 Latest: 
 https://gist.github.com/rikkimax/fe2578e1dfbf66346201fd191db4bdd4

 Current: 
 https://gist.github.com/rikkimax/fe2578e1dfbf66346201fd191db4bdd4/0bb4442c092e061d520c35a43278f0819666f26f

 It uses the `` async`` attribute to transform into a type that 
 is used to describe the function, with the help of implicit 
 conversions using knowable library types and a hook for 
 construction to produce a library object that represents the 
 function.

 There is support for such UDA's as `` Route`` to make the 
 function automatically marked as `` async`` to prevent explicit 
 annotation requirement.

 An example usage of one:

 ```d
 void clientCO(Socket socket)  async {
 	writeln("Connection has been made");

 	socket.write("GET / HTTP/1.1\r\n");
 	socket.write("Accept-Encoding: identity\r\n");
 	socket.write("\r\n");

 	while(Future!string readLine = socket.readUntil("\n")) {
 		if (!readLine.isComplete) {
 			writeln("Not alive and did not get a result");
 			return;
 		}
 		
 		string result = readLine.result;
 		writeln(result);

 		if (result == "</html>") {
 			writeln("Saw end of expected input");
 			return;
 		}
 	}
 }
 ```



the proof

There should be no distinction between an async/sync function
Aug 05
parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 05/08/2024 10:17 PM, ryuukk_ wrote:


 
 There should be no distinction between an async/sync function


I started with the position that the compiler should be able to do it 
completely transparently to the user. It failed. Too many holes in it. 
It was not implementable at all.

This is why I had to remove synchronous function support out of the DIP, 
because it would do the wrong thing guaranteed.

Also the ``Future`` type in the DIP is a library type, the DIP itself 
does not introduce it. But it is something I know works, as I have it 
implemented already.
Aug 05
parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Monday, 5 August 2024 at 10:30:24 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 On 05/08/2024 10:17 PM, ryuukk_ wrote:


 is the proof
 
 There should be no distinction between an async/sync function


 I started with the position that the compiler should be able to 
 do it completely transparently to the user. It failed. Too many 
 holes in it. It was not implementable at all.


The only way it can work is to make all functions async and have 
the compiler do an optimisation pass to turn those it can proof 
into sync ones.

It is similar to the approach Go takes in that it makes calling C 
functions more difficult though.
Aug 05
parent "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 06/08/2024 6:11 AM, Sebastiaan Koppe wrote:

 It is similar to the approach Go takes in that it makes calling C 
 functions more difficult though.


Go goes a bit further than that, their goroutines are effectively in 
their own calling convention.

We cannot replicate what they did, as we have strict requirements on 
interactivity to C. I did check with Walter and he confirmed it wasn't 
acceptable from his stance either.
Aug 05
prev sibling next sibling parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 Coroutines is a stack machine transformed representation for a 
 function. It enables storing the state of a function externally 
 to the stack to allow for high throughput event handling.


Thank you for spearheading this. Having coroutines in the 
language would be a big step forward, and hopefully pave the way 
for more non-blocking programming in D.

There are a few points I would like to bring up early though.

- I see no mention of C++'s coroutines. I think it would be good 
to learn from their design and implementation.

- As you might know I am a big proponent of C++'s 
Senders/Receivers (a.k.a. P2300). One awesome integration they 
have is that Senders can be awaited by coroutines, and coroutines 
can await Senders. This allows for users to pick their 
preference, e.g. use convenient coroutines but suffer some 
allocation costs, and use Senders for more performant sections if 
need be. See
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2300r7.html#design-aw
itables-are-senders and
https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/

- I don't understand the choice for ` async`. Sometimes 
resembling the word "coroutine" would be better in my opinion.

- In `while(Future!string readLine = socket.readUntil("\n"))` I 
suspect it to do an explicit await. How does that work?

- I find the use of `Future` a bit confusing. Futures generally 
carry too much synchronisation overhead with them and I doubt 
coroutines need a full Future implementation anyway. Perhaps call 
it a Task like they do in C++?

- The use of ` isasync` is a bit too cute for me. It also hides 
the fact sometime is a coroutine.

- Instead of allowing a coroutine in a function that is not a 
coroutine itself - and injecting a blocking call - I would 
require explicit call to evaluate the coroutine instead. No magic.

- Can coroutines be continued on another thread, assuming 
sequential consistency?
Aug 05
parent reply "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 06/08/2024 3:50 AM, Sebastiaan Koppe wrote:

 On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
 Cattermole wrote:

 Coroutines is a stack machine transformed representation for a 
 function. It enables storing the state of a function externally to the 
 stack to allow for high throughput event handling.


 
 Thank you for spearheading this. Having coroutines in the language would 
 be a big step forward, and hopefully pave the way for more non-blocking 
 programming in D.
 
 There are a few points I would like to bring up early though.
 
 - I see no mention of C++'s coroutines. I think it would be good to 
 learn from their design and implementation.

 - As you might know I am a big proponent of C++'s Senders/Receivers 
 (a.k.a. P2300). One awesome integration they have is that Senders can be 
 awaited by coroutines, and coroutines can await Senders. This allows for 
 users to pick their preference, e.g. use convenient coroutines but 
 suffer some allocation costs, and use Senders for more performant 
 sections if need be. See
 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2300r7.html#design-aw
itables-are-senders and
https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/


My conclusion about P2300 is that it is all library code. This DIP would 
allow you to implement it. Although some language integration may be 
missing as the data processing use case is not covered here (I have no 
experience with it in context and so currently I am not the best person 
for it).


 - I don't understand the choice for ` async`. Sometimes resembling the 
 word "coroutine" would be better in my opinion.


It was `` co`` for a long time.

I had a number of people request ``async`` instead.


 - In `while(Future!string readLine = socket.readUntil("\n"))` I suspect 
 it to do an explicit await. How does that work?


When a coroutine is acquired, it'll yield automatically, it is implicit.

We may want to support explicit yielding via a multiple return.

I should probably add this, however I'm divided upon it currently. Need 
time to think about it some more.


 - I find the use of `Future` a bit confusing. Futures generally carry 
 too much synchronisation overhead with them and I doubt coroutines need 
 a full Future implementation anyway. Perhaps call it a Task like they do 
 in C++?


This DIP does not propose library code. You are free to write whatever 
library code you want and have it construct itself from the language 
representation of a coroutine.

This is a key design goal as there is a good chance we'll want different 
solutions for different tasks. Being stuck with only one solution (like 
how new'ing a class calls a specific hook) will only lead to people 
being unhappy.

Note: we can introduce hooking into a specific library with a new 
expression, however that is not present in this DIP as we have enough to 
get on with with just this DIP.


 - The use of ` isasync` is a bit too cute for me. It also hides the fact 
 sometime is a coroutine.


I want to be placing a lot more emphasis on UDA's like `` Route``, what 
we do right now with reflection is far too costly in terms of how to 
register symbols.

But yes, I do want to hide that it is a coroutine. The average person 
shouldn't have to care if its asynchronous of synchronous, it does not 
enable them to archive business goals faster.


 - Instead of allowing a coroutine in a function that is not a coroutine 
 itself - and injecting a blocking call - I would require explicit call 
 to evaluate the coroutine instead. No magic.


And that is library code ;)

But yes, I did try to explain that you did not need language integration 
for this. In fact the prime sieve example show cases exactly what you 
suggest!


 - Can coroutines be continued on another thread, assuming sequential 
 consistency?


Yes. There is nothing preventing it. There is also nothing making it 
safe either.
Aug 05
parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Tuesday, 6 August 2024 at 02:20:52 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 On 06/08/2024 3:50 AM, Sebastiaan Koppe wrote:

 On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) 
 Andrew Cattermole wrote:

 Coroutines is a stack machine transformed representation for 
 a function. It enables storing the state of a function 
 externally to the stack to allow for high throughput event 
 handling.


 
 Thank you for spearheading this. Having coroutines in the 
 language would be a big step forward, and hopefully pave the 
 way for more non-blocking programming in D.
 
 There are a few points I would like to bring up early though.
 
 - I see no mention of C++'s coroutines. I think it would be 
 good to learn from their design and implementation.

 - As you might know I am a big proponent of C++'s 
 Senders/Receivers (a.k.a. P2300). One awesome integration they 
 have is that Senders can be awaited by coroutines, and 
 coroutines can await Senders. This allows for users to pick 
 their preference, e.g. use convenient coroutines but suffer 
 some allocation costs, and use Senders for more performant 
 sections if need be. See
 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2300r7.html#design-aw
itables-are-senders and
https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/


 My conclusion about P2300 is that it is all library code. This 
 DIP would allow you to implement it.


https://github.com/symmetryinvestments/concurrency already 
implements a fairly large chunk of it.

I suppose what you mean is that this DIP would allow me to 
integrate coroutines with it.


 - I don't understand the choice for ` async`. Sometimes 
 resembling the word "coroutine" would be better in my opinion.


 It was `` co`` for a long time.

 I had a number of people request ``async`` instead.


 - In `while(Future!string readLine = socket.readUntil("\n"))` 
 I suspect it to do an explicit await. How does that work?


 When a coroutine is acquired, it'll yield automatically, it is 
 implicit.


What do you mean with 'acquired'?


 - I find the use of `Future` a bit confusing. Futures 
 generally carry too much synchronisation overhead with them 
 and I doubt coroutines need a full Future implementation 
 anyway. Perhaps call it a Task like they do in C++?


 This DIP does not propose library code. You are free to write 
 whatever library code you want and have it construct itself 
 from the language representation of a coroutine.


I fail to see what it then _does_ provide.


 This is a key design goal as there is a good chance we'll want 
 different solutions for different tasks.


It ultimately needs to integrate with the language coroutine 
support, so I don't understand how it can be completely separate. 
And if it can't, then the language needs to provide some 
low-level interface to it, which, granted, libraries can extend 
on.


 - The use of ` isasync` is a bit too cute for me. It also 
 hides the fact sometime is a coroutine.


 I want to be placing a lot more emphasis on UDA's like 
 `` Route``, what we do right now with reflection is far too 
 costly in terms of how to register symbols.


I think it distracts from the proposal. Likely ` Route` will be 
implemented in a library anyway.


 But yes, I do want to hide that it is a coroutine. The average 
 person shouldn't have to care if its asynchronous of 
 synchronous, it does not enable them to archive business goals 
 faster.


I very much like the low-level/high-level proposed approach to 
Phobos3. I very much do not want the language to hide coroutine 
details, and instead want to be in full control, when and if a 
coroutine is called/yielded to.


 - Instead of allowing a coroutine in a function that is not a 
 coroutine itself - and injecting a blocking call - I would 
 require explicit call to evaluate the coroutine instead. No 
 magic.


 And that is library code ;)

 But yes, I did try to explain that you did not need language 
 integration for this. In fact the prime sieve example show 
 cases exactly what you suggest!


I do not understand what it does - and how! It is unclear to me 
how `&generate` is turned into a `InstantiableCoroutine!(int)`, 
how `makeInstance` works (or what it even does) and what 
`ch.block` does.

I can guess of course, but that explanation needs to be part of 
the DIP.
Sep 24
parent "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 24/09/2024 10:47 PM, Sebastiaan Koppe wrote:

 On Tuesday, 6 August 2024 at 02:20:52 UTC, Richard (Rikki) Andrew 
 Cattermole wrote:

 On 06/08/2024 3:50 AM, Sebastiaan Koppe wrote:

 On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
 Cattermole wrote:

 Coroutines is a stack machine transformed representation for a 
 function. It enables storing the state of a function externally to 
 the stack to allow for high throughput event handling.


 Thank you for spearheading this. Having coroutines in the language 
 would be a big step forward, and hopefully pave the way for more 
 non-blocking programming in D.

 There are a few points I would like to bring up early though.

 - I see no mention of C++'s coroutines. I think it would be good to 
 learn from their design and implementation.

 - As you might know I am a big proponent of C++'s Senders/Receivers 
 (a.k.a. P2300). One awesome integration they have is that Senders can 
 be awaited by coroutines, and coroutines can await Senders. This 
 allows for users to pick their preference, e.g. use convenient 
 coroutines but suffer some allocation costs, and use Senders for more 
 performant sections if need be. See
 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2300r7.html#design-aw
itables-are-senders and
https://ericniebler.com/2024/02/04/what-are-senders-good-for-anyway/


 My conclusion about P2300 is that it is all library code. This DIP 
 would allow you to implement it.


 
 https://github.com/symmetryinvestments/concurrency already implements a 
 fairly large chunk of it.
 
 I suppose what you mean is that this DIP would allow me to integrate 
 coroutines with it.


Yeah, the specific library isn't so important. It is up to you how you 
translate the coroutine descriptor into your library. The hooks are in 
place so there is no hard coded library code required.


 - I don't understand the choice for ` async`. Sometimes resembling 
 the word "coroutine" would be better in my opinion.


 It was `` co`` for a long time.

 I had a number of people request ``async`` instead.


 - In `while(Future!string readLine = socket.readUntil("\n"))` I 
 suspect it to do an explicit await. How does that work?


 When a coroutine is acquired, it'll yield automatically, it is implicit.


 
 What do you mean with 'acquired'?


Stored in a variable.

On that note, I'm wondering if this is a little too limited, even to 
begin with.

A built-in to language "method" called ``yield`` on a coroutine library 
type, might be a good way to force a yield.

Yields should probably only happen if methods annotated as requiring a 
yield is accessed.

Needs thinking about.


 - I find the use of `Future` a bit confusing. Futures generally carry 
 too much synchronisation overhead with them and I doubt coroutines 
 need a full Future implementation anyway. Perhaps call it a Task like 
 they do in C++?


 This DIP does not propose library code. You are free to write whatever 
 library code you want and have it construct itself from the language 
 representation of a coroutine.


 
 I fail to see what it then _does_ provide.


The language feature, that then gets sliced and diced by the compiler 
into a descriptor, that then gets taken by library code into their own 
representation.

Library code cannot slice and dice a function up into a coroutine it has 
to be compiler backed.

See "Example Descriptor Object" 
https://gist.github.com/rikkimax/fe2578e1dfbf66346201fd191db4bdd4/0bb4442c092e061d520c35a43278f0819666f26f#example-descriptor-object


 This is a key design goal as there is a good chance we'll want 
 different solutions for different tasks.


 
 It ultimately needs to integrate with the language coroutine support, so 
 I don't understand how it can be completely separate. And if it can't, 
 then the language needs to provide some low-level interface to it, 
 which, granted, libraries can extend on.


Recognizing a library type as a coroutine, yielding, multiple returns 
ext. are all integrated yes.

What I was talking about here is related to data processing vs event 
processing vs whatever task people come up with. They have different 
needs to give the best user experience.

My focus here is to get enough to make it work for event processing as 
that is the one I have experience in with my library code.


 - The use of ` isasync` is a bit too cute for me. It also hides the 
 fact sometime is a coroutine.


 I want to be placing a lot more emphasis on UDA's like `` Route``, 
 what we do right now with reflection is far too costly in terms of how 
 to register symbols.


 
 I think it distracts from the proposal. Likely ` Route` will be 
 implemented in a library anyway.


I did not define a ``Route`` UDA. Only ``isasync`` to make library code 
like that work.


 But yes, I do want to hide that it is a coroutine. The average person 
 shouldn't have to care if its asynchronous of synchronous, it does not 
 enable them to archive business goals faster.


 
 I very much like the low-level/high-level proposed approach to Phobos3. 
 I very much do not want the language to hide coroutine details, and 
 instead want to be in full control, when and if a coroutine is 
 called/yielded to.


I understand that you want this.

A design goal is the average programmer does not need to care about the 
function they are writing is a coroutine.

They should be able to slap `` Route`` on their function, ask for some 
data and get it back without them having to do anything special.

This is the target audience I am designing this for.

If we need to allow the advanced user the ability to disable automatic 
yielding, then we can do that with a UDA later on. It does not need to 
be in a DIP nor be done now.


 - Instead of allowing a coroutine in a function that is not a 
 coroutine itself - and injecting a blocking call - I would require 
 explicit call to evaluate the coroutine instead. No magic.


 And that is library code ;)

 But yes, I did try to explain that you did not need language 
 integration for this. In fact the prime sieve example show cases 
 exactly what you suggest!


 
 I do not understand what it does - and how! It is unclear to me how 
 `&generate` is turned into a `InstantiableCoroutine!(int)`, how 
 `makeInstance` works (or what it even does) and what `ch.block` does.
 
 I can guess of course, but that explanation needs to be part of the DIP.


They are not provided by the DIP, these are examples that are based off 
my own codebase.

Note: they are in fact defined (except ``makeInstance`` as the name is 
self explanatory).

"The following template inference must work:"

```d
struct InstantiableCoroutine(Return, Args...) {
	static InstiableCoroutine opConstructCo(CoroutineDescriptor : 
__descriptorco)(CoroutineDescriptor) {
		return InstatiableCoroutine.init;
	}
}

void acceptCo(Return, Arguments...)(InstatiableCoroutine!(Return, 
Arguments) co) {
	static assert(Arguments.length == 1);
	static assert(is(Arguments[0] == int));
	static assert(is(Return == string));
}

acceptCo((int value) {
	return "hello!";
});
```

"This is described due to the introduction of the implicitly 
constructing operator overload function opConstructCo which may not be 
friendly towards template inference."

How you implement ``opConstructCo`` is specific to your library. It has 
no place in the DIP.

"It can also be used to construct a coroutine object using variable 
assignment or by returning a function with a typed coroutine library 
type on the outer function."

```d
void main() {
	InstantiableCoroutine!(int, int, int) var = &myCo;
}

int myCo(int a, int b)  async {
	return a + b;
}

InstantiableCoroutine!(int, int, int) returnedCo() {
	return (int a, int b) {
		return a + b;
	};
}
```

I can see that ``block`` while what it does is described all throughout, 
it is not spelled out in the example. Okay examples need more text 
describing them!

 From what I gather from you reply in general, you are trying to find a 
library proposal where there is only a language one. It'll need some 
rework to hopefully stop that.
Sep 24
prev sibling next sibling parent reply Meta <jared771 gmail.com> writes:
On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

I see you linked to that classic article on function colouring, 
but it wasn't clear to me how your DIP avoids the function 
colouring problem. We'd basically need something like parametric 
polymorphism over function effects, unless there's some trick or 
assumptions we can make to circumvent it.
Aug 07
parent "Richard (Rikki) Andrew Cattermole" <richard cattermole.co.nz> writes:
On 08/08/2024 1:37 PM, Meta wrote:

 On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
 Cattermole wrote:
 
 I see you linked to that classic article on function colouring, but it 
 wasn't clear to me how your DIP avoids the function colouring problem. 
 We'd basically need something like parametric polymorphism over function 
 effects, unless there's some trick or assumptions we can make to 
 circumvent it.


Originally there was meant to be behavior in synchronous functions to 
add blocking automatically.

That way it didn't matter how you "yield" implicitly.

Unfortunately that had major problems, and had to be removed.
Aug 07
prev sibling parent Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Monday, 5 August 2024 at 01:36:31 UTC, Richard (Rikki) Andrew 
Cattermole wrote:

 Coroutines is a stack machine transformed representation for a 
 function. It enables storing the state of a function externally 
 to the stack to allow for high throughput event handling.

 [...]


This deserves more attention
Sep 22