"Generators" in Python (and C!) (was Re: "Python for LispProgrammers")

[Eric Kidd <address@hidden>]

On Sun, 2001-12-09 at 03:35, Michael Vanier wrote:
> Having been out of the perl loop for some time, I'm curious about this.
> How does perl support iterators?

In much the same fashion as C++ or Java.

Python 2.2, on the other hand, supports nifty co-routine iterators (it
calls them "generators"):

  from __future__ import generators

  def upto(n):
      for i in range(0,n):
          yield i

  def every_other(iter):
      skip = 0
      for i in iter:
          if not skip:
              yield i
          skip = not skip
 
  for i in every_other(upto(10)):
       print i

This will print:
 
  0
  2
  4
  6
  8

Note that these aren't full co-routines--they're only "one function
deep" (so you don't need separate stacks), and they only occur in
certain, special functions (so you don't need to muck up your
implementation just to get them working).

It's a nice technique.  And surprisingly enough, you can do it in
portable C, using a fantastically evil variant of Duff's device (see the
attached code for a good shudder).

You can also build these beasties on top of call/cc, if you have it.

Cheers,
Eric


#include <stdio.h>

/*=========================================================================
**  Generator Co-Routines in C
**=========================================================================
**  We want to compile the following Sather-inspired generator into
**  plausible C code:
**
**  iter twoway (n: int): int;
**    for (var i:int = 0; i < n; i=i+1)
**      yield i
**    end
**    for (var j:int = (n-1); j >= 0; j=j+1)
**      yield j
**    end
**  end
**
**  for (var i in twoway(10))
**    printf("next = %s\n", i)
**  end
**
**  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;
}