リリカル☆Lisp開発日記

（この記事はLisp Advent Calendar 2日目のためのエントリです。）

「え、お前の家、カレーに味噌汁付けてるの！？」

頑張って作っていたLispインタプリタがついに完成。友達に自慢してソースコードを見せてみたら
「え、なんでそんな実装になってるの？ それって変じゃない？」
といった反応が返ってきたことはありませんか。きっとありますよね。昔から「人の数だけLispがある」と言われていまして、書く人によって色々と違いが出てくるのは当然です。しかし、どんな違いが出てくるのかを知らないと、要らぬ混乱を招く可能性があります。

この記事を読むことで、一言に「自作Lispインタプリタ」と言っても、色々なやり方があることを知り、友人の心ない発言に傷ついたり、逆に人を傷つけないようにする知識を身につけた気分になれます。

「あの人は自分でごみ集めを書いてくれたのに」

Lispインタプリタを書くにあたって、一番最初に決めなければいけないのが、実装に使う言語です。世の中には星の数ほどプログラミング言語がありますが、Lispを作るにあたって重要になるのはごみ集め(garbage collection)が付いているかどうかです。ご存知の通り、Lispにはごみ集めが(非常に特殊な実装を除き)必ず付いてきます。JavaScriptなどごみ集めが付いている言語を使う場合は、自分では何もしなくてもうまくいきますが、C言語などごみ集めが付いていない言語を使う際には自分でごみ集めを実装しなければなりません。そしてそれは(慣れないと)非常に難しいのです。

では、ごみ集めが付いている言語で書けば安心だな、と思ったら大間違いです。
世の中には「Lispを作った」と聞くと、Lispをどう作ったかより、ごみ集めをどう作ったかの方に注目する人たちがいるのです。そういった人に「ごみ集めは実装に使った言語の方にあったのでなにもやってません」と言うと、両親がコロコロコミックと間違えて別冊コロコロコミックを買ってしまった時のお子さんのような表情をされることになるでしょう。残念な顔をされても落ち込まないように気をつけてください。

「お前のLispインタプリタ、タグがデータに付いてるの！？」

使う言語を決めて、実際にLispインタプリタを書き始めようとしたときに、一番最初に悩むのは「Lispのデータをどう表すか」ということでしょう。
「数は実装側の数値型を使えばいいし、シンボルは文字列か何かでも使っておこう。コンスセルはポインタが2つあったら作れるな」
などと考えた後に
「ちょっとまて。Lispは実行時まで型が分からないのだから、どこかに型の情報を入れておかないとダメだ」
と気づくでしょう。そして次のようなプログラムを書く人も多いのではないでしょうか。

typedef struct {
  int tag;  // データの種類
  union data {  // 実際のデータ
    ..
  }
} LispObject;

LispObject* obj = カッコイイアロケーション();

まあ、実際のデータの部分はunionだったりchar[1]だったりchar[0]だったり人それぞれですが、自信満々にこういった実装を人に見せると予想外の反応をさせることあります。データサイズとか構造体のpaddingとか細かいところに対する反応ではなく、まるで
「え、お前の家、カレーに味噌汁を付けてるの！？」
といった感じの驚きの反応が返ってくるのです。

前述のとおり、Lispを作る際にはどこかに型の情報を入れておく必要がありますが、どこにいれるかは、2つのやり方があります。ひとつは先程のようにデータと一緒に格納する方法。そしてもうひとつはポインタに格納するという方法です。

typedef void* LispObject;
#define MAKE_CONS(x) ((LispObject)((uintptr_t)(x) | 1))
#define MAKE_SYM(x) ((LispObject)(((uintptr_t)(x) << 3) | 3))
#define MAKE_NUM(x) ((LispObject)(((uintptr_t)(x) << 3) | 7))
#define MAKE_OTHER(x) ((LispObject)(uintptr_t)(x))

急に禍々しくなりました。おまけにどのデータが何バイト境界にアラインされているかなどを意識しないと大変なことになってしまいます(前者の実装でもそれは大事ですが)。しかしながら、実際の処理系ではこういった実装が多いのも事実です。現実問題として、ポインタを辿って型を確認するよりも、ポインタそのものを見て型が分かったほうがメモリの参照が減り、キャッシュミスなども減少しそうです。

残念なことに、一度データに型を持たせる実装をしてしまったら、それをポインタに型を持たせる実装に書き換えるのはかなり大変です。80年代のbit (共立出版) にもこの後悔が載っている記事があったような気がします。既にデータに型を持たせる実装をしてしまったのであれば、
「俺は自分の意志でこの実装にしたんだよ！」
と主張し、心を強く持ちましょう。

ちなみに、高級な言語を使っている場合、そもそもこの議論ができない可能性があります(特に実装側の言語にtypeofのようなものがある場合など)。そのような場合は間違えてワイルドミニ四駆を買ってしまった子供のような顔をされる可能性もありますが、ワイルドミニ四駆はワイルドミニ四駆で楽しいものです。心を強く持ちましょう。

「お前、ケツに挿入するの！？」

Lispインタプリタの実装をしていると、リスト操作をたくさん書くことになりますが、リストを作るときには人の癖が出ます。例えば、S式を読み込んでリストに直すリーダのプログラムを考えてみてください。文字列を先頭から読みながら、次々とコンスセルをつないでいくわけですが、さて、あなたは前につなげますか？後ろにつなげますか？

普段、リストを多用する言語を使っていない人はリストを後ろに伸ばしていく実装をする人が多いのではないでしょうか。毎回リストを辿るのはバカバカしいですが、リストの末尾を指すポインタをもったりすると真っ当な感じになります。

Cons head;
head.cdr = NIL;
Cons* tail = &head; 
while (...) {
  ...
  Cons* cell = newCons(element, NIL);
  tail->cdr = cell;  // 末尾に挿入
  tail = tail->cdr;
}
return head.cdr;

しかし、リストの末尾に要素を追加していくのではなく、先頭に要素を追加していって、最後に反転する実装にすると、驚くほどシンプルに書けます。

Cons* ret = NIL; 
while (...) {
  ...
  ret = newCons(element, ret);  // 先頭に挿入
}
return nreverse(ret);

後ろ向きに伸ばす実装でもキレイにかけていれば問題はないのですが、汚い実装になっていると、「あっ・・・(察し)」という反応が返ってくるかもしれません。ちなみに、高級な言語を使っている場合、(以下略)

「そこはどうした？ あー、それか。それはアレだね」

さて、最後はみんな大好き、末尾再帰最適化と一級継続のお話です。これを自分で考えて実装しようと思うとかなりの苦労が強いられますが、それがまた楽しいところです(書籍などで先に冴えたやり方を知ってしまった人はレーシングラグーンをやらないのと同程度に人生を損しています)。
「次に呼ぶ関数を入れたオブジェクトを返そうか、いや、gotoで色々と頑張って......むしろスタックを連結リストにしてしまったらどうだろう」
色々と考えた末になんとか完成するでしょうが、なんとも人に説明しがたいものが出来上がるのではないでしょうか。しかし、興味をもたれやすいのも末尾再帰最適化と一級継続といった部分なのです。「どうやって作ったの？」と聞かれてしどろもどろの説明になりがちですが、

大抵の場合、しどろもどろの説明で通じます。

それどころか、「あー、分かる分かる」と、どこからともなく次々と人が現れ、「その実装だと効率が」「いや、けどそれは手間だから趣味で作るぶんには」と次々と自分の実装についての話を始め、自分のLispインタプリタの自慢話を始めたはずが、いつの間にか人のLispインタプリタの話を聞くことになったりします。Lispインタプリタを書いたことがある人はいったいどれほどいるんだ。ちょっと多すぎるぞ、という気分になるでしょう。群がってくる人がいない場合は、周りの人たちにLispインタプリタを実装させましょう。

私の経験から言うと、末尾再帰最適化や一級継続の実装法に「これだ！」という強い自信を持っている人は少なく、また、試行錯誤をした人が多いため、自分が思いついた手法というのは、他の人も思いついていて、場合によっては試したことがあるというケースも多いようです。そのためか、この部分に関しては優しい人が多いので、自信を持って自慢しましょう。完成させたら勝ちです。

まとめ

ワイルドミニ四駆は意外と楽しい。

参考文献

• Twitter / zick_minoh: 江東運転免許試験場でカツカレーを頼んだら味噌汁が付いてきた。 ... [twitter.com]
• 別冊コロコロコミック [ja.wikipedia.org]
• 1/32 ワイルドミニ四駆シリーズ 1/ 1 [www.tamiya.com]
• レーシングラグーン [ja.wikipedia.org]