WebAssemblyを出力するMinCamlコンパイラを実装しました

コンパイラ Haskell WebAssembly 言語処理系

概要

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に変換します。

  1. パース
  2. アルファ変換
  3. 型推論
  4. クロージャ変換
  5. コード生成

特に説明のない部分はオリジナルの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
本当はこんな感じになって欲しかった

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

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

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

今後の課題

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

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

参考リンク

*1:https://github.com/WebAssembly/wabtを使うとコマンドラインでWebAssemblyを試せます。

*2:設計した当時はペンシルバニア大学に所属していたようです 美しい日本のMLコンパイラ – 未踏iPedia -まだ誰も踏み入れたことのない世界へ-

ネットワークデバイスドライバを一からビルドしてインストールした

Linux

概要

新し目のコンピュータにDebianを入れたら、ネットワークデバイスドライバが入ってなくて結構大変だった。

経緯

最近、自分の使っていたコンピュータ(6年前くらいのデスクトップ)に限界を感じ始めたので、日本橋で新しいものを買ってくることにした。購入に当たっては、換装が難しいCPUをCorei7 8700kに決定し、フィーリングで選ぶことにした。日本橋を端から端まで歩き回って、結局LM-iH700XD1-EX4を買った。

f:id:a_kawashiro:20180928082938g:plain

Windows10をDebian streachで上書きして起動すると、ネットワークドライバが入ってないことがわかった。マザーボードが新しすぎるのでドライバがDebianに取り込まれていないのだろう。こういう場合は自前でドライバをビルドする必要がある。

NIC(Network Interface Card)の型番を調べる

まず、NICの型番を調べる。商品のスペックを確認したが、「LAN:10/100/1000BASE-T LAN(オンボード)」としか書いていない。マザーボードの方には「マザーボード:Intel B360 Micro ATX LGA1151」と書いてあった。オンボードのNICなのだから、たぶん「Intel B360」のほうが関係しているのだろうと考えられる。ここから「Intel B360 network driver」などで検索して一時間ほど頑張ったが、なんの成果も得られなかった。

次はLinux側からNICを調べてみる。

% lspci
(省略)
00:1f.6 Ethernet controller: Intel Corporation Device 15bc (rev 10)

なるほど、「Intel Corporation Device 15bc linux driver」で検索すれば良さそうである。検索すると、Linux Kernel Driver DataBaseがトップに出てきた。「15bc 」でページ検索すると

vendor: 8086 ("Intel Corporation"), device: 15bc ("Ethernet Connection (7) I219-V")

が出てくる。「I219-V linux driver」で検索してみると「e1000e」の最新のドライバを入れればいいらしい?

そこで、もうどこで見たのか忘れたけど Intel Ethernet Drivers and Utilities の最新版をインストールすればいいらしい。(検索しすぎて記憶がないorz)

makeを入れる

というわけでe1000e-3.4.2.1.tar.gzをビルドする。 ネットワークに繋がらないので別のパソコンでファイルをダウンロードしてUSBメモリでコピーした。

展開して、make installすると...makeコマンドが入ってないと言われた。 Debianのインストール元のlive USBをマウント後、apt install build-essentialで入れた。 最初から入れといてほしい...

デバイスドライバをビルドする

e1000e-3.4.2.1.tar.gzを展開して、make installするとカーネルのヘッダファイルが足りないと言われた。

% uname -a
Linux gley 4.9.0-8-amd64 #1 SMP Debian 4.9.110-3+deb9u4 (2018-08-21) x86_64 GNU/Linux

4.9.0-8-amd64のヘッダファイルが必要なようだ。別のパソコンで該当のdebファイルを落としてきてdpkg -iで入れる。ちなみにcommonとamd64の両方が必要だった。

その後、再度make install。 再起動するとネットワークに繋がっていた。

まとめ

新し目のパソコンでLinuxを動かすのは大変。 ただドライバをビルドしてインストールする作業は初めてで勉強になった。 もうやりたくない。

ちなみにオーディオデバイスドライバが入っていないので音は出ない。 そのうち頑張る。

プログラミング言語Egisonの型システムを設計するインターンをした

概要

2018年3月11日から4月14日まで楽天技術研究所でEgisonの型システムの設計 & 型検査器を書くインターンをしていた。 もうインターンから半年も経ってしまったが、何も書かないよりはましというわけでブログ記事を書くことにした。

実装した型検査器はここにある。 まだまだ不完全ではあるが、一応動くのでよかったら試してみてほしい。

Egisonとは

Egisonとは江木さんという方が開発しているLisp likeなプログラミング言語で、非常に強力なパターンマッチ機構を持つ言語である。 江木さんは2007年からほぼ一人でEgisonを開発し続けており、その歴史はここで見ることができる。 最近ではパターンマッチ機構を活かして、数式処理システムの制作に使われている(江木さんがつかっている)。

インターンが始まるまで

Twitterをぼんやり眺めていたら「Haskellで言語実装するバイトがある!」ということで即応募した。 DMを送ったらSkypeで面接することになって、そのまま採用してもらった。 普段は京都に住んでいるので、東京に行かずに済んだのはすごく助かった。

採用が決まった後は、Egisonが微分幾何の記述に使われるということなので局面と曲線の微分幾何を読んでいた。 研究室でPPL2018に行ったら隣の席に江木さんがいて、そのとき初めて江木さんに会った。

インターン初週

インターン初日、東京で疲れてしまったのか、高熱と吐き気がして会社を休んだ。 社会人失格かと思ったが、次の日出社したら「大丈夫ですか」と気遣ってくれて嬉しかった。 後でTwitterを見た感じ、東京で風邪が流行っていたらしい。

インターン初週はEgisonの実装を読むことが主な業務だった。 Egisonは巨大な構文木インタープリタとして実装されており、相次ぐ機能の拡張によってエライことになっていることが分かった。

インターン2週目

江木さんがEgisonに型検査を入れたいというので、Egisonのサブセットを抽出、定式化をして、そのサブセットに対して型システムを設計しようという話になった。 Egisonにはmatcherやprimitive patternなどの通常の言語には無い構文要素があり、ちょっと大変だった。

この週の金曜日、江木さんが東大の出身研究室(萩谷研)を訪問するというのでくっついて行った。 萩谷研では、Egisonの意味論をどう定義するかという話をしていた(僕は議論する様子を眺める係をしていた)。 この議論は後々論文になり、APLAS 2018に採択されている。

インターン3週目

2週目に設計した型システムを型検査器として実装した。 基本的にはHM型の制約解消アルゴリズムで実装したが、 型付けできない式を受理するためにワイルドカード型を入れたりした(Egisonはもともと型なしの言語なので、型付けできないが動く式が基本ライブラリ中に存在する)。 当時は知らなかったのだが、あとで確認してみると漸進的型付けの型検査と同じような実装になっていた。

インターン4週目

引き続き型検査器を実装した。 matcherを正しく型付けできたときがとても嬉しかったのを覚えている。

f:id:a_kawashiro:20180403122554j:plain:w300

↑インターン中の食事の一例

インターン5週目

成果発表のためのスライド制作&発表練習をした。 スライドが全直しになったりしていい経験になった。 この経験が後々、未踏の二次審査で役に立ったような気がする。 最終発表の後で江木さんと二人でもんじゃ焼きを食べにいった。

感想

インターンを通して基本的に江木さんと二人だけで仕事をしていたが、江木さんがとても良い方だったのであまり苦ではなかった。 また週に一度kotapikuさんや梅崎さんがアルバイトに来て、数学の話をしたりするのが楽しかった。 食堂も大変美味しいのでついつい食べすぎてしまい、かなり太った。

ISUCON8予選に参加した

ISUCON8の予選にokeigoさん、mayokoさんとチーム「しょラーさんのおかげ」として参加していた。 最終的な得点は8000点くらいで予選落ちだった。悔しい。

チームメイトの参加記

brookbach.com

予選まで

とか言っていたら としょらーさんの穴を埋める形で誘ってもらい、参加することになった。

ISUCONの参加が決定してからは手元でISUCON7の予選、ISUCON6の予選を立てて練習していた。 N+1クエリ問題について初めて知った。 あとsystemd、MySQL、nginx、pythonのプロファイラの設定も初めてでいろいろ勉強になった。

予選の一週間前にokeigoさんがISHOCON2をセットアップしてくれて、そのサーバを使って3人で練習した。 3人とも離れたところに住んでいるので、Discordで音声通話、Slackでチャット、GitHubでコードを共有することになった。 言語は3人とも読めるPythonを使うことにした。

予選当日

朝

6時ぐらいに目が覚めた。いつもより6時間くらい早起き。

10時〜

予選スタート。 設定ファイルやpythonのアプリの実装をデプロイするスクリプトを書いた。 h2oをnginxに切り替えるのはokeigoさんがやってくれた。 この間にmayokoさんがアプリを読んでいた。

11時〜

とりあえずベンチマークを取った。 /favicon.icoが異常に重かったのだが、okeigoさんが設定のtypoを見つけて直したら解消した。

13時〜

僕はapp.pyの中でsheetをランダムに並び替えているところを小手先の小技で高速化しようとしていた。 が、あまり早くならなかった。 mayokoさんとokeigoさんがapp.pyのget_eventの改善をやっていた。

14時〜

mayokoさんの実装が終わった。 マージしてベンチを取ったら5000点ぐらい出て、学生3位になったので正直勝ったと思った。

15時〜

okeigoさんがredisを使ってキャッシュを実装していた。 venv環境にどうやってredisをインストールするのかがわからずに悪戦苦闘した。 結局バイナリをコピーして対応したらしい。SUGOI

16時〜

キャッシュの実装が動いたので、そろそろ3台構成にしましょうか、という話になった。 が、ポートの開放とかでいろいろ詰まった。 僕はあんまり何もできなかった。

17時〜

17:30ぐらいに3台構成が動いた。 あとは何度がベンチマークをとって終了。 最終的には7900点ぐらいでたはず。

18時〜

お祈りした。

19時ごろ

結果が出た。予選を通過することはできなかった。

反省

  • okeigoさんの負担が重すぎた。もうちょっとサーバの設定とか練習しとけばよかった。
  • 役割分担がきちんと決まっていなかった。アプリ2人、インフラ1人というのがバランスが良さそうだった。
  • 複数台構成におけるサーバ間の通信についてわかっていなかった。ISUCONのような特殊な環境ではファイヤーウォールを切って、全サービスが0.0.0.0:portをリッスンしてしまえば良いと思った。
  • サービスとして登録するpythonスクリプトに新しくライブラリ(redis)を追加する処理についてわかっていなかった。
  • プロファイルをちゃんと見ていなかった。ログの可視化スクリプトを作成しておくべきだった。

まとめ

チカラが足りなかった。悔しい。

Vimをコンパイルしてインストールする

使っているプラグインの関係で+python,+lua,+perlなVimが必要になりました。
しかし、Ubuntuのパッケージで条件を満たすものが見当たりません。
そこで自分で一からコンパイルしてインストールしました。

僕は自分でコンパイルしたソフトウェアを$HOME/.local/以下にインストールしているので、
--prefix=$HOME/.localとしています。
必要に応じて適当に変更してください。

git clone https://github.com/vim/vim
cd vim
./configure --prefix=$HOME/.local/ --with-features=huge --enable-multibyte --enable-gpm --enable-cscope --enable-fail-if-missing --enable-perlinterp --enable-python3interp --enable-rubyinterp
make install

あとは$HOME/.local/bin/vimにパスを通すだけです。

nvimに移行したほうがいいのかなぁ。

githubのバックアップを取る

年末も近くなってきたのでgithubが落ちた時に備えてリポジトリのバックアップを取ることにしました。
以下のスクリプトを実行するとgithub以下にすべてのリポジトリがバックアップされます。

YOUR_ACCESS_TOKENはSign in to GitHub · GitHubで作れます。
Select scopesのところでreposの欄をすべてチェックしてトークンを作成してください。 

#! /bin/bash

token=YOUR_ACCESS_TOKEN
curl "https://api.github.com/user/repos?access_token=${token}&per_page=100&affiliation=owner" 2>/dev/null -o tmp
repos=`cat tmp | grep ssh_url | cut -d" " -f 6 | sed -e 's/"//g' | sed -e 's/,//g'`
mkdir github
cd github
for r in ${repos}; do
    name=`echo ${r} | sed -e "s:git.*/::" -e "s:[.]git::"`
    git clone ${r}
    cd ${name}
    for branch in `git branch -a | grep remotes | grep -v HEAD | grep -v master `; do
        git branch --track ${branch#remotes/origin/} $branch
    done
    cd ..
done
rm tmp

これでgithubが落ちても安心ですね。