言語処理系 Advent Calender１日目の記事です。 初日なのであまりハードルを上げすにライトなネタを。
趣味でコンパイラを作る際に最終的な出力ファイルを何にするのかは悩みどころです。
手づくりの温かみのあるバックエンドでやるのか、LLVMやC--,COINSを経由するのか、
はたまたJVMバイトコードなどのバイトコードにするのか。
CやJavaScriptに出力するのは相対的に簡単そうで実用的だなぁという感触もあります。
今回はそれなりの言語をちゃちゃっと走らせるための対象プラットフォームとしてJVMを検証するために、
min-camlのサブセットのJVMバックエンドを実装してみました。
サブセットと言っているのはクロージャの対応が終わってないからです。実装の見通しは立ってます。
感想としてはJVMバイトコードへのコンパイルはそれほど難しくないけども
JVM特有のつらみがあるという知見が得られました。
１日目ということでJVMバイトコードの説明や、
スタックマシンへのコンパイルについて書きたいと思います。
min-camlに移植した話は別の記事ということで……間に合わなかったとも言いますがが。
詳しくない人が読むことを期待して結構真面目に基本的な部分から書きます。
JVMバイトコードについて
JVMはスタックマシンですが、純粋なスタックマシンではなく 無限のローカル変数をストアしたりロードするための機能があります。 なのでこのマシンへのコンパイルはとても簡単です。
ちなみに別に.javaファイルを最終結果として出力しても良いのですが
その場合gotoが使えません。末尾再帰最適化をしたくなったら直接バイトコードを吐かねばなりません。
Compiling standard ML to Java bytecodes
というICFP98の論文ではSMLをJavaバイトコードにコンパイルしていますが
末尾呼び出し最適化のためにgotoを用いたと書かれています。
(そのために分割コンパイルできなくなったんだと思いますが……)
スタックマシンというのは木構造をほぼそのままコンパイルしやすい構造です。
基本的なアイディアは、再帰的にコンパイルする関数compを定義しcomp tの出力する命令列を実行すると、
評価結果１つだけがスタックにプッシュされるように設計することです。
この不変条件だけを意識すれば非常に簡単です。簡単な場合の
- 四則演算の場合
- 関数呼び出し（スタティックメソッド呼び出し）の場合
- ローカル変数がある場合
について考えてみます。
四則演算
例えば(- t1 t2)をコンパイルする場合を考えてみましょう。
整数同士の引き算を行うための命令isubは
スタックの上から２番目の値とスタックトップの値をポップして、２つの差を取って
スタックにプッシュする命令です。スタックの動きを表してみると
..., i1, i2 ->
..., (i1 - i2)
という動きになります。(一番右がスタックトップ、矢印が実行したあとだという気持ちです) 詳しくはリファレンスを見てください。 Wikipediaの記事の表も見やすいと思います。
ちなみに命令の接頭辞のiはintを表していて、接頭辞l(long)やf(float)、d(double)、a(ポインタ)
も存在します。
t1の評価結果１つだけをプッシュするようにコンパイルし、
同様にt2の評価結果１つだけをスタックにプッシュするようにコンパイルして、
最後に引き算を実行するようにします。Haskell風に書くならば(文法は適当です型とか考えてません)
comp :: prog -> instruction []
comp (- t1 t2) = comp t1 ++ comp t2 ++ [isub]
でしょうか。これを実行すると
comp t1, comp t2により２つの整数がスタックトップに追加され、
その２つの値をポップした後、その２つの値の差をとったものがスタックにプッシュに追加されます。
更にこれは上で述べたcomp (- t1 t2)の出力は実行結果１つだけを
スタックトップに追加する、という不変条件を守っています。
関数呼び出し
関数呼び出し(スタティックメソッド呼び出し)のためには
invokestatic命令があります。これはn引数関数(スタティックメソッド)を実行するときに
スタックトップからn個の値をポップして引数として渡して実行結果をスタックにプッシュする、というものです。
..., v1, v2, ..., vn ->
..., f (v1, v2, ..., vn)
この方針でcompを関数適用の場合でも実装してみると、例えば
f (t1, t2, ..., tn)は引数部分の木を順番にコンパイルして結合し、最後にfを呼べばいいことがわかります。
comp (f (t1, t2, ..., tn)) =
comp t1 ++ comp t2 ++ ... ++ comp tn ++ [invokestatic f (typeof f)]
ちなみにinvokestatic命令には一緒にメソッドの型を書きます。
JVMの場合は書かないとオーバーロードがあるのでどのメソッドを呼び出すのか分からないですし、
何個引数を消費するのか、またスタックに載っている値の長さは揃っていないので
(int型は32bit, long型は64bit)どれくらいの長さをパラメータとして渡すのかも分かりません。
ローカル変数
iload nはスタックにn番目のローカル変数をプッシュする命令です。
istore nはスタックトップの値をn番目のローカル変数に代入しポップする命令です。
int x := t
のようなプログラムは以下のようにコンパイルできます。
comp (:= x t) = comp t ++ [istore n] (ただしnはフレッシュ)
変数自体のコンパイルは変数が格納されている場所を覚えておいてiload nなどその型にあった
ロード命令を呼ぶだけです。
また最初についているiもisubと同じくintを表しており、
longやdouble、ポインタをロードするバージョンも存在します。
具体例
Javaコードをコンパイルしてそれをjavapコマンドで逆アセンブルしてみましょう。
javap -c -s Hogeの実行結果は以下のようになります
プログラム（それ以外省略）：
public static int f (int x, int y)
{
return x + M.f (3 * y, M.g (4));
}
実行結果：
public static int f(int, int);
Signature: (II)I
Code:
0: iload_0
1: iconst_3
2: iload_1
3: imul
4: iconst_4
5: invokestatic #2 // Method M.g:(I)I
8: invokestatic #3 // Method M.f:(II)I
11: iadd
12: ireturn
iconst_n命令はスタックに整数nをプッシュしますireturn命令はスタックトップの値をポップして返り値とし、呼び出し元に戻る
一応1命令ごとのスタックの実行イメージ図を貼っておきます。
上のプログラムを中置演算子をすべて前置にしてcompでの変換を考えてみると
comp (+ x (M.f [* 3 y, M.g [4]]))
= comp x ++ comp (M.f [* 3 y, M.g [4]]) ++ [iadd]
= [iload_0] ++ comp (* 3 y) ++ comp (M.g [4]) ++ [invokestatic M.f] ++ [iadd]
= [iload_0] ++ comp 3 ++ comp y ++ [imul] ++
comp 4 ++ [invokestatic M.g] ++ [invokestatic M.f] ++ [iadd]
= [iload_0, iconst_3, iload_1, imul, iconst_4, invokestatic M.g, invokestatic M.f, iadd]
ireturnを補ってやれば全く同じ出力になりました！(四則演算は他のものも加算と全く同様です)
Javaのような言語ではトップレベルにいきなり式を書くことはできず
returnやassign, void型のメソッド呼び出しであることが簡単にわかるのでireturnなども補うことができます。
JVMバイトコードには他にもif文のための命令や配列操作、キャストなどもありますが
最適化などを考えなければcompの実行結果の不変条件をきちんと守ればそんなに難しくはありません。
Jasminでバイトコードを手書きする
直接JVMが解釈できるバイナリを書くのも難しくないと思いますが
デバッグがつらそうなのでアセンブラを経由して出力させましょう。
僕はよくわからないですがJasmin
がアセンブラとしてそれなりに使われているようです。
Debian 8のstableレポジトリから普通にaptでインストールしたものはなんだか ヒープ使いきって死んだりするのでforge からダウンロードするといいですサンプルもついてきますし。
jasminの使い方はどうやらいろいろな大学で教材として使っているようで
なんだかたくさんヒットします。
マニュアルのリファレンスとサンプルだけでも十分に理解できますが、
このへん
を見るといいと思います。
jasminに限らずJVMバイトコードを出力するときに気をつけることは、
javaコマンドで実行するときにベリファイヤがバイトコードの型検査のよようなものをするということです。
例えば実態がIntegerだと明らかにわかっているObject型の値から
メソッドintValueを呼ぼうとするとcheckcast typ命令でキャストを行わない限り
ベリファイヤが不正なバイトコードだと言って実行させてくれません。
-noverifyオプションをつけると検査無しで実行できるのでベリファイエラーになったらば一度
検査無しで実行してみるといいと思います。
どの命令で失敗したのかなどあまり親切なメッセージを出してくれないところがあれですが
コンパイラ開発者にしか関係ないことですからね……。
おまけ
EmacsVM向けのバイトコードもバックエンドとして検討していました。
elispコードはバイトコードにコンパイルされますがこれもスタックマシンベースです。
elispバイトコードの関連だと、 ちょっとだけ検索してみると面白い記事がヒットします。
- Emacs Byte-code Internals
- emacs-cl elispで実装されたCommon Lisp ! Emacs拡張をCommon Lispでかける、らしい
Emacsにはdisassembleコマンドがあり、Emacsが読み込んだバイトコードを表示できます。
下のプログラムをファイルに保存してbyte-compile-fileしload-fileで読み込んでから
disassembleを実行してみます。
;;; -*- lexical-binding: t -*-
(defun f (x y)
(+ x y)
)
(defun fact (n)
(if (= n 0) 1 (* n (fact (- n 1))))
)
実行結果はこちら
byte code for f:
doc: ...
args: 514
0 stack-ref 1
1 stack-ref 1
2 plus
3 return
byte code for fact:
doc: ...
args: 257
0 dup
1 constant 0
2 eqlsign
3 goto-if-nil 1
6 constant 1
7 return
8:1 dup
9 constant fact
10 stack-ref 2
11 sub1
12 call 1
13 mult
14 return
JVMと違いローカル変数という概念はelispバイトコードにはありません。
fのバイトコードを見てみると引数はスタックに格納されてから関数呼び出しされることがわかります。
stack-ref nはトップからn番目の値をコピーしてプッシュする、というものです。
0-basedな数え方をするのでstack-ref 1は上から２番目の値(fの最初のバイトコードならばxを指す)
をコピーすることになります。次のstack-ref 1はxが積まれたのでyを指します。
あとはJVMバイトコードが理解できれば特に難しい部分はないのですが、
関数呼び出しの際に関数もpushして関数呼び出しを行います(fact関数の中の9命令目のconstant fact)。
ちなみにlexical-scopeにするオプションをつけてコンパイルすると
引数はスタックに格納されて渡されますが、つけないと名前でアクセスすることになります。
byte code for f:
args: (x y)
0 varref x
1 varref y
2 plus
3 return
このくらいにしておきますがなんだかスタックマシンとして普通なので このあたりを読めばわかります。