Chibi Scheme の組み込み手続きは C 言語の関数で記述してあり、 C 言語の auto 変数をヒープ中の Scheme のセルに束縛しています。 そのため、 ゴミ集め時に C 言語のコール・スタックを調べる必要が生じ、 3 つの方式を処理系のビルド時に選べるようになっています。
- Boehm GC による保守なゴミ集め
- 組み込みマーク & スイープによる保守なゴミ集め
- 組み込みマーク & スイープによる完全なゴミ集め
保守なゴミ集めは、 コール・スタックとプロセッサのレジスタの退避値を使えば済みますが、 完全なゴミ集めのためには、 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 にする必要こそありませんが、 最適化の余地が狭くなる点では、 保守なゴミ集めよりも不利な気がします。