Как реализовать Lazy Evaluation в C?

Question

Взять, к примеру,

Следующий код Python:

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

Как мы можем перевести это в C-код?

Edit: я хочу перевести этот код Python в аналогичный генератор в C, с функцией next (). Чего я не ищу, так это как создать функцию в C для вывода кратных 2. Множители 2 - просто пример, иллюстрирующий проблему ленивых генераторов eval в C.

Answer 1

Вы можете попытаться инкапсулировать это в 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;
}

Затем вы определяете свои множители с помощью:

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

Вы получаете следующий кратный по телефону

next(&multiples_of_2);

Answer 2

Недавно я нашел хорошую статью о сопрограммах в C , в которой описан один из способов сделать это. Это, конечно, не для слабонервных.

Answer 3

Как уже упоминалось, такие языки, как python, сохраняют состояние стека между последовательными вызовами генератора. Поскольку C не имеет этого механизма, вам придется сделать это самостоятельно. «Общий» способ сделать это не для слабонервных, как указал Грег. Традиционный способ сделать это на C состоит в том, чтобы вы сами определяли и поддерживали состояние и передавали его в и из вашего метода. Итак:

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 4

Клавиша поддерживает состояние функции между вызовами. У вас есть несколько вариантов:

1. Статическое (или глобальное) состояние. Означает, что последовательность вызовов функции не является реентерабельной, т. Е. Вы не можете иметь рекурсивный вызов самой функции и не можете иметь более одного вызывающего абонента, выполняющего различные последовательности вызовов.

2. Инициализация (и, возможно, распределение) состояния во время или перед первым вызовом и передача его функции при каждом последующем вызове.

3. Выполнение умных вещей с помощью setjmp / longjmp, стека или изменяемого кода (где-то есть статья о функциях каррирования в C, которая создает объект с кодом, необходимым для вызова функции каррирования; подобный метод может создать объект с состоянием функции и необходимым кодом для сохранения и восстановления его для каждого вызова). ( Редактировать Нашел - http://asg.unige.ch/site/papers/Dami91a.pdf)

Грэг цитирует интересную статью выше, в которой представлен способ использования статического состояния с синтаксисом, похожим на оператор yield. Мне понравилось это академически, но, вероятно, я бы не стал его использовать из-за проблемы с повторным входом, и потому что я все еще удивлен, что печально известное Устройство Даффи даже компилируется ;-).

На практике большие программы на Си хотят лениво вычислять, например, сервер базы данных может захотеть удовлетворить запрос SELECT ... LIMIT 10, заключив простой запрос SELECT во что-то, что будет возвращать каждую строку до тех пор, пока не будет возвращено 10, вместо того, чтобы вычислять весь результат и затем отбрасывать большинство из них. Наиболее C-подобный метод для этого - явное создание объекта для состояния и вызов функции с ним для каждого вызова. Для вашего примера вы можете увидеть что-то вроде:

/* 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);
}

Это кажется громоздким для кратных двух, но становится полезным шаблоном для более сложных генераторов. Вы можете усложнить состояние без необходимости загружать весь код, который использует ваш генератор, деталями. Еще лучшая практика - возвращать непрозрачный указатель в функции new и (если GC не доступен) предоставлять функцию для очистки генератора.

Большим преимуществом выделения состояния для каждой новой последовательности вызовов являются такие вещи, как рекурсивные генераторы. Например, генератор, который возвращает все файлы в каталоге, вызывая себя в каждом подкаталоге.

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

(Вы должны будете извинить мое неправильное использование readdir и др. И мое предлог, что C имеет поддержку строки, защищенную от идиота.)

Answer 5

Вы можете передать аргумент как указатель, чтобы функция могла изменить его без использования возвращаемого значения:

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

И назовите это:

int i = 0;
multiples_of_2(&i);

Answer 6

Проверить setjmp / longjmp

setjmp.h - заголовок, определенный в C стандартная библиотека для обеспечения "нелокальной прыжки ", или поток управления помимо обычный вызов подпрограммы и возврат последовательность. Парные функции setjmp и longjmp обеспечивают это функциональность. Первый setjmp сохраняет среда вызывающей функции в структуру данных, а затем Longjmp может использовать эту структуру для «прыгнуть» обратно к тому, что было создано при вызове setjmp.

( Lua сопрограммы были реализованы таким образом)

Answer 7

Основной подход - не делать этого. В Python (и C #) метод yield сохраняет локальное состояние между вызовами, тогда как в C / C ++ и большинстве других языков локальное состояние, хранимое в стеке, не сохраняется между вызовами, и это принципиальная разница в реализации. Таким образом, в C вы должны явно сохранять состояние между вызовами в некоторой переменной - либо глобальной переменной, либо параметром функции для вашего генератора последовательности. Так что либо:

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

или

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

в зависимости от того, существует ли одна глобальная последовательность или несколько.

Я быстро рассмотрел longjmp и GCC, вычисленные gotos и другие нестандартные вещи, и я не могу сказать, что порекомендую любую из них для этого! В C, сделай это способом C.

Answer 8

Я реализовал свой собственный ленивый eval, в отношении решения проблемы Хэмминга.

Вот мой код для всех, кому интересно:

#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 9

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

Статический int i ведет себя как глобальная переменная, но видим только в контексте multiples_of_2 ().