Generatoren in C

Question

Ich habe dieses Stück Code, den ich nicht wirklich verstehen kann.

Ich blieb stecken, nachdem es pow2s g zu einer gen-Struktur einer Karte ersetzt. Und von dort kann ich nicht sehen, wie es den Wert verfolgt und wie er gespeichert wird.

Der Code wird kompiliert und ausgeführt.

Kann jemand mir helfen, diesen Code zu verstehen? Vielen Dank!

PS: Ich lerne C

Aus der Folge Python-Code übersetzt wird:

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

und die übersetzte 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

Es bildet den Wert von wachsenden ein Schwanz von struct mapgen Instanzen gemischt mit times2 Instanzen

Jeder Aufruf von pow2next fügt ano hinzu ther Paar an den Schwanz.

Der einzige Wert dieses Beispiels ist eine Illustration, wie viel Hochsprachen für uns tun und wie eine naive Implementierung von High-Level-Konzepten Ihre Leistung zunichte machen kann.

Answer 2

Der Code zeigt, wie Sie eine beliebige Folge von Zahlen
mittels ‚Generatoren‘ erzeugen kann.

Generatoren ein beliebtes Tool in dynamischen Sprachen wie Python und ermöglichen eine bis
Iterierte über eine beliebig lange Sequenz, ohne die gesamte Sequenz auf einmal zuweisen.

Die Tracking geschieht in den Zeilen

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

Welche p sagt, dass es pow2next nennen sollte das nächste Element in der Sequenz
und continue_from = erhalten 0 um anzuzeigen, wo am Anfang des Seque nce.

Wenn Sie nennen p> weiter (p) es in der Tat nennen nur pow2next mit p wie es Parameter ist. Für den ersten Anruf wird einfach zurückgegeben und continue_from zu .

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

Auf dem zweiten Aufruf (continue_from = 2) Es wird eine neue map_gen Struktur arbeiten auf einem frischen Struktur erstellenpow2s und mit der Funktion times2:

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

Alle weiteren Anrufe gehen durch p> g-> weiter (p> g) die times2 verwendet und map_gen den nächsten Wert abzurufen/erstellen neue map_gen Strukturen nach Bedarf. Die gesamte Wertverfolgung erfolgt mithilfe des Strukturelements continue_from oder mithilfe von Rückgabecodes.

Während ich einen interessanten Ansatz für Generatoren in C zeige, muss ich feststellen, dass dieser Code Speicher verliert! Wie Sie sehen, es ordnet neue Strukturen mit malloc aber nie frei ‚s ihnen.

Ich hoffe, diese Erklärung ist nicht einmal zu verwirrend, wenn Sie nur C zu lernen beginnen
Wenn Sie wirklich Generatoren wollen verstehen Sie ex-Kurs ein wenig Python haben mögen;)

UPDATE

Wie Sie in Ihrem Kommentar festgestellt haben, scheint keiner der Generatoren jemals einen Wert> 2 zurückzugeben.
Der Schlüssel zu den steigenden Zahlen in der map_next Funktion liegt:

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

Was dies bedeutet ist, sondern eine Korrektur der Rücksendung, die Zahl gilt es p> f()
(in unserem Fall der Funktion times2() das Ergebnis der p-> g-> next (p-> g).

Dies ist ein rekursiver Aufruf.

Es wird weiterhin map_next() auf jeder map_gen in der Liste nennen, bis es die letzte erreicht.
Dieses letzte Element gibt einen festen Wert zurück (entweder oder).
die dann zurück zum vorherigen Aufruf übergeben, die wird times2() auf sie anzuwenden und das Ergebnis zurück, um es Anrufer ist, was wiederum times2() auf sie anzuwenden und das Ergebnis an es ist Anrufer .... (Sie bekommen die Idee).

Alle diese rekursiven Aufrufe summieren sich und bilden den endgültigen Wert.
Wenn Sie das Ergebnis jedes pow2next ausdrucken() rufen Sie diese bekommen:

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

Sie deutlich die Art und Weise alle die sehen können, wie das Ergebnis der obersten Anruf zurückgeführt wird erster Aufruf, um das Ergebnis zu bilden.