Генераторы в С

Question

Я получил этот кусок кода, который не могу понять.

Я застрял после того, как он заменил pow2s на структуру генов карты. И оттуда я не вижу, как он продолжает отслеживать значение и как оно сохраняется.

Код компилируется и запускается.

Может кто-нибудь помочь мне понять этот код? Спасибо!

PS: я учусь C

Это переводится из следующего кода Python:

>>> 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)

и переведенный код C:

#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

Код показывает, как вы можете генерировать произвольную последовательность чисел
с помощью 'генераторов' .

генераторы - это популярный инструмент в динамических языках, таких как python, который позволяет
итерация по произвольной длинной последовательности без выделения всей последовательности сразу.

Отслеживание происходит в строках

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

Что говорит p , что он должен вызвать pow2next , чтобы получить следующий элемент в последовательности
и continue_from = 0 , чтобы указать, что где в начале последовательности.

Когда вы звоните p-> next (p) , на самом деле он просто позвонит pow2next с p как параметр. Для первого вызова это просто вернет 1 и увеличит continue_from до 2 .

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

При втором вызове ( continue_from = 2 ) он создаст новую map_gen работающую структуру на свежую struct pow2s и использование функции times2 :

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

Все последующие вызовы проходят через p-> g-> next (p-> g) , который использует times2 и map_gen для получения следующего значение / создание новых map_gen структур по мере необходимости. Отслеживание всех значений выполняется с помощью struct-member continue_from или с помощью кодов возврата.

Показывая интересный подход к генераторам в C, я должен заявить, что этот код теряет память! Как вы можете видеть, он распределяет новые структуры, используя malloc , но никогда не free их.

Надеюсь, это объяснение не должно сбивать с толку, даже если вы только начинаете изучать C.
Если вы действительно хотите разбираться в генераторах, вам может понравиться небольшой курс Python;)

UPDATE

Как вы указали в своем комментарии ни один из генераторов никогда не возвращает значение> 2 .
Ключ к увеличивающимся числам лежит в функции map_next :

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

Вместо того, чтобы возвращать исправление, он применяет номер, к которому он применяется p-> f ()
(в нашем случае функция times2 () с результатом p-> g-> next (p-> g) .

Это рекурсивный вызов.

Он будет продолжать вызывать map_next () для каждого map_gen в списке, пока не достигнет последнего.
Этот последний элемент возвратит фиксированное значение ( 1 или 2 ).
Который затем возвращается к предыдущему вызову, который будет применяться times2 () к нему и возвращать результат вызывающему, который, в свою очередь, будет применять times2 ( ) и верните результат вызывающему объекту .... (вы поняли).

Все эти рекурсивные вызовы суммируют и формируют окончательное значение.
Если вы распечатаете результат каждого pow2next () вызова, вы получите следующее:

/* 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 */

Вы можете ясно видеть, как результат самого верхнего вызова передается полностью до первого вызова, чтобы сформировать результат.

Answer 2

Отслеживает значение, выращивая хвост экземпляров struct mapgen, смешанных с экземплярами times2

Каждый вызов pow2next добавляет еще одну пару к хвосту.

Единственное значение этого примера - это иллюстрация того, как много языков высокого уровня делают для нас, и как наивная реализация концепций высокого уровня может убить вашу производительность.