気づいたら1月が終わりそうです。そしてPS5が当たりました。まだ特にやるものは決めてないんですが、総計抽選回数2回目で当たったので、日頃の行いが良かったんだと思います。

最近引っ越しにかこつけて、環境をいろいろ変更しています。その話でもう一回くらい書けるネタはあるんですが、今回はなんとなく始めたOCamlでのScheme実装について書いてみたいと思います。

とりあえずリポジトリ

https://github.com/derui/scheme-ocaml-impl

この記事の時点だと、

という、必要最小限すぎる実装となっています。いろいろ余裕があったら、r7rsに準拠できるように実装していく想定ですが、途中で飽きる可能性もめっちゃ高いです。

動機

さて、なんでOCamlでSchemeを実装しようと思ったのか?ですが、これはもうかなり簡単です。

という、やってみたかった駆動開発です。SchemeはSICPとかでもサブセットの実装を行ったりしているらしく、またscheme/lispでの実装例が結構多いです。これは、scheme/lispをそのまま使う場合、めんどくさいread/parserの部分が全部ないし一部をそのまま流用できるため、実装の総量が減り、また見通しが良くなりやすい、という理由っぽいです。

実装の参考にしている資料

昔探したとき、なんかいろいろあったよなー・・・と思いながら探していたら、こんなのを見つけました。

https://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v13/schintro%5Ftoc.html

本当に最小限の実装から、lambdaやmacroの実装、compilerの実装とかまで進んでいくようで、結構分量が多いです。ちなみにこの資料だと、schemeでschemeするタイプなので、OCamlで実装する場合は前提になっているいろいろなものを事前に実装する必要があったりします。

OCamlで実装してみてよかったこと・悪かったこと

JSONやES5のlexer/parserくらいは実装したことがありますが、実際にOCamlで言語を実装したのは初めてでした。とりあえず動く、というところまでやってみて、OCamlで書いた感想を挙げてみます。

Pros/Cons内容
Proslexer/parserの実装からASTを組み上げるのが楽
Prosパターンマッチがeval時にやはり強力
Consschemeのcons listをパターンマッチだけでやるとこれはこれでめんどくさい。OCamlのlistに変換とかできるけど、それを毎回やるとそれはそれで重くなりそう
Prosmonadicな実装が簡単(まだちゃんとやっていないけど)
Cons引数のリストを組み上げるときとかがめんどくさい

概ね、schemeで超多用されるlistをOCaml内で扱うのがめんどくさい・・・、という感想です。どこかで見ましたが、最低限のspecial formとmacro/syntax-ruleなどを実装したら、後はschemeだけで実装していくのがやはり楽なのでは・・・?と思ってしまいます。もちろん、scheme自体では実装できないもの(比較とか)はprimitiveで実装しないとなりませんが。

ただ、OCamlで組み込み関数を実装するのは、Cとかで実装するより楽です。型のチェックでパターンマッチを使うだけで済むので、他の関数を呼び出す必要もありませんし。

これから実装していく方向

現在、schemeの式はすべて (data, string) result という型になるようにしています。ただ、例外とかを考えると、もうちょっとちゃんとしたmonadになるようにしてあげた方がいいかな?とは思っています。エラーの種類とかもほしいので。

まだmacro/syntax-ruleとかの実装が全くできていないので、ここを早めに実装していこうかなー、と思っています。

言語実装でOCamlはオススメです

もともと関数型言語(Haskell/Lispとか)は、言語実装に向いている言語です。OCamlはReasonML(リブランドされてReScriptになるようですが)などの実装自体でも利用されていますし、以外なところで使われていたりします。

また、OCamlはMenhirという強力なパーサージェネレータがあったり、ocamllexというlexerジェネレータが組込だったり(ocamllexにもより強力な代替があったりします)と、手軽にlexer/parserを実装する環境があります。

OCamlに興味があるけどなー・・・、という方は、簡単な言語実装などしてみちゃーいかがでしょうか。楽しい?よ?