GC撲滅への道 - GC Advent Calendar
Garbage Collection Advent Calendarの5日目の記事です。
私はGCが嫌いです。GCは幼稚で礼儀知らずで気分屋で
甘やかすといつまでも動き、ほったらかすとセグフォする。
そんなGCのために、私達人間は何もする必要はありませんよ ♪
ということで、GC撲滅の1方法としてLinear Lispなるものを紹介します。Linear Lispは線形論理という論理に基づいたLisp処理系です。
元論文はこれです。
Lively Linear Lisp -- 'Look Ma, No Garbage!'
http://home.pipeline.com/~hbaker1/LinearLisp.html
線形論理については、ここのページが感動的なほどわかりやすいです。
線形論理って何？ (情報科学演習 III 課題紹介（小林研究室）)
http://web.yl.is.s.u-tokyo.ac.jp/kobalab/kadai99/linear-logic.html
線形論理はふつうはリソースとして扱わない数なんかもリソースとして考えるという説明。これも分かりやすいです。こういう子供を算数を出来ない子として切り捨てている例、結構ありそうですね。
1+1ができない子と線形論理 (檜山正幸のキマイラ飼育記)
http://d.hatena.ne.jp/m-hiyama/20070411/1176255532
Linear Lispはごみが出ないのです。ごみが出なければGCはいらないわけです。なぜごみが出ないかというと、常にすべてのオブジェクトのリファレンスカウントが１になるように、注意深く代入やCARなどのプリミティブ*1が定義されているからです。
プリミティブを見てみましょう。ただし、ATOMはLisp用語でリストじゃないものです。ここではNILとシンボルがATOMになります。
r1<->r2; /* r1,r2 の交換 */
r1<->CAR(r2); /* r1,r2 違うこと; r2はリスト */
r1<->CDR(r2); /* r1,r2 違うこと; r2はリスト */
NULL(r1); /* r1=NILの判定 */
ATOM(r1); /* r1=NIL か symbolp(r1)の判定 */
EQ(r1,r2); /* r1, r2がともにATOMの場合のみ有効; see [Baker93ER] */
r1:='foo; /* r1, 'fooはATOM */
r1:=r2; /* r1, r2はともにATOM */
CONS(r1,r2): /* r1,r2 違うこと; r2<-CONS(r1,r2) and set r1=NIL, frはfree list */
{r1<->CAR(fr); r2<->fr; fr<->CDR(r2);};
PUSH(r1,r2): /* r1,r2 違うこと; r2にr1をPUSHしr1=NILにする */
CONS(r1,r2);
POP(r1,r2): /* r1,r2 違うこと; r1がNILでなければCAR(r2)をr1に代入しr2からPOP */
if NULL(r1) and not ATOM(r2)
then {fr<->CDR(r2); r2<->fr; r1<->CAR(fr);}
else die;プリミティブを用いて、FREE, COPY, EQUALを定義します。
FREE(r1): /* 本質的にはKコンビネータ */
if not NULL(r1) then
if ATOM(r1) then r1:='NIL;
else
{PUSH(r2,sp); POP(r2,r1); /* temporary r2 ~= r1. */
FREE(r1); /* [footnote 4] free the cdr of the cell. */
r2<->r1; FREE(r1); /* free the car of the cell. */
POP(r2,sp);}COPYは元のリストは消えて２つのリストが作られます。
COPY(r1,r2): /* assert(r2=NIL). 本質的にはSコンビネーター */
if not NULL(r1) then
if ATOM(r1) then r2:=r1;
else
{PUSH(t1,sp); PUSH(t2,sp);
POP(t1,r1); COPY(r1,r2);
t1<->r1; t2<->r2; COPY(r1,r2);
t1<->r1; t2<->r2; PUSH(t1,r1); PUSH(t2,r2);
POP(t2,sp); POP(t1,sp);}EQUAL(r1,r2): /* 再帰的にリストをたどって等価性を判定する */
(or (and (ATOM r1) (ATOM r2) (EQ r1 r2))
(and (not (ATOM r1)) (not (ATOM r2))
(progn (PUSH t1 sp) (PUSH t2 sp) (POP t1 r1) (POP t2 r2)
(prog1
(and (EQUAL r1 r2)
(progn (<-> t1 r1) (<-> t2 r2)
(prog1 (EQUAL r1 r2)
(<-> t1 r1) (<-> t2 r2))))
(PUSH t1 r1) (PUSH t2 r2) (POP t2 sp) (POP t1 sp)))))これらを使うとこんな感じでもっと高レベルの操作も定義できます。
r1:=r2: /* r1, r2は異なっていること */
{FREE(r1); COPY(r2,r1);}
r1:=CAR(r2): /* r1, r2は異なっていること */
{r3<->CAR(r2); r1:=r3; r3<->CAR(r2);}
r1:=CDR(r2): /* r1, r2は異なっていること */
{r3<->CDR(r2); r1:=r3; r3<->CDR(r2);}
RPLACA(r1,r2): /* CAR(r1):=r2. r1, r2は異なっていること */
{r3<->CAR(r1); r3:=r2; r3<->CAR(r1);}
RPLACD(r1,r2): /* CDR(r1):=r2. r1, r2は異なっていること */
{r3<->CDR(r1); r3:=r2; r3<->CDR(r1);}これでEVALが構成できます。定義は長いので引用しません。論文のAppendix. Aを見てください。EVALが構成できるということはLispプロうグラムがGCから解放されるのです。素晴らしい。
再帰がちょいやりにくいとか些細な問題がありますが、まあ問題ないでしょう。
階乗はYコンビネーターを使ってこんな感じで定義するとよいでしょう。
(defun fact (f n) (if (zerop n) 1 (* n (funcall f f (1- n))))) (defun factorial (n) (fact #'fact n))
な、簡単だろ。じゃまものは消してしまえ。すみごこちのいい世界にしようじゃないか(藤子・F・不二雄 ドラえもん)
※ 効果には個人差があります
追伸
ナイーブに実装すると当然コピーの嵐になってまともな速度では動かないことが考えられるけど、論文の後半では効率よく実装するテクニックが紹介されています。
さらに、完全にごみを無くすのではなく、静的に解析してFREEできるところはFREEしてGCの頻度を減らすというアプローチも考えられます。
たとえば、
http://web.yl.is.s.u-tokyo.ac.jp/kobalab/kadai98/kadai3.html
では型推論の要領でプログラムを静的に解析してmalloc/freeを自動的に挿入するML Kit with Regionsなるものが紹介されています。
このページ中のML Kit with Regionsのページはリンク切れなので
http://www.it-c.dk/research/mlkit/index.php/Main_Page
に訪れるといいと思います。
