# Lua Coroutines Versus Python Generators

The next version of Javascript will apparently have a feature very much like Python generators; the alternative of Lua-style coroutines was rejected after a long debate which is summarised on [Neil Mix's blog].

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` loop:

```for label in coroutine.wrap(inorder), coroutine.yield, t do
-- something with label
end
```

or as a sort of `foreach` function:

```inorder(print, t)
```

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 `sum` and `islice` (first `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[1]) 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[1])
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
```

RecentChanges · preferences
edit · history
Last edited September 8, 2009 2:02 pm GMT (diff)