プログラミング言語の基礎概念の練習問題を解くプログラムを作った(EvalML3まで)

プログラミング言語の基礎概念を学んでる - はこべブログ ♨ の続きです。

前の記事では、プログラミング言語の基礎概念という本を紹介した。この本では学んだことを確認するために、S(S(Z)) + Z evalto S(S(Z))のような式が正しいことを、与えられた推論規則にもとづいて導出するという練習問題が用意されている。しかし、本の中盤くらいの問題から人間ががんばって手で解くのが辛くなってくる。( 例えばこういうのを丁寧に書かないといけない https://gist.github.com/hakobe/860fd1dd9c56c1d33a33 )

前回の記事についたブックマークの中で、id:OKU_s62 さんが以下のようにおっしゃていた。

後半の問題の導出木を書くのは人間業ではないので、導出木を生成するプログラムを書きましょう
http://b.hatena.ne.jp/OKU_s62/20140714#bookmark-205135689

なるほど、たしかに。ということで、問題を解くプログラムを作ってみた。本の中で説明されているEvalML3という言語の式を、したにあるtextareaに与えると導出木を作って出力してくれる。出力を、本の演習システムにコピペすると正解という判定になるはず。

下のtextareaの中身を適当に変更すると導出木も変わるのでおためしあれ。サンプルにいくつかEvalML3の式をリストしてあるので、コピペするとためせる。

y = 3 |- let add = fun x -> y + x in add 5
|- let twice = fun f -> fun x -> f (f x) in twice twice (fun x -> x * x) 2
|- let rec fib = fun n -> if n < 3 then 1 else fib (n - 1) + fib (n - 2) in fib 5

人間がやると辛い問題もすばやく結果が返ってきて、ありがたい。フィボナッチ数を計算してる式とか絶対手でやりたくなかったし助かった。

CoffeeScriptでわりと雑な感じに実装したけどおおよそ動いてそう。ソースコードは、hakobe/copl · GitHubにおいてある。

実装は、入力した式をパースしたあと、ASTをたどりながら計算を実行しつつも同時に導出木を作る、という風になってる。ほぼインタプリタを作ったと言う感じになった。本には、パーサを書くための厳密なBNFは書かれていないので、自分で適当にBNFを考えてパースするのだけど、BNFを見ただけでLL文法なのかLR文法なのかを判定する知識がなかったので困った。id:tarao 先生曰く、LALRのパーサがあれば十分なはずとのことだったので、jisonというJavaScrip用パーサジェネレータを使うことにした。jisonはCoffeeScriptをパースするのにも使われて実績があって、ほぼbisonと同じことができて高機能。文法は、こういう感じにに書ける。

実は、今定義してある文法にはshift/reduce conflictが残ってる。例えば、パーサが1 + f まで読んで、次のトークンが3だったときに、1 + f でreduceするか、1 + f 3 のようにみなすためにshiftするかが曖昧になっているっぽい。これはEvalML3の関数適用の文法が原因なのはわかってる(このへん)。結局解決方法はわかってない。衝突した場合はshiftが優先になるらしく、意図どおりなので放置してるけど、なんとかしたいという気持ちは残ってる。

本題とは関係ないけど、もともと手元のNode.jsで動かしてためしていたコードを、browserifyでブラウザ上で動かすというのもやってみた。gulp, TypeScript, Browserify で Chrome 拡張を書く - 詩と創作・思索のひろばがともても参考になった。構文定義をコンパイルしたり、coffeeのファイルをコンパイルしたりというのもあるので、gulpでビルドの仕方を記述してみている(このへん)。

本はまだ途中で今後少しづつ言語が拡張されていくのだけれど、それに合わせてこのプログラムも拡張していけば、演習問題も余裕で解けるはず。人間がコンパイルするのはまちがってるので、自動化成功してよかった。