python - lazy - ¿Cómo se implementaría una evaluación perezosa en C?

lazy evaluation

Question

Tomar como ejemplo,

El siguiente código de python:

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

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

Edición: Estoy buscando traducir este código de 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. Los múltiplos de 2 son simplemente un ejemplo para ilustrar el problema de los generadores de evaluación perezosos en C.

Answer 1

Como mencionó Will, los lenguajes como python hacen el trabajo de almacenar el estado de la pila entre 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 débiles de corazón, como señaló Greg. La forma tradicional de hacer esto sería que usted definiera y mantuviera el estado usted mismo y lo pasara dentro y fuera de su método. Asi que:

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 2

Echa un vistazo a setjmp/longjmp

setjmp.h es un encabezado definido en la biblioteca estándar de C para proporcionar "saltos no locales" o flujo de control además de la secuencia de retorno y llamada de subrutina habitual. 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" al punto en que se creó, en la llamada a setjmp.

( Lua coroutines se implementaron de esa manera)

Answer 3

El enfoque básico es no hacerlo. En Python (y C #), el método de ''rendimiento'' 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 conserva entre las llamadas y esta es una diferencia fundamental de implementación. Entonces, en C, tendría que almacenar el estado entre las llamadas en alguna variable explícitamente, ya sea una variable global o un parámetro de función para su generador de secuencias. Entonces, 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 muchas.

Rápidamente consideré las fotos de longjmp y GCC computadas y otras cosas no estándar, ¡y no puedo decir que recomendaría cualquiera de ellas para esto! En C, hazlo a la manera C

Answer 4

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

Answer 5

He implementado mi propia evaluación perezosa, con respecto a resolver el problema de Hamming.

Aquí está mi código para cualquier persona que esté interesada:

#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++;
  }
}

Answer 6

La clave es mantener el estado de la función entre las llamadas. Tienes un número 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 hacer que la función se llame a sí misma recursivamente, ni puede tener más de una persona que llama ejecutando diferentes secuencias de llamadas.

2. Inicializando (y posiblemente asignando) el estado en o antes de la primera llamada, y pasándolo a la función en cada llamada subsiguiente.

3. Haciendo cosas inteligentes con setjmp / longjmp, la pila o el código modificable (hay un artículo en alguna parte acerca de las funciones de currying en C que crea un objeto con el código necesario para llamar a la función curred; 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). ( Edit Found it - http://asg.unige.ch/site/papers/Dami91a.pdf )

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

En la práctica, los programas grandes en C desean computar las cosas con pereza, por ejemplo, un servidor de base de datos puede querer satisfacer una consulta SELECT ... LIMIT 10 envolviendo la consulta SELECT simple dentro de algo que producirá cada fila hasta que se hayan devuelto 10, en lugar de calculando todo el resultado y luego descartando 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 con él para cada llamada. Para su ejemplo, podría 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. Incluso una práctica mejor es devolver un puntero opaco en la new función y (a menos que esté disponible GC) 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 en 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;
}

(Tendrá que disculpar mi uso indebido de readdir, et al. Y mi pretensión de que C tiene soporte de cadena a prueba de idiotas).

Answer 7

Podrías intentar encapsular esto en una 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;
}

Luego te definimos múltiplos con:

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

Obtienes el siguiente múltiplo llamando

next(&multiples_of_2);

Answer 8

Puede pasar el argumento como un puntero para permitir que la función lo modifique sin usar el valor de retorno:

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

Y llámalo:

int i = 0;
multiples_of_2(&i);

Answer 9

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

El int estático se comporta como una variable global, pero solo es visible en el contexto de multiples_of_2 ().