<p>I used to code a lot in a language called <a href="https://supercollider.github.io/" rel="noreferrer">Supercollider</a>, which is a domain-specific language for sound synthesis and computer music.</p>
<p>One really nice feature it has is coroutines. Python also has these (via the <code>yield</code> 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.</p>
<p>*<sub>or at least I thought they were when asking this question, now I'm not so sure. <code>yield from</code> didn't exist when I learned Python and I wasn't aware of it when writing the question.</sub></p>
<p>I'm using the terminology from SuperCollider here, which might be idiosyncratic, as it seems that &quot;routines&quot; are more commonly called &quot;generators&quot;. The kind of coroutines I'm talking about are only about control flow, not concurrency - they run until they hit a <code>yield</code> 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.)</p>
<p>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.</p>
<p>As in Python, SuperCollider has a <code>yield</code> keyword. (Technically a method in SuperCollider.) So you can write a function like this</p>
<pre><code>~myFunction = {
    var x = 10;
    while {x&gt;0} {
        yield(x);
        x = x - 1;
    };
    yield(&quot;I've run out of x's!&quot;);
};

// note on SuperCollider's syntax: the { ... } syntax creates a Function
// object, which we assign to the global variable ~myFunction.
</code></pre>
<p>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 &quot;I've run out of x's!&quot;. In SuperCollider that looks like this:</p>
<pre><code>// here we create a Function object and then pass it to the Routine constructor
~myRoutine = Routine({
    var x = 10;
    while {x&gt;0} {
        yield(x);
        x = x - 1;
    };
    yield(&quot;I've run out of x's!&quot;);
});

postln(~myRoutine.next); // 10
postln(~myRoutine.next); // 9
// ...
</code></pre>
<p>So far this is just the same as Python's generators. However, in Python the <code>yield</code> 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 <code>Routine</code>. This allows things like the following example, which behaves identically to the previous one:</p>
<pre><code>~countDownFrom = {
    arg x;
    while {x&gt;0} {
        yield(x);
        x = x - 1;
    };
};

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

postln(~myRoutine.next); // 10
postln(~myRoutine.next); // 9
// ...
</code></pre>
<p>There are also other useful things you can do with routines in SuperCollider, such as embedding one inside another or composing them.</p>
<p>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.</p>
<p>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?</p>

<coroutines><generators>
Why do so few languages have this type of coroutine feature?
CC BY-SA 4.0
2023-07-20T06:16:33.780Z
It's definitely not limited to interpreted languages - Scala is a compiled language, and has [`LazyList.unfold`](https://dotty.epfl.ch/api/scala/collection/immutable/LazyList%24.html#unfold-fffff43a) to provide similar behaviour to `yield` (it's not a structure, but it could theoretically be turned into a structure)
lyxal
CC BY-SA 4.0
2023-07-20T06:26:11.390Z
@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.
N. Virgo
CC BY-SA 4.0
2023-07-20T06:27:28.973Z
(Or at least it seems that way to me. I am not a very experienced functional programmer and it might be that you can do that sort of thing more easily than I think you can.)
N. Virgo
CC BY-SA 4.0
2023-07-20T06:28:22.377Z
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")
lyxal
CC BY-SA 4.0
2023-07-20T06:29:38.027Z
Python has the `yield from` construct to yield every item from some other generator. It appears to work similarly to the `~` construct in SuperCollider
mousetail 'he-him'
CC BY-SA 4.0
2023-07-20T06:37:36.113Z
@mousetail I didn't know about `yield from`, but it looks similar to SuperCollider's `embedInStream`. I don't think it lets you do what I'm asking about here, though there might be some non-obvious way in which it does. (`~` just indicates a global variable. I probably should have explained that. I've tidied up the code a bit so that point is less confusing and added some comments in the code about SuperCollider's syntax.)
N. Virgo
CC BY-SA 4.0
2023-07-20T06:44:06.283Z
@N.Virgo My apologies I misunderstood that syntax
mousetail 'he-him'
CC BY-SA 4.0
2023-07-20T13:34:45.950Z
Kotlin also has the `sequence` function that creates a `yield()`able closure
Seggan
CC BY-SA 4.0
2023-07-20T13:59:41.297Z
Are these yields 'lifted' out of the coroutine in the same sense as things are lifted by monads and applicative functors?
Bruce Adams
CC BY-SA 4.0
2023-07-20T15:50:08.480Z
Python coroutines have nothing to do with `yield`, that’s just for generators. You can _implement_ coroutines using generators, but native coroutines in Python are something different.
Austin Hemmelgarn
CC BY-SA 4.0
2023-07-20T15:50:34.593Z
So what happens in SuperCollider when you call a function that does `yield()` without wrapping it in a `Routine()`?
Bergi
CC BY-SA 4.0
2023-07-21T01:22:26.313Z
@Bergi you get a "yield was called outside of a Routine" error.
N. Virgo
CC BY-SA 4.0
2023-07-21T01:35:16.823Z
@N.Virgo So `~countDownFrom.(10)` wouldn't work outside of `~myRoutine`?
Bergi
CC BY-SA 4.0
2023-07-21T01:36:12.527Z
@Bergi right, it would throw an error.
N. Virgo
CC BY-SA 4.0
2023-07-21T01:42:21.707Z
@Bergi if that seems like an odd language design choice it might help to know that in SuperCollider everything inherits from Object, and yield is just a method of the Object class, not a keyword.
N. Virgo
CC BY-SA 4.0
2023-07-21T01:52:48.863Z
@N.Virgo Seems to me like it was more sensible if `yield` was a method of the `Routine` class… Regardless, it seems that the design decision comes down to verbosity and safety: is any function call allowed to suspend the current coroutine, or does it need to be explicitly annotated where in the control flow a suspension can happen?
Bergi
CC BY-SA 4.0
2023-07-21T04:51:07.190Z
@Bergi I don't think yield could easily be a method of Routine, because then you'd need to create the routine first, before you could call yield on it. In Supercollider yield is something that happens at runtime: it checks if there's an enclosing routine and yields to the routine's caller if so, throwing an error otherwise. That does mean any function call could potentially suspend the current routine, and I do see that that could cause issues with encapsulation.
N. Virgo
CC BY-SA 4.0
2023-07-22T08:43:02.747Z
I've dabbled in Supercollider myself. It didn't really occur to me that it works like this.
Karl Knechtel
CC BY-SA 4.0
2023-07-24T18:28:10.553Z
Lua has this feature.
Criticize SE actions means ban
<h2>It might be a library feature instead of a language feature</h2>
<p>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++ (<a href="https://www.boost.org/doc/libs/1_74_0/libs/coroutine/doc/html/coroutine/coroutine.html" rel="noreferrer">Boost::Coroutine</a> existed long before C++20 introduced <a href="https://en.cppreference.com/w/cpp/language/coroutines" rel="noreferrer">coroutines as a language feature</a>).</p>
<h2>Coroutines are complicated</h2>
<p>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 <a href="https://langdev.stackexchange.com/questions/697/what-are-the-benefits-of-stackful-vs-stackless-coroutines">stackful or stackless coroutines</a>, 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.</p>
<p>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 <a href="https://en.cppreference.com/w/cpp/coroutine/generator" rel="noreferrer"><code>std::generator</code></a>).</p>
<h2>Composing generators</h2>
<p>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?</p>
<p>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:</p>
<pre><code>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 &quot;I've run out of x's!&quot;

for x in myRoutine():
    print(x)
</code></pre>
<p>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 <code>~countDownFrom.(10)</code> to <em>not</em> be passed to the caller?</p>
<h1>It's not an issue of compiled vs. interpreted</h1>
<blockquote>
<p>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?</p>
</blockquote>
<p>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 <code>myRoutine()</code> could be written in C++, if you appease the type system:</p>
<pre><code>std::generator&lt;int&gt; countDownFrom(int n) {
    while (n &gt; 0)
        co_yield n--;
}

std::generator&lt;std::variant&lt;int, std::string&gt;&gt; myRoutine() {
    for (auto x: countDownFrom(10))
        co_yield x;

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

for (auto x: myRoutine())
    std::visit([](auto x){ std::print(&quot;{}\n&quot;, x); }, x);
</code></pre>
<p>The <code>for</code>-loop in <code>myRoutine()</code> is necessary in C++, but it's easy to imagine adding a language feature like Python's <code>yield from</code> that will be equivalent to yielding all the values from the called coroutine to the caller. <code>co_yield_from CountDownFrom(10)</code> perhaps? It could be defined as being equivalent to the shown <code>for</code>-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:</p>
<pre><code>std::generator&lt;std::variant&lt;int, std::string&gt;&gt; myRoutine() {
    countDownFrom(10);
    co_yield &quot;I've run out of x's!&quot;;
}
</code></pre>
<p>Would be equivalent to the code above. However, this goes against how C++ normally works; things are not automatically <code>return</code>ed or <code>yield</code>ed 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.</p>

CC BY-SA 4.0
2023-07-20T08:20:39.687Z
2023-07-20T09:20:43.890Z
2023-07-20T09:20:43.890Z
G. Sliepen
CC BY-SA 4.0
2023-07-20T09:10:40.667Z
"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.
N. Virgo
CC BY-SA 4.0
2023-07-20T23:33:17.450Z
On interpreted vs compiled, I have issues with Crock's ["The Next Programming Language"](https://www.youtube.com/watch?v=R2idkNdKqpQ) 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](https://babeljs.io/docs/babel-plugin-transform-regenerator) plugin back-ported coros onto older JS engines via an SM rewrite for the latter.
Mike Samuel
<p>I don't know about Superrcollider, but often coroutine facilities are described as:</p>
<ul>
<li><em>delegating</em> or <em>non-delegating</em> (whether a coroutine can delegate yielding to something that it calls)</li>
<li><em>symmetric</em> or <em>asymmetric</em></li>
</ul>
<p>I suspect the former might be interesting to you as you talked about</p>
<blockquote>
<p>However, in Python the <code>yield</code> keyword always yields from the function it's in</p>
</blockquote>
<p>I don't know that that's still true for Python, but that's indicative that it's non-delegating.  JavaScript for example, added <code>yield*</code> 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.</p>
<p>Slide 175 of <a href="https://www.dabeaz.com/coroutines/Coroutines.pdf" rel="noreferrer"><em>A Curious Course on
Coroutines and Concurrency</em></a> explains trampolining as a way to allow delegation.</p>
<p><a href="https://stackoverflow.com/a/42042904/20394"><em>What is the difference between asymmetric and symmetric coroutines?</em></a> explains the differences between <em>symmetric</em> and <em>asymmetric</em>: 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.</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Icon_%28programming_language%29" rel="noreferrer"><em>Icon</em></a>.</p>
<p>Chapter 9 § Co-Expressions of <a href="https://www2.cs.arizona.edu/icon/ftp/doc/lb1up.pdf" rel="noreferrer"><em>THE ICON PROGRAMMING LANGUAGE</em></a></p>
<blockquote>
<p>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.</p>
</blockquote>

CC BY-SA 4.0
2023-07-20T17:07:16.107Z
2023-07-20T17:07:16.107Z
Mike Samuel
CC BY-SA 4.0
2023-07-21T00:50:52.217Z
Python has `yield from` where JavaScript has `yield*`. But in both cases, they're explicit keywords
Bergi
CC BY-SA 4.0
2023-07-21T16:30:39.613Z
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.
Mike Samuel
<blockquote>
<p>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?</p>
</blockquote>
<p>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 <code>yield</code>, 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.)</p>
<p>The strength of typing of the language is an entirely orthogonal concern.</p>
<p>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.</p>

CC BY-SA 4.0
2023-07-28T14:31:41.653Z
2023-07-28T14:31:41.653Z
Donal Fellows
<h2>Stackless!</h2>
<p>There are two kinds of coroutines.  &quot;Stackless&quot; and &quot;stackful&quot;.</p>
<p>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 &quot;started coroutining&quot;) and return the value you want to return.</p>
<p>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.</p>
<p>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.</p>
<p>So, stackful pseudo code:</p>
<pre><code>coroutine bob
  invoke coroutine alice
  yield from bob 7
</code></pre>
<p>stackless pseudo code:</p>
<pre><code>coroutine bob
  await foreach value x from alice
    yield x
  yield from bob 7
</code></pre>
<p>where alice in turn generates 0 or more values.</p>
<p>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.</p>
<p>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.</p>
<p>With stackless coroutines, any such control flow is going to be explicit in your code.</p>
<h2>There is more going on here</h2>
<p>You can think of a function as a thing you can interact with.</p>
<ul>
<li>Functions can be passed arguments, <strong>pass args</strong>.</li>
<li>Functions can start executing (with is a kind of goto), aka <strong>run</strong>.</li>
<li>Functions can store a return value once they start executing</li>
<li>Functions can resume the code that started their execution, aka <strong>return</strong>.</li>
</ul>
<p>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 &quot;goto&quot;).</p>
<p>The code that the function is running then does stuff, reads the arguments, stores a return value, then calls the &quot;resume the code that started me&quot;.</p>
<p>Functions in turn can chain onto other functions.  They can pass arguments to them, store a return value, etc.</p>
<p>In some cases (tail recursion), you even pass <strong>your</strong> resumption location and <strong>your</strong> return value storage to the function you call!  This bypasses doing extra work.</p>
<p>This may seem like a strange way to think about functions, but once you do this coroutines become fun.</p>
<p>Coroutines add some extra capabilities to functions.</p>
<ul>
<li>Coroutines can <strong>suspend</strong>.</li>
<li>Coroutines can <strong>resume</strong>.</li>
</ul>
<p>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.</p>
<p>Often there are side channels for communicating extra data.</p>
<p>When you <strong>run</strong> a function, you pass in a (arguments)(calling location)(return value) tuple, then run it.</p>
<p>When you resume a coroutine, you pass in a (arguments sometimes)(calling location)(return value) tuple.</p>
<p>Often (but not always) when you start a coroutine, the initial <strong>run</strong> acts differently.  It is a constructor rather than an execution.</p>
<p>You can use these to produce a generator.  But you can also generate things more powerful than generators!</p>
<p>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.</p>
<pre><code>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
</code></pre>
<p>this is very similar to</p>
<pre><code>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
</code></pre>
<p>with optimizations.</p>
<p>The next fun thing is what &quot;await&quot; means.  Await changes meaning depending on what the coroutine you are awaiting on state is.</p>
<p>If that coroutine is ready, you advance.  If not, you suspend and resume your caller.</p>
<p>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.</p>
<p>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.</p>
<p>The semantics on await to make this abstract are ... well, interesting.</p>
<p>In any case, you can continue to have stackful coroutines, or do a transformation and make stackless coroutines act stackful.</p>

CC BY-SA 4.0
2023-07-21T18:31:56.750Z
2023-07-21T18:31:56.750Z
Yakk - Adam Nevraumont
CC BY-SA 4.0
2023-07-21T22:57:27.383Z
This stackless/stackful distinction sounds similar to delimited/undelimited continuations; is it the same? (e.g. https://www.researchgate.net/publication/228584945_Yield_Mainstream_Delimited_Continuations )
Warbo
CC BY-SA 4.0
2024-03-13T16:58:53.503Z
Delimited continuations are powerful enough to implement stackful coroutines. Stackless coroutines are less powerful and can be implemented with just first class functions, and correspond to the continuation monad in Haskell, where you basically use monadic return types (Task<T>) to CPS transform your code and have an event loop at the top that acts as a scheduler and trampoline. Implementations at the language level will optimize the Task<T> to a state machine
saolof
<p>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.</p>
<p>In practice, I think that MS's terminology of &quot;fibers&quot; 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.</p>
<p>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 &quot;the unix way&quot;, 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.</p>

CC BY-SA 4.0
2023-07-20T14:58:10.443Z
2023-07-20T14:58:10.443Z
Mark Morgan Lloyd
CC BY-SA 4.0
2023-07-20T15:09:49.540Z
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](https://en.wikipedia.org/wiki/Setcontext) in Posix. Things like [libuv](https://en.wikipedia.org/wiki/Libuv) seem to have taken over now. I'm not sure there is any question of using something as heavy as a process.
Bruce Adams
CC BY-SA 4.0
2023-07-20T15:16:07.737Z
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.
Mark Morgan Lloyd
CC BY-SA 4.0
2023-07-20T15:20:45.877Z
Yes indeed and both stackful and stackless coroutines have their place.
Bruce Adams
CC BY-SA 4.0
2023-07-20T21:07:52.503Z
@BruceAdams: Forking a process on early Unix was cheaper than doing an ordinary context switch, but that's because context switches were slow.  Context switching between threads in the same process space could have been an order of magnitude faster than context switching between processes.
supercat
CC BY-SA 4.0
2023-07-20T21:29:50.777Z
@supercat I'm uncomfortable with that: forking is the /creation/ of a new process while context switching is /between/ two already-created processes.
Mark Morgan Lloyd
CC BY-SA 4.0
2023-07-20T21:31:34.767Z
@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.
supercat
# Why do so few languages have this type of coroutine feature?
Posted by: username_0 on 2023-07-20
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?
**Tags:** coroutines generators
> **Comments:**
> **username_1**: It's definitely not limited to interpreted languages - Scala is a compiled language, and has [`LazyList.unfold`](https://dotty.epfl.ch/api/scala/collection/immutable/LazyList%24.html#unfold-fffff43a) to provide similar behaviour to `yield` (it's not a structure, but it could theoretically be turned into a structure)  
> **username_0**: @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.  
> **username_0**: (Or at least it seems that way to me. I am not a very experienced functional programmer and it might be that you can do that sort of thing more easily than I think you can.)  
> **username_1**: 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")  
> **username_2**: Python has the `yield from` construct to yield every item from some other generator. It appears to work similarly to the `~` construct in SuperCollider  
> **username_0**: @mousetail I didn't know about `yield from`, but it looks similar to SuperCollider's `embedInStream`. I don't think it lets you do what I'm asking about here, though there might be some non-obvious way in which it does. (`~` just indicates a global variable. I probably should have explained that. I've tidied up the code a bit so that point is less confusing and added some comments in the code about SuperCollider's syntax.)  
> **username_2**: @N.Virgo My apologies I misunderstood that syntax  
> **username_3**: Kotlin also has the `sequence` function that creates a `yield()`able closure  
> **username_4**: Are these yields 'lifted' out of the coroutine in the same sense as things are lifted by monads and applicative functors?  
> **username_5**: Python coroutines have nothing to do with `yield`, that’s just for generators. You can _implement_ coroutines using generators, but native coroutines in Python are something different.  
> **username_6**: So what happens in SuperCollider when you call a function that does `yield()` without wrapping it in a `Routine()`?  
> **username_0**: @Bergi you get a "yield was called outside of a Routine" error.  
> **username_6**: @N.Virgo So `~countDownFrom.(10)` wouldn't work outside of `~myRoutine`?  
> **username_0**: @Bergi right, it would throw an error.  
> **username_0**: @Bergi if that seems like an odd language design choice it might help to know that in SuperCollider everything inherits from Object, and yield is just a method of the Object class, not a keyword.  
> **username_6**: @N.Virgo Seems to me like it was more sensible if `yield` was a method of the `Routine` class… Regardless, it seems that the design decision comes down to verbosity and safety: is any function call allowed to suspend the current coroutine, or does it need to be explicitly annotated where in the control flow a suspension can happen?  
> **username_0**: @Bergi I don't think yield could easily be a method of Routine, because then you'd need to create the routine first, before you could call yield on it. In Supercollider yield is something that happens at runtime: it checks if there's an enclosing routine and yields to the routine's caller if so, throwing an error otherwise. That does mean any function call could potentially suspend the current routine, and I do see that that could cause issues with encapsulation.  
> **username_7**: I've dabbled in Supercollider myself. It didn't really occur to me that it works like this.  
> **username_8**: Lua has this feature.  
---
## 5 answers
### Answer by username_9 on 2023-07-20. Score: 16
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 countDownFrom(int n) {
    while (n > 0)
        co_yield n--;
}

std::generator> 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> 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.
> **Comments:**
> **username_0** (2023-07-20): "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.  
> **username_10** (2023-07-20): On interpreted vs compiled, I have issues with Crock's ["The Next Programming Language"](https://www.youtube.com/watch?v=R2idkNdKqpQ) 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](https://babeljs.io/docs/babel-plugin-transform-regenerator) plugin back-ported coros onto older JS engines via an SM rewrite for the latter.  
---
### Answer by username_12 on 2023-07-21. Score: 7
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.
> **Comments:**
> **username_13** (2023-07-21): This stackless/stackful distinction sounds similar to delimited/undelimited continuations; is it the same? (e.g. https://www.researchgate.net/publication/228584945_Yield_Mainstream_Delimited_Continuations )  
> **username_14** (2024-03-13): Delimited continuations are powerful enough to implement stackful coroutines. Stackless coroutines are less powerful and can be implemented with just first class functions, and correspond to the continuation monad in Haskell, where you basically use monadic return types (Task<T>) to CPS transform your code and have an event loop at the top that acts as a scheduler and trampoline. Implementations at the language level will optimize the Task<T> to a state machine  
---
### Answer by username_10 on 2023-07-20. Score: 6
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*](https://www.dabeaz.com/coroutines/Coroutines.pdf) explains trampolining as a way to allow delegation.

[*What is the difference between asymmetric and symmetric coroutines?*](https://stackoverflow.com/a/42042904/20394) 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*](https://en.wikipedia.org/wiki/Icon_%28programming_language%29).

Chapter 9 § Co-Expressions of [*THE ICON PROGRAMMING LANGUAGE*](https://www2.cs.arizona.edu/icon/ftp/doc/lb1up.pdf)

> 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.
> **Comments:**
> **username_6** (2023-07-21): Python has `yield from` where JavaScript has `yield*`. But in both cases, they're explicit keywords  
> **username_10** (2023-07-21): 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.  
---
### Answer by username_11 on 2023-07-28. Score: 4
> 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.
---
### Answer by username_15 on 2023-07-20. Score: 2
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.
> **Comments:**
> **username_4** (2023-07-20): 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](https://en.wikipedia.org/wiki/Setcontext) in Posix. Things like [libuv](https://en.wikipedia.org/wiki/Libuv) seem to have taken over now. I'm not sure there is any question of using something as heavy as a process.  
> **username_15** (2023-07-20): 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.  
> **username_4** (2023-07-20): Yes indeed and both stackful and stackless coroutines have their place.  
> **username_16** (2023-07-20): @BruceAdams: Forking a process on early Unix was cheaper than doing an ordinary context switch, but that's because context switches were slow.  Context switching between threads in the same process space could have been an order of magnitude faster than context switching between processes.  
> **username_15** (2023-07-20): @supercat I'm uncomfortable with that: forking is the /creation/ of a new process while context switching is /between/ two already-created processes.  
> **username_16** (2023-07-20): @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.  
---
