GC

最近サボってたけどGCが正しく動くようになった。アルゴリズムは保守的mark & sweep。
cons cellをたどるときはただ再起呼び出しをしているだけなので、スタックを消費してしてしまう簡易実装。
EmacsやRubyのソースを参考にしているので、ソースはかなり似ている。というか、もう確立した方法だから、あまり変なことはできない。どの言語でも保守的GCなら必ずグローバルオブジェクト、マシンスタック、シンボルテーブルはマークする。変わるところは実際にオブジェクトをマークするときの関数の中身くらい。スイープも確保したcellを全部なめてマークしていないcellをfreelistに追加するだけ。もう決まっている。

実装してみてわかったのは、双方向リストを作れる位のC言語の知識があればLispの基礎の部分は実装できるということ。シンボルテーブルも、環境も、S式の構築も解析も（線形探索になるから遅いけど）全てリストで実装できる。GCはリストを辿ることができれば最低限実装できる。

とりあえず一通りlisp処理系としての機能はそろったので、次はリファクタリングする予定。nil、undefined、eof、toplevelとかはobjectを確保するのではなく定数にしたい。
シンボルテーブルの終端にはnilが入っているが、freelistの終端はNULLだったり、トップレベル環境はNULLで表現していたりするので、ちょっと複雑なのがつらい。鶏と卵みたいになってて、シンボルテーブルの最後にnilを入れたりするのは泥臭くなってる。

あと、'()はシンボルのnilに変換されるけどnilを再定義したら'()が再定義した先を指すようになってしまうのは痛い、気がする。

こんな感じか

トップレベルでのset!でシンボルには値が関連付けられる。最初、シンボルnilに関連付けられているのはnilになっている。

nil.valueはnil
nilを評価するとnilが返る
'()はnilになるので、'()を評価するとnil.valueのnilが返る
nil.valueをシンボルのtにする。（トップレベルで(set! nil 't)もしくは(set! '() 't)）
nil.valueはt
'()はnilになるので、'()を評価するとnil.valueのtが返る
まずい！

ここまで書いて試したら、上に書いた様にははならなかった！

'()は(quote nil)になってた！
()がnilだった。
nilはtになった。
()はtになった。
(set! '() 't)は実行できなかった。

sbclではnilは定数扱いだから、代入不可だった。gaucheでも(set! () 2)や(set! '() 2)は不正。定数だから当たり前か。。。

つか、自分の書いたものぜんぜん管理できていないな。。文章も支離滅裂だし。