stackful v.s. stackless coroutine
2022年10月27日
coroutine （协程）是一般function的泛化。[1]一般function一旦开始运行，就必须运行到return（或抛出异常）。coroutine除了可以开始运行和return，还能在中间的某个地方休息一会儿，歇完了能在刚才停下的地方继续运行。coroutine在执行时中间暂停的能力，一般实现为yield关键字。
从这个定义上看，function是一种特殊的coroutine，其内部没有yield命令。[2][3]
从实现方式上来说，coroutine本身是一个抽象结构，它有很多种实现方式。比如，可以用多线程实现coroutine，也可以用单线程实现coroutine；coroutine yield时的状态可以保存在stack上e，也可以保存在heap上。
判断标准1：stackless coroutine typically refers to a state machine implementation whereas stackful coroutine refers to a thread implementation.
stackful coroutine也被叫做Fiber （纤程）。[4]
state machine-based coroutines, thus called stackless, can be hand-crafted or synthesized by a compiler by expanding syntax sugars.
既然可以用多线程实现stackful coroutine (Fiber)，那么线程与stackful coroutine有什么区别？
我们首先要研究线程是什么。在Linux，线程与进程是一样的，创建时由一个flag标记能共享哪些数据。[5]进程可以视作线程，因此可以自己独立运行，不需要再创建一个线程。而在Windows，线程是调度的最小单位，进程必须有一个线程。[6]另见Threading models。
CPython创建的两个线程不能在多核CPU上同时运行，只有进程才可以多核CPU上同时运行。
stackful coroutine作为caller调用另一个function（或coroutine？），caller似乎可以暂停callee，并且帮callee保存局部变量，以后resume的时候恢复。（那caller是怎么yield的？）
判断标准2：stackless coroutine是调用栈里的一帧。stackful coroutine是调用栈里自此以后的所有部分。[4]
stackless coroutine
我们先看几个stackless coroutine的例子。
static void Main(string[] args)
{
int n = 3;
foreach (int v in DoublePlus1(n))
Console.WriteLine(v);
}
static int Double(int n)
{
n = n + n - 1;
// can I yield here?
return n + 1;
}
static IEnumerable DoublePlus1(int n)
{
n = Double(n);
yield return n;
n = n + 1;
yield return n;
//return new List();
} 代码的输出是6、7。
DoublePlus1是stackless coroutine。我们不能说DoublePlus1是stackful coroutine。第一，DoublePlus1是一个function，运行时为一帧。stackful coroutine需要指调用栈里自此以后的所有部分。第二，如果这段代码创建stackful coroutine，那么DoublePlus1在内部调用Double，Double要能够在内部yield。而在C#，没有语法允许我们这么做。第三，用RedGate Reflector反编译该C#代码，发现yield return是一个语法糖，C#编译器帮我们展开成了class，里面MoveNext实现了一个状态机。这符合判断标准1，即C#的coroutine是stackless。
代码同时显示C#的coroutine是受限制的，它不是function的超集，因为它不能使用return关键字。我们把这种情况的coroutine叫做generator。
import dis
def Double(n):
n = n + n - 1
return n + 1
def DoublePlus1(n):
# return 30
n = Double(n)
yield n
n = n + 1
yield n
return 20
if __name__ == '__main__':
print(dis.dis(DoublePlus1))
# exit()
n = 3
# g = DoublePlus1(n)
# a = next(g)
# print(a)
# a = next(g)
# print(a)
# a = next(g)
# print(a)
for v in DoublePlus1(n):
print(v)可以用dis package查看代码被CPython解释后的bytecode，发现有YIELD_VALUE bytecode，说明yield在CPython里面是原生的关键字。
Python允许caller通过send命令向callee coroutine发送信息，参见《yield随想》。要注意，C#的yield是编译为状态机的，所以程序员可以手写一个IIterable class允许调用发发送信息。
在语法级别上，Python的coroutine比C#更好一点，因为Python允许coroutine使用return语句。然而，the returned value is not directly passed to the caller, but as a field value in the StopIteration exception. Python还有C#没有的yield from语法糖。
即便如此，Python只支持stackless coroutine。DoublePlus1 calls Double. Although Double can have a yield statement, but the execution then switches back to DoublePlus1, not all the way to the root. What is the root? 根据判断标准2，stackful coroutine是调用栈里自此以后的所有部分。如果你说Python可以从DoublePlus1创建stackful coroutine，那么DoublePlus1的sub-functions or descendant functions必须yield到main这一层。Python不论关键字还是类库都没有提供这个功能。
function* foo(index) {
while (index < 2) {
yield index;
index++;
}
return "done";
}
const iterator = foo(0);
console.log(iterator.next().value);
console.log(iterator.next().value);
console.log(iterator.next().value);ECMAScript 2015 (ECMAScript 6)开始支持yield。代码演示了这个。包含yield的function必须标记成function*，在一般的function context，yield不被允许使用。function*结构中允许使用return，相当于C#的yield return加yield break。JavaScript的coroutine没有用传统方式return的能力。
JavaScript提供yield*关键字，其作用跟Python的yield from一样。《Coroutine Event Loops in Javascript》用状态机模拟了JavaScript的原生yield，但根据判断标准1、2, coroutines in JavaScript are stackless。
var double = Fn.new {|n|
n = n + n -1
Fiber.yield(n)
return n + 1
}
var doublePlus1 = Fn.new {|n|
n = double.call(n)
//Fiber.yield(n)
n = n + 1
//Fiber.yield(n)
return "done"
}
System.print(doublePlus1.call(3)) // Line A
System.print("going to return")
return // Line B
var g = Fiber.new {
System.print("inside: " + doublePlus1.call(3).toString)
return "fiber"
}
System.print("outside: " + g.call().toString)
System.print("continue running ...")
System.print("outside: " + g.call().toString)代码里，Line B提前结束此程序，所以我们先看Line B之前的部分。两个function被定义，分别是double和doublePlus1。Wren定义function要用Fn.new，类似library call。double方法体里有yield语句，它同样类似library call而不是语言关键字。这些部分已经显示了Wren的不同之处——它可以在一般function内yield。
接着运行此代码，发现没有任何输出，甚至连"going to return"都没有输出，为什么？Wren implements stackful coroutine。代码在Line B之前，没有创建(stackful) coroutine，因此整个main函数被视作在一个大的、外层的(stackful) coroutine当中。所以double yield，就把整个main coroutine暂停了。这符合判断标准2。
Line B之后，Fiber g被创建。光看名字就知道，它是stackful coroutine。g没做啥别的，只是调用doublePlus1，最后return一个字符串。如果我们把Line A到Line B注释掉，整个程序的输出是
outside: 5 continue running ... inside: done outside: fiber
发现double yield，程序跳转到outside，尽管double is a subfunction inside a subfunction. double虽然有yield命令，像是coroutine，但它还可以用return关键字，return的内容像往常般地传给doublePlus1。Coroutine g可以用return关键字。
I will say the body of g is the entry point of the coroutine. The entry point is thus the stack frame marking the beginning of a coroutine. All frames including and after the entry point frame are in the coroutine. Any stack frame (or you call it function) in this stackful coroutine can yield. The data yield by the subsequent frames or returned by the entry point frame both are received by the previous frame of the entry point, i.e., the main function in 代码.
所以在一个支持stackful coroutine的语言里，你敢不敢直接调用一个方法，就像Line A所做的？不敢，因为就算doublePlus1自己没有yield，你无法保证其调用的子程序、子子程序没有yield。一旦doublePlus1的调用栈的任何一层yield，你整个程序都会暂停退出。所以在支持stackful coroutine的语言，你要在程序入口点尽快创建运行coroutine。
package main
import (
"fmt"
)
func double(n int) int {
ci := make(chan int)
n = n + n - 1
ci <- n
n = n + 1
return n
}
func doublePlus1(n int) int {
n = double(n)
n = n + 1
return n
}
func main() {
fmt.Println(doublePlus1(3)) //Line A
//go func(){fmt.Println(doublePlus1(3))}() //Line B
fmt.Println("done")
}把代码的点子用到go语言上，写成代码。一般人不仔细看，直接在main function里调用doublePlus1，程序就报错了。
fatal error: all goroutines are asleep - deadlock!
goroutine 1 [chan send]:
main.double(...)
/home/hjiaguo/co.go:11
main.doublePlus1(...)
/home/hjiaguo/co.go:17
main.main()
/home/hjiaguo/co.go:23 +0x3a
exit status 2
道理其实和Wren的情况是一样的。只不过，golang没有用yield这个词，double通过make关键字创建了一个channel，用channel发送数据，相当于yield。问题是，整段代码没有创建(stackful) coroutine，因此中间一个frame yield，整个程序就停掉了。
总结
我们先研究了coroutine的定义，和stackful、stackless的特征，然后调查了C#、Python、JavaScript、Wren、go这些编程语言对coroutine的支持情况。
C#、Python、JavaScript支持stackless coroutine；Wren、go支持stackful coroutine。stackless coroutine的创建和yield一般通过语言关键字实现；stackful coroutine的创建和yield一般通过类库调用实现。
golang的channel可以像参数一样传递，coroutine就可以对yield分类，灵活一点。Wren相当于只有一个channel。
| call | return | yield | resume | |
|---|---|---|---|---|
| C# | syntax error | |||
| Python | StopIteration | |||
| JavaScript | 相当于yield | |||
| Wren | ||||
| Go | 用channel发送消息 | 用channel接收消息 | ||
| runtime.Gosched | 运行时自动resume |
package main
import (
"time"
"fmt"
"runtime"
)
func sayHello(n int) {
for i := 0; i < 5; i++ {
time.Sleep(100 * time.Millisecond)
fmt.Printf("%v: hello ", n)
fmt.Println("world")
//runtime.Gosched()
}
}
func main() {
_ = runtime.Gosched //Golang requires all imports to be used.
go sayHello(1)
go sayHello(2)
go sayHello(3)
sayHello(4)
}如果代码没有runtime.Gosched()，输出可能是交错的，如
1: hello world 2: hello world 3: hello world 4: hello world 4: hello 2: hello world world 3: hello world 1: hello world
线程4输出完hello，刚要输出
《有栈协程与无栈协程》用C++和assembly code基于stack实现了(stackfu) coroutine。
async/await
https://blog.varunramesh.net/posts/stackless-vs-stackful-coroutines/
参考资料
- Christopher D. Marlin; . Coroutines A Programming Methodology, a Language Design and an Implementation. . 1980, (): 16 [].↑
- Aleksandar Prokopec and Fengyun Liu; . Theory and Practice of Coroutines with Snapshots. 32nd European Conference on Object-Oriented Programming. 2018, (): []. “Coroutines generalize subroutines”↑
- Konrad Anton and Peter Thiemann; . Typing Coroutines. TFP 2010. , (): []. “⊥ means that the expression will under no circumstance ever yield.”↑
- ; . Fibers under the magnifying glass . . , (): [].↑↑
- Ellen Spertus. Are Linux kernel threads really kernel processes?. . 2012-02-12 [2022-10-28].↑
- . Processes and Threads. Microsoft. [2022-10-28].↑
- ChayimFriedman2. What's the difference between fiber and generator? . . 2021-03-17 [2022-10-30].↑