リリカル☆Lisp開発日記

Kashiwa Schemeは、大学院の研究(ごみ集めの実装)が面倒になってきて、
なかば現実逃避気味に始めたのですが、
KASHIWAのごみ集めを作ったりするのが想像以上に面白くて、
わりとのめり込んでしまいました。

結果として、研究を放置しすぎてしまったので、
そろそろ研究にコンテキストスイッチしないといけないので、
今考えてることを忘れないようにメモしておきます。

私のためのメモなのでかなりテキトーに書きます。

—

KASHIWAの現状

• Chenery on the M.T.A.の概念は実装完了
• ごみ集めはスタックとヒープの2世代の世代別GC
• ただし、シンボルは別管理になっていて、この部分のGCは未実装
• あと、ライトバリアの実装が酷いので修正が必要
• 組み込みの手続きはまだちょっとしか実装していない
• 組み込みの手続きは書けばいくらでも増やせる
• 構文はlambda, if, set!, quoteなどプリミティブなものしか実装していない
• caseやandなどの構文はifなどのプリミティブな構文に展開するマクロとして書ける

今後の展望という名の妄想

• 最終目標はKASHIWAのコードをKASHIWA自身でコンパイルすること
• とりあえずの指標としてR5RSにほぼ準拠したらできるはず
• 衛生的なマクロは正直、実装しなくてもいい気がする
• 今の時代に作ってるんだからR7RS準拠とか目指したほうがいい気もする
• SchemeからCの関数を呼び出したり、CからSchemeの手続きを呼び出したい
• 余力があればヒープのなかも2世代くらいに分割して世代別GCしたい
• 元気が有り余っていたらマルチスレッドとか考えたいけど、そんなに元気はない

今後考えないといけない箇所

• グローバル変数をどう扱うか
• 現状は、(define x …)とするとxというCのグローバル変数ができる
• (複数のファイルを経由して)同じ変数を2回defineしたときどうするか
• 対話環境を作って、そこからコンパイルしたときどうするか
• Cのグローバル変数を使うか、「環境オブジェクト」のようなものを作るか
• SchemeからCの関数(非CPS)を呼ぶのは結構簡単なはず
• ただし、GCとの連携はちょっと面倒
• Cの関数からSchemeの手続きを呼び出すのをどう作るか
• Schemeのプログラムから.soやDLLを作ればいい？
• 共有ライブラリを2個以上使うときは誰がGCなどをするのか
• KASHIWAのコア自身を共有ライブラリにして、他の手続きはそいつに色々お願いする？
• そうなると、やはり「グローバルな環境」をどうするかが問題になりそう
• valuesどうしよう。call/ccをテキトーに作ったのが祟ってきそうだ

以上。あとで何か思いついたらここに書き足すかも。

Rubyとか、Dalvik(Android用の仮想マシン)には、
(少なくても正式には)世代別GCが付いていないらしいですね。
そういった意味ではKashiwa SchemeはRubyやDalvikを、
超えた…そういっても過言ではないかもしれません。
いえ、ずばり過言でしょう。ごめんなさい。

Kashiwa Schemeでは、オブジェクトは1回のごみ集めを生き残るだけで、
tenuring(殿堂入り)します。たったの1回です。
「1回」というパラメータを意図的に設定しているのではなく、
仕組み上、そうすることしかできません。安っぽい殿堂入りですね。

—

世代別GCを付けたといっても、ごく普通のヒープに対するGCを書いただけです。
ヒープを半分に分けて片方だけ使うという、ごく普通のcopying GCを書きました。
＃ここでいう「ヒープ」はScheme用に管理している領域のことであり、
＃プロセス自体のヒープのことではありません。

スタックに対するGCは、
『スタックをfrom-space、ヒープをto-spaceとしたcopying GC』
であったのに対して、ヒープに対するGCは
『ヒープの半分をfrom-space、ヒープのもう半分をto-spaceとしたcopying GC』
であり、本質的には同じものです。
書き加えたのはわずかに100行ほどです。なんと楽なことでしょう。

—

ヒープに対するごみ集めでも、スタックへの参照を見つけたら、
それをヒープにコピーするようにしています。
こうすることで、ヒープに対するごみ集めが完了すれば、
スタックに対するごみ集めも同時に完了するようになります。

少し面倒なのは、ヒープに対するGCは、
スタックに対するGCの途中で発生する(可能性がある)ということです。
スタック上のものをヒープにコピーしている途中でヒープが足らなくなると、
ヒープに対するごみ集めが動き出します。

このとき、スタック上にはヒープを指すforwarding pointerがある可能性があります。
そのため、ヒープに対するごみ集めの最中にforwarding pointerを見つけても、
そのまま鵜呑みにするのではなく、どこを指しているのか確認する必要があります。

—

また、ヒープに対するごみ集めの途中で、ヒープが足りなくなることがあります。
オブジェクトのコピーがヒープの中で完結していれば大丈夫なのですが、
スタックからもオブジェクトをコピーするため、ヒープが不足することがあります。

ヒープが不足した場合、mallocを使って現在のヒープの「2倍」の領域を確保します。
そして、以前のヒープ全体(from-spaceとto-spaceの両方)を改めてfrom-spaceとして、
新しく確保した領域(の半分)をto-spaceとして再度GCを行います。
こうすることにより、オブジェクトが新しい領域にうまく移動してくれます。

ヒープの拡張にはreallocを使ってもよさそうなのですが、
reallocは(古い領域を拡張するのではなく)別の場所に領域を新たに確保した場合、
古い領域をその場で開放してしまうのが問題になります。
スタックからヒープへの参照が残っている可能性を考えると、
古い領域をその場で解放されてしまっては困ります。
理想は、ヒープが移動しない場合はreallocを用いて、
そうでない場合はmallocを使うということなのですが、
そんなことってできるのでしょうか。
sbrkを使って自分で書くしかないんですかね。

—

また、上記の「2倍」という数字には根拠がありません。
新たに設定するfrom-spaceと同サイズのto-spaceを設定するためには、
2倍にするのが都合がいいのですが、
スタックからのオブジェクトのコピーが非常に多い場合には、
ヒープ拡張後に、再度ヒープが足らなくなる可能性があります。

今のところ、ヒープが再度不足した場合には、
その場で終了するようにしています。
本当は、from-spaceをうまく設定して再度GCをやり直すか、
そもそも不足が置きないだけの十分な領域を確保するのが良いでしょう。

整合性を保ったままfrom-spaceを設定するのはかなり面倒です。
そのため、十分な領域を確保するというのがいいのですが、
これはこれで意外と厄介です。

スタックの長さが閾値を超えたら、GCが始まるわけですが、
閾値を「どれだけ超える可能性があるか」は分からないのです。
とはいえ、どれだけ超えたかは知ることが可能なので、
現在のスタック全体をヒープにコピーしても大丈夫なくらい、
ヒープを拡張すればいいということに今気づきました。
なんでエントリを書き始めてから気づくんでしょう。

「え？ 今まで出来なかったの！？」という感じですが、
はい。今まで出来ませんでした。

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

(write (fact 5))  ; => 120
(newline)
(write (fact 10))  ; => 3628800
(newline)

何故、今まで出来なかったかというと、
可変長引数の手続き(ここでは*と-)を放置してきたからです。
簡単そうに見えて、意外と考えさせられたのが、この可変長引数でした。

—

Kashiwa Schemeでは組み込み手続きを呼び出すコードは
builtin_cons(continuation, foo, bar);
といったように、C言語の関数呼び出しの形に変換されます。

そのため、組み込み関数の側(つまりC言語)で、
stdarg.hに含まれるva_startやva_argなどを用いると、
可変長引数の組み込み手続きを作ることができます。
ここまでは簡単です。

しかし、Scheme側でapplyを用いて、
可変長引数の組み込み手続きを呼び出す場合はどうでしょうか。
引数はリストの形でやって来ます。
こうなると、C言語の可変長引数の仕組みを利用することはできなくなります。

対応策として、手続き呼び出しの式
(proc arg1 arg2 ...)
のprocに組み込み手続きが現れた場合と、argNに組み込み手続きが現れた場合で、
それぞれ違う関数を用いるという方針を取りました。
procの位置に手続きが現れた場合は、C言語の可変長引数の仕組みを使う関数を利用して、
argNの位置に手続きが現れた場合は、リストを処理する別の関数を使うということです。

組み込み手続きは、引数として渡されることよりも、
直接呼び出すことの方が多いと仮定すると、
このように2種類の関数を用意して、
直接の呼び出しの場合を少しでも速くするということは、
それなりに価値があると思っています。

—

話は変わりますが、組み込み手続きではない手続き、
つまりユーザ定義の手続きには、
また別の問題が色々とあります。

Kashiwa Schemeは、まずCPS変換を行うため、
ユーザ定義の手続きは大量に生まれ、それらの大半は引数を通して渡されます。
つまり、(型推論でもしない限り)コンパイル時点で関数の型が分からなくなります。

そのため、クロージャ(手続きオブジェクト)には、関数ポインタや環境の他に、
「引数の数」を覚えさせておき、引数の数が正しいかチェックする必要があります。
Schemeなのだから、引数の数を実行時にチェックするのは当たり前なのですが、
意外と面倒なのが、関数ポインタを適切な型にキャストするということです。

引数が1つの場合、1引数関数へのポインタにキャスト、
引数が2つの場合、2引数関数へのポインタにキャスト、
引数が3つの場合、3引数関数へのポインタにキャスト、
……
このようにすべてを列挙するという方法が無理なのは言うまでもありません。

それならば、(C言語の)可変長引数の仕組みを使ってみてはどうでしょうか。
キャストの種類は常に1種類にして、
呼び出される側の関数はva_argを使って引数を取り出すようにする。
これだとうまく行きそうです。

しかし、この方法はスタックに対するGCが起こると問題が生まれます。
スタックに対するGCが起こると、直前に呼ばれた関数の関数ポインタと引数を保存して、
スタックからヒープに必要なものをコピーした後に、longjmpでスタックを縮め、
保存した情報を用いて、関数を再度呼び出します。
問題となる点は「関数を再度呼び出す」というところです。

再度呼び出すというプログラムは一体どう書けばいいのでしょうか。
C言語ではN個の引数を付けて関数を呼ぶ場合は
f(a1, a2, ..., aN)
といったように、すべての引数を括弧の中に書かないといけません。
しかし、引数の数が実行時まで分からない場合は、これができません。

さて、この問題への対応策として、
引数が閾値より少ない場合(今のところ4個まで)は、力技(すべての場合を列挙)で対応して、
引数が閾値より多い場合は、実引数をすべて構造体の中に放り込み、
関数にはその構造体だけを渡す(つまり1引数関数にキャストする)方針を取りました。

イメージとしては
f(1, 2, 3, 4, 5)
と書く代わりに、
args->v[0] = 1; ... args->v[4] = 5; f(&args);
と書くような感じです。

もちろん、常にこの構造体を中継して引数を渡すという方針を取ることもできますが、
「引数が少ない手続き」の方が「引数が多い手続き」よりも多いと仮定すると、
引数が少ない場合を特別扱いして速くすることに価値はあると思います。

—

その場その場で考えてコードを書いているため、
これらの手法が本当に適切かは分かりません。
どなたか、もっといい方法をご存知であれば教えて下さい。

昨日(9/23)、『第二回 カーネル／VM探検隊＠関西』が行われまして、
場所が京都ということで、行って来ました。

(各発表の内容などは、きっと何処かで誰かが書いてあるので割愛)

残りの発表が少なくなってきた所で、主催である@naota344さんから、
「時間があまりそうなので、誰か飛び入りでLT(ライトニングトーク)やりませんか？」
というアナウンスがあったので、せっかくなので何か話をしようと思い、
大急ぎでスライドをその場で作り、厚かましく飛び入りLTに名乗りを上げました。
(naota334さん、本当にありがとうございます。)

ネタはKashiwa Schemeの元ネタであるCheney on the M.T.A.の概要。
低レイヤが好きな人が多い会のようなので、C言語に焦点を当てて話しました。
大急ぎで作った粗いものですが、一応発表資料を置いておきます。

『いつから「関数を呼び出したら、いつかは戻ってくる」と錯覚していた？』

10秒くらいで考えたテキトー過ぎるタイトルでごめんなさい。
発表後に気づいた誤字などは修正しています(誤字が多すぎて少し絶望しました)。
今後も誤字に気づいたら随時修正するかもしれません。

前回のエントリの最後に

面白いのが、スタックからヒープへのコピーという処理は、
スタックをyoung領域、ヒープをold領域とした世代別GCとも見なせる点です。
……と、ここまで書いた時点で、ヒープからスタックへの参照を、
remember setに入れて覚えておく必要がありそうな気がしてきたけど、
そんな処理は書いてないぞ。なんてこった。ライトバリアとか書きたくないぞ。

などと言いましたが、結局ライトバリアを書きました。

—

そもそも何が問題だったかを簡単に書きます。

(define (g x)
  (lambda (z)
    (set! x (cons z x))
    x))
(define ls (g 1))
(ls 2)
(ls 3)
...

Kashiwa Schemeは基本的にすべてのオブジェクトをスタックに割り当てます。
(ただしシンボルは最初からヒープに割り当てます。)
そのため、上記プログラムでは、(g 1)によって作られるクロージャは、
スタックに割り当てられ、そのアドレスがグローバル変数lsに代入されます。

しばらくしてスタックに対するごみ集めが起こると、先ほどのクロージャはヒープに移されます。
その後に(ls 3)などの評価を行うと、上記のクロージャが呼び出され、
クロージャの保持する変数xに『新しいコンス』が代入されます。
新しいコンスはもちろんスタックに割り当てられるわけです。

このようにして、ヒープからスタックへの参照が生まれます。
この状態でスタックに対するごみ集めが起こると、
上記のクロージャはルートセットに含まれないため、
コンスがごみとして回収されてしまいます。
これはどう考えてもまずいわけです。

—

で、解決策はいくつかありまして、一番簡単なのは、
スタックに対するごみ集めのたびにヒープ全体を舐めることです。
これは確実な上、簡単に書くことができますが、
ごみ集めにかかる時間が明らかに増大します。

別の解決策として、ヒープからスタックへの参照を記憶する方法があります。
ヒープからスタックへの参照を覚えておき、それをルートセットに加えることで、
回収漏れを防ぐというやり方です。これだとごみ集めの時間はあまり増えません。

ヒープからスタックへの参照の集合をremember setと呼ぶことにします。
ごみ集めを正しく行うためにはremember setを正しく作る必要があります。
ヒープからスタックへの参照がいつ生まれるかというと、set!やset-car!などの、
破壊的代入が行われる時のみです。
それらの場所で、必要があればremember setに参照を加えればいいわけです。
書き込みを行う場所で見張るため、この処理をライトバリアと呼びます。

remember setにも作り方が色々あります。
一つは単純にアドレスを1つずつ覚える方法。
この方法だと、ヒープからスタックへの参照の数だけメモリが必要です。
例えば、対象となる参照が1M個ある場合、remember setは4MB必要です。
(アドレスは32bitとして計算してます)

もう一つの方法は「おおよその場所」を覚える方法です。
ヒープを例えば512bytesごとのブロックに区切り、
ブロックの中にヒープからスタックへの参照が(1個以上)あるかを記憶します。
remember setのサイズは参照の数ではなくヒープサイズに比例します。
参照の有無は1bitあれば表せるので、ヒープが1GBあっても、
remember setはたったの256KBで十分なわけです。
(K=1024, M=1024K, G=1024Mで計算しています)

さてさて、どちらの方針が有利でしょうか。
対象となる参照の数が非常に多い場合は、おおよその場所を覚える方がいいでしょう。
しかし、おおよその場所しか覚えない場合は、
スタックに対するごみ集めの時に「実際の場所」を探すために
余計なスキャンを行う必要があります。
対象となる参照の数が少ない場合はアドレスを1つずつ覚える方がいいでしょう。

さて、Schemeといえば、破壊的代入を嫌う文化があります。
そのため、対象となる参照の数は十分に少ないと仮定していいでしょう。多分。
そんなわけでアドレスを1つずつ覚える方針を取ることにしました。
これを書きたかっただけなのに説明がえらく長くなってしまった。

先日述べたとおり、Kashiwa SchemeはSchemeからCへのトランスレータであり、
Schemeの(CPS変換された)手続きはCの関数に変換されます。
しかし、そのCの関数ではreturnにたどり着くことはなく、スタックは伸び続けます。
(詳しくは元ネタのこの論文を読んでください)

とまあ、本当にスタックが伸び続けたらいつかは死んでしまう訳で、
実際のところはスタックが一定より伸びた所で手を打ちます。
具体的には、スタック上にある『必要なもの』だけをヒープにコピーして、
longjmpを呼び出してスタックを巻き戻してから処理を再開します。

変換されたCの関数というのは以下のような形をしています

static void fun112_(env_t* penv113_, lobject g108_) {
  cont_t clos125_;
  env_t* cenv114_;
  check_stack(fun112_, penv113_, 1, g108_);
  ... (略)  ...
}

見ての通り、先頭でcheck_stackという関数を呼んでいます。
この関数は、スタックがどれほど伸びたかを確認します。
そして、スタックが閾値より伸びていた場合、
最後に呼ばれた関数(この場合fun112_)とその引数の値をヒープに保存して、
先ほど保存した引数からたどれるオブジェクトをすべてヒープにコピーします。
コピーが終了すると、longjmpでスタックを巻き戻し、
ヒープに保存した情報(最後に呼ばれた関数と引数)を使って処理を再開します。

「関数はreturnにたどり着かないため、呼び出し元に戻ることはない」
ということは
「最後に呼ばれた関数とその引数さえ覚えておけば処理を再開できる」
というわけです。
ただし、スタックに作ったSchemeのオブジェクトは、
『必要があれば』ヒープに移動する必要があります。
逆に言えば不要なものは捨ててしまうわけです。

この「オブジェクトのスタックからヒープへのコピー」という処理は、
スタックを”from space”、ヒープを”to space”としたcopying GCとみなせます。
ここでCheneyのアルゴリズムを用いると、
これ以上スタックを消費することもなく、安心してごみ集めを行えるわけです。

今回書いたのはこのスタックにおけるごみ集めだけで、
ヒープにおけるごみ集めはまだ書いてません。
まあ、こちらはただのごみ集めになるのであまり面白みもなさそうです。

面白いのが、スタックからヒープへのコピーという処理は、
スタックをyoung領域、ヒープをold領域とした世代別GCとも見なせる点です。
……と、ここまで書いた時点で、ヒープからスタックへの参照を、
remember setに入れて覚えておく必要がありそうな気がしてきたけど、
そんな処理は書いてないぞ。なんてこった。ライトバリアとか書きたくないぞ。

ええ、そうです。
また、Schemeの処理系を書き始めました。
これでLisp(系)処理系を書くのが何度目か数えるのも面倒になってきました。

今回作っているのはSchemeからC言語へのトランスレータで、
現在、こんなコードをコンパイルして動かすことができます。

(define cc 0)
(define (f x)
  (cons
   (call-with-current-continuation
    (lambda (k)
      (set! cc k)
      0))
   x))

(write (f 3))      ; => (0 . 3)
(newline)
(write (cc 48))  ; => (48 . 3)
(newline)

まだシンボルも作っていませんが、既にcall/ccが動作します。
完成まで程遠いのに『Kashiwa Scheme』という名前は決めました。

—

さてさて、時を遡ること、約半年。
偶然Chicken SchemeのWikipediaの記事を読んで衝撃を受けました。

A scheme program is compiled into C functions. These C functions never reach the return statement; instead, they call a new continuation when complete.

Schemeの手続きをCの関数にコンパイルするにもかかわらず、
そのCの関数は一切returnしないというのです。
説明を書くと長くなりそうなので、詳しくはこの論文を読んでください。

ということで、この実装があまりにも楽しそうだったので、
私も真似してみようと思い、Kashiwa Schemeを書き始めました。

今のところ、Cのreturnを一切使わないという目標は達成できているんですが、
この実装方法のもう一つの肝である『スタックを対象としたごみ集め』に関しては、
まだ一切コードを書いていません。ここを書くのが楽しみなんですが、
先にシンボルを作ったり煩雑なところを少し進めることになりそうです。

—

継続について気になったことがあったので少しメモ。

最初、トップレベルの(define以外の)式は1つの手続きにまとめて、
Cのmain関数からはその手続き(をCの関数に変換したもの)を、
呼び出すような作りにしていました。

;;; コンパイル対象
(define (f x) ...)
(define (g y z) ...)
(f 3)
(g 4 5)

;;; main関数からこの手続を呼ぶ
(lambda ()
  (f 3)
  (g 4 5))

多くの場合はこれで問題なく動いたんですが、
call/ccが出てくると問題が発生しました。

例えば、上記のプログラムの場合、手続きfの途中で継続を取り出し、
手続きgの中でその継続を呼びだしてしまうと、
手続きfの途中から処理が再開してしまうため、再び手続きgが呼ばれ、
プログラムが無限ループに陥ってしまいます。

Schemeのレベルでこの問題を解決する方法が思いつかなかったため、
C言語のレベルで汚らしい方法で解決してしまったんですが、
なんとかならないものなんでしょうかね。
CPS変換についてもう少し詳しく調べたら定番の方法でも見つかるのかな。

何を言ってるのか　わからねーと思うが、
取り敢えず下の2つのファイルを御覧ください。

;;; a.lisp
(defmacro foo (x)
  `(list ,x ,x))

;;; b.lisp
(defun bar ()
  (foo (+ 1 2)))  ; 上記マクロを使いたい

処理系を起動した直後に、
これらのファイルを次のようにコンパイルする場合を考えます。

(compile-file "a.lisp")
(compile-file "b.lisp")

さて、この行為は実は問題があります。
a.lispをコンパイルしただけでは、マクロfooは定義されません。
そのため、b.lispをコンパイルするときにfooは未束縛になってしまいます。

例えばAllegro CLであればコンパイル時に次のような警告が出ます。

Warning: While compiling these undefined functions were referenced:
FOO from character position 0 in b.lisp

Clozure CLであればこんな感じ。

;Compiler warnings for “b.lisp” :
; In BAR: Undefined function FOO

上記メッセージから分かるように、fooが関数扱いされるため、
この後、コンパイル済みのファイルをロードして、
(bar)を評価するとエラーになります。

と　こ　ろ　が、
SBCLやCLISPで同じ事をやると、問題なく動いてしまいます。

(compile-file "a.lisp")
(compile-file "b.lisp")
(load "b")
(f)  ; => (3 3)

コンパイル時に警告がでることもありません。

何が起こっているのか調べてみたところ、
compile-fileした時点で、マクロが定義されているみたいです。

(compile-file "a.lisp")
(macro-function 'bar)  ; => #<FUNCTION>

これは驚きです。

でも、ポータブルなコードでなくなるので、
こんなコードは書かないほうがいいでしょう。