自前LISPのGCの実装

昨日の続きで自分でLISPを実装した話をしていきます。

今回の実装でいちばんバグが多かったのは今日話すガーベジコレクタ（GC)ですね

GCとは動的に取ってきたメモリ領域を使われなくなった部分だけ開放するというものです。

まず、このような処理系を実装するのは初めてなので自分は王道がわかりませんでした。

それなので、静的記憶域、動的記憶域(スタック)と関数テーブルの中を探索してここは使われてますよっていう、チェックをつけました。
しかし、これだけでは変数が参照として持っているものが開放されてしまうので、チェックしたところの中の値を調べて参照ならまたその中を調べるを再帰的に繰り返すことで、必要なところ全てにチェックがつきました。
そして、これをコンパクションつまり、詰めて行きます。

そして、実行したら動きました。

しかし、GCを動かしたあとにたまに不具合が。
テストをいっぱいしていると不具合が起こるところに大体のパターンが見えてきました。
そのパターンはだいたいGCを走らせる前にヒープ領域の最初の方に入っていた変数たちです。
そして、よくよく考えるとコンパクションしたあとに変数に入っているポインタの値がコンパクションする前の値になってましたorzこれを直すとうまくうごきました。

GCの実装はやっぱりポインタのいろんな使い方がわかったのでかなりやった価値があった気がします。

現在ではGC自体の動作が重いのでどうにかして最適化していきたいな〜。