Chibi Scheme のゴミ集め

Chibi Scheme の組み込み手続きは C 言語の関数で記述してあり、 C 言語の auto 変数をヒープ中の Scheme のセルに束縛しています。 そのため、 ゴミ集め時に C 言語のコール・スタックを調べる必要が生じ、 3 つの方式を処理系のビルド時に選べるようになっています。

  1. Boehm GC による保守なゴミ集め
  2. 組み込みマーク & スイープによる保守なゴミ集め
  3. 組み込みマーク & スイープによる完全なゴミ集め

保守なゴミ集めは、 コール・スタックとプロセッサのレジスタの退避値を使えば済みますが、 完全なゴミ集めのためには、 Scheme のセルへのポインタがコール・スタック中のどこにあるのかわかっている必要があります。 この目的のため、 Chibi Scheme は、 auto 変数へのリストを作成します。

struct scheme_root_list {
    scheme_value_t** root;
    struct scheme_root_list* next;
};

void scheme_gc_mark_root_list (scheme_t* ctx)
{
    struct scheme_root_list *list;

    for (list = ctx->root_list; list != NULL; list = list->next)
        scheme_gc_mark_cell (ctx, *(list->root));
}

auto 変数へのリストは C プリプロセッサ・マクロでポインタ・リストで作るようになっています。 それを展開すると、 コール・スタック中にポインタ・リストを作成するコードに展開されます。 概念上は次のようになります。

scheme_value_t* scheme_append2(scheme_t* ctx; scheme_value_t* a, scheme_value_t* b)
{
    scheme_value_t* res = SCHEME_NULL;
    scheme_value_t* p = SCHEME_NULL;
    scheme_value_t* t = SCHEME_NULL;

    // 完全なゴミ集め用のポインタ・リストのセル
    struct scheme_root_list gclist_a;
    struct scheme_root_list gclist_b;
    struct scheme_root_list gclist_res;

    // 完全なゴミ集め用のポインタ・リストに auto 変数を追加
    gclist_a.root   = &a;   gclist_a.next   = ctx->root_list;
    gclist_b.root   = &b;   gclist_b.next   = &gclist_a;
    gclist_res.root = &res; gclist_res.next = &gclist_b;
    ctx->root_list = &gclist_res;

    // append2 本体
    if (scheme_null (ctx, a)) {
        res = b;
    }
    else {
        res = p = scheme_make_pair (ctx);   // ゴミ集めする可能性あり
        scheme_set_car (ctx, p, (scheme_car (ctx, a)));
        a = scheme_cdr (ctx, a);
        while (scheme_pair_ques (ctx, a)) {
            t = scheme_make_pair (ctx);     // ゴミ集めする可能性あり
            scheme_set_car (ctx, t, scheme_car (ctx, a));
            scheme_set_cdr (ctx, p, t);
            a = scheme_cdr (ctx, a);
            p = t;
        }
        if (! scheme_null (ctx, a)) {
            scheme_error_cstr (ctx, "append2 - improper list");
        }
        scheme_set_cdr (ctx, p, b);
    }

    // 完全なゴミ集め用のポインタ・リストから auto 変数を削除
    ctx->root_list = gclist_a.next;

    return res;
}

ポインタ・リストにアドレスを書き込む auto 変数をスタック・メモリに割り当てることを C コンパイラに要求していることになります。 マーク & スイープなので、 ポインタの値をゴミ集めが変更することはないため、 volatile にする必要こそありませんが、 最適化の余地が狭くなる点では、 保守なゴミ集めよりも不利な気がします。