How do Python generators differ from Lua coroutines? The most important feature is that in Lua,
coroutine.yield() is an ordinary function which can be invoked anywhere in the dynamic extent of a
coroutine.resume() with the limitation that you cannot
yield through a
C callback (unless you use MikePall 's [Coco] library.) In Python,
yield is syntactic, and can only be in the lexical body of the generator function.
This means that Python generators must be written as generators, and cannot easily be factored into smaller functions; nor can they easily be recursive. You can achieve recursion by a form of chaining; a message on the [Python mailing list] describes both the mechanism:
!Python def inorder(t): if t: for x in inorder(t.left): yield x yield t.label for x in inorder(t.right): yield x
In Lua, one might write a more agnostic
inorder function as a higher-order function:
function inorder(f, t) if t then inorder(f, t.left) f(t.label) return inorder(f, t.right) end end
The Lua function could then be used either as the iterator in a
for label in coroutine.wrap(inorder), coroutine.yield, t do -- something with label end
or as a sort of
In an attempt to reduce the comparison of recursive generators to its minimum, I wrote a pair of simple programs which generate the infinite [Ruler function]. (A more interesting page about this function is Michael Naylor's [Abacaba-Dabacaba] which includes a musical exploration.)
The ruler function can be generated non-recursively, but in this example it's standing in for something like a depth-first search, so we'll just look at the recursive implementation. The programs generate the first
2^k values in the sequence and add them up as a sort of validity test, since it's easy to show that the sum of the first
2^k elements of the ruler function is
2^(k+1)-1. Python's built-in functions and standard library were handy here; in Lua, I had to implement the
k elements of a sequence) functions myself, but fortunately that's not difficult.
So here's the Lua implementation:
function ruler(put, k) for i = 1, k do put(i) ruler(put, i-1) end end function eachruler() return coroutine.wrap(function() return ruler(coroutine.yield, 100) end) end function sumseq(k, f, o, s) local sum = 0 for v in f, o, s do k, sum = k-1, sum + v if k <= 0 then break end end return sum end local howmany = tonumber(arg) or 24 local now = os.clock() local sum = sumseq(2^howmany, eachruler()) local took = os.clock()-now print(("%2i: %7.3f seconds %i check %i"):format(howmany, took, sum, 2^(howmany+1)-1))
and the very similar and somewhat shorter Python implementation:
!Python from itertools import islice from sys import argv from time import clock def ruler(k): for i in range(1, k+1): yield i for x in ruler(i-1): yield x howmany = int(argv) now = clock() total = sum(islice(ruler(100), 2**howmany)) took = clock()-now print "%2d: %7.3f seconds %d check %d" % (howmany, took, total, 2**(howmany+1)-1)
The slightly odd formulation of the recursion is the result of manually changing the tailcall into a
for loop, because Python doesn't do tailcalls, and the original tailcall implementation put Python at even more of a disadvantage.
Since both programs passed the check, I'll only paste the comparative timings here (in seconds as reported above). I don't believe this is simply a "Lua is faster than Python" benchmark; I think it shows that coroutines are inherently faster; the main difference is not having to pass the values up through a chain of yields.
N Lua Python -- ----- ------ 12: 0.000 0.008 13: 0.000 0.023 14: 0.008 0.055 15: 0.016 0.109 16: 0.031 0.227 17: 0.078 0.469 18: 0.148 0.961 19: 0.305 1.961 20: 0.602 4.000 21: 1.211 8.148 22: 2.430 17.211 23: 4.820 40.094 24: 9.875 94.992