2年ほど前、ごみ集めのない（頭の悪い）LISPを実装した （スライド, コード）。 日本語の情報がスライドだけというのもイマイチなので、 記憶が薄れないうちに日本語の文章を書こうと思っていたら、 いつの間にか2年も経過してしまい、すっかり記憶が薄れてしまった。 そんなわけで詳細を書くのは諦め、趣向を変えて、オチの部分だけを書く。 ついでにもう少しまともなプログラムについて妄想する。
いきなりだがこれがオチだ。このオチを理解するためには、 「ごみ集めのないLISP処理系」 「LISP処理系の上で動くLISPプログラム」 「超循環評価器の上で動くLISPプログラム」 の三つの要素を理解する必要がある。順番に説明していく。
C言語のようなごみ集めのない言語でLISPインタプリタを書くことを考える。 素直に実装しようとすると、自分で（C言語で）ごみ集めを書く必要があり、 これがなかなかに面倒だ。かといって、単純に実装をサボってしまうと （生きているオブジェクトの数にかかわらず）有限個のオブジェクトしか 作ることができず、これでは面白くない。 なんとかして、ごみ集めを実装せずに、 （生きているオブジェクトの数が有限であれば） 無限のオブジェクトを作る方法はないか。 そこで思いついたのが、リングバッファの上にオブジェクトを割り当てる方針だ。
void* alloc() {
if (alloc_head >= cons_area_end) {
alloc_head = cons_area_begin;
}
void* ret = reinterpret_cast<void*>(alloc_head);
alloc_head += kWordSize;
return ret;
}
新しいオブジェクトを作るたびに古いオブジェクトが消えていく。 なんとも新陳代謝が良さそうな方針だ。 古いオブジェクトを触らないようにするのは、 この上でプログラムを書くLISPプログラマの責任ということにする。 この方針をとればLISPインタプリタを書くのは非常に簡単だ。
こんなごみ集めのない頭の悪いLISP処理系の上では普通のLISPプログラムは動かない。 例えば次のような0からnの総和を求める関数を考える。
(defun sum (n)
(if (eq n 0)
0
(+ (sum (- n 1)) n)))
(sum 100)
残念ながらこのプログラムは動かない。何が悪いのか考えてみよう。 まず再帰呼び出しを使っているが、これはスタックフレームを必要とする。 LISPのスタックフレームは例のリングバッファに割り当てられるため、 古いものからどんどん壊れていく。 この問題は末尾再帰でスタックフレームを積み重ねないようにすれば解決する。
しかし、末尾再帰を使っただけではまだプログラムは動かない。 sumという関数の定義自体がリングバッファに置かれているため、 （一時データがリングバッファに溜まっていくと） 関数定義が壊れてしまい、途中で末尾再帰ができなくなってしまう。 この問題を解決するには関数定義が消えないように、 再帰呼び出しのたびに関数定義をコピーしてやればいい。 ちょうどラムダ計算の不動点演算子を使った式のようなことをする。
(setq sum
'(lambda (fn n acc)
(if (eq n 0)
acc
(fn (copy fn) (- n 1) (+ acc n)))))
(sum sum 100 0)
こんな感じで工夫をしてやれば、ごみ集めのない頭の悪いLISP処理系でも 任意のLISPプログラムを動かすことができる。 具体的には超循環評価器（LISPのevalをLISP自身で書いたもの）を書ける。 どんなプログラムになるか知りたい人は compile.sh の生成するコードを見てほしい。
そんなわけで、ごみ集めのない頭の悪いLISP処理系でも工夫をすれば 超循環評価器が動くのだが、この超循環評価器の上で動くLISPプログラムを考える。 実は超循環評価器の上では普通のLISPプログラムが動くのだ。
(defun sum (n)
(if (eq n 0)
0
(+ (sum (- n 1)) n)))
(sum 100)
これは元々の「ごみ集めのないLISP処理系」の上で動かなかったプログラムだが、 その上で動く超循環評価器の上では普通に動作する。 これは超循環評価器が実質的にオブジェクトの生死を判断しているからだ。 先程「sumをコピーする」例を見たが、これを一般化すると 「まだ使うものをコピーする」ことになり、 これは実質的に「生存しているオブジェクトをコピーする」のと同じである。 つまりcopying GCだ。「工夫」というのは手でcopying GCを書くことだったのだ。
「ごみ集めのないLISP処理系」はオブジェクトの生成と（実質的な）削除に集中し、 「LISP処理系の上で動く超循環評価器」はオブジェクトの生死判定に集中し、 「超循環評価器の上で動くLISPプログラム」は本来動かしたいプログラムに集中する。 最終的には普通のLISPプログラムが動くようになるのだが、 超循環評価器を書く過程で実質的にごみ集めを書いている。つまり、 「ごみ集めを書かずにLISP処理系を作るとLISPでごみ集めを書くことになる」 というオチがやってくるわけだ。
もちろんこのプログラムはただのジョークだ。 頻繁にオブジェクトをコピーし続けることになり、実行速度はひどいものになる。 また、まともにプログラムを書くためには超循環評価器が必須なのもいただけない。 ただ、ごみ集めをLISPで書けるという一点だけはよかったので、 ここをもう少し掘り下げる。
「C言語（など）でLISPインタプリタを書くが、ごみ集めの部分はLISPで書く」 といったことはできるだろうか。 ぱっと思いつくのは、メモリが足りなくなったときに、 LISPの関数を呼ぶという方式だ。
void* alloc() {
if (alloc_head >= cons_area_end) {
enable_gc = false;
alloc_head = eval("(gc)");
enable_gc = true;
}
void* ret = reinterpret_cast<void*>(alloc_head);
alloc_head += kWordSize;
return ret;
}
LISPから低レベルのメモリ操作をできるようにしたり、 ごみ集め中は通常とは違うところからメモリを割り当てたり、 色々と工夫は必要だろうが、基本的にはこれで動きそうな気はする。
速度はどうだろうか。雑な数字だが、 インタプリタを一段かませると10倍から100倍程度遅くなるという経験則がある。 それに基づくと、この方式はごみ集めが10倍程度遅くなることになる。 これはあまりうれしくない数字だろう。
速度が問題ならコンパイルすれば良い。 一度LISPインタプリタが手に入れば、その上でLISPコンパイラを書くのは （気合を十分に入れれば）それほど難しくない。 なにせLISPでコードを書けるのだから。
そんなわけで、まずは（ごみ集めが10倍遅い） LISPインタプリタでLISPコンパイラを書き、 そのLISPコンパイラでLISPで書かれたごみ集め関数をコンパイルする。 これでごみ集めが本来の（C言語などで書いた場合と同等の）速さで動作するはずだ。
コンパイラの生成するコードにはごみ集めのためのコードが含まれる可能性があるが、 ごみ集めのためのコードをコンパイルする際には、 ごみ集めのためのコードを生成しないようにしたり、 何らかの工夫がいるかもしれない。
本当はここで 「LISPでごみ集めを書いてコンパイルした完成品はこれです」 と言いたいのだが、私の気合が足りないためそのようなものは作っていない。 Ichigo Lispを改造すれば 比較的簡単にこの実験ができるかもしれないが、 それでもかなり面倒が予想されるため手を動かす気になれない。 困った。
2022-07-17