Generators in C

Question

I got this chunk of code I can't really comprehend.

I got stuck after it replaced pow2s's g to a map's gen structure. And from there, I can't see how it continues tracking the value, and how it is stored.

The code compiles and runs.

Can someone help me understand this code? Thanks!

PS: I'm learning C

It is translated from the follow Python code:

>>> def pow2s():
      yield 1
      for i in map((lambda x:2*x),pow2s()):
        yield i
>>> def mymap(f,iter):
      for i in iter:
        yield f(i)

And the translated C code:

#include <stdio.h>
#include <stdlib.h>

struct gen { // generic structure, the base of all generators
  int (*next)() ;
  int continue_from ;
} ;

typedef int (*fptr)() ; 

// Each iterator has 3 components: a structure, a constructor for the structure,
// and a next function

// map

struct mapgen { // structure for map
  int (*next)() ;
  int continue_from ; // not really required, provided for compatibility
  fptr f ;
  struct gen *g ;
} ;

int map_next(struct mapgen *p) { // next function for map
  return p->f(p->g->next(p->g)) ;
}

struct gen *map(fptr f, struct gen *g) { // constructor for map iterator
  struct mapgen *p = (struct mapgen *)malloc(sizeof(struct mapgen));
  p->next = map_next;
  p->continue_from = 0;
  p->f = f;
  p->g = g;
  return (struct gen *)p ;
}


// powers of 2

struct pow2s { // structure
  int (*next)() ;
  int continue_from ;
  struct gen *g ;
};

int times2(int x) { // anonymous lambda is translated into this
  return 2*x ;
}

struct gen *pow2() ; // forward declaration of constructor

int pow2next(struct pow2s * p){ // next function for iterator
  switch(p->continue_from) {
  case 0:
    p->continue_from = 1;
    return 1;
  case 1:
    p->g = map(times2,pow2()) ;
    p->continue_from = 2;
    return p->g->next(p->g) ;
  case 2:
    p->continue_from = 2;
    return p->g->next(p->g) ;
  }
}    

struct gen * pow2() { // constructor for pow2
  struct pow2s * p = (struct pow2s *)malloc(sizeof(struct pow2s));
  p->next = pow2next;
  p->continue_from = 0;
  return (struct gen *)p;
}

// in main, create an iterator and print some of its elements.

int main() {
  int i ;
  struct gen * p = pow2() ;
  for(i=0;i<10;i++)
    printf("%d ",p->next(p)) ;
  printf("\n");
}

Answer 1

The code shows how you can generate an arbitrary sequence of numbers
by means of 'generators'.

generators are a popular tool in dynamic languages like python and enable one to
iterate over an arbitrary long sequence without allocating the whole sequence at once.

The tracking happens in the lines

p->next = pow2next;
p->continue_from = 0;

Which tells p that it should call pow2next to obtain the next item in the sequence
and continue_from = 0 to indicate that where at the start of the sequence.

When you call p->next(p) it will in fact just call pow2next with p as it's parameter. For the first call this will simply return 1 and increment continue_from to 2.

switch(p->continue_from) {
 case 0:
    p->continue_from = 1;
    return 1;
/* ... */

On the second call (continue_from = 2) it will create a new map_gen structure working on a fresh struct pow2s and using the function times2:

case 1:
  p->g = map(times2,pow2()) ;
  p->continue_from = 2;
  return p->g->next(p->g) ;
/* ... */

All further calls go through p->g->next(p->g) which uses times2 and map_gen to retrieve the next value / create new map_gen structures as needed. All value tracking is done using the struct-member continue_from or by using return codes.

While showing an interesting approach to generators in C I have to state that this code leaks memory! As you can see it allocates new structures using malloc but it never free's them.

I hope this explanation is not to confusing even if you're just starting to learn C.
If you really want to understand generators you may like to have a little python ex-course ;)

UPDATE

As you stated in your comment none of the generators ever seems to return a value > 2.
The key to the increasing numbers lies in the function map_next:

int map_next(struct mapgen *p) {
    return p->f(p->g->next(p->g));
}

What this does is, instead of returning a fix, number it applies p->f()
(in our case the function times2() to the result of p->g->next(p->g).

This is a recursive call.

It will continue to call map_next() on each map_gen in the list until it reaches the last one.
This last element will return a fix value (either 1 or 2).
Which is then passed back to the previous call which will apply times2() on it and return the result to it's caller, which in turn will apply times2() on it and return the result to it's caller.... (you get the idea).

All these recursive calls sum up and form the final value.
If you print out the result of each pow2next() call you will get this:

/* first call */
  1
pow2next: returning 1
pow2next: returning 2  /* times2(1) */

  2
pow2next: returning 1
pow2next: returning 2 /* times2(1) */
pow2next: returning 4 /* times2(2) */

  4
pow2next: returning 1
pow2next: returning 2 /* times2(1) */
pow2next: returning 4 /* times2(2) */
pow2next: returning 8 /* times2(4) */

 8
pow2next: returning 1
pow2next: returning 2 /* times2(1) */
pow2next: returning 4 /* times2(2) */
pow2next: returning 8 /* times2(4) */
pow2next: returning 16 /* times2(8) */

16 

/* and so on */

You can see clearly how the result of the top most call is passed all the way back to the first call to form the result.