【译文】比较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:感谢云风的留言,修改了一些错误的地方。