ややプログラム紀行

博士2年のプログラムに関する日記

C言語でSchemeの処理系を作ってみる②

前回の更新から１ヶ月経ってることに今気づいてびっくりしました
１ヶ月の間何もしてなかったわけじゃなく、実はもうScheme処理系も結構出来上がってるんですね

じゃあなんで１ヶ月更新してなかったんだよ！！っていうと、まあ単に忙しかったのもありますが、Scheme処理系がちゃんと完成させられるのか自信がなかったからです(言い訳
途中まで記事書いといて、この仕様じゃ詰むってことが発覚したりしたら怖いんでね、、、とりあえず末尾最適化は実装し終わり、call/ccもまあなんとかなりそうなんで今処理系に採用してる方針で記事にしていこうと思います

ちなみにですが、学校ではguileというScheme処理系が使われていますが、僕の作った処理系はguileの50倍遅いです！！！
まあわかりやすさ重視ということで目を瞑ってやっていきましょう…

ガベージコレクション

まずはガベージコレクションを考えていこうと思います
SchemeではC言語のように自分で明示的にmalloc/freeせずとも変数を用意できますが、この背景には自動でメモリ管理をしてくれるガベージコレクションというものがあるわけです

ガベージコレクションには様々なやり方があります

Copying方式

seesaawiki.jp
ざっくりいうと、メモリプールを2つ用意しておいて、ガベージコレクションするたびに使うメモリプールを切り替える方針です
強みとしては、GCするたびにオブジェクトが詰めて配置されるので、フラグメンテーションが発生しないという点ですかね

上のサイトに書いてある通り多くのScheme処理系に使われているらしいので最初はCopying GCを採用していましたが、アルゴリズムの性質上GCするたびにオブジェクトの位置が変わってしまうので、扱いには少し注意が必要になります

Mark & Sweep方式

seesaawiki.jp
とても直感的なアルゴリズムなので割と単純に実装できます
ルートオブジェクトから参照しているオブジェクトを辿っていってマークをつけていくマークフェイズと、マークのついていないオブジェクトの後処理を行うスイープフェイズの2つから成ります

今回処理系にはこちらを採用しました
理由としては、Copying方式と違いオブジェクトのアドレスは変わらないため途中でGCが行われても気にせず作業を続行できるので色々楽だからです
あと、本来Mark & Sweepはフラグメンテーションが弱点ですが、確保したいオブジェクトの型を統一してしまえばこの問題を回避できるからです
Obj型の配列にしてしまえばフラグメンテーションも何もないからですね

Reference Counter方式

seesaawiki.jp
(このサイトありがたすぎる)
参照カウンタ方式はスマートポインターなどで使われているので僕としては一番馴染み深いです
各オブジェクトに参照カウンタというものを付属させ、参照するたびに+1、参照をやめると-1していき、0になったら解放するという戦略です

僕のイメージですが、これをC言語で実装するのはC++と違ってクラスもないので結構めんどくさそう
あと循環参照といった、参照カウンタ特有の問題もついて回るのでなかなか難しい方式だと思います

コードの概略

今回はMark & Sweep GCを使い、処理系に登場するオブジェクトを全てObj型というものに統一することにしました、なかなか脳筋なやり方です*1

Obj型の構成は

typedef struct Object{
	enum TYPE type;
	Data data;
	struct Object* child;
	struct Object* next;
	short gc_mark;
}Obj;

こんな感じになっています、GCではchildとnextをどんどん辿っていく感じです
このObj型はScheme中の数字や文字列やシンボル、関数などありとあらゆるものを代入できるようになっているので、Mark & Sweep GCはObj型の配列を管理すればよく都合がいいわけです


まずMark & Sweep GCはObj型をたどるためのルートオブジェクトが必要なので、初期化すると共にルートオブジェクトをセットする関数を用意します

void initGC(int _size) {
	size = _size;
	pool = malloc(sizeof(Obj[size]));
	for (int i = 0; i < size; i++) {
		pool[i].type = UNDEFINED;
		pool[i].child = NULL;
		pool[i].next = NULL;
		pool[i].gc_mark = 0;
	}
	allocPtr = 0;
};

void setRootObj(Obj* _root) {
	root = _root;
}

size…メモリプールのサイズ
pool…メモリプール
allocPtr…メモリの現在地
root…ルートオブジェクト
です

オブジェクトを確保するたびにallocPtrを進めていって、allocPtrがメモリプールの端まで来たらGCを行います

Obj* newObj(enum TYPE type, Data data) {
	if (pool == NULL) return NULL;
	Obj* obj = NULL;

	int flag = 0;
	for (; allocPtr < size; allocPtr++) {
		if (pool[allocPtr].gc_mark == 0) {
			flag = 1;
			break;
		}
	}

	if (flag == 0) {
		runGC();
		
		for (; allocPtr < size; allocPtr++) {
			if (pool[allocPtr].gc_mark == 0) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) return NULL;
	}

	obj = pool + allocPtr;
	obj->type = type;
	obj->data = data;
	obj->child = NULL;
	obj->next = NULL;
	obj->gc_mark = 1;
	return obj;
}

allocPtrを進めつつgc_markが0になっているところを探す、もし見つからなかった場合はrunGC()でGCを行い、再度探してみる
確保できる場所が見つかったらObj型の初期化をする
って流れです

GCを行う関数ではマークフェイズとスイープフェイズを行う必要があります

static void runGC() {
	for (int i = 0; i < size; i++) pool[i].gc_mark = 0;
	allocPtr = 0;

	if (root == NULL) return;

	// mark
	markObj(root->child);

	// sweep
	sweepObj();
}

これstaticがついてるのはrunGC関数はgc.cファイルでしか使わないからです
まんまコードの通りですが、一度gc_markを全て0にしたらmarkObj関数でルートから辿れるオブジェクトをマークしたのち、sweepObj関数でマークのついていないオブジェクトの後処理を行います

static void markObj(Obj* obj) {
	if (obj == NULL) return;
	if (obj->gc_mark) return;

	obj->gc_mark = 1;
	markObj(obj->child);
	markObj(obj->next);

	if (obj->type == ENV_MEMORY) markObj(obj->data.p_env);
}

static void sweepObj() {
	for (int i = 0; i < size; i++) {
		if (pool[i].gc_mark == 0) {
			if (pool[i].type == STRING || pool[i].type == SYMBOL || pool[i].type == PROCEDURE || pool[i].type == BUILT_IN) {
				if (pool[i].data.name != NULL) {
					free(pool[i].data.name);
					pool[i].data.name = NULL;
				}
			}
			pool[i].type = UNDEFINED;
		}
	}
}

(ちょっと説明めんどい所があるのでそこは飛ばす(^^;)
markObjでは自分をまずマーク、次に自分の子(child)と隣(next)をmarkObjに渡すことで再帰的にやってます
sweepObjではメモリプールを端から見てってgc_markが0になっているとこの後処理をしてます

後処理ってなんだよ！！って感じですが、この処理系では文字列などもObj型に突っ込むためにObj型のdataという変数がなかなか無茶をしてくれています
Data型はunion(久しぶりに使った…)で、例えば文字列だったらdata.nameがchar*になっているわけです
で、data.nameにはmallocを使って文字列のメモリを確保しているので、後処理ではそれのfreeを行なっています
なんかGCなのに非効率ですが、Obj型で統一した代償ですね



だいたいMark & Sweep GCの主要な部分はこんな感じです
概略とか言いつつコードそのまま載せちゃいましたが、やってることはコードの通りですね

はじめに突貫で作った処理系はGCを搭載していませんでしたが、それだと流石にきつかったです
次は処理の流れとルートオブジェクト以下の説明をすると思います！

*1:C++であればクラスが使えるので親クラスにObjクラスを、そこから各種の型に継承していくという方式を取れますが、今回はC言語で指定されているので難しいですね ちなみにC言語で継承まがいのこともできるみたいです