索引

もともとのfib関数の定義は，以下．

int fib(int n) {
    if (n <= 1) return 1;
    return fib(n-1)+fib(n-2);
}

この版は関数の入れ子定義をしているので，もちろん，Cでは動かない．．．

void fib(cont_t c, int n) {
    void fib_k1(int r1) {
        void fib_k2(int r2) {
            c(r1 + r2);
        }
        fib(fib_k2, n-2);
    }
    if (n <= 1) c(1);
    else fib(fib_k1, n-1); 
}

上記を適当にクロージャ変換してみる

void fib(/*fib_cls, */clos_t c_cls, int n) {
    func_t c = c_cls[0];
    if (n <= 1) c(c_cls, 1);
    else {
        void *fib_k1_cls[3] = { fib_k1, c_cls, (void*)n };
        fib(fib_k1_cls, n-1);
    }
}
 
void fib_k1(clos_t fib_k1_cls, int r1) {
    clos_t c_cls = fib_k1_cls[1];
    int n = (int)fib_k1_cls[2];
    void *fib_k2_cls[3] = { fib_k2, c_cls, (void*)r1 };
    fib(fib_k2_cls, n-2);
}
void fib_k2(clos_t fib_k2_cls, int r2) {
    clos_t c_cls = fib_k2_cls[1];
    int r1 = (int)fib_k2_cls[2];
    func_t c = c_cls[0];
    c(c_cls, r1 + r2);
}

Closureレコードはスタックに確保

#include <stdlib.h>
#include <stdio.h>
 
typedef void** clos_t;
typedef void *(*func_t)(void);
 
void *fib(void);
void *fib_k1(void);
void *fib_k2(void);
 
clos_t clos;
int arg1;
int arg2;
 
typedef void *record_t[3];
 
record_t stack[1024*1024*32];
int sp;
 
void *fib(void) {
    int n = arg2;
 
    if (n <= 1) {
        clos = (clos_t)arg1;
        arg1 = 1;
        return clos[0];
    }
    void **fib_k1_cls = stack[sp++];
    fib_k1_cls[0] = fib_k1;
    fib_k1_cls[1] = (void*)arg1;
    fib_k1_cls[2] = (void*)n;
    arg1 = (int)fib_k1_cls;
    arg2 = n-1;
    return fib;
}
void *fib_k1(void) {
    int n = (int)clos[2];
    int r1 = arg1;
    void **fib_k2_cls = stack[sp-1];
    fib_k2_cls[0] = fib_k2;
  /*fib_k2_cls[1] = c_cls;*/ 
    fib_k2_cls[2] = (void*)r1;
    arg1 = (int)fib_k2_cls;
    arg2 = n-2;
    return fib;
}
void *fib_k2(void) {
    clos_t c_cls = clos[1];
    int r1 = (int)clos[2];
    int r2 = arg1;
    sp--;
    arg1 = r1 + r2;
    clos = c_cls;
    return c_cls[0];
}
void *stop(void) {
    int r = arg1;
    printf("result: %d\n", r);
    exit(0);
}
 
int main(int argc, void *args[]) {
    void *c[1] = { stop };
    int n = atoi(args[1]);
 
    arg1 = (int)c;
    arg2 = n;
    func_t func = fib;
    while (func = func());
 
    return 0;
}

さらに，継続を関数ポインタからgotoラベルを用いた表現に変更（gccの拡張機能を使用）．

void fib(void) {
    void *c[1] = { &&l_stop };
    arg1 = (int)c;
l_fib:
{
    int n = arg2;
    if (n <= 1) {
        clos = (clos_t)arg1;
        arg1 = 1;
        goto *clos[0];
    }
    void **fib_k1_cls = stack[sp++];
    fib_k1_cls[0] = &&l_k1;
    fib_k1_cls[1] = (void*)arg1;
    fib_k1_cls[2] = (void*)n;
    arg1 = (int)fib_k1_cls;
    arg2 = n-1;
    goto l_fib;
}
// void *fib_k1(void) {
l_k1:
{
    int n = (int)clos[2];
    int r1 = arg1;
    void **fib_k2_cls = stack[sp-1];
    fib_k2_cls[0] = &&l_k2;
  /*fib_k2_cls[1] = c_cls;*/
    fib_k2_cls[2] = (void*)r1;
    arg1 = (int)fib_k2_cls;
    arg2 = n-2;
    goto l_fib;
}
// void *fib_k2(void) {
l_k2:
{
    clos_t c_cls = clos[1];
    int r1 = (int)clos[2];
    int r2 = arg1;
    sp--;
    arg1 = r1 + r2;
    clos = c_cls;
    goto *c_cls[0];
}
//void *stop(void) {
l_stop:
{
    int r = arg1;
    printf("result: %d\n", r);
    exit(0);
}
}
 
int main(int argc, void *args[]) {
    int n = atoi(args[1]);
    arg2 = n;
    fib();
    return 0;
}