generator functions in another language

[Gabriel Genellina]

En Sun, 04 May 2008 08:11:35 -0300, <castironpi at gmail.com> escribió:

> On May 4, 12:21 am, "Gabriel Genellina" <gagsl-... at yahoo.com.ar>
> wrote:
>> En Sun, 04 May 2008 01:08:34 -0300, Marc 'BlackJack' Rintsch <bj_... at gmx.net> escribió:
>>
>> > On Sat, 03 May 2008 16:39:43 -0700, castironpi wrote:
>>
>> >> I'm actually curious if there's a way to write a generator function
>> >> (not a generator expression) in C, or what the simplest way to do it
>> >> is... besides link the Python run-time.
>>
>> > The reference implementation of Python is written in C, so obviously there
>> > must be a way to write something like generators in C.
>>
>> Yes and no. Generators are tied to frames, and frames execute Python code, not C. There is no simple way to write generators in C, but there are some generator-like examples in the itertools module.
>> See this threadhttp://groups.google.com/group/comp.lang.python/browse_thread/thread/...
>
> Gabriel,
> How did your attempt turn out from last May?  At first look, it's
> outside the scope of Python, but it is not the scope of C
> necessarily.  Generators offer a lot of simplicity (which I haven't
> read about extensively, but am starting to see) that could gain some
> reputation for Python.  What is the midpoint at which C could meet
> Python?
>
> There is no such thing as a 'frame' per se in C; byte code is
> integral.  As there is no such thing as suspended state without
> frames, and no such thing as generators without suspended state.  It's
> a hard thing to Google for without knowing the prior terminology for
> the work that's already been done on them in C.  What work is there?
> Are any devs interested in pursuing it?

The frame and generator implementations are very tightly coupled to Python code, they aren't useful for implementing generators in C. Don't bother to read them.

Unfortunately, converting a C function into something like a generator isn't as easy as using the "yield" statement... Although the idea is simple, the implementation may be hard sometimes: You have to wrap the function within an object, maintain all state information into that object, and do all computation in the "next" method. Also, __iter__ should return itself so it can be called as an iterator.
(those objects are sometimes called "functors" <http://en.wikipedia.org/wiki/Function_object> not the same meaning as functors in Mathematics)

All examples that I have at hand are propietary code so I can't post them. The itertools module may be used as reference - "cycle" and "chain" are the easiest I think, although they might be *too* easy to understand the structure. "groupby" is a more complex example but at the same time harder to understand. See http://svn.python.org/projects/python/trunk/Modules/itertoolsmodule.c

Ok, I'll try to use Python code as an example. A generator for Fibonacci numbers:

def fibo():
     a = b = 1
     while True:
         a, b = b, a+b
         yield b

We can convert that function into this object; it should be written in C, not Python, but the idea is the same:

class fibo:
     def __init__(self):
         self.a = 1
         self.b = 1
     def next(self):
         temp = self.a + self.b
         self.a = self.b
         self.b = temp
         return temp
     def __iter__(self):
         return self

It behaves exactly the same as the generator above; we can even use the same code to test it:

py> for n in fibo():
...   if n>100: break
...   print n
...
2
3
5
8
13
21
34
55
89

Converting that class into C code should be straightforward. And then you have a generator-like function written in C.

-- 
Gabriel Genellina