大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

利用高阶函数来实现协程(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;
}