Cで継続渡し

できた。試行錯誤している内に無駄に凝った作りになってしまった。ここまで来ると完全に手段が目的と化しているな。

• fib.h:

#ifndef __FIB_H__
#define __FIB_H__

typedef void (*destructor_t)();

typedef struct object {
    int ref_count;
    size_t size;
    destructor_t destructor;
} *object_t;

void addRef(object_t obj);
void release(object_t obj);
object_t newObject(size_t size, destructor_t destructor);
void deleteObject(object_t obj);

typedef void* (*func_t)();

typedef struct closure {
    // inherited from object_t
    int ref_count;
    size_t size;
    destructor_t destructor;
    // own data
    func_t func;
    int var_num;
    void *vars[0];
} *closure_t;

closure_t newClosure();

#endif /* __FIB_H__ */

• fib.c:

#include <stdio.h>
#include <stdlib.h>

#include "fib.h"

void addRef(object_t obj)
{
    obj->ref_count++;
}

void release(object_t obj)
{
    obj->ref_count--;
    if (obj->ref_count <= 0) {
        if (obj->destructor)
            obj->destructor(obj);
        deleteObject(obj);
    }
}

object_t newObject(size_t size, destructor_t destructor)
{
    object_t obj = malloc(size);
#ifdef DEBUG
    fprintf(stderr, "malloc: %p\n", obj);
#endif
    obj->ref_count = 0;
    obj->size = size;
    obj->destructor = destructor;
    addRef(obj);
    return obj;
}

void deleteObject(object_t obj)
{
#ifdef DEBUG
    size_t size = obj->size;
    char *p = (char*) obj;

    // filled by `de ad be ef' ... pattern
    for (int i = 0; i < size / 4; i++) {
        *p++ = '\xde'; *p++ = '\xad';
        *p++ = '\xbe'; *p++ = '\xef';
    }
    switch (size % 4) {
        case 3: p[2] = '\xbe';
        case 2: p[1] = '\xad';
        case 1: p[0] = '\xde';
    }
#endif /* DEBUG */

    free(obj);

#ifdef DEBUG
    fprintf(stderr, "free: %p\n", obj);
#endif
}

closure_t newClosure(int var_num)
{
    size_t size = sizeof(struct closure) + sizeof(void*) * var_num;
    closure_t c = (closure_t) newObject(size, NULL);
    c->var_num = var_num;
    return c;
}

int fib_cps(int n, closure_t k);

static int fib_cps_2(int v2, closure_t k2)
{
    int v1 = (int) k2->vars[1];
    closure_t k = k2->vars[0];
    release((object_t) k2);
    return (int) k->func(v1 + v2, k);
}

static int fib_cps_1(int v1, closure_t k1)
{
    int n = (int) k1->vars[1];
    closure_t c = newClosure(3);
    c->func = (func_t) fib_cps_2;
    c->vars[0] = k1->vars[0];
    c->vars[1] = (void*) v1;
    c->vars[2] = (void*) n;
    release((object_t) k1);
    return (int) fib_cps(n - 2, c);
}

int fib_cps(int n, closure_t k)
{
    if ((n == 1) || (n == 2)) {
        return (int) k->func(1, k);
    } else {
        closure_t c = newClosure(2);
        c->func = (func_t) fib_cps_1;
        c->vars[0] = (void*) k;
        c->vars[1] = (void*) n;
        return fib_cps(n - 1, c);
    }
}

static int fib_cps_0(int n, closure_t k)
{
    release((object_t) k);
    return n;
}

int main(int argc, char *argv[])
{
    closure_t c = newClosure(0);
    c->func = (func_t) fib_cps_0;

    for (int i = 1; i < 10; i++) {
        addRef((object_t) c);
        printf("Fibonacci(%d) = %d\n", i, fib_cps(i, c));
    }

    release((object_t) c);

    return EXIT_SUCCESS;
}

見て分かる通り、参照カウンタを使って自前でオブジェクトの寿命を管理している。ガベージコレクションがない言語でクロージャを使うのがいかに大変かということがよく分かった。

なお、C99で拡張された機能を使っているので、gccでコンパイルする場合は

% gcc -Wall -std=c99 -DDEBUG fib.c

のように-std=c99を付けてコンパイルして下さい。