オレオレLisp処理系を実装してみた(1日目)

この週末でLisp処理系をスクラッチから作ってみたので、そのときのメモをアップしていきいます。
この記事はその初日のメモです。(2日目、3日目)

あんまり推敲もしてないので読みにくいかもしれません。
その日のコードは最後に Gist を貼っておきます。



== 1日目 ==
SICPを読んでて4章に入ったところで無性にLispをつくりたくなったので作ることにした。
Lispを実装したことないとLisperを名乗れないらしいとどこかで見た気がするので、
完成したら(REPLができたら)俺もLisperを名乗れるかもしれない。

実装言語はSICPだとSchemeだけど、C++にすることにした。理由は:
* 静的型付けでどうやって実装するのか考えてみたかった
* C++で書けばもしかして少しは速いんじゃないか、という下心

まず大雑把な設計を考える。

LISP-2にするとちょっと大変そうな気がするのでLISP-1にする。

Lispは変数じゃなくて値の方に型を持ってるらしいので、たぶんLispObjectみたいな
スーパークラスを作ってあげて、そいつを継承したサブクラスを作っていけばよさげ。

Cで書く場合はポインタのアラインメントを利用して下位バイトに型情報を持たせたり
するテクニックがあるらしいけど、GCまで自前実装しないといけなくなりそうなので却下。
GC は楽そうな std::shared_ptr を使う。

S式の内部表現はreadを書くのがだるいのでuSchemeRの本にあったみたいに
std::listとかにするかなーとも思ったけど、よく考えたらC++自体REPLがないから
std::listで楽できても違うS式を評価しようとするたびにコンパイルが
必要になる気がするので、 結局readは書かないとつらそう。

あとLispオブジェクトクラスとstd::listを継承したクラス作って大丈夫か自信ない。
というわけで、ちゃんとListになるクラスを真面目に作ることにする。

AtomはFixnumがあればいいか。

LispObject は virtual string str() = 0; を実装しといてprintはcoutに<<する
だけにしよう

とりあえずのクラス階層は
* LObj
** Fixnum
** List
** Env
** Proc
くらいか。

**

大まかな設計を決めたので適当に実装してく。

どうせオモチャなのでソース分割とかは考えずに #include <bits/stdc++.h>
と using namespace std; してヒャッハーすることにする。

LObjはvirtual static str() = 0;だけ書いといて、インスタンス化
できないようにしとく。あと typedef std::shared_ptr<LObj> lptr; しとく。

Fixnum はとりあえずint をメンバ変数にしといて value() で取り出せるように
しておく。

List を std::list をメンバに持ったクラスとして実装しようとしてたが、
そもそも Cons を作ってやればいいことに気づいた。

lptrでくるんだやつから特定のクラスのポインタを取り出すのに少し悩む。
typedef std::shared_ptr<Fixnum> FixnumP;
とか作っといで shared_ptr::dynamic_pointer_cast で変換する方向
で実装始めたけど、全部のクラスにxxxP用意しないと行けないのと、
どのみち各クラスのポインタを取り出したいときは生ポインタが必要なとき
なのでLObjにrawptr<T>()なメンバ関数を用意することにした。
取り出した生ポインタをまたlptrでくるむようなことをしなければOKだろう。

lptrなオブジェクトに対してprmcons, prmcar, prmcdr 等を実装して動くのを確認。

**

Proper Listを作るにはNILが必要なのでクラスに加える。
とりあえず List : public LObj な空のクラスをつくって
Nill : public List で継承、Cons は List を継承するように変更
した。これで listp, consp の関係と整合するはず。
NILはTHE_NILというグローバル変数でインスタンス化しておく。

そのうち環境フレームが必要になるので Env クラスを書く。
が、そのまえに Env のキーになる String, Symbolクラスが必要なので
そっちを先に作る。

Stringはstd::stringのラップ、Symbolも同様だけど、同じ文字列の
シンボルは同じメモリに配置できるようにしたいので、文字列からSymbol
が欲しくなったら必ずstd::unordered_map<std::string, lptr>なハッシュ経由で
取得するようにする。ハッシュは THE_SYMBOL_TABLE として1個だけ
生成しとく。

Envの実装に戻るEnvは原則として単なるハッシュなんだけど、階層構造になるので
外側のEnvを指すlptrなparentとハッシュ本体のstd::unordered_map<std::string, lptr>
として作った。あと一番外側のグローバル環境フレームとしてparentがTHE_NILの
EnvをひとつTHE_ENVIRONMENTとして生成しておく。
Env の親子を考慮して symbol -> lptr の変換する prmgetenv を実装。
prmdefine と prmsetenv がどういう意味論を持つべきか考えてそいつらも実装しておく。

Envから値を得るときに見つからなかったときに返すために Error クラスを 実装。

そろそろ内部構造が形をなしてきたのでちゃんとした PRINT 関数、printerlptr を書く。
Cons だったら printCons に飛んで、'('を出力したらまた
printerlptr を再帰的に呼び出すようにしてうまく行った。

eval を実装するために適当に Proc クラスと prmbegin とか prmcond などの
特殊形式の実装を始める。

疲れたので今日はここまで。（次の日のメモはこちら）

現在のクラス階層
class LObj
class Error : public LObj
class List : public LObj
class Nil : public List
class Cons : public List
class Fixnum : public LObj
class Symbol : LObj
class Env : public LObj
class Proc : public LObj

1日目のコード