在C语言中的生成器

10

我有一段代码,但是我无法理解它。

在将pow2s的g替换为map的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");
}

1
在那里加入一些printf语句来查看它正在做什么,怎么样? - user181548
你能提供一些关于这个算法的背景吗?比如,你从哪里得到这段代码?它应该展示什么?等等。 - James Morris
我已经添加了上下文,这是从Python代码(生成器)翻译的。 - nubela
2个回答

10

下面的代码展示了如何通过 '生成器' 生成任意序列的数字。

生成器 是像 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结构,使用一个新鲜的structpow2s, 并使用函数times2:

case 1:
  p->g = map(times2,pow2()) ;
  p->continue_from = 2;
  return p->g->next(p->g) ;
/* ... */
所有后续调用都通过 p->g->next(p->g) 进行,它使用 times2map_gen 检索下一个值/根据需要创建新的map_gen结构来实现。所有值跟踪都使用结构成员continue_from或使用返回代码完成。
虽然这段代码展示了 C 中生成器的有趣方法,但我必须声明此代码会泄漏内存!正如您所看到的,它使用 malloc 分配新结构,但从未释放它们。
我希望这个解释不会让你感到困惑,即使你刚开始学习 C。如果你真的想理解生成器,你可能会喜欢一点 Python 的课程 ;)
更新:
正如你在评论中所说,“没有一个生成器似乎返回大于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(),直到到达最后一个元素。
这个最后一个元素将返回一个固定值(12)。
然后将该值传回给上一个调用,在其上应用 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 */

你可以清楚地看到最顶层调用的结果如何一直传递回第一个调用以形成结果。


感谢您清晰的解释。这是我的理解。在创建新的pow2()时, 调用next() -> 返回1, 调用next() -> p->g = map_gen1,使用新的pow2s返回21 调用next() -> p->g = map_gen1,返回22,并使用FRESH pow2s创建map_gen2在下一次调用时,我认为它会再次调用2*1,但似乎并不是这样?我哪里错了? - nubela

0
它通过增加一系列struct mapgen实例和times2实例的尾部来跟踪值。
每次调用pow2next都会向尾部添加另一对。
此示例的唯一价值在于说明高级语言对我们做了多少工作,以及高级概念的天真实现如何影响性能。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接