概要

WebAssemblyを出力するMinCaml コンパイラml2wasmをフルスクラッチで実装しました。
github.com

マンデルブロ集合を計算するこんな↓感じのMinCamlのソースコードが

f:id:a_kawashiro:20181029180551p:plain:h325,w500 — マンデルブロ集合を出力するMinCaml ソースコード

こんな↓感じのWebAssemblyに変換されて

f:id:a_kawashiro:20181029183757p:plain:h325,w500 — 出力されたWebAssembly

実行して、適切にプロットするとこんな↓感じになります。

f:id:a_kawashiro:20181029180607p:plain:h325,w500 — 作成したコンパイラでコンパイルし実行・プロットしたもの

導入

WebAssemblyとは

WebAssemblyとはブラウザで実行可能な低級プログラミング言語であり、仮想的なスタックマシン上で動作します。また、JavaScriptに比べて構文解析が容易であり高速に動作します。 WebAssemblyは最近のほとんどのブラウザで動かすことができます。*1

;; WebAssembly のテキスト表現の例
(module
  (func (export "add") (result i32)
    (i32.add
      (i32.const 1)
      (i32.const 3))))

MinCamlとは

MinCamlとは東北大学の住井先生*2が設計したプログラミング言語MLのサブセットです。言語仕様が小さく、処理系を制作するのが比較的容易なのが特徴です。住井先生は未踏事業としてMinCamlのコンパイラも制作されています。このコンパイラは読みやすくドキュメントもしっかりしているので、コンパイラを作ってみたい人には非常にオススメです。 ml2wasmの開発でもこのコンパイラを大いに参考にしました。

(* MinCaml の例 *)
let rec add = 1 + 3 in add

コンパイラの作成

今回はMinCamlのソースコードをWebAssemblyのテキスト表現に変換するコンパイラml2wasmを作成しました。基本的にml2wasmはオリジナルのMinCaml コンパイラと同じ構造ですが、WebAssemblyがスタックマシンであることを利用していくつかの変換の工程が省略されています。

ml2wasmの実装の詳細

ml2wasmでは次の5段階の工程でMinCamlをWebAssemblyに変換します。

パース
アルファ変換
型推論
クロージャ変換
コード生成

特に説明のない部分はオリジナルのMinCaml コンパイラと同じです。今回はHaskellで実装しましたが、もともとの実装言語がOCamlでHaskellとそれほど変わらないので、その点は苦労しませんでした。以下、WebAssembly特有のコンパイラ実装事情をいくつか説明します。

オリジナルのMinCaml コンパイラには3と4の間にK正規化、4と5の間にレジスタ割当という処理がありましたが、ml2wasmではこれら2つの処理を省略しています。 K正規化はWebAssemblyでは命令のオペランドとしてスタックの先頭の値を使い、オペランドをレジスタに格納する必要がないため、レジスタ割当はWebAssemblyにはレジスタが存在しないため、それぞれ省略できました。

逆に、WebAssembly特有の難しい工程としてはコード生成があります。通常、関数型言語のコンパイラではプログラムをクロージャ変換し、関数から自由変数を削除します。その後コード生成の工程で関数呼び出しは間接ジャンプ(MIPSならjr命令)に変換されます。

この間接ジャンプをWebAssemblyではcall_indirect命令で実現します。

;; call_indirect命令はこんな感じで呼び出される。
...
(i32.load)
(call_indirect (param f32) (param f32) (param i32) (result i32)))))
...
;; (param f32) (param f32) (param i32) (result i32) ← 型が必要

ここで問題になるのがcall_indirect命令が呼び出す関数の型をオペランドとして要求する点です。これはクロージャ変換後の中間言語に型情報を残しておく必要があることを意味します。コンパイラを書き始めたときにはこのことに気づかなかったので、あとから型情報を追加するのに苦労しました。

他には公式のリファレンスがどこにあるのかイマイチわからない問題もあります。結局これを使ったのですが、 URLに公式感がなく最後までこのリファレンスが公式のものなのかはわからずじまいでした。

結果

マンデルブロ集合を出力するプログラムをコンパイルできるようになりました! やったね!

マンデルブロ集合を出力するMinCamlのソースコード
 mandelbrot.ml · GitHub
コンパイル結果
mandelbrot.wast · GitHub

ちなみにマンデルブロ集合っていうのはこんな↓やつです。

f:id:a_kawashiro:20181031155626j:plain:h325,w500 — 本当はこんな感じになって欲しかった

今回作ったコンパイラでコンパイルし実行した結果(を適切にプロットしたもの)は↓

まあ大体あってますね。点の数が以上に少ないのは大量の点をプロットしようとするとすぐにメモリ不足に陥るからです。

今後の課題

ml2wasmで出力したWebAssemblyコードはすぐにメモリ不足に陥ります。理由は単純でGCがないからです。 WebAssemblyでGCを実装する試みとしては κeenさんのWebAssemblyでGC | κeenのHappy Hacκing Blog がありますが、今回はめんどくさいのでメモリは確保しっぱなしです。

そのうちWebAssemblyにデフォルトでGCが入るとかいう噂も聞くので、そのときにGCを入れればいいやと思っています。