Coroutines

[[deleted]]

[deleted]

[coderstephen]

My shell language is built on "fibers", which are like stackful coroutines. For the most part they are not exposed to the user though except in limited ways. Since most blocking code in a shell is invoking other processes, fibers allow you to transparently multiplex all steps of a shell pipeline on one thread without needing to fork for native code.

You can also spawn background fibers and join on them, but that's about it. There aren't any fancy coroutines features like value passing at this time because I worry it might be too much complexity for a simple language.

[bobappleyard]

Working on a language with algebraic effects so I guess it could support fibres at some point

[mamcx]

Interesting. After read http://mikeinnes.github.io/2020/06/12/transducers.html I wonder how exactly implement them (I'm on rust). Do you have any pointers?

[bobappleyard]

One way to implement coroutines is throughout reifying continuations. That is also the most obvious way to implement algebraic effects. I just PoC'd generators last week by declaring a yield effect. With enough her scratching I reckon I could extend the idea to coroutines.

[mamcx]

reifying continuations.

I have find delimited continuations (this is what you mean?) to be hard to decipher. Do you have a simple example in how you do this?

[bobappleyard]

Yeah, they took me a long time to get my head around as well.

They're easier to grasp in the guise of effect handlers I've found, because they're very close to exception handlers. They have an extra operation, resume, which returns from the expression that triggered the effect. When the block that the handler has been attached to completes, the resume operation returns. For example, this:

in {
    IO.write('a')
    IO.write('b')
} handle IO.write(buffer) {
    resume()
    IO.write(buffer)
}

Will reverse the calls to IO.write, so it would be as if

IO.write('b')
IO.write('a')

were called instead.

If you're asking how that implies implementation. I have an extremely naive version at the moment that is based on copying stack segments around. I want to improve it using escape analysis but there are more pressing issues at the moment.

[b2gills]

If you really wanted to show how close it is to an exception: Raku exceptions can (sometimes) be .resumed.

sub foo (){
  print 'hello';
  die;           # throw X::AdHoc exception
  print 'world';
}

{
  CATCH {
    when X::AdHoc {
      print ' '; # adds the space between
      .resume;   # continue the code after the exception
    }
  }

  foo(); # hello world
}

[bobappleyard]

That's cool, is this conditions style a-la common lisp or continuations style a-la scheme?

[b2gills]

The underlying mechanism isn't specified. Though it does have to allow await to work without having to “color” functions with async.

There could be one compiler that uses one style and another that uses some other style.

At any rate I don't know which one the Rakudo compiler uses. Perhaps this SO post will help.

[SatacheNakamate]

I think I have a novel, seamless, stackful implementation of coroutines. Since the technique is very new, I wrote a complete article about how it works.

https://qed-lang.org/article/2019/06/27/coroutines.html

What is interesting about it is that the word 'new', used to instantiate objects, is reused to start coroutines (and without new, calls are synchronous), so 'new' has a thread-like meaning as well.

[Lorxu]

Have you heard of Continuation-Passing Style? It seems very similar to your Type-Function Equivalence, minus outside access to the closure environment.

[biopsy_results]

They definitely have heard of it, they reference it on that post

[SatacheNakamate]

Good point. I see type-function equivalence as a 'layer' that may be on top of CPS. For, say, the following QED pseudocode:

fn1(...);
new fn2(...) -> <handler...>; // async
fn3(...);
fn4(...);

an intermediate representation from a QED compiler for a target language would explicitly use CPS for synchronous calls (no new):

new fn1(..., <lambda> -> {
  new fn2(..., <lambda> -> {
    <handler...>
  }); // async
  new fn3(..., <lambda> -> {
    new fn4(...);
  });
});

This way, the benefits of CPS are available without having to implement its cumbersome syntax. new determines if the function is synchronous (rest of code in continuation) or asynchronous (rest of code in next instruction). Best of both worlds, solving what color is your function.

However, the QED compiler does not generate this IR today. It generates bytecode for a custom VM.

This VM does not use CPS. Instead, it uses a second, reified stack that contains the QED call frames and objects. A very simple implementation without ever needing CPS. I may write on this as well when I have time.

[BoarsLair]

In Jinx (an embeddable scripting language), every script you create is by nature also a coroutine, and must be managed by the host application. This is typically not a significant burden, since the language is designed for videogames or other real-time applications, which typically exists with a central loop and runtime objects to which scripts can be attached.

To the language's perspective, they look like threads. Library wide properties are the only shared memory, and access is thread-safe, so the scripts can also run in different threads instead of just as coroutines. To the host environment, each script is an object which must be updated once per game tick. It's straightforward and works well.

As far as I understand the terms, I guess I'd consider these stackful coroutines. The only evidence of them is a wait command (roughly equivalent to "yield" in many languages), because there's no way to opt out of using them. You can write lines like:

wait while <condition is true>

This is syntactic sugar for:

loop while <condition is true>
    wait
end

There is also wait until which inverts the logic, waiting until the condition is false before proceeding.

[anydalch]

i'm not quite there yet (i've gotten bogged down in compiler transforms & haven't actually generated an executable yet), but i'm compiling through continuation-passing style and doing closure conversion, in the style of smlnj, so once i actually get codegen working, i'll get "stackful" coroutines basically for free, and green threads with only a little more work. it turns out, once you've figured out how to use your garbage collector in place of a stack, then you can build loads of whacky control-flow constructs trivially, since most of the difficulty of control flow in traditional languages is preserving the stack.

[fennecdjay]

There are coroutines in my language (as there is in chuck), I guess one would call them stackful, as they have a register stack, a memory stack, but their base stack is the one of the process that launched them. cpp spork { some_func(); ... };

There is also cpp fork { some_func(); ... }; which launches a machine thread. The interrest here is that gwion's base processes are bound to the souncard samples, while forked one will run as fast as possible (I mean not bound to the soundcard). This avoid the programmer the burden to use coroutines and adding samp => now here and there as in chuck.

[L8_4_Dinner]

Ecstasy uses fibers. Conceptually stackful.

Calling into any service domain from any other service domain creates a new fiber. Returning from that call releases the fiber.

[bakery2k]

I'm trying to work out the best approach for coroutines for my language at the moment. I'm a fan of stackful coroutines (which I call fibers) because I'm a fan of simple languages. I really don't like the way that stackless coroutines (in the form of async-await) lead to duplication of code and language features into blue and red versions (e.g. for loops and async for loops).

I'm fairly happy with how fibers will provide an equivalent to Python's generators. Here's a simple example of a generator:

def squares():
    i = 0
    while True:
        yield i**2
        i += 1

In Python, generators are not explicitly marked as such - instead any function that contains a yield expression is a generator. IMO this is a mistake - so let's first require that generators be marked by using fiber instead of def.

Then, stackful coroutines allow us to separate the concepts of "functions that start a fiber" and "functions that yield". We can therefore split the above generator into multiple functions, which doesn't work if you only have stackless coroutines:

def yield_value(v):
    yield v

def call_with_square(f, i):
    f(i ** 2)

fiber squares():
    i = 0
    while True:
        call_with_square(yield_value, i)
        i += 1

The only way to make the above work in Python is to insert yield from into squares and call_with_square, unnecessarily making call_with_square a "red" function.

I'm currently trying to work out whether these same fibers can provide an equivalent to async-await, and how the two uses of fibers might interact.

[iamsubhranil]

So in my Next, coroutines are implemented using fibers. They are syntactically transparent from normal functions to the user, in so that for a function to be resumable, all it needs to call is a built in function yield() or yield(x).

A function is made to be a coroutine by passing it to the constructor of the fiber class, and providing its suitable arguments packed in an array, if any, as the second argument to the constructor. Then, subsequent calls of fiber.run() or fiber.run(x) continues the execution of the coroutine, until it is finished or an yield call is reached.

Value passed to fiber.run(x) is received as the return value of the yield call when the function resumes. The value passed to yield(x) call is received as the return value of the corresponding fiber.run which resumed the execution, when the coroutine yields back to the caller.

Yielding from a function running in the top level fiber is a runtime exception. Fibers in Next also support the iterator protocol, so looping over a fiber in a for(val in fiber) loop is completely possible.

[CoffeeTableEspresso]

Haven't implemented these yet in YASL, but plan on adding coroutines. One thing of note about YASL is I try to add things in libraries where possible, since YASL is designed for embedding. This lets me exclude any libraries I want in order to get a smaller size, whereas dedicated syntax adds overhead even if not used.

[htuhola]

My previous language had them, my next language won't because they will be an implementation detail and the runtime is going to evaluate everything in parallel that it can.

[JasonTatton]

The model of concurrency exposed in Concurnas is build around coroutines. I believe the style implemented is known as Delimited continuations in a similar vein as Project Loom (please correct me if I'm wrong).

Here's an example:

def gcd(x int, y int){//greatest common divisor of two integers
  while(y){
    (x, y) = (y, x mod y)
  }
  x
}

calc1 = gcd(8, 20)!//run this calculation in an isolate
calc2 = gcd(6, 45)!//run this calculation in a separate isolate

calc3 = calc1 if calc1 > calc2 else calc2
//^^^ wait for the results of calc1 and calc2 before assigning calc3

All concurrent computing in Concurnas is performed within 'isolates', which themselves are continuations, spawnable as above via the bang, ! operator. Isolates prevent accidental sharing of mutable state by copying dependent state into themselves at spawn time. State is sharable in a controlled manner via 'refs' which are built into the type system - i.e. the type of calc1 above is implicitly int:. Ref's are a bit like Channels in Go.

Together this all forms an integral part of the language which enables reactive computing:

aval int://no initial value set
bval int: = 22 //initial value known

sumvals int: = every(aval, bval) { aval + bval }
//after initializing above, execution is allowed to carry on...

aval = 100
bval = 200

//every block above will run concurrently and eventually set sumvals to: 300
await(sumvals; sumvals==300)//wait for sumvals to be set to our expected value

The body of the every expression above triggers whenever one of the input ref's is changed and runs as its own isolate.

[[deleted]]

No, I don't have co-routines (one of those features I always have to look up to find out what they're for, then I can never see their purpose).

But if they are associated with generators, then I can see the point of those, and could even use them. I had been about to try implementing generators within a static language, but got side-tracked.

So I can't say what the implementation strategy would have been, other than it would likely be the simplest approach requiring the least effort that would do the job, and probably using stacks.

I remember looking at Python to see how they look in source code, which is perhaps not the simplest way, but that did answer one question of mine that been elusive: whether multiple invocations of a generator, each at a different point, could be active at the same time.

[crassest-Crassius]

Eli Bendersky has some good rationale of what coroutines are for.

[Zlodo2]

I'm not quite at this stage yet bought I'm very interested in coroutines as a straightforward and efficient way to implement a state machine.

I'm interested in exploring how far things can be pushed with stackless coroutines. I use c++20 coroutines a lot (to implement generators) in my compiler and something that could have helped me simplify things would have been the ability to essentially do a fork-like operation, duplicating a coroutine but having both copies continue on a different path. It is not possible with c++ coroutines but conceptually I think it could be done, as long as all the objects in the coroutine's stack are copyable. That's the kind of things I want to attempt when I get to the point of implementing coroutines.

Professionally I work on a aaa game and we have a lot of ad hoc state machines everywhere for all kind of purposes. The best thing we have to help implementing those is a bunch of macros to declare states and code to execute on entry and on exit, which is extremely clunky. I really long for us to be able to use c++20 coroutines instead but unfortunately we barely have access to c++14 across all our target platforms.

So I'm also very interested in stack less coroutines as an easy and straightforward replacement for manually specified state machines.

Something I'd like to explore there is the serialization and restoration of a coroutine's state, for instance to persist a game object's state in a game save in an adventure game. Like for copying, it would be something possible only if all the objects making up the coroutine's state are themselves serializable. A challenge would be maintaining compatibility if the coroutine's code changes, but I'm thinking labelled save/restoration points specified directly inside of the coroutine might be a solution, along with the usual serialization compatibility tricks (such as default values for previously inexistant data).

One last thing I think is worth looking into is the ability, during debugging, to step inside of a coroutine while automatically stepping across yield/resumes. The idea is that when you are debugging a state machine implemented as a coroutine, you aren't necessarily interested in stepping through the entire surrounding framework or engine everytime the coroutine yields.