【译文】比较Lua协程与Python生成器

Translate from:

http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators

——————

Javascript1.7版有一个非常类似Python生成器(generator)的特性;而类似Lua协程风格的变体在经过长期讨论以后被拒绝(参考http://www.neilmix.com/2007/02/07/threading-in-javascript-17/

Python生成器与Lua协程有什么不同之处?Lua最重要的特性,coroutine.yield()是个一般函数,可以在coroutine.resume()动态扩展的任意位置被调用,限制是你不能yield操作C回调函数(除非你使用了Coco库)。在Python中,yield是一个语法,只能在生成器(generator)的语句体里存在。

这意味着Python生成器必须写成生成器形式,不能分解成更小的函数,也不能递归调用自身。你可以通过一个链的形式实现,有封讨论组的邮件http://mail.python.org/pipermail/python-list/2005-August/335545.html 描述了这种机制:

image

在Lua中,我们可以写神秘的(agnostic)inorder函数作为高阶函数(higher-order)。

image

这个Lua函数可以用作for loop里面的枚举器:

image

或者是类似foreach函数排序:

inorder(print, t)

我试图尽量简化递归型生成器的比较,写了一些简单程序生成infinite ruler function(http://www.research.att.com/~njas/sequences/A001511 )。关于这个函数的一个更有意思的网页是Michael Naylor的http://www.ac.wwu.edu/~mnaylor/abacaba/abacaba.html

Ruler function可以写成没有递归的形式。但是这个例子里它需要一些特性如深度优先搜索,所以我们还是看看递归实现方式。程序按顺序生成2 ^ K值,然后把它们加到一系列校验测试中。很容易知道ruler函数中前面2 ^ K个元素的和是2^(K+1) -1。Python内嵌函数及标准库可以很容易完成它;在Lua中,我不得不实现sum和islice函数,幸运的是这并不难。

所以Lua实现如下:

image

Python也非常类似:

image

这里面递归有些诡异,原因是我们手动改变尾调用为一个for loop,因为Python不支持尾调用,而且原始的尾调用实现使得Python数据更难看。

两个程序都可以通过检查,所以只粘贴一下比较结果。我不相信这仅仅是因为“Lua跑得比Python快”,真正原因应该是协程coroutine更快一些,主要不同的地方是不需要传递值到一系列yield中。

image

 

译者注:

关于Ruler function,可以参考wiki http://en.wikipedia.org/wiki/Thomae%27s_function

(后记,由于这方面知识的缺乏,翻译的非常蹩脚难懂,自己都感觉很难受,希望有达人能提出建议意见)

2010-6-14 Update:感谢云风的留言,修改了一些错误的地方。

《【译文】比较Lua协程与Python生成器》有6个想法

  1. higher-order function 通译 高阶函数。

    In an attempt to reduce the comparison of recursive generators to its minimum,

    reduce 的是 comparison ,此句指,作者想用最小的代码去比较递归生成器。

    btw, the infinite ruler function 是一个词组。

    the sum of the first 2^k elements of the ruler function is 2^(k+1)-1

    ruler function 的前 2^k 个元素之和是 2^(k+1)-1

  2. Python 3.3 之后新增了 yield from 语法,可以对子生成器展开。虽然还是不能像 Lua 一样将 coroutine 封装成普通函数,但是封装成一个需要特殊语法调用的子生成器是没有问题了。

  3. Python 3.3 之后新增了 yield from 语法,可以对子生成器展开。虽然还是不能像 Lua 一样将 coroutine 封装成普通函数,但是封装成一个需要特殊语法调用的子生成器是没有问题了。

发表评论