Primes using setjmp

I wrote a simple Haskell function, that gives a list of primes.

primes' :: [Int] -> [Int]
primes' (p : xs) = p : primes' (filter (\x -> x `rem` p /= 0) xs)

primes :: [Int]
primes = primes' [2 ..]

On each step it gives a filter of numbers not divisible by first element. As far as I understand, p is saved as a part of filter condition, and it saved on a stack by calling primes' recursively.

I want to implement the same behavior in C. I know that filter is a generator coroutine, and that such behavior can be implemented using either state variables, or setjmp.h, but I can't figure out how to do this.

Note that I don't want any arrays, in particular, I don't want to call malloc/realloc, and I understand that it might be a simpler approach in terms of C. I want to do this using stack memory, just as Haskell program does (although I understand that Haskell probably allocates memory for lists, to create a generator).

If there is a way to avoid setjmp by passing additional state argument it is probably better, but setjmp is fine.

Also, if there is any kind of mathematical analysis on these computations, it will be even better.

As I writing this, I start to think there is no way to avoid dynamic allocation, but I don't know how to prove it.

If the actual question is "how to do generators in C", you don't need setjmp/longjmp. A generator can be implemented simply as a closure: a structure of (a pointer to) an environment and a function pointer.

// generator of int
typedef struct {
  void* env;
  int (*next_)(void*);
} generator;

The next function yields the next value from the generator. The generator's next_ function is applied to its environment. That outputs the next value of the generator and modifies the environment for the next call.

int next(generator* g) {
  return g->next_(g->env);
}

For example, a counter generator uses an int as the environment, and next increments it and returns its old value.

int count_next(void* n) {
  return (*((int *) n))++;
}

A counter generator is allocated on the stack as follows:

// equivalent of "[2..]" in Haskell
int n = 2;  // counter state
generator count_from_two = { .env = (void *) &n, .next_ = &count_next };

The other generator in the prime sieve example is filter (\n -> n `mod` p /= 0) xs. The closure environment captures the parameters p and xs, so we create a struct:

typedef struct {
  int filter_div_p;
  generator* filter_div_xs;
} filter_div_env;

The following function keeps calling the underlying generator xs until it finds a value not divisible by p.

int filter_div_next(void* env) {
  int p = ((filter_div_env *) env)->filter_div_p;
  generator *xs = ((filter_div_env *) env)->filter_div_xs;
  int i;
  while (1) {
    i = next(xs);
    if (i % p != 0) {
      return i;
    }
  }
}

The equivalent of the Haskell primes function in your example is below. We take a generator xs as an argument (which contains the numbers not sieved out so far). Its next value p is a prime number. We output it, and we call primes recursively on a generator which filters xs with p, which is allocated on the stack.

void primes(generator* xs) {
  int p = next(xs);

  // do something with the prime number p
  printf("%d\n", p);

  // construct the generator (filter (\n -> n mod p /= 0) xs) and store it in variable fxs
  filter_div_env env = { .filter_div_p = p, .filter_div_xs = xs };
  generator fxs = { .env = (void *) &env, .next_ = &filter_div_next };

  primes(&fxs);
}

Full code:

#include <stdio.h>

typedef struct {
  void* env;
  int (*next_)(void*);
} generator;

int next(generator* g) {
  return g->next_(g->env);
}

int count_next(void* n) {
  return (*((int *) n))++;
}

typedef struct {
  int filter_div_n;
  generator* filter_div_xs;
} filter_div_env;

int filter_div_next(void* env) {
  int p = ((filter_div_env *) env)->filter_div_p;
  generator *xs = ((filter_div_env *) env)->filter_div_xs;
  int i;
  while (1) {
    i = next(xs);
    if (i % p != 0) {
      return i;
    }
  }
}

void primes(generator* xs) {
  int p = next(xs);

  // do something with the prime number p
  printf("%d\n", p);

  // construct the generator (filter (\n -> n mod p /= 0) xs) and store it in variable fxs
  filter_div_env env = { .filter_div_p = p, .filter_div_xs = xs };
  generator fxs = { .env = (void *) &env, .next_ = &filter_div_next };

  primes(&fxs);
}

int main() {
  int two = 2;
  generator count_from_two = { .env = (void *) &two, .next_ = &count_next };
  primes(&count_from_two);
}

Output:

2
3
5
7
11
13
17
19
23
29
...