Schemeをつくろう(18) GC作ってみた。
前回作ったSchemeの欠点を克服すべく第二段を作ろうかと。まったりペースでSchemeを作ります。
今回の目標は、
- 独自GC
- 末尾呼び出しの最適化
とりあえず2点を目標にしていきたいと思います。
まず
ペアと、数字オブジェクトを作りました。
これだけあればなんとかなるかな。
使ってるオブジェクトにチェックを入れる
参照があるものはチェックを入れて、
ペア-+->数字 U | U +->ペア-+->数字 U | U +->NULL
コレは消しちゃダメー。とフラグを立てる。
するっと
使ってないオブジェクトがわかるので、Nの立ってる奴を探して、
ペア->ペア->数字->数字->ペア->NULL U U U U N
freeして、繋ぎなおし。
ペア->ペア->数字->数字->NULL U U U U
綺麗になる。
実装
やってみると案外簡単。
#include <stdio.h> #include <stdlib.h> typedef struct object* object; typedef struct scheme* scheme; enum {T_NUMBER, T_PAIR}; enum {GC_USE, GC_NOT_USE}; struct pair { object car; object cdr; }; struct object { int type; union { int n; struct pair *c; } data; int gc_flag; struct object *gc_next; }; int malloc_counter = 0; void *xmalloc(int size) { malloc_counter++; return malloc(size); } void xfree(void *o) { malloc_counter--; free(o); } struct scheme { int object_counter; object gc_used; }; /* object */ object new_object(scheme scm, int type) { scm->object_counter++; object o = xmalloc(sizeof (struct object)); o->type = type; o->gc_next = scm->gc_used; scm->gc_used = o; return o; } void free_object(scheme scm, object o) { scm->object_counter--; switch(o->type) { case T_PAIR: xfree(o->data.c); break; } xfree(o); } /* objects */ object new_number(scheme scm, int n) { object o = new_object(scm, T_NUMBER); o->data.n = n; return o; } object new_cons(scheme scm, object car, object cdr) { object o = new_object(scm, T_PAIR); o->data.c = xmalloc(sizeof (struct pair)); o->data.c->car = car; o->data.c->cdr = cdr; return o; } #define cons(a, d) new_cons(scm, a, d) #define number(a) new_number(scm, a) object car(object o) { return o->data.c->car; } object cdr(object o) { return o->data.c->cdr; } object null(void) { return NULL; } int is_null(object o) { return o == NULL; } int is_pair(object o) { return !is_null(o) && o->type == T_PAIR; } int is_list(object o) { return is_null(o) || o->type == T_PAIR; } void display(object o) { if (o == NULL) { printf("()"); return; } switch(o->type) { case T_NUMBER: printf("%d", o->data.n); return; case T_PAIR: printf("("); for (;;) { display(car(o)); o = cdr(o); if (is_null(o)) { break; } else if (!is_pair(o)) { printf(" . "); display(o); break; } else { printf(" "); } } printf(")"); return; } } void newline(void) { printf("\n"); } /* gc */ void gc_clean_iter(scheme scm, object o) { if (o == NULL) return; gc_clean_iter(scm, o->gc_next); free_object(scm, o); } void gc_clean_all(scheme scm) { gc_clean_iter(scm, scm->gc_used); } void gc_check(scheme scm) { object o; for (o = scm->gc_used; o != NULL; o = o->gc_next) o->gc_flag = GC_NOT_USE; } void gc_mark_object(object o) { if (o == NULL) return; o->gc_flag = GC_USE; switch(o->type) { case T_PAIR: gc_mark_object(car(o)); gc_mark_object(cdr(o)); return; default: return; } } object gc_sweep(scheme scm, object o) { if (o == NULL) return NULL; else if (o->gc_flag == GC_NOT_USE) { object tmp = gc_sweep(scm, o->gc_next); free_object(scm, o); return tmp; } else { o->gc_next = gc_sweep(scm, o->gc_next); return o; } } /* scheme */ scheme scheme_init(void) { scheme scm = xmalloc(sizeof (struct scheme)); scm->object_counter = 0; scm->gc_used = NULL; return scm; } void scheme_end(scheme scm) { gc_clean_all(scm); printf("end : %d\n", scm->object_counter); xfree(scm); printf("malloc : %d\n", malloc_counter); } void gc_test(scheme scm, object o) { object copy = cons(car(o), cdr(o)); printf("check : %d\n", scm->object_counter); gc_check(scm); printf("copyを残す : "); display(copy); newline(); gc_mark_object(copy); scm->gc_used = gc_sweep(scm, scm->gc_used); printf("clean : %d\n", scm->object_counter); } int main(void) { scheme scm = scheme_init(); object o = cons(number(2), cons(number(1), null())); display(o); newline(); gc_test(scm, o); scheme_end(scm); return EXIT_SUCCESS; }
やっぱScheme作るのは楽しいっす。