利用高阶函数来实现协程（Racordon 1812.08278）
协程的概念与实现
协程（coroutine）这一概念最早在1963年由Convay提出，虽然在上世纪80年代受到冷落，但在此之后，协程在Lua、Python、Ruby、Kotlin等诸多主流语言中都发挥了重要的作用。然而，包括Java、Swift等在内的很多语言并不能原生支持协程。本文作者提出了一种利用高阶函数来实现协程的方法，这可以应用于几乎所有编程语言。
协程和函数非常相像，通常来说，二者都接受若干参数，然后产生一定的结果。二者的区别在于，协程可以暂时挂起（通常会使用一个yield语句），保留其运行环境，并将控制权转交给另一个协程。在此之后，这一协程会重新获得控制权，继续运行直到再次挂起或终止。由于协程运行在同一个线程内，不存在资源共享的问题，无须使用锁，因而就避免了死锁的发生。
协程有很多不同的实现方法。这些方法间一个重要的分野就在于协程的实现是（全）对称还是半对称。所谓“（全）对称”，是指协程的切换可以发生在任意两个协程之间，而“半对称”则表示协程的切换只能在调用栈中直接的父/子（parent/child）之间发生。对称实现的协程有利于对整个流程进行更加全面的把控，而半对称的协程实现通常更容易理解、使用和调试。
这两种实现方式在最终的效果上并没有差异（参见de Moura & Ierusalimschy, 2009）
另一个重要的区别在于协程是否是“栈满”（stackfull）的。栈满的协程可以从调用栈的更深层被挂起，而非栈满的则不行。如果要在一个非栈满的协程实现环境下，编写一个异步非阻塞的程序，就要求所有函数都能作为生成器，并且所有的函数调用都要显式地调用内层嵌套函数的结果。
同样的，这两种实现方式在最终的效果上也没有差异。
本文方法是一个半对称非栈满的协程实现。
协程实现：生成器方法
原文图1 JavaScript利用生成器实现Fibonacci序列的计算
上图给出了一个在JavaScript中利用生成器（generator）来实现协程的例子。函数内部的while(true)并不会一直运行，而是每次在yield处暂时挂起，直到下一次的.next()被调用时才继续进行。
协程实现：高阶函数方法（本文方法）
在这一部分作者给出了一个更加简单的例子：利用协程实现两个元素的加法。
首先是生成器的实现：
function * f(n) {
const x = yield n
yield n + x
}
const add2 = f(2)
add2.next() //=>2
add2.next(3) //=>5
add2.next(5) //=>undefined (因为一共只有两次yield)
接下来是高阶函数版本的实现：
function f(n) {
let inst = 1
return function(x) {
switch (inst) {
case 1 : inst += 1; return n
case 2 : inst += 1; return n + x
default: break
}
}
}
const add2 = f(2)
add2() //=>2
add2(3) //=>5
add2(5) //=>undefined
利用高阶函数来实现协程的出发点很简单：大部分支持高阶函数的编程语言都实现了闭包（closure），而实现协程的关键就在于保存环境（现场），那么就可以借助于高阶函数的函数闭包，来保存协程挂起时的所在环境。与生成器版本相比，利用高阶函数实现的协程不需要使用额外的语法（function*/yield/next）。
同样的，可以用高阶函数来实现上一节中Fibonacci序列的例子。
function fib() {
let inst = 1; let a = null; let b = null
return function() {
while (true) {
switch (inst) {
case 1:
inst = 2; a = 1; b = 2
case 2:
inst = 3; return a
case 3:
inst = 2; const c = a; a = b; b = c + a
}
}
}
}
const f = fib()
f() //=>1
f() //=>2
f() //=>3
f() //=>5
f() //=>8
那么如果编程语言不支持闭包怎么办呢？那就需要自行实现类似闭包的保存环境机制，作者在附录中给出了一个C语言的例子，可以参考一下。
结语
这篇文章的内容到这里就介绍完了。用高阶函数的方式实现协程是不是很清晰明了呢？感兴趣的话，就亲自尝试一下吧！
附：Fibonacci序列生成器的C语言实现
// Emulation of first order functions.
typedef struct {
void* env;
void* (*fn)(void*);
} function_t;
void* apply(function_t closure) {
return closure.fn(closure.env);
}
// Rewriting of the fibonacci sequence coroutine.
typedef struct {
int inst;
int a;
int b;
} fib_env;
void* fib_fo(void* e) {
fib_env* fe = (fib_env*)(e);
while (1) {
switch (fe->inst) {
case 1:
fe->inst = 2; fe->a = 1; fe->b = 2;
case 2:
fe->inst = 3; return &(fe->a);
case 3:
fe->inst = 2; int c = fe->a; fe->a = fe->b; fe->b = c + fe->a;
}
}
}
function_t fib() {
fib_env* env = (fib_env*)(malloc(sizeof(fib_env)));
env->inst = 1;
function_t closure = { env, &fib_fo };
return closure;
}
// Example of invocation.
int main() {
function_t g = fib();
for (int i = 0; i < 10; ++i) {
printf("%i\n", *(int*)(apply(g)));
}
free(g.env);
return 0;
}
