C中的生成器

Question

我得到了一些我无法理解的代码.

在将pow2s的g替换为地图的gen结构后,我陷入了困境.从那里开始,我无法看到它如何继续跟踪价值以及如何存储价值.

代码编译并运行.

有人可以帮我理解这段代码吗？谢谢!

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)时,它实际上只是用p作为参数来调用pow2next.对于第一次调用,这将只返回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或使用返回码完成的.

虽然在CI中向生成器展示一种有趣的方法,但必须声明此代码会泄漏内存!正如你所看到的,它使用malloc分配新的结构,但它永远不会释放它们.

我希望这个解释不要混淆,即使你刚开始学习C.
如果你真的想了解发电机,你可能希望有一个小蟒蛇前课程;)

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_gen上调用map_next(),直到它到达最后一个. 最后一个元素将返回一个修复值(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 都会在尾部添加另一对。

这个例子的唯一价值是说明高级语言为我们做了多少事情，以及高级概念的幼稚实现如何影响你的性能。