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

Ответ 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);

Ответ 2

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

Ответ 3

Как уже упоминалось, такие языки, как python, выполняют задачу хранения состояния стека между последовательными вызовами генератора. Поскольку 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);
}

Ответ 4

Основной подход - не делать этого. В Python (и С#) метод "yield" хранит локальное состояние между вызовами, тогда как в 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.

Ответ 5

Отъезд setjmp/longjmp

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

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

Ответ 6

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

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

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

int i = 0;
multiples_of_2(&i);

Ответ 7

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

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

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

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

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

На практике, большие программы на C хотят вычислить вещи лениво, например. сервер базы данных может захотеть удовлетворить запрос 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 поддерживает поддержку идиотов.)

Ответ 8

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

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

Ответ 9

Я реализовал свой собственный ленивый 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++;
  }
}