ブラウザで動くラムダ計算器を作った（Scala で）

最近 Types and Programming Languages を読んでいて、はじめは我慢していたものの、やはりラムダ式の簡約をコンピュータで確認したい気持ちが高まってきたので、ブラウザで動くものを書いてみた。この本には OCaml による実装の章がときどき挟まれるので、演習の一環ともいえる。

Lambda Calculator

"(λx.λy.x y)(λz.z)" といったラムダ式を入力して送信すると（λ は \ で代用可能）、解析された項が出力される。その後1ステップずつ簡約して、項が評価されていく過程を眺められる。評価戦略は TAPL にしたがって call-by-value と call-by-name を提供してるつもりです。毎回どのサブ項が評価されたのかがハイライトされるので、実用的。

同じ項を何度も入力するのが辛いので文字列マクロを導入してあり、"$omega" などと書くと展開した上で解析される。グローバル変数のような概念がないので、文字列置換です。いくつかのよく使う（？）式を定義しておいた。

パーマリンクもあるので、ラムダ式を SNS で共有することもできる。

http://motemen.github.io/lambda-calculator/untyped.html?s=call-by-value#$omega

実装は JavaScript……ではなく主に Scala で行い、Scala.js で JS に変換した。ハマると解決できなそうなので動かなかったら諦めようと思っていたんだけど、普通に動いてしまったので感動です。とはいえいくつか工夫しなくてはならなかった点があるのでここに記す。

Scala.js で parser-combinators を使う

id:xuwei さんのアドバイスにしたがって、bintray にアップロードされているものを使うよう変更できました。あざーす！

Scala.js には Scala のパーザコンビネータは含まれていない（JS にコンパイルできない）が、2.11 になって切り出されたもののフォークが存在するので、これを利用する。（参考）

今のところ公開された場所に登録はされていないらしいので、依存プロジェクトとして sbt のビルド定義に含んでやる。この時、サブプロジェクトの plugins.sbt は読み込まれないのでルートプロジェクトのプラグインとして指定する必要がある。コアプロジェクトをこれに依存させる。（build.sbt）

JS として切り出すプロジェクトを分ける

はじめ Scala で実装してテストも Scala で書いてたんだけど、このプロジェクトをそのまま Scala.js のプロジェクトとすると sbt test の挙動も変わってしまった。これは意図的なもので 、Scala がコンパイルするものと Scala.js がコンパイルするものとの間に互換性がないためらしい（JVM のバイトコードを　JS に変換してるわけではないってことかな）。なので JS 側へのインターフェースだけ別プロジェクトに切り出し、コア部分に依存させるということにする。

ちなみに Scala.js でクライアントサイドの JS を全て書くこともできるんだけど、そこまでの意欲はないのでコア部分のインターフェースを書いたら、あとは生の JS でやることにした。

結果、こんな感じの構成になった。

. [Scala, depends modules/scala-parser-combinators]
|-- js [Scala.js, depends root]
|-- modules
    `-- scala-parser-combinators

gulp でビルドしたい

sbt が律速（重い）なのでビルドは sbt に一元化したくなるけれど、とにかく重いしこの前段階でもう飽き飽きしたので、gulp から sbt を呼ぶようにした。まあ必要なのはほぼ sbt ~fastOptJS だけなので spawn するだけ。Scala.js はコンパイル時、生成先のファイルにどんどん追記して完成させるらしいのだけど、これが gulp.watch と相性悪い。内部ではファイルシステムのイベントに対して debounce と呼んでる遅延処理がデフォルト 500ms かかっているんだけど、どちらかというと throttle と呼ぶべき代物で（underscore のネーミングを拝借すると）、困るのは、最後の書きこみが行われたあとにイベントが発生しないことがある。そこでコールバックのほうで 1s ほど _.debounce してやることにした。

そのほか

本体の話全然書いてないけどライブラリ使ったらパーザもだいぶ楽できた。愚直に書いたら無限に再帰しだして、久しぶりに左再帰とかいう言葉を思い出した。項を簡約するときに木のどの位置が簡約されたのか示すあたりのコードがあんまり綺麗ではない。

結局のところ評価して得られたこの値って何なの、というのがどうしても分からないことがあるので、ラムダ式を JS の関数に評価する API も作ってある。チャーチ数の確認とかにご利用ください。

> λ('λs.λz.s (s z)')
function (s) { return (function (z) { return s(s(z)) }) }
> λ('λs.λz.s (s z)')(function (x) { return x+1 })(0)
2

最後に書くようなことではないけど、実装が合ってるのかどうかイマイチ自信がない。業界で標準的なテストケース集とかあったら教えてほしいです。プルリク待ってます。

型システム入門 −プログラミング言語と型の理論−

Scalaスケーラブルプログラミング第2版