type t (* void *)

ソフトウエアのこととか

コンパイラ: min-camlをJVMバックエンドに移植した話

この記事は言語実装アドベントカレンダー21日目、MLアドベントカレンダー21目の記事です

min-camlのJVMバックエンドを作ったという話を前に書いたのですが、 それの詳細を書きたいと思います。 前の話はこの辺にかかれています。

JVMバックエンドに移植するのは大して難しくないというのは上の記事で書きました。 スタックマシンへのコンパイルの方針はほぼ説明尽くしたと思っていますが、 そのへんで説明していないものについて説明します。

基本方針

min-camlのシンタックスというのは以下で表される非常にシンプルなものなのです。

f:id:no_maddojp:20151222022715p:plain

移植する際はこれを直接扱わずに済みます。直接対象にするのはClosure.progです。 min-camlでは以下のように形式が変換されます。

f:id:no_maddojp:20151222022729p:plain

min-camlではまずK正規化され(ここを見てください)、次にクロージャ変換されます。 次の中間言語Asm.progからはマシン依存の中間コードとなります。標準のmin-camlのプロジェクトでは x86やSPARCフォルダに入っているのがそれぞれの実装です。 今回はここにjvmファイルを加え、マシン依存の中間表現を書き換えるところから始まります。

扱う対象のClosure.progの定義を見てみましょう。これはK正規化・クロージャ変換後の言語で、 クロージャ変換が終わっているためトップレベルの関数定義(fundef list)と実行部分(t)に分かれています。 下の定義を見て下さい(ここのコピーです)。

type closure = { entry : Id.l; actual_fv : Id.t list }
type t =
  | Unit
  | Int of int
  | Float of float
  | Neg of Id.t
  | Add of Id.t * Id.t
  | Sub of Id.t * Id.t
  | FNeg of Id.t
  | FAdd of Id.t * Id.t
  | FSub of Id.t * Id.t
  | FMul of Id.t * Id.t
  | FDiv of Id.t * Id.t
  | IfEq of Id.t * Id.t * t * t
  | IfLE of Id.t * Id.t * t * t
  | Let of (Id.t * Type.t) * t * t
  | Var of Id.t
  | MakeCls of (Id.t * Type.t) * closure * t
  | AppCls of Id.t * Id.t list
  | AppDir of Id.l * Id.t list
  | Tuple of Id.t list
  | LetTuple of (Id.t * Type.t) list * Id.t * t
  | Get of Id.t * Id.t
  | Put of Id.t * Id.t * Id.t
  | ExtArray of Id.l
type fundef = { name : Id.l * Type.t;
        args : (Id.t * Type.t) list;
        formal_fv : (Id.t * Type.t) list;
        body : t }
type prog = Prog of fundef list * t

val fv : t -> S.t
val f : KNormal.t -> prog

この段階ではlet rec id x = x in let x = let y = id 2 in 1 + y - 3 in print_int xみたいなプログラムは以下のように 脱糖衣されています(id関数を途中に噛ませているのは最適化で四則演算が消えないようにするためです)。

(* 
  let rec id x = x in
  let x =
    let y = id 2 in
  1 + y - 3 in
  print_int x をコンパイルする
*)
# Main.str_to_cls "let rec id x = x in let x = let y = id 2 in 1 + y - 3 in print_int x";;
free variable print_int assumed as external
iteration 1000
iteration 999
directly applying id__5
eliminating closure(s) id__5
- : Closure.prog =
Prog
([{name = (Id.L "id__5", Type.Fun ([Type.Int], Type.Int));
   args = [("x__6", Type.Int)]; formal_fv = []; body = Var "x__6"}],
Let (("Ti1__7", Type.Int), Int 2,
Let (("y__8", Type.Int), AppDir (Id.L "id__5", ["Ti1__7"]),
Let (("Ti2__9", Type.Int), Int 1,
Let (("Ti3__10", Type.Int), Add ("Ti2__9", "y__8"),
Let (("Ti4__11", Type.Int), Int 3,
Let (("x__12", Type.Int), Sub ("Ti3__10", "Ti4__11"),
AppDir (Id.L "min_caml_print_int", ["x__12"]))))))))

これを見ると以下のことがわかります。正確なことはmin-camlの説明文を読んでください。

  • K正規化によって定数にも逐一名前が付いている
  • すでに木構造は平たくなっており、1+2+3みたいな四則演算もlet x = 1 + 2 in let y = x + 3 in y みたいに１つの計算（？）ごとに細かく分割されている
  • ネストしたlet式はすでに平たくなっている

前の記事で木構造を簡単にコンパイルできることがスタックマシンのいいところだ、みたいな 話を書きましたが木構造を対象にする必要はありません。 JVMバイトコードの性質を活かすならばコンパイラのパイプライン自体を変えたほうがいいでしょう。 今回はそこまでやりませんでした。

中間言語と上のことを踏まえると、タプルとクロージャくらいしか難しそうにないことがわかります。

変換の基本方針は前の記事のとおりで、 transl関数を再帰的に定義して出力のコード列を実行すると１つだけ スタック上に値が追加されるようにするというものです。 現実にはこれに引数をいくつか追加しなければなりません。

JVMバイトコードでは、そのメソッドでの最大のスタックサイズとローカル変数のサイズを 指定してやらねばなりません。またローカル変数を取り扱うためにどのローカル変数が何番地(?)に入っているのか 覚えておかねばなりません。そのためtranslの型はtransl: int -> int -> table -> instruction listとならねば なりません。最初のintが今のところのスタック使用最大サイズ、2番目のintがローカル変数の数、3番目が何かしらのテーブルだという気持ちです。

実装詳細

あまり自明じゃない部分についてのみ説明します。

クロージャの実装

まだ実装してないのですが、基本的な方針は立っています。 1つしかメソッドのないクラスを新たに作り、コンストラクタでクロージャの環境に入る 要素を受け取りそのクラスのフィールドにセットし、呼び出すときにはcls.app(arg1, arg2, ...)のように 関数呼び出しのためのメソッドを呼び出し普通に引数を渡せばOKです。

現在のmin-camlには部分適用がないのでこんな実装で大丈夫だと思います。 ちなみにもし存在したとしたらフルのMLと同じような部分適用を扱うのはおそらく効率が悪いです(cf: Scala)。

TODO: Scalaの部分適用のサーベイ

タプル

タプルはポインターの配列にコンパイルされます。プリミティブ型の値はBoxingする必要があります。 例えばlet x = (1, 3.14) in print_tuple xみたいなコードがあったとしたら このタプルの生成はjava/lang/Object型の配列を確保し、1と3.14を Integer.valueOfメソッドとDouble.valueOfメソッドでInteger、Double型に変換し それらをそれぞれ0, 1番地に代入するコードになります。

辛いところが、タプルをパターンマッチで破壊し中身を取り出す 時にBoxingした値をUnboxingする必要があります。

UnboxingのためにInteger型をint型にするためにはInteger.intValueメソッドを 呼び出す必要がありますが、上で述べたようにタプルはObject型の配列なので 取り出してメソッド呼び出しをするためには、なんとキャストが必要になります。 これをサボるとJVMのバイトコード検証機が不正なバイトコードだと言って コードを実行させてくれません(検証しないオプションをつければ実行できるのですが……)。

まぁ型付きのアセンブリみたいなものは面倒だという話です。

妄想：パラメータ多相性を加えると

min-camlは単相型な型しかつけません。これに多相的な型を加えるとバイトコードがどうなるのか 考えてみましょう。

まず思いつく問題は、多相的な配列に対する操作です。 JVMでは生の配列というのは5種類に分かれます(int, long, float, double, ポインタの配列)。 例えば多相関数Array.getではどんな型の配列に対しても要素にアクセスできる必要がありますが、 配列の種類が型によって分かれていてはこれを行うことができません。

主に2つ解決策が考えられます

  • 実行時に型をディスパッチして分岐する
  • 配列の要素はすべてBox化する

1番めの解決策の実行時のディスパッチはプログラムを遅くしてしまいます。 特にmapみたいに何回も繰り返す計算の中で毎回Array.getみたいな関数が 型ディスパッチを行うと地獄です。

2番目の解決策を取るとするとアセンブリを出力することを考えると、 Uniformでない(データのサイズが1ワードに揃っていない) 値だけをBox化すればよかったのが、すべての要素をBox化しなければならなくなってしまいました。

多相性とJVMバイトコードというのは相性がよくなさそうだなぁという感じです。 Javaのジェネリクスの実装がああなっているのもうなずける話です。

おまけ: Mixed representation

多相性をうまく扱う研究は古くからたくさん行われてきました。 その1つとしてXavier LeroyのMixed Representationがあります。

speakerdeck.com

研究の概略だけ説明すると、 伝統的なMLで実装されている全ての値をUniformにするのはやりすぎなので 単相的な関数に渡すときには単相的な表現を用いて、 多相関数に渡す時だけBox化などを用いた多相的な表現用いたら 効率的になりそうだから実験しましたというものです。

例えばlet make_pair x = (x, x) in print_tuple (make_pair 3.14)をコンパイルすることを 考えてみましょう(補助関数の型はprint_tuple: float * float -> unitです)。 mak_pairは多相関数で仮引数のxはBox化された表現だと思っているので、 make_pairに渡すときに3.14はBox化されている必要があります。 make_pairの返り値のタプルは中身がBox化されているわけですが、 print_tupleに渡すときにはフラットなタプルを渡したいので、返り値のタプルを 壊してフラットなタプルを作りなおす必要があります。

boxとunboxという操作を加えてみると上のプログラムは以下のようになります。

let make_pair x = (x, y) in
let a = make_pair(box 3.14) in
let b = (unbox(fst a), unbox(snd a)) in
print_tuple b

この研究ではもちろんアセンブリを対象にしているのですが、 同じ議論がJVMバイトコードにも当てはまります。

確かに単相的な配列を受け取る関数に対しては単相的な 配列を渡して、多相的な関数には多相的な表現をした配列を渡すというのは自然な気がします。 これで一部Box化をなくすことができ、パフォーマンスが大菊恒常するでしょうか？

この実装方法の問題はデータ構造を何回も作りなおさないといけないことです。 上の例ではタプルをmake_pairで作ってから後で単相的な関数に渡すために fstとsndでそれを壊してまた作りなおしています。

これが長さが短いタプルならばOKだと思うのですが、長さ10000の配列に対して適用できるでしょうか？

実際上のスライドの論文でもlistやarrayに対して この表現を適用するのは諦めています。タプルも長さが3以下のものにのみ適用しています。 (フラットにできない理由がもうひとつあるのですがそれはスライドを見てください)