¿Cómo implementaría Lazy Evaluation en C?

Question

Tomemos, por ejemplo,

El código de seguimiento de pitón:

def multiples_of_2(): 
    i = 0 
    while True: 
    i = i + 2 
    yield i 

¿Cómo podemos traducir esto en código C?

Editar: Estoy tratando de traducir este código python en un generador similar en C, con la función next(). Lo que no estoy buscando es cómo crear una función en C para generar múltiplos de 2. Múltiplos de 2 es simplemente un ejemplo para ilustrar el problema de los generadores de evaluación perezosos en C.

Answer 1

Puede intentar encapsular esto en un struct:

typedef struct s_generator { 
    int current; 
    int (*func)(int); 
} generator; 

int next(generator* gen) { 
    int result = gen->current; 
    gen->current = (gen->func)(gen->current); 
    return result; 
} 

A continuación se definen los múltiplos con:

int next_multiple(int current) { return 2 + current; } 
generator multiples_of_2 = {0, next_multiple}; 

Se obtiene el siguiente múltiplo llamando

next(&multiples_of_2); 

Answer 2

Encontré un buen artículo recientemente en coroutines in C , que describe un método para hacer esto. Ciertamente no es para los débiles de corazón.

Answer 3

El enfoque básico es no hacerlo. En Python (y C#) el método 'yield' almacena el estado local entre llamadas, mientras que en C/C++ y en la mayoría de los otros idiomas el estado local almacenado en la pila no se preserva entre llamadas y esta es una diferencia de implementación fundamental. Entonces en C tendrías que almacenar el estado entre llamadas en alguna variable explícitamente, ya sea una variable global o un parámetro de función para tu generador de secuencia. Así que o bien:

int multiples_of_2() { 
    static int i = 0; 
    i += 2; 
    return i; 
} 

o

int multiples_of_2(int i) { 
    i += 2; 
    return i; 
} 

dependiendo de si hay una secuencia global o muchos.

He considerado rápidamente los gotos calculados con longjmp y GCC y otras cosas no estándar, ¡y no puedo decir que recomiende alguno de ellos para esto! En C, hazlo de la manera C

Answer 4

int multiples_of_2() { 
    static int i = 0; 
    i += 2; 
    return i; 
} 

La int estática me comporto como una variable global pero solo es visible dentro de múltiplos_de_2().

Answer 5

Salida

setjmp.h es un encabezado definido en la biblioteca estándar de C para proporcionar "no locales saltos", o flujo de control, además de la habitual llamada a subrutina y volver secuencia. Las funciones emparejadas setjmp y longjmp proporcionan esta funcionalidad . Primero setjmp guarda el entorno de la función de llamada en una estructura de datos, y luego longjmp puede usar esta estructura para "saltar" de nuevo al punto en el que se creó , en la llamada setjmp.

(Lua coroutines se implementaron esa manera)

Answer 6

puede pasar el argumento como un puntero para permitir la función de modificar sin necesidad de utilizar el valor de retorno:

void multiples_of_2(int *i) 
{ 
    *i += 2; 
} 

y lo llaman:

int i = 0; 
multiples_of_2(&i); 

Answer 7

Como se ha mencionado Will, lenguajes como Python hacen el trabajo de almacenar el estado de la pila entre las llamadas sucesivas del generador. Como C no tiene este mecanismo, tendrás que hacerlo tú mismo. La forma "genérica" ​​de hacer esto no es para los pusilánimes, como señaló Greg. La forma tradicional de hacer esto sería definir y mantener el estado usted mismo y pasarlo dentro y fuera de su método. Entonces:

struct multiples_of_two_state { 
     int i; 
     /* all the state you need should go in here */ 
}; 

void multiples_of_two_init(struct multiples_of_two_state *s) { 
    s->i = 0; 
} 

int multiples_of_two_next(struct multiples_of_two_state *s) { 
    s->i += 2; 
    return s->i; 
} 

/* Usage */ 
struct multiples_of_two_state s; 
int result; 
multiples_of_two_init(&s); 
for (int i=0; i<INFINITY; i++) { 
    result = multiples_of_two_next(&s); 
    printf("next is %d", result); 
} 

Answer 8

La clave es mantener el estado de la función entre llamadas. Tiene una serie de opciones:

1. Estado estático (o global). Significa que la secuencia de llamadas a la función no es reentrante, es decir, no puede tener la función de llamada de manera recursiva, ni puede tener más de un llamante ejecutando diferentes secuencias de llamadas.

2. Inicializar (y posiblemente asignar) el estado en la primera llamada o antes, y pasarla a la función en cada llamada posterior.

3. Haciendo cosas inteligentes con setjmp/longjmp, la pila o código modificable (hay un artículo en alguna parte sobre funciones de currificación en C que crea un objeto con el código necesario para llamar a la función al curry, una técnica similar podría crear un objeto con el estado de la función y el código necesario para guardarlo y restaurarlo para cada llamada). (Editar encontrado que - http://asg.unige.ch/site/papers/Dami91a.pdf)

Greg cita un artículo interesante, más arriba, que presenta una forma de usar estado estático con una sintaxis similar a la declaración yield. Me gustó académicamente pero probablemente no lo usaría debido al problema de reentrada, y porque todavía estoy sorprendido de que el infame dispositivo de Duffy compila ;-).

En la práctica, los programas de C grandes sí quieren calcular cosas perezosamente, p. Ej. un servidor de base de datos puede querer satisfacer una consulta SELECT ... LIMIT 10 envolviendo la consulta simple SELECT dentro de algo que producirá cada fila hasta que se hayan devuelto 10, en lugar de calcular el resultado completo y luego descartar la mayoría de ellos. La técnica más parecida a C para esto es crear explícitamente un objeto para el estado y llamar a una función para cada llamada.Para su ejemplo, es posible ver algo como:

/* Definitions in a library somewhere. */ 
typedef int M2_STATE; 
M2_STATE m2_new() { return 0; } 
int m2_empty(M2_STATE s) { return s < INT_MAX; } 
int m2_next(M2_STATE s) { int orig_s = s; s = s + 2; return orig_s; } 

/* Caller. */ 
M2_STATE s; 
s = m2_new(); 
while (!m2_empty(s)) 
{ 
    int num = m2_next(s); 
    printf("%d\n", num); 
} 

Esto parece engorroso para los múltiplos de dos, pero se convierte en un patrón útil para generadores más complicados. Puede hacer que el estado sea más complicado sin tener que cargar todo el código que usa su generador con los detalles. Una práctica aún mejor es devolver un puntero opaco en la función new y (a menos que GC esté disponible) proporcionar una función para limpiar el generador.

La gran ventaja de asignar el estado para cada nueva secuencia de llamadas es cosas como generadores recursivos. Por ejemplo, un generador que devuelve todos los archivos bajo un directorio, llamándose a sí mismo en cada subdirectorio.

char *walk_next(WALK_STATE *s) 
{ 
    if (s->subgenerator) 
    { 
     if (walk_is_empty(s->subgenerator)) 
     { 
      walk_finish(s->subgenerator); 
      s->subgenerator = NULL; 
     } 
     else 
      return walk_next(s->subgenerator); 
    } 

    char *name = readdir(s->dir); 
    if (is_file(name)) 
     return name; 
    else if (is_dir(name)) 
    { 
     char subpath[MAX_PATH]; 
     strcpy(subpath, s->path); 
     strcat(subpath, name); 
     s->subgenerator = walk_new(subpath); 
     return walk_next(s->subgenerator); 
    } 
    closedir(s->dir); 
    s->empty = 1; 
    return NULL; 
} 

(Vas a tener que disculpar mi mal uso de readdir, et al., Y mi pretensión de que C tiene soporte de serie a prueba de idiotas.)

Answer 9

he implementado mi propia eval perezoso, con respectos a resolviendo el problema del hamming

Heres mi código para cualquier persona interesada whos:

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

// Hamming problem in C. 

typedef struct gen { 
    int tracker; 
    int (*next)(struct gen *g); 
} generator; 

int twos_gen(struct gen *g) { 
    g->tracker = g->tracker + 2; 
    return g->tracker; 
} 

generator* twos_stream() { 
    generator *g = malloc(sizeof(generator)); 
    g->next = twos_gen; 
    g->tracker = 0; 
    return g; 
} 

int threes_gen(struct gen *g) { 
    g->tracker = g->tracker + 3; 
    return g->tracker; 
} 

generator* threes_stream() { 
    generator *g = malloc(sizeof(generator)); 
    g->next = threes_gen; 
    g->tracker = 0; 
    return g; 
} 

int fives_gen(struct gen *g) { 
    g->tracker = g->tracker + 5; 
    return g->tracker; 
} 

generator* fives_stream() { 
    generator *g = malloc(sizeof(generator)); 
    g->next = fives_gen; 
    g->tracker = 0; 
    return g; 
} 

int smallest(int a, int b, int c) { 
    if (a < b) { 
    if (c < a) return c; 
    return a; 
    } 
    else { 
    if (c < b) return c; 
    return b; 
    } 
} 

int hamming_gen(struct gen *g) { 
    generator* twos = twos_stream(); 
    generator* threes = threes_stream(); 
    generator* fives = fives_stream(); 

    int c2 = twos->next(twos); 
    int c3 = threes->next(threes); 
    int c5 = fives->next(fives); 

    while (c2 <= g->tracker) c2 = twos->next(twos); 
    while (c3 <= g->tracker) c3 = threes->next(threes); 
    while (c5 <= g->tracker) c5 = fives->next(fives); 

    g->tracker = smallest(c2,c3,c5); 
    return g->tracker; 
} 

generator* hammings_stream() { 
    generator *g = malloc(sizeof(generator)); 
    g->next = hamming_gen; 
    g->tracker = 0; 
    return g; 
} 

int main() { 
    generator* hammings = hammings_stream(); 
    int i = 0; 
    while (i<10) { 
    printf("Hamming No: %d\n",hammings->next(hammings)); 
    i++; 
    } 
}