16
$\begingroup$

I used to code a lot in a language called Supercollider, which is a domain-specific language for sound synthesis and computer music.

One really nice feature it has is coroutines. Python also has these (via the yield keyword) but Supercollider's ones are much more powerful*, and I've often wondered why none of the other languages I'm familiar with have a similar feature.

*or at least I thought they were when asking this question, now I'm not so sure. yield from didn't exist when I learned Python and I wasn't aware of it when writing the question.

I'm using the terminology from SuperCollider here, which might be idiosyncratic, as it seems that "routines" are more commonly called "generators". The kind of coroutines I'm talking about are only about control flow, not concurrency - they run until they hit a yield and then return control to their caller until the caller chooses to resume them. (In SuperCollider you can also schedule them on a clock, but that's kind of a separate mechanism and is optional.)

In the rest of this question I will describe SuperCollider's coroutines, in order to make it clear what I mean. Like Python, SuperCollider is a dynamically typed interpreted language.

As in Python, SuperCollider has a yield keyword. (Technically a method in SuperCollider.) So you can write a function like this

~myFunction = {
    var x = 10;
    while {x>0} {
        yield(x);
        x = x - 1;
    };
    yield("I've run out of x's!");
};

// note on SuperCollider's syntax: the { ... } syntax creates a Function
// object, which we assign to the global variable ~myFunction.

You can then use this to create an object (called a routine in Supercollider, or a generator in Python) that will give a different output each time it's called, in this case counting down from 10 to 1 and then outputting "I've run out of x's!". In SuperCollider that looks like this:

// here we create a Function object and then pass it to the Routine constructor
~myRoutine = Routine({
    var x = 10;
    while {x>0} {
        yield(x);
        x = x - 1;
    };
    yield("I've run out of x's!");
});

postln(~myRoutine.next); // 10
postln(~myRoutine.next); // 9
// ...

So far this is just the same as Python's generators. However, in Python the yield keyword always yields from the function it's in, so you can't have a coroutine that calls another function and then yields from that function. In SuperCollider you can do this, because the yield command yields from the enclosing Routine. This allows things like the following example, which behaves identically to the previous one:

~countDownFrom = {
    arg x;
    while {x>0} {
        yield(x);
        x = x - 1;
    };
};

~myRoutine = Routine({
    ~countDownFrom.(10); // call the function ~countDownFrom with argument 10
    yield("I've run out of x's!");
});

postln(~myRoutine.next); // 10
postln(~myRoutine.next); // 9
// ...

There are also other useful things you can do with routines in SuperCollider, such as embedding one inside another or composing them.

I always found this sort of thing very useful in SuperCollider. (It's particularly useful in music, where routines can be used to produce sequences of notes, but I can imagine a lot of uses in things like game programming as well.) My question is just why it seems to be so rare in other languages - Python seems unusual in having a yield keyword at all, and even then it's very restricted compared to SuperCollider's one.

Is it because the language really has to be interpreted in order for this to work? Would there be impassible barriers that would prevent it from being implemented in a strongly typed, compiled language?

$\endgroup$
19
  • 4
    $\begingroup$ It's definitely not limited to interpreted languages - Scala is a compiled language, and has LazyList.unfold to provide similar behaviour to yield (it's not a structure, but it could theoretically be turned into a structure) $\endgroup$
    – lyxal
    Jul 20, 2023 at 6:16
  • 2
    $\begingroup$ @lyxal that kind of state machine type construction is one way to create streams, but in terms of the code you write it's quite different from coroutines. For example, suppose you wanted to output the numbers 1 to 100 in sequence, then 20 random numbers, then all the primes between 3 and 97. With a routine it would be just three for-loops one after the other, whereas with that type of construction you'd have to explicitly create a type for the internal state that can keep track of which loop it's currently in. It can do exactly the same things, but differs in what's easy or natural to express. $\endgroup$
    – N. Virgo
    Jul 20, 2023 at 6:26
  • 3
    $\begingroup$ That's what I meant. Yes the implementation of the unfold method requires an internal state. But my point is that it would be possible to create a syntax structure that abstracts away that state allowing just the for loops like you mentioned. Essentially, I'm saying that it is technically possible and theoretically achievable to create a generator structure in a compiled language (as to address your question "is it because the language has to be interpreted") $\endgroup$
    – lyxal
    Jul 20, 2023 at 6:28
  • 12
    $\begingroup$ Python has the yield from construct to yield every item from some other generator. It appears to work similarly to the ~ construct in SuperCollider $\endgroup$
    – mousetail
    Jul 20, 2023 at 6:29
  • 4
    $\begingroup$ So what happens in SuperCollider when you call a function that does yield() without wrapping it in a Routine()? $\endgroup$
    – Bergi
    Jul 20, 2023 at 15:50

5 Answers 5

15
$\begingroup$

It might be a library feature instead of a language feature

In some languages it might be feasible to implement coroutines as a library, without needing any support from the language itself. For example, there are coroutine libraries for C and C++ (Boost::Coroutine existed long before C++20 introduced coroutines as a language feature).

Coroutines are complicated

A generator is a very limited form of a coroutine. If a general-purpose language wants to implement coroutines, it probably wants to support a wider range of applications than just generators. However, there are lots of things to worry about then: how do you schedule coroutines, do you have stackful or stackless coroutines, how should it integrate with the existing language features, and so on. It could be that some languages decided that it's better to wait before committing to a specific implementation which might later turn out to be a bad decision.

But once you have generic coroutines in your language, then it's rather easy to have generators as well. In fact, that's the very first type of coroutine that will be supported in the C++ standard library (C++23's std::generator).

Composing generators

You already pointed out that there is a difference in how generators compose between Python and SuperCollider. That's another thing you have to worry about when impementing this as a language feature. Do yields cross coroutine function boundaries or not?

Not automatically passing yields means that each coroutine function has more control over what happens. It can then decide whether or not to pass a yielded value on to the parent. For exampe, in Python you would just write:

def countDownFrom(n):
    for x in range(n, 0, -1):
        yield x

def myRoutine():
    for x in countDownFrom(10):
        yield x

    # Or shorter:
    # yield from countDownFrom(10)

    yield "I've run out of x's!"

for x in myRoutine():
    print(x)

This is a bit more verbose. On the other hand, you probably need something more verbose in SuperCollider if you wanted the results of the call to ~countDownFrom.(10) to not be passed to the caller?

It's not an issue of compiled vs. interpreted

Is it because the language really has to be interpreted in order for this to work? Would there be impassible barriers that would prevent it from being implemented in a strongly typed, compiled language?

There is no reason why this couldn't work in a strongly typed, compiled language. Even your example that can return either an integer or a string from myRoutine() could be written in C++, if you appease the type system:

std::generator<int> countDownFrom(int n) {
    while (n > 0)
        co_yield n--;
}

std::generator<std::variant<int, std::string>> myRoutine() {
    for (auto x: countDownFrom(10))
        co_yield x;

    co_yield "I've run out of x's!";
}

for (auto x: myRoutine())
    std::visit([](auto x){ std::print("{}\n", x); }, x);

The for-loop in myRoutine() is necessary in C++, but it's easy to imagine adding a language feature like Python's yield from that will be equivalent to yielding all the values from the called coroutine to the caller. co_yield_from CountDownFrom(10) perhaps? It could be defined as being equivalent to the shown for-loop. You can even say that if you call a coroutine from a coroutine, and don't do anything with the value, it will automatically be all yielded, so that:

std::generator<std::variant<int, std::string>> myRoutine() {
    countDownFrom(10);
    co_yield "I've run out of x's!";
}

Would be equivalent to the code above. However, this goes against how C++ normally works; things are not automatically returned or yielded unless the programmer explicitly writes those keywords. I think it's the same for Python. SuperCollider can probably do this because it's a domain-specific language, and thus optimizes the language for the specific use case it has.

$\endgroup$
2
  • 3
    $\begingroup$ "On the other hand, you probably need something more verbose in SuperCollider if you wanted the results of the call to ~countDownFrom.(10) to not be passed to the caller?" Yes, you'd do ~innerRoutine = Routine(~countDownFrom) and then ~innerRoutine.next(10) to get the first value. Maybe you're right that the choice between "do this if you don't want the values passed to the caller" and "use yield from if you do want that" is largely a syntactic one. $\endgroup$
    – N. Virgo
    Jul 20, 2023 at 9:10
  • $\begingroup$ On interpreted vs compiled, I have issues with Crock's "The Next Programming Language" talk but he does observe that non-delegating asymmetric coroutines can be treated as syntactic sugar for a function that returns on pause and is called to resume. You need to pull local variables out into a closure and a way to jump to the instruction after the pause point on resumption. The Babel transform-regenerator plugin back-ported coros onto older JS engines via an SM rewrite for the latter. $\endgroup$ Jul 20, 2023 at 23:33
6
$\begingroup$

I don't know about Superrcollider, but often coroutine facilities are described as:

  • delegating or non-delegating (whether a coroutine can delegate yielding to something that it calls)
  • symmetric or asymmetric

I suspect the former might be interesting to you as you talked about

However, in Python the yield keyword always yields from the function it's in

I don't know that that's still true for Python, but that's indicative that it's non-delegating. JavaScript for example, added yield* as a way to allow a limited form of delegation, so some languages' coros start off non-delegating and end up supporting at least limited forms of delegation.

Slide 175 of A Curious Course on Coroutines and Concurrency explains trampolining as a way to allow delegation.

What is the difference between asymmetric and symmetric coroutines? explains the differences between symmetric and asymmetric: whether the power to resume is available to coroutines, so that coroutines can coordinate with each other, or whether that ability is reserved to a scheduler. Maybe Supercollider and Python differ along that dimension.

If you're interested in flexible coroutine implementations in less-widely-used languages, and how they can be deeply integrated, you might want to check out Icon.

Chapter 9 § Co-Expressions of THE ICON PROGRAMMING LANGUAGE

Furthermore, the results of an expression can be produced only by iteration or goal-directed evaluation; there is no mechanism for explicitly resuming an expression to get a result. Consequently, the results produced by an expression are strictly constrained, both in location and in the sequence of program evaluation. Co-expressions overcome these limitations. A co-expression “captures” an expression so that it can be explicitly resumed at any time and place.

$\endgroup$
2
  • 2
    $\begingroup$ Python has yield from where JavaScript has yield*. But in both cases, they're explicit keywords $\endgroup$
    – Bergi
    Jul 21, 2023 at 0:50
  • $\begingroup$ Thanks. I thought I remembered something like that. iiuc, if you wanted unlimited delegation, you need to be able to pass yield or pass a lambda that uses it the way you'd pass any other lambda. By restricting it to a keyword or other special syntax, you preclude that. $\endgroup$ Jul 21, 2023 at 16:30
6
$\begingroup$

Stackless!

There are two kinds of coroutines. "Stackless" and "stackful".

A stackful coroutine is a full function call stack state, the kind of thing a thread would have. When you suspend, you save the entire call stack (up to the point where you "started coroutining") and return the value you want to return.

A stackless coroutine is like an object. All of the local variables of the function the coroutine has, or any captured data, is part of the state of the coroutine. When suspended, it saves up just that data, and returns to the caller.

You can daisy-chain stackless coroutines and make it act stackful. In a stackless coroutine X, you can resume a coroutine Y in a loop. When Y returns a value, you yield it to your caller. When Y finishes, you continue your code.

So, stackful pseudo code:

coroutine bob
  invoke coroutine alice
  yield from bob 7

stackless pseudo code:

coroutine bob
  await foreach value x from alice
    yield x
  yield from bob 7

where alice in turn generates 0 or more values.

There is a cost to making all coroutines stackful. Each coroutine ends up using up megabytes of space, or requiring fancy space-expansion capabilities for storage.

There is also a code organization cost. You don't know if a function you are calling is going to take over your control flow or not.

With stackless coroutines, any such control flow is going to be explicit in your code.

There is more going on here

You can think of a function as a thing you can interact with.

  • Functions can be passed arguments, pass args.
  • Functions can start executing (with is a kind of goto), aka run.
  • Functions can store a return value once they start executing
  • Functions can resume the code that started their execution, aka return.

typically these are bundled together. So you call a function, passing in arguments, the place to resume once you finish the function, and where to store the return value. Then you start it running (do the "goto").

The code that the function is running then does stuff, reads the arguments, stores a return value, then calls the "resume the code that started me".

Functions in turn can chain onto other functions. They can pass arguments to them, store a return value, etc.

In some cases (tail recursion), you even pass your resumption location and your return value storage to the function you call! This bypasses doing extra work.

This may seem like a strange way to think about functions, but once you do this coroutines become fun.

Coroutines add some extra capabilities to functions.

  • Coroutines can suspend.
  • Coroutines can resume.

When a coroutine suspends, it stores where it is currently running (a goto like label). When a coroutine resumes, it restarts where it left off.

Often there are side channels for communicating extra data.

When you run a function, you pass in a (arguments)(calling location)(return value) tuple, then run it.

When you resume a coroutine, you pass in a (arguments sometimes)(calling location)(return value) tuple.

Often (but not always) when you start a coroutine, the initial run acts differently. It is a constructor rather than an execution.

You can use these to produce a generator. But you can also generate things more powerful than generators!

When you resume (or run) a coroutine, you could pass in your calling location as the spot they should resume to, and your return data store as the spot they should store the return value. When they terminate, you could choose your own code instead of the caller.

coroutine bob: (constructs an iterator)
  return bob::iterator:
    a = create coroutine alice(10)
      resume location of alice is bob::iterator resume
      retval location of alice is bob::iterator retval
      return location is bob::iterator body
    resume a until a is finished
    return 17

 auto it = bob();
 while(val : resume it)
   print val

this is very similar to

coroutine bob: (constructs an iterator)
  return bob::iterator:
    a = create coroutine alice(10)
    while( val : resume a )
      yield val
    return 17

 auto it = bob();
 while(val : resume it)
   print val

with optimizations.

The next fun thing is what "await" means. Await changes meaning depending on what the coroutine you are awaiting on state is.

If that coroutine is ready, you advance. If not, you suspend and resume your caller.

This is useful for async stuff like io -- the data isn't there yet, and you don't want to waste your caller's time.

In javascript, awaiting commonly results in your entire subtask being put to sleep and awoken on a later loop of the main javascript event loop to continue with the data you want, once you have access to it.

The semantics on await to make this abstract are ... well, interesting.

In any case, you can continue to have stackful coroutines, or do a transformation and make stackless coroutines act stackful.

$\endgroup$
1
  • 1
    $\begingroup$ This stackless/stackful distinction sounds similar to delimited/undelimited continuations; is it the same? (e.g. researchgate.net/publication/… ) $\endgroup$
    – Warbo
    Jul 21, 2023 at 22:57
4
$\begingroup$

Is it because the language really has to be interpreted in order for this to work? Would there be impassible barriers that would prevent it from being implemented in a strongly typed, compiled language?

The language does not need to be interpreted to have coroutines with a stack. The way you compile these things isn't trivial, but it definitely can be done. The generated code tends to end up looking really strange, as there are typically a lot of transformations applied on the way. Essentially you get a family of functions, one for each section of source code-path between points where you yield, plus a fully-generated coordination function, and then the optimizer gets busy inlining. (At the point where I was last working in the area, compiler support for this stuff was very experimental, but I'd be startled if things haven't matured since then.)

The strength of typing of the language is an entirely orthogonal concern.

I believe that many languages don't have stackful coroutines because their implementers believed it was easier to not do that. It does mean that you can make coroutines with a bit less ceremony, but you instead end up with the function coloring problem if you want to make fully generic libraries.

$\endgroup$
2
$\begingroup$

I think that originally they came from Wirth's Modula-2, although I don't know to what extent predecessor languages (Modula, Edison and so on) had them: documentation on those tends to be sparse and scanned so not always searchable.

In practice, I think that MS's terminology of "fibers" is as least mostly synonymous, i.e. support has been moved into the OS's non-preemptive thread facility rather than being part of the language.

At that point things get messy, since my own experience is that on a bare-metal kernel it's possible to build (preemptive) threads onto coroutines/fibers and then processes (i.e. with resource ownership) onto threads. However "the unix way", which influences so many things these days, is to start off with processes and then munge them into threads: the idea of using something relatively heavyweight like a process to implement what should be a featherweight coroutine makes me uncomfortable.

$\endgroup$
6
  • 2
    $\begingroup$ Bear in mind that processes on unix were traditionally as cheap as threads on windows so no ditinction was necessary. Fibers and coroutines are a different matter. I recall early versions of them using ucontext in Posix. Things like libuv seem to have taken over now. I'm not sure there is any question of using something as heavy as a process. $\endgroup$ Jul 20, 2023 at 15:09
  • 1
    $\begingroup$ Processes /have/ to be slower because a memory context switch is involved hence cache flushes etc. Still pretty fast, mind, compared with some of the original timesharing stuff which was still "a thing" when OS/2 and Windows NT (which of course underlies modern Windows) were designed. $\endgroup$ Jul 20, 2023 at 15:16
  • 1
    $\begingroup$ Yes indeed and both stackful and stackless coroutines have their place. $\endgroup$ Jul 20, 2023 at 15:20
  • 2
    $\begingroup$ @supercat I'm uncomfortable with that: forking is the /creation/ of a new process while context switching is /between/ two already-created processes. $\endgroup$ Jul 20, 2023 at 21:29
  • 3
    $\begingroup$ @MarkMorganLloyd: Context switching required writing a memory snapshot of the current task to disk and reading a snapshot of the task to switch to. Forking merely required writing a memory snapshot of the current task to disk and changing the task slot number that will be used the next time the current task is written to disk, with no need to load a task memory snapshot from disk. $\endgroup$
    – supercat
    Jul 20, 2023 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .