How Would One Implement Lazy Evaluation In C?

August 21, 2024 Post a Comment

Take for example, The follow python code: def multiples_of_2(): i = 0 while True: i = i + 2 yield i How do we translate this into C code? Edit: I am looking to transla

Solution 1:

You could try to encapsulate this in a 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;
}

Then you define you multiples with:

intnext_multiple(int current) { return2 + current; }
generatormultiples_of_2= {0, next_multiple};

You get the next multiple by calling

next(&multiples_of_2);

Solution 2:

I found a good article recently on coroutines in C, which describes one method of doing this. It's certainly not for the faint of heart.

Solution 3:

As Will mentioned, languages like python do the job of storing the state of the stack between successive calls of the generator. Since C does not have this mechanism, you'll have to do it yourself. The "generic" way of doing this is not for the faint-hearted, as Greg pointed out. The traditional C way of doing this would be for you to define and maintain the state yourself and pass it in and out of your method. So:

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

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

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

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

Solution 4:

The basic approach is to not do it. In Python (and C#) the 'yield' method stores local state between calls, whereas in C/C++ and most other languages the local state stored on the stack is not preserved between calls and this is a fundemental implementation difference. So in C you'd have to store the state between calls in some variable explicitly - either a global variable or a function parameter to your sequence generator. So either:

intmultiples_of_2() {
   staticint i = 0;
   i += 2;
   return i;
}

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

depending upon if there's one global sequence or many.

I've quickly considered longjmp and GCC computed gotos and other non-standard things, and I can't say I'd recommend any of them for this! In C, do it the C way.

Solution 5:

Check out setjmp/longjmp

setjmp.h is a header defined in the C standard library to provide "non-local jumps," or control flow besides the usual subroutine call and return sequence. The paired functions setjmp and longjmp provide this functionality. First setjmp saves the environment of the calling function into a data structure, and then longjmp can use this structure to "jump" back to the point it was created, at the setjmp call.

(Lua coroutines were implemented that way)

Python Guru