2日目のためのエントリです。頑張って作っていたLispインタプリタがついに完成。それって変じゃない?」といった反応が返ってきたことはありませんか。昔から「人の数だけLispがある」と言われていまして、書く人によって色々と違いが出てくるのは当然です。どんな違いが出てくるのかを知らないと、要らぬ混乱を招く可能性があります。この記事を読むことで、一言に「自作Lispインタプリタ」と言っても、色々なやり方があることを知り、友人の心ない発言に傷ついたり、逆に人を傷つけないようにする知識を身につけた気分になれます。「あの人は自分でごみ集めを書いてくれたのに」Lispインタプリタを書くにあたって、一番最初に決めなければいけないのが、実装に使う言語です。collection)が付いているかどうかです。ご存知の通り、Lispにはごみ集めが(非常に特殊な実装を除き)必ず付いてきます。JavaScriptなどごみ集めが付いている言語を使う場合は、自分では何もしなくてもうまくいきますが、C言語などごみ集めが付いていない言語を使う際には自分でごみ集めを実装しなければなりません。それは(慣れないと)非常に難しいのです。ごみ集めが付いている言語で書けば安心だな、と思ったら大間違いです。世の中には「Lispを作った」と聞くと、Lispをどう作ったかより、ごみ集めをどう作ったかの方に注目する人たちがいるのです。いった人に「ごみ集めは実装に使った言語の方にあったのでなにもやってません」と言うと、両親がコロコロコミックと間違えて別冊コロコロコミックを買ってしまった時のお子さんのような表情をされることになるでしょう。残念な顔をされても落ち込まないように気をつけてください。使う言語を決めて、実際にLispインタプリタを書き始めようとしたときに、一番最初に悩むのは「Lispのデータをどう表すか」ということでしょう。「数は実装側の数値型を使えばいいし、シンボルは文字列か何かでも使っておこう。コンスセルはポインタが2つあったら作れるな」などと考えた後に「ちょっとまて。Lispは実行時まで型が分からないのだから、どこかに型の情報を入れておかないとダメだ」と気づくでしょう。次のようなプログラムを書く人も多いのではないでしょうか。カッコイイアロケーション();まあ、実際のデータの部分はunionだったりchar[1]だったりchar[0]だったり人それぞれですが、自信満々にこういった実装を人に見せると予想外の反応をさせることあります。データサイズとか構造体のpaddingとか細かいところに対する反応ではなく、まるで「え、お前の家、カレーに味噌汁を付けてるの!?」といった感じの驚きの反応が返ってくるのです。前述のとおり、Lispを作る際にはどこかに型の情報を入れておく必要がありますが、どこにいれるかは、2つのやり方があります。ひとつは先程のようにデータと一緒に格納する方法。ひとつはポインタに格納するという方法です。((LispObject)(uintptr_t)(x))急に禍々しくなりました。おまけにどのデータが何バイト境界にアラインされているかなどを意識しないと大変なことになってしまいます(前者の実装でもそれは大事ですが)。実際の処理系ではこういった実装が多いのも事実です。現実問題として、ポインタを辿って型を確認するよりも、ポインタそのものを見て型が分かったほうがメモリの参照が減り、キャッシュミスなども減少しそうです。残念なことに、一度データに型を持たせる実装をしてしまったら、それをポインタに型を持たせる実装に書き換えるのはかなり大変です。この後悔が載っている記事があったような気がします。「俺は自分の意志でこの実装にしたんだよ!」と主張し、心を強く持ちましょう。ちなみに、高級な言語を使っている場合、そもそもこの議論ができない可能性があります(特に実装側の言語にtypeofのようなものがある場合など)。そのような場合は間違えてワイルドミニ四駆を買ってしまった子供のような顔をされる可能性もありますが、ワイルドミニ四駆はワイルドミニ四駆で楽しいものです。心を強く持ちましょう。「お前、ケツに挿入するの!?」Lispインタプリタの実装をしていると、リスト操作をたくさん書くことになりますが、リストを作るときには人の癖が出ます。S式を読み込んでリストに直すリーダのプログラムを考えてみてください。文字列を先頭から読みながら、次々とコンスセルをつないでいくわけですが、さて、あなたは前につなげますか?後ろにつなげますか?普段、リストを多用する言語を使っていない人はリストを後ろに伸ばしていく実装をする人が多いのではないでしょうか。毎回リストを辿るのはバカバカしいですが、リストの末尾を指すポインタをもったりすると真っ当な感じになります。head.cdr;しかし、リストの末尾に要素を追加していくのではなく、先頭に要素を追加していって、最後に反転する実装にすると、驚くほどシンプルに書けます。nreverse(ret);後ろ向きに伸ばす実装でもキレイにかけていれば問題はないのですが、汚い実装になっていると、「あっ・・・(察し)」という反応が返ってくるかもしれません。それはアレだね」さて、最後はみんな大好き、末尾再帰最適化と一級継続のお話です。これを自分で考えて実装しようと思うとかなりの苦労が強いられますが、それがまた楽しいところです(書籍などで先に冴えたやり方を知ってしまった人はレーシングラグーンをやらないのと同程度に人生を損しています)。考えた末になんとか完成するでしょうが、なんとも人に説明しがたいものが出来上がるのではないでしょうか。興味をもたれやすいのも末尾再帰最適化と一級継続といった部分なのです。場合、しどろもどろの説明で通じます。それどころか、「あー、分かる分かる」と、どこからともなく次々と人が現れ、「その実装だと効率が」「いや、けどそれは手間だから趣味で作るぶんには」と次々と自分の実装についての話を始め、自分のLispインタプリタの自慢話を始めたはずが、いつの間にか人のLispインタプリタの話を聞くことになったりします。Lispインタプリタを書いたことがある人はいったいどれほどいるんだ。多すぎるぞ、という気分になるでしょう。群がってくる人がいない場合は、周りの人たちにLispインタプリタを実装させましょう。私の経験から言うと、末尾再帰最適化や一級継続の実装法に「これだ!」という強い自信を持っている人は少なく、また、試行錯誤をした人が多いため、自分が思いついた手法というのは、他の人も思いついていて、場合によっては試したことがあるというケースも多いようです。そのためか、この部分に関しては優しい人が多いので、自信を持って自慢しましょう。完成させたら勝ちです。まとめワイルドミニ四駆は意外と楽しい。カツカレーを頼んだら味噌汁が付いてきた。Reply返信をキャンセルする。