BYR Achieve · 镜像论坛

早在第9期的《惊喜不断》节目中，我们介绍了Python的Coroutine，即：generator。 https://bbs.byr.cn/#!article/Linux/132235 为了方便不知道coroutine的伙伴们，介绍一下：coroutine，通常译作“协程”，是一种控制结构。和线程类似，也是两个相互平行的控制流，可以分别向前执行，但协程之间谁先执行谁后执行，是完全确定的，协程必须主动交出它的执行权，才会暂时停下来。不像线程，可以随时被抢占（preempt）。这使得协程非常适合“生产者、消费者”类的程序，生产者可以写成直线形（而不是回调式）的代码，甚至可以进行递归的函数调用，不断产生结果；消费者则在循环里不断从生产者那里拉取结果，处理完以后再让生产者继续。整个过程在同一个线程中进行，通信效率比多线程（指的是本地线程、native thread，就是需要内核配合的那种多线程）更高，适合大量并发，而计算并不是瓶颈的场合，如网络服务器。这一期《惊喜不断》比较3种编程语言：Ruby、Lua、Python里的协程实现，同时给热爱Python的程序员一点惊喜。而且这一期是为 @dzcs 制作的。 https://bbs.byr.cn/#!article/Python/22321 先看Ruby。这个flatten函数把一个嵌套的数组压缩成平板的数组。它运行在一个协程里，不断产生结果。它也是一个递归函数，用来处理嵌套的数组。 def flatten(obj) if obj.instance_of? Array for elem in obj flatten(elem) end else Fiber.yield obj end nil end f = Fiber.new do flatten([[1,2,3],[4,[5,6],7],8,[9,10]]) nil end while true x = f.resume if x == nil break end puts x end 然后是Lua，功能完全一样，代码也非常相似。 function flatten(obj) if type(obj) == "table" then for _,elem in ipairs(obj) do flatten(elem) end else coroutine.yield(obj) end end c = coroutine.create(function() flatten({{1,2,3},{4,{5,6},7},8,{9,10}}) end) while true do local _,x = coroutine.resume(c) if x == nil then break end print(x) end 最后是Python。读的时候留意#Why?那一行。 def flatten(obj): if isinstance(obj, list): for elem in obj: for yielded_thing in flatten(elem): # Why? yield yielded_thing else: yield obj f = flatten([[1,2,3],[4,[5,6],7],8,[9,10]]) try: while True: x = f.send(None) print(x) except StopIteration: pass 为什么？别的语言的协程里，函数都可以递归地调用自己，在内层函数里yield，为什么Python里必须要再来一层循环在里面，好像非得要用yield把里面yield出来的东西“转发”出去似的？ Python语言到底有什么特殊的？难道不是Python语言，而是Python语言的实现？为什么非要把Python设计或者实现成这个鬼样子，让 @dzcs 小朋友学起Python来这么痛苦？改成这样难道不行吗： def flatten(obj): if isinstance(obj, list): for elem in obj: flatten(elem) # 像别的语言一样，省掉内层循环，直接递归调用，行不行？ else: yield obj 大家猜一猜。 =================我是华丽的分割线==================== 下面公布答案。给不耐烦的人快速解释一下：官方Python使用的是stackful interpreter，而且generator.send方法也对应着一个C层次的函数调用，所以，这使得Python的generator只能有一个frame。官方Lua使用的是stackless interpreter，但它的coroutine.resume是用C层次的函数调用实现的，只不过，由于Lua实现的是非对称（asymmetric）coroutine，yield一定会回到resume所在的coroutine，所以这也不是问题。官方Ruby使用了swap_context做换栈（swapstack）操作，每个coroutine一个stack，所以即使实现symmetric coroutine也没有问题，就更不用说asymmetric coroutine了。下面说Python、Lua、Ruby的协程（coroutine）实现有什么不同。首先要详细介绍一下什么是协程。我们这里定义，协程是手动调度的多个独立的控制流。控制什么时刻从哪个协程跳到哪个协程，是完全由用户控制的。这和线程（thread）相对。多个线程理论上可以同时执行。实际实现的时候可能由操作系统或者运行时来调度，复用同一个执行单元（CPU核心），也可以在不同核上并行执行。在下面的讨论中，我们始终假设只有一个线程，在多个协程之间跳来跳去。可以认为，线程是执行者，协程是执行的内容。接下来，我们要好好解释一下什么是“栈”（stack）。 “栈”是用来记录嵌套的函数调用的执行环境的。一个“栈”里有很多“帧”（frame），每个帧表示一个函数的执行环境。比如，下面的程序： def baz(): print("I am here") def bar(): baz() def foo(): bar() 执行到baz里的print的时候，栈是这样的：栈上面有3个帧，分别是baz, bar和foo的。大家都知道，栈是一个“后入先出”的数据结构。而“函数调用”也是“后入先出”的：最里层的函数最后被调用，但最先返回。这和“栈”的形态是一样的。所以，函数调用一般用“栈帧”来实现。函数调用一次，增加一个帧，返回一次，去掉一个帧。但是这种结构是不适合“协程”的。“协程”是多个独立的控制流，每个都可以有嵌套的函数调用，可以各自独立地调用、返回。这时候，一个栈的模型就不适合了。为了解决这个问题，我们可以引入多个栈，一个线程在多个栈之间互相换。举个例子。就用上述的flatten函数为例，由于Python不支持完整的协程，这里就用Lua为例。主协程为了遍历一个列表中的元素，创建一个副协程。它们就有两个栈了。执行了coroutine.resume，线程从主协程跳到副协程，开始执行flatten({1,{2,3,{4,5},6},7,8})。 flatten会用coroutine.yield跳回主协程，同时带着一个值，这里，第一次会带回“1”。在主协程里，独立地调用print，打印它。这个print的帧是在主协程上的。当回到副协程以后，flatten会递归地调用它自己，来处理嵌套的列表{2,3,{4,5},6}和{4,5}。当副协程进行这样的递归调用的时候，它的帧会被压在副协程的栈上，这独立于主协程。主协程打印的时候，print还是压在主协程的栈上。如下图：可以看出，想实现协程，关键是如何实现多个栈，以及一个线程如何在多个栈之间互相跳来跳去。 ====我是朴素的分割线==== 接下来，我们来介绍“解释器”的实现方法。所谓“解释器”（interpreter）就是一个程序，它读另一个程序的源代码或者字节码，然后，读一个指令，执行一个指令，读一个指令，执行一个指令，如此这般，一切操作都是解释器做的，但效果就像是执行那个被解释的程序一样。解释器是实现编程语言的一种常用方式（另一种是“编译器”）。解释器很容易移植，实现简单，速度不一定快。官方的Python、Ruby、Lua语言的实现都是用解释器实现的。有函数调用的语言（现代的语言都有吧，起码Python、Ruby、Lua里都有函数）都会实现“栈”。但是，对于解释器来说，“栈”有两重含义。 1、第一重含义是解释器自己的栈。解释器也是程序，比如Python的解释器是用C语言写的。Python解释器在解释Python程序的时候自己也要调用函数，比如调用PyNumber_Add来计算两个数的和。这个栈其实就是C程序的栈，和其他C程序执行的时候的栈是一样的。我们暂且把这个栈称为“C栈”。官方Ruby、Lua的解释器也是用C语言写的，它们也有“C栈”。 2、第二重含义就是被解释的程序的栈。比如有一个Python函数叫flatten，里面有局部变量，它还会调用isinstance这个函数。Python解释器也要维护一个栈来记录Python应用程序的执行环境。一般来说，这个栈不是C栈，因为C栈里存的是解释器本身的局部变量等环境。Python程序的栈一般用手动定义的struct组成一个链表来表示。具体地说，对于官方Python解释器CPython来说，Python帧（frame）是这样定义的： typedef struct _frame { PyObject_VAR_HEAD struct _frame *f_back; /* previous frame, or NULL */ PyCodeObject *f_code; /* code segment */ PyObject *f_builtins; /* builtin symbol table (PyDictObject) */ PyObject *f_globals; /* global symbol table (PyDictObject) */ PyObject *f_locals; /* local symbol table (any mapping) */ PyObject **f_valuestack; /* points after the last local */ /* Next free slot in f_valuestack. Frame creation sets to f_valuestack. Frame evaluation usually NULLs it, but a frame that yields sets it to the current stack top. */ PyObject **f_stacktop; PyObject *f_trace; /* Trace function */ char f_trace_lines; /* Emit per-line trace events? */ char f_trace_opcodes; /* Emit per-opcode trace events? */ /* Borrowed reference to a generator, or NULL */ PyObject *f_gen; int f_lasti; /* Last instruction if called */ /* Call PyFrame_GetLineNumber() instead of reading this field directly. As of 2.3 f_lineno is only valid when tracing is active (i.e. when f_trace is set). At other times we use PyCode_Addr2Line to calculate the line from the current bytecode index. */ int f_lineno; /* Current line number */ int f_iblock; /* index in f_blockstack */ char f_executing; /* whether the frame is still executing */ PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */ PyObject *f_localsplus[1]; /* locals+stack, dynamically sized */ } PyFrameObject; 其中，f_back指向调用者的frame。这些frame在一起串成一个单向链表。上面说到了两种栈，一个是C栈，另一个是Python、Ruby、Lua语言的栈（暂且称为“应用栈”吧）。但是，要真正解释Python解释器对于coroutine的诡异行为，还需要解释两个词汇：stackful interpreter和stackless interpreter。 ======我是朴素的分割线====== 所谓stackful解释器，就是说，解释器通过自己的函数调用，来实现高级语言的函数调用。所谓stackless解释器，就是说，解释器实现高级语言的函数调用时，不会增加自己的C栈的高度。举个例子。我们设计一个简单的解释器，我们用一个interpret(Func *func)函数来解释一个高级语言函数func。如果这样实现： void interpret(Func *func, Frame *frame) { while(1) { inst = get_next_instruction(); switch(inst.op) { case OP_CALL: Func *callee = inst.callee; Frame *new_frame = create_frame(); new_frame->prev = frame; interpret(callee, new_frame); ... } } } 看到，interpret递归地调用自己（即：interpret(callee)）来实现函数调用。虽然有由Frame对象构成的应用栈，但是这样会使得C栈增长。调用了几个函数之后，C栈和应用栈的格局是这样的：其中C栈的每个frame是一个interpret函数的环境。如果interpret函数像下面这样实现： void interpret(Func *entry_function) { Func *func = entry_function; Frame *frame = new_frame(); while(1) { inst = get_next_instruction(); switch(inst.op) { case OP_CALL: Func *callee = inst.callee; Frame *new_frame = create_frame(); new_frame->prev = frame; func = callee; frame = new_frame; ... } } } 注意：这样的实现方法，interpret并不调用自己。这个函数随时维护一个局部变量func表示当前的函数，和一个变量frame表示当前函数的帧。调用函数的时候，只是创建一个新的Frame（应用帧），然后让当前的func和frame指向新的函数和帧。这种实现方法，可以不断创建应用帧来实现高级语言的栈；而由于interpret本身就是一个循环，C栈不会增高。所以，调用了几个函数以后，C栈和应用栈的格局是这样的：一般来说，我们认为stackless解释器更有优势——它更灵活，而且不会因为太多的递归使得C栈溢出（应用栈帧一般是在堆上分配的，很容易分配），但实现起来或许不如stackful解释器容易。我们现在知道了两种解释器——stackful和stackless——的区别，那么这两种不同的解释器和coroutine的实现有什么关系呢？ ======我是朴素的分割线====== Lua、Ruby、Python的官方实现中，只有Lua是用stackless解释器实现的，Ruby和Python的解释器都是stackful解释器。要实现coroutine，最主要的就是在多个栈之间切换。最理想的实现方式是stackless解释器，不管是函数调用，还是coroutine切换，都不增加C栈的帧。用图来描述，就像下图那样。看，C栈上始终只有一个帧。程序从第一个协程（栈）切换到第二个协程（栈），然后切换到第三个协程（栈），C栈上始终只有一个帧。这种实现可以保证程序随时可以从一个协程（栈）切换到任何一个协程（栈）。看图吧： Lua的协程应该是三个语言里最干净的，但是，很可惜，虽然Lua的函数调用是stackless的，但协程切换却是stackful的：它用C语言的函数调用来实现协程切换。看图：它每切换一次协程，就会在C栈上创建一个帧。看：想想，这样实现有什么问题？很明显，如果协程1切换到协程2，协程2切换到协程3，这时候协程3不能切换到协程1，因为协程1已经被C栈上的一个帧使用着。程序只能切换到一个全新的协程（栈），或者切换回上一个协程（栈）。嗯。是这样的。Lua每次只能用coroutine.resume切换到一个全新的协程，或者用coroutine.yield切换回上一个协程。这也意味着，Lua的协程是非对称的。（注：不要忘了Lua、Ruby、Python的协程都是非对称的），每个活跃（曾经被resume）的协程（除了第一个协程）都有一个“父协程”，yield的时候会切换到“父协程”，而resume的时候必须切换到非活跃（不曾被resume）的协程。这种非对称性便于用这种方法实现：resume的时候，会在C栈上创建一个新帧；yield的时候，会从C栈上去掉一个帧。下面讨论Ruby和Python的协程。 Ruby的解释器是stackful的。所以，Ruby程序每调用一个函数，Ruby解释器也会调用一个函数来解释它。这样，当Ruby程序嵌套地调用了多个函数之后，C栈上也会有对应的几个帧。这时候如果要切换协程，难道要把C栈上的帧都去掉，全都换成新的帧吗？应用栈是自己实现的，就是一个链表，好换；C栈是编译器编译出来的C代码压上去的，换C栈上的帧，可是真的不好办的。总不能全都拷贝走，然后把新的C帧都拷贝回来吧？（没那么简单，还有寄存器，尤其是callee-saved registers的问题，这真不好办。）所以，Ruby用了一种非常规的实现方法：Ruby里，每个协程都有一个自己的C栈。每次切换协程，就是让CPU把当前的C栈换成另一个C栈，这样应用栈也跟着换了，如下图。这样做理论上没有问题，但是，Ruby的C栈切换是用POSIX函数swap_context实现的，但这个接口被deprecated了，因为接口设计得不是很容易移植。下面就要说到大家期待以久的Python协程了。官方的CPython是stackful解释器，而且也没有切换C栈的方法。这种实现方法理论上是不能实现完整的协程的。但是，Python做了个折衷。Python的协程只能在应用栈的最下面的帧里yield。为什么？这回我们先来看图。当Python程序创建一个generator，它会创建一个应用帧（这里我就不说“栈”了）。反正应用帧是在堆上分配的，也不用管它具体在什么地方。看图： Python切换协程（即generator.send()）的时候，Python创建一个新的C栈的帧，来解释这个新帧。新帧重用“上一帧”所用的那个指针（就是PyFrameObject.f_back）来指向“父协程”。的最上面的帧。所以，一定程度上来看，Python里切换协程和调用函数差不错。看图： flatten可以调用函数，比如isinstance()。这会创建一个新的应用帧和一个新的C帧。如图：思考一下，isinstance()里能yield回主协程里的g()函数吗？显然不能。看C栈：C栈上中间还有interpret(flatten{1,2,{3,4},5})的C帧。如果要yield过去，怎么“跳过”或者“去掉”这个C帧呢？做不到。就算做到了，interpret(flatten{1,2,{3,4},5})执行的上下文也丢失了。所以，在Python里，必须等isinstance()返回了，回到flatten({1,2,{3,4},5})函数里，才可以yield。如图。yield的时候，C帧会被去掉（yield使用C层面的return实现的），而应用帧会被保留。所以，flatten({1,2,{3,4},5})的帧会变成一个“悬浮”的帧。g()函数可以再调用别的函数（比如print()），调用的时候创建print的应用帧和C帧，但flatten的应用帧不会丢失。之后，再给flatten的generator做send()的时候，还是像老样子切换到这个协程。注意到flatten里面有这一段： for yielded_thing in flatten(elem): yield yielded_thing 这里flatten(elem)会递归地创建一个flatten的应用帧，然后用同样的方法切换到那个协程。到最后，会创建多个flatten的帧，旧的帧是新的帧的“父协程”，而不是“上一帧”。如图：还是同样的原因，最里面的flatten({3,4})也是不能直接yield到g()的，只能一级一级地yield。每级都被yield yielded_thing这个语句递归地“转发”到它的父协程，直到转发到g()为止。这个过程中，每个flatten的C帧都会返回，但应用帧会保留。如图：递归地yield完了以后，恢复还是一级一级地恢复。如图（其实就是上一幅图反过来）： ========我是比较华丽的分割线======= 以上就是Python里为什么coroutine只能在最下面的frame里yield的原因了。官方的Python解释器使用stackful interpreter，同时又不能更换C栈，而且用C函数调用/返回的方法实现协程send/yield。这就导致Python语言里，不管是函数返回还是协程切换，都不能跳过已有的C帧，这就使得Python的协程非常受限。相比之下，Lua使用stackless interpreter，而Ruby可以切换C栈，所以都没有这个问题。所以，Python程序员们受苦了。 ================我是华丽的分割线================= 到这里，Python语言的coroutine的诡异用法的解读告一段落。enjoy~ （难道真的就完了吗？真的完了吗？真的完了吗？真的没有别的好说的了吗？敬请期待接下来的番外篇。）

惊喜不断15：为什么Python的coroutine这么特殊？