Re: A Problem with Python's 'yield'

[Eric Kidd <address@hidden>]

On Tue, 2003-05-27 at 12:53, Jeremy Hylton wrote:
> On Tue, 2003-05-27 at 11:15, Eric Kidd wrote:
> > I'm going to pick on Python here, but only because the example code will
> > be short and sweet. :-) I believe several other implementations of
> > generators have the same problem.
> 
> I expect you'll find this limitation in every language that is
> imlemented using a C stack and recursion for function calls.  Python's
> generator are sometimes called "simple generators" because they are
> simple to implement.  There is only a single function call frame that
> needs to be kept around after a generator yields a value.

Actually, it's possible to implement a recursive yield_all in portable
ANSI C.  It's just ugly. :-)

I've attached some C code for the non-recursive case.  It (ab)uses
Duff's Device to temporarily suspend a C function.  Local variables of
the C function are lifted into a struct (as though you were implementing
a closure).

To generalize to the recursive case, you need to add a front-end
function which builds a stack (or linked list) of structs and keeps
track of which iterator is currently active.  If you do a bit of extra
work, you can ensure this front-end function only gets called for
recursive iterators, and let non-recursive ones run at full speed.

I think this is just about as evil as you can get within the constraints
of ANSI C.

> The Jython developers tell us they'd have trouble, too.

I haven't spent much time thinking about recursive iterators on the
JVM.  I suspect that the JVM doesn't like Duff's Device very much.

Cheers,
Eric


#include <stdio.h>

/*=========================================================================
**  Generator Co-Routines in C
**=========================================================================
**  We want to compile the following Sather-inspired generator into
**  plausible C code:
**
**  def twoway (n: int): int
**    for (var i: int = 0; i < n; i=i+1)
**      yield i
**    for (var j: int = (n-1); j >= 0; j=j+1)
**      yield j
**
**  for (var i in twoway(10))
**    printf("next = %s\n", i)
**
**  To do this, we abuse some interesting properties of C's switch
**  statement.  Much credit is due to Duff's device; all the blame is
**  due to me.
**
**  Eric Kidd
**  eric.kidd@pobox.com
*/

typedef struct {
    // Saved iteration state.
    int state;

    // Lift all the local bindings into an environment object.
    int n;
    int i;
    int j;
} twoway_env;
  
void twoway_init (twoway_env *env, int n) {
    env->state = 1;
    env->n = n;
};

#define GENERATOR_HEAD(env) switch ((env)->state) { case 1:
#define GENERATOR_QUIT(env) (env)->state = 0; return 0
#define GENERATOR_TAIL(env) case 0: GENERATOR_QUIT(env); }
#define GENERATOR_YIELD(env,n) (env)->state = (n); return 1; case n:

// Returns true iff it was able to find an element.
int twoway_next (twoway_env *env, int *yielded_value) {
    GENERATOR_HEAD(env);

    for (env->i = 0; env->i < env->n; env->i++) {
        *yielded_value = env->i;
        GENERATOR_YIELD(env, 2);
    }
    for (env->j = (env->n - 1); env->j >= 0; env->j--) {
        *yielded_value = env->j;
        GENERATOR_YIELD(env, 3);
    }
    GENERATOR_TAIL(env);
}

int main (int argc, char **argv) {
    twoway_env env;
    int i;

    twoway_init(&env, 10);
    while (twoway_next(&env, &i)) {
        printf("next = %d\n", i);
    }

    return 0;
}