ガベージコレクション実装したいからLISP風インタプリタ作った
ガベージコクレクションは手を動かすまでがちょっと遠い
下記の記事で書いたように、私は今ガベージコレクションに夢中です。
少し勉強して、ガベージコレクションの難しさの1つは「実装してみる」までが遠いところなのではないかと思っています。
ガベージコレクションというのは、それ単体で成り立つものではなく、基本的にはプログラミング言語の処理系と一緒に実装されるものです。したがって「ガベージコレクションに入門するぞ〜」と意気込んで理論を勉強しても、実装する対象となる適切な処理系がない、という問題に直面することになると思います。
多分、多くの人がそうなったのでは？と勝手に予想しているんですが、どうなんでしょう。
少なくとも私はそうなりました。
現実の処理系は複雑で難しい
ガベージコレクションが実装されており、かつ日本語話者が関わりやすい処理系としてはまず CRuby が思いつきます。しかし CRuby においてガベージコレクタなどが実装されている gc.c は、現時点で 14,000 行を超えており、初心者にとって理解しやすいとは言えないでしょう。
CRuby 以外でも、たとえば私が普段書く JavaScript の処理系である JavaScriptCore や V8 もそうですが、大体の現実的な処理系には、パフォーマンスのために高機能なガベージコレクションが実装されています。
実際、CRuby はマーク&スイープですが、コンパクションもするし世代別GCだし、年長世代ではイクリメンタルGCもするようです。Web 開発を行う一人のプログラマとしてはこれらの高機能なガベージコレクションには感謝するばかりですが、一方で、ガベージコレクションの初心者としては理解するハードルが高すぎます。
それはそれとして、CRuby のガベージコレクションの全体感を把握するのに下記の記事が役立ちました。この記事を執筆されたのは Shopify の Ruby Infrastructure チームのエンジニアだそうです。
他にも、もっと簡単なガベージコレクションが実装された処理系をいじることも考えられます。たとえば SerenityOS の Web ブラウザである Ladybird に搭載されている JavaScript 処理系である LibJS なんかは、理解しやすいガベージコレクタが実装されています。
とはいえ、C言語やC++の経験がない私にとっては、人の書いたものを読んで改造するというのは難しいです。
それになにより、ちゃんと理解したいのであったら、自分で設計して失敗して後悔して直して、というサイクルを踏むのが一番良いと思ったので、小さなガベージコレクション付きの処理系を自分でイチから実装してみることにしました。
自分で作る
ということで worsp という小さな LISP 風言語の処理系を作りました。名前の由来は、筑波大学内の WORD編集部 室で git init されたため、「WORD の LISP」で worsp です。リポジトリは以下。
LISP ってあんまり知らなかったんですが、S式って多分パーサー書くの簡単そうだし、なんとなくインタプリタの実装も想像がつくなーと思ったので LISP 風を作ってみることにしました。
ガベージコレクタを実装するために処理系を作るので、ガベージコレクションがない言語で書いた方が良いんだろうなーと考えました。候補としてC言語、C++、Rust、Zigあたりが思い浮かびましたが、C言語が一番覚えることが少なくてすぐ手を動かせそうなのでC言語を選びました(Cの経験もほとんどないですが)。
これ以降はこの言語処理系およびその仕様を指して worsp と呼びます。
作戦
おおまかに、以下の作戦を立てました。
- まず最低限動くインタプリタを、テストありで書く。
- ガベージコレクタを実装して、テストをパスさせる。
また、「ガベージコレクタを実装するためにこのソフトウェアを書いているので、他のことはどうでも良い」と割り切ることにしました。たとえば、最低限動くインタプリタを書くときに、worsp内でオブジェクトとして扱うものも、そうでないもの(ASTとか)も、たくさん malloc するわけですが、とにかく全部 free しませんでした(別に動くし)。他にも色々雑なところがあります。
動くインタプリタを書く
まずパーサーを書きます。最初は Bison とかパーサージェネレータを使おうかとも悩んだのですが、使い方がわからなかったので、手で書くことにしました(これも割り切りですね)。
次に評価器というんですかね、抽象構文木から実際に実行していくところ書きます。木を再帰的に見ていって、式として評価して、結果のオブジェクトを割り付けていって、という感じです。多分普通？
パーサーは何度か書いたことがあるんですが、実際の処理系って書いたことがないので、ちょっと大変でした。特にレキシカルスコープと関数呼び出しを実現するあたりでちょっとハマりました。
そして、ここでできるだけたくさんテストを書いておきました。テストファイルは以下で、気づいたら1000行を超えていました。これのおかげですごい開発体験が良かったです。
とはいえ、テストを毎度実行する開発スタイルはちょっとめんどくさいので、インタプリタが動くようになったタイミングで REPL 的なやつを実装してみました。入力された文字列を式としてパースして評価して、シリアライズして表示するっていう単純なやつですが、こちらも開発体験の向上につながりました。
一応、簡単に言語仕様を説明しておきます。
データ型は整数と文字列と真偽値とリストと nil と関数があります。
こんな感じのS式で関数を呼び出します。組み込み関数として、基本的な四則演算と論理演算に加えて car cdr cons print を実装しています。
(+ 1 2 )
リストはこんな感じ
'(1 2 3 4)
特別なS式として、if、=(変数宣言と代入)、defun(関数宣言) があります。こんな感じで使います。
(if (= 1 1) (print "Hello") (print "World"))
(= a 3)
(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))
ガベージコレクタ書く
ここまで来ると、ついにガベージコレクタを書きはじめることができます。ガベージコレクタを書くといっても色々選択肢がありますが、今回は多分最も簡単であろうただのマーク&スイープを採用しました。
ガベージコレクタのために、以下の関数と構造体を実装しました。ガベージコレクションを導入する前はオブジェクトのメモリを確保するために malloc を使っていたところで、ここで作った allocate を使うようにします。
AllocatorContext 構造体
AllocatorContext 構造体は、ヒープの開始地点と終了地点のアドレスと、フリーリストの先頭へのポインタを持ちます。
後述する allocate 関数は引数としてこの AllocatorContext を受け取ります。メモリ割り付けを行うときに、この構造体に格納されている状態を使います。
また、今回はガベージコレクションを有効にしない gc_less_mode というフラグもこの構造体に含まれています。gc_less_mode では、メモリ割り付けは単純な malloc になります。
FreeCell 構造体
FeeCell はフリーリストの要素を表す構造体です。今回フリーリストは連結リストとして実装しました。したがって、FreeCell は次のような形をしています。
struct FreeCell {
struct FreeCell *next;
struct Object *object;
};
*object には、オブジェクトを格納する領域の中で空いているところへのポインタが入っています。
initAlocator 関数
initAllocator 関数はフリーリストやアロケータの初期化を行います。具体的には malloc で、予め決められたサイズ分だけオブジェクトのための領域を確保して、フリーリストを構築します。
ちなみに、今回はオブジェクトは全て同じサイズなので、#define OBJECT_SIZE 100 みたいにして定義された上で、sizeof(struct Object) * OBJECT_SIZE 分だけ malloc して、その分だけの要素を持つフリーリストを作ります。
そして前述の AllocatorContext 構造体のインスタンス(Cでこういう用語が正しいのかは知らない)を作ります。
mark 関数
mark 関数は、オブジェクトのマークを行います。マークの手法として、オブジェクトにマークビットをもたせる方法や、ヒープ外にマークビットのテーブルを確保する方法などがあると思いますが、今回は前者を採用しました(実装が簡単だから)。
引数で受け取ったオブジェクト(のポインタ)がすでにマークされていたら、何もしません。マークされていなければ、そのオブジェクトをマークします。また、自身の子供オブジェクトに対しても mark を呼び出します。今回実装したworspでは、リストのみが子供のオブジェクトを持つので、渡ってきたオブジェクトがリストだったら、その要素のオブジェクトに対しても mark を実行します。
markAll 関数
markAll 関数は、ルート集合に含まれるオブジェクトからすべての生きているオブジェクトをマークする関数です。今回はグローバル変数をルート集合として扱っています。
sweep 関数
sweep 関数はヒープの先頭から末尾まで走査して、死んでいるオブジェクト(マークされていないオブジェクト)をフリーリストにつなぎます。
gc 関数
gc 関数は markAll と sweep を順番に呼び出します。
allocate 関数
allocate 関数はフリーリストの先頭のオブジェクトのポインタを返します。
フリーリストが空いてないときは、gc を実行して、死んだオブジェクトをフリーリストにつないでから、フリーリストの先頭のオブジェクトを返します。それでもフリーリストがないときは普通にメモリが足りないということなので、Out of memory で失敗します。
前述の gc_less_mode が有効になっているときは、ここでただ malloc が実行されます。
感想
多分、一応簡単なケースでは動く？っぽいんですが、めちゃくちゃ不安定でダメダメな感じです(メモリが足りないときに out of memory って言わずに変なアドレスを指したり、segmentation faultしたりする)。けどガベージコレクションの理論を学ぶだけではわからなかったことが、実装して初めてわかった気もします。
次は、これを安定させるのもやりたいし、もっといろんなガベージコレクションアルゴリズムを実装したいです。次はスイープのあとのコンパクションするやつにするか、コピーにするか、悩んでいます。
それにそもそも本当に最低限の機能しかないLISP風なので、GCを実装してもあんまりちゃんと試せないんですよね。もっと言語としてまともなやつを作って試したい。
ただ、不安定でも動くだけのやつを実装するなら思っていたよりは簡単だなと思いました。多分作業時間合計しても24時間くらいしかかかりませんでした。ちゃんとやるとめっちゃ大変なんだろうとは思います。
Discussion