リリカル☆Lisp開発日記

【eval知ってるくらいでえばるな！】

「evalって関数が凄くて……」という話をされたら、こう言い返す。
「これだからLisperは傲慢なんだよ」と相手に言わせたら勝ち。

【継続は力なり】

「継続ってなんですか？」と人に聞かれたときは、
このように説明するとよい。相手が酔っているときは効果的。

【Lispを使う理由? 括弧いいから】

「何故Lispを使うのか」と尋ねられたときに返す言葉。
これを言えば多くの人は納得するか、諦めの目で見てくれる。

巷でAdvent Calendarとやらが流行っているらしいです。
もともと日本の風習ではないのでよく分かりませんが、
12/1から12/25まで毎日ネタを書くものらしいです。
なにか間違っているような気もします。

人を集めるページで開催するのが通例のようなので、
私もそうしてみました。
LispギャグAdvent Calendar : ATND
何か間違っているような気もします。

(2011/12/02追記)
Advent Calendarについて調べてみたんですが、想像と違ったようです。
やっぱり何か間違ってました。

アドベントカード (Advent card) とは、アドベントの期間中に窓を毎日ひとつずつ開けていくカードである。アドベントカレンダーとも言う。カードに作られた窓を1日に1つずつ開けていく。そして、全部の窓を開け終わるとクリスマスを迎えたことを教えてくれる仕掛けになっている。

(アドベントカード – Wikipedia より)

ということで、本当のAdvent Calendarを作り始めました。

意外と良い感じに出来てます。

(2011/12/09追記)

(2011/12/19追記)

(2011/12/25追記)

いつの間にやら、GoogleからDartという言語が発表されました。
世間の評判を見てみると、一部の方々からは
「無難な感じで刺激が足りない」
「クラスベースが気に食わない。JavaScriptみたいに実行時にプロパティを追加したい」
などといった意見も出ているようです。

そこで本エントリでは、刺激を求める方々のために、
Dartで実行時にメソッドを追加する方法を紹介します。
まずはこちらのコードを御覧ください。

main() {
  var i = new Flexible();
  i.addMethod("plus1", (self, n) { return n + 1; });
  i.addMethod("wawa",
              (self, x, y) {
                return self.plus1(x) + self.plus1(y);
              });
  var x = i.plus1(99);
  print(x);  // => 100
  var y = i.wawa(23, 103);
  print(y);  // => 128
}

実行時にメソッドが追加できているのが確認できます。
これでJavaScript信者の方々も、少しは心やすらぐかと思います。

メソッドaddMethodを持つクラスFlexibleの定義は次のようになっています。

class Flexible {
  var methods;
  Flexible() : methods = new Map();
  addMethod(name, fun) {
    methods[name] = fun;
  }
  noSuchMethod(name, args) {
    if (methods[name] == null) {
      throw new NoSuchMethodException(this, name, args);
    } else if (args.length == 0) {
      return methods[name](this);
    } else if (args.length == 1) {
      return methods[name](this, args[0]);
    } else if (args.length == 2) {
      return methods[name](this, args[0], args[1]);
    }
    throw new NotImplementedException();
  }
}

methodsという変数を用意しておき、コンストラクタで空のMapに初期化します。
addMethodはmethodsに引数で渡された関数を追加するだけです。
noSuchMethodは存在しないメソッドを起動した際に呼ばれる特殊なメソッドで、
ここでaddMethodで追加した関数をディスパッチしてやるという訳です。

パラメータが2つの場合までしか対応していなかったり、
厳密に言えばメソッドを追加しているわけではなかったり、
見れば見るほど卑怯なコードですが、動けばいいんですよ。動けば。

とはいったものの、このコードはstandalone VMでしか動きません。
コンパイラはどうもnoSuchMethodの対応をしていないような気がします。
また、上のソースではnoSuchMethodは2引数ですが、仕様では1引数です。
本当は仕様通り書きたいところですが、それが動く環境がないようなのでやむなしです。
VMのソースを見たら「あとで仕様に合わせる」というコメントが書いてあるので、
そのうち仕様通りに書けば、動くようになってくれるでしょう。

そんなわけで、Dartもその気になれば実行時にメソッドを追加することができます。
皆さんも是非お試しください。おすすめしませんが。

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つずつ覚える方針を取ることにしました。
これを書きたかっただけなのに説明がえらく長くなってしまった。