SMLでコンパイラを書いた

このエントリはML Advent Calendar 2015と言語実装 Advent Calendar 2015の20日目の記事です。 言語実装 Advent Calendar 2015の19日目の記事はh_sakuraiさんのJavaのサブセットコンパイラの作成でした。

タイトルの通り、Standard MLでコンパイラを書いた話をします。 対象言語はSMLのサブセットで、仮想機械の命令を出力します。

対象言語

だいたいこんな感じ SMLを触った事があれば何となく分かりますよね…？

SMLのサブセットと言いつつ、λ計算にintとboolとタプルとletを入れて中置演算子のサポートを手厚くしたような感じです。 +, -, *, <=の四つの中置演算子が予め定義されています。

仮想機械

無限個のレジスタがあって、レジスタの内容が指しているアドレスにジャンプできるような仮想機械です。命令セットはこんな感じ 例えば、

let
  val s = fn x => fn y => fn z => x z (y z)
  val k = fn x => fn y => x
in
  s k k
end

をコンパイルすると次のようなプログラムが出力されます。

main_462:
  e_387 := 0
  e_393 := 1
  e_369 := 100
  n_352 := e_369
  acc_350 := e_387
  k_383 := HALT_368
  goto direct_457

direct_457:
  if_cond_385 := <= (n_352, e_387)
  if if_cond_385 then goto then_463 else goto else_464

then_463:
  stack_459 := acc_350
  stack_458 := #0 k_383
  f_465 := #1 k_383
  goto [f_465]

else_464:
  e_391 := - (n_352, e_393)
  e_397 := + (acc_350, n_352)
  n_352 := e_391
  acc_350 := e_397
  goto direct_457

x_456:
  k_383 := stack_461
  acc_350 := stack_460
  n_352 := stack_459
  e_393 := #1 stack_458
  e_387 := #0 stack_458
  goto direct_457

どうせ吐くならSSAとかにしてさらに最適化をしたいところですが、第一級クロージャのせいでコントロールフローが自明ではないので止めておきました。

あとはレジスタ割り当てさえ済ませてしまえば機械語が手に入りそうな気がしないでもないですが、僕が低レイヤーに詳しくないのと、 まだ文字列の表示も行えないぐらい対象言語が貧弱なのもあって今はこの程度に留めておきます。

コンパイラの構成

コンパイルの流れはこんな感じ。その処理の実装が書かれたファイル名も併記しておきます。 CPS変換が行われているので分かる通り、中間表現にはCPSを使っています。

構文解析

字句解析はmllexに丸投げなので特に言及する事も無いです。

なぜ構文解析と中置演算子の構文解析が分かれているかと言うと、今回の対象言語には中置演算子の優先順位と結合性を変える構文があるせいです。 中置演算子の優先順位と結合性をプログラマが変えられるためにmlyaccでは手に負えないので、それ以外の部分をパースした次のような構文木を出力させます。

  datatype exp =
    (* constant *)
      CONST of Const.t
    (* variable *)
    | VAR of string
    (* non-infixed operator *)
    | OP of string
    (* if M then N_1 else N_2 *)
    | IF of exp * exp * exp
    (* fn x => M *)
    | ABS of string * exp
    (* let d in N end *)
    | LET of dec list * exp
    (* sequence of expression *)
    | SEQ of exp list
    (* ( M ) *)
    | PAREN of exp
    (* (M_1, ... , M_n) *)
    | TUPLE of exp list
    (* case M of (x_1, ... , x_n) => N *)
    | CASE of exp * string list * exp
  and dec =
    (* val x = M *)
      VAL of string * exp
    (* val rec f = M *)
    | VALREC of string * exp
    (* infix d vid_1 ... vid_n *)
    (* infixr d vid_1 ... vid_n *)
    | INFIX of Infixer.Assoc.assoc * int * string list
    (* nonfix vid_1 ... vid_n *)
    | NONFIX of string list

これをinfixing.smlで演算子順位構文解析して最終的に次のような構文木を得ます。

  datatype exp =
    (* constant *)
      CONST of Const.t
    (* variable *)
    | VAR of string
    (* if M then N_1 else N_2 *)
    | IF of exp * exp * exp
    (* fn x => M *)
    | ABS of string * exp
    (* M N *)
    | APP of exp * exp
    (* let d in N end *)
    | LET of dec list * exp
    (* (M_1, ... , M_n) *)
    | TUPLE of exp list
    (* case M of (x_1, ... , x_n) => N *)
    | CASE of exp * string list * exp
    (* op (+) (M_1, ..., M_n) *)
    | PRIM of Prim.t * exp list
  and dec =
    (* val x = M *)
      VAL of string * exp
    (* val rec f = M *)
    | VALREC of string * exp

型推論

Rémy's algorithmを用いてlet多相な型を推論しています。 とは言え趣味のプログラムであんまり計算量を気にしても仕方ないので、レベルを使って量化できる変数か判定するだけに留めていますが。

今回の対象言語には参照も配列も存在しないのでvalue restrictionはまだ入れていません。

型推論を行うと、次のように型抽象と型適用が明示された構文木が生成されます。

  type id = Id.t * Type.t
  type polyId = Id.t * Type.scheme

  datatype exp =
    (* constant *)
      CONST of Const.t
    (* x [T_1] ... [T_n] *)
    | VAR of Id.t * Type.t list
    (* if M then N_1 else N_2 *)
    | IF of exp * exp * exp
    (* fn (x_1 : T_1, ... , x_n : T_n) => M *)
    | ABS of id list * exp
    (* M (N_1, ... , N_n) *)
    | APP of exp * exp list
    (* let d in N end *)
    | LET of dec list * exp
    (* (M_1, ... , M_n) *)
    | TUPLE of exp list
    (* case M of (x_1, ... , x_n) => N *)
    | CASE of exp * id list * exp
    (* op (+) (M_1, ..., M_n) *)
    | PRIM of Prim.t * exp list
  and dec =
    (* val x : forall X_1 ... X_n. T = /\X_1. ... /\X_n. M *)
      VAL of polyId * exp
    (* val rec f : forall X_1 ... X_n. T = /\X_1. ... /\X_n. M *)
    | VALREC of polyId * exp

カリー化された関数の最適化

MinCamlなどでは対象言語で複数引数の関数を認めていますが、 今回のコンパイラの対象言語では認めていないので、複数引数の関数を定義しようと思うとカリー化するかタプルを使う事になります。 カリー化された関数をそのまま機械語に落としてはあまりに非効率的ですから、何としても最適化したい所です。

とは言え、あまり良い方法が思い付かなかったのでfn x => fn y => fn z => ...のように関数抽象が連続している場合に限って これをfn (x, y, z) => ...のような項に置き換えるだけに留めています。

実際には以降の最適化でうまくやってくれる事を期待してfn x' => fn y' => fn z' => (fn (x, y, z) => ...) (x', y', z')のような式に置き換えるように実装されています。

CPS変換

一般的なCPS変換の実装になっていると思われるので特筆する事も無いですが、 面倒だったので型の情報を捨ててしまっています。

  (* t *)
  datatype term =
    (* c *)
      CONST of Const.t
    (* x *)
    | VAR of Id.t
    (* fn (x_1, ..., x_n) => e *)
    | ABS of Id.t list * exp
    (* ( + ) (x_1, ... , x_n) *)
    | PRIM of Prim.t * Id.t list
    (* (x_1, ..., x_n) *)
    | TUPLE of Id.t list
    (* #n x *)
    | PROJ of int * Id.t
  (* e *)
  and exp =
    (* x (y_1, ..., y_n) *)
      APP of Id.t * Id.t list
    (* let val rec f = t in e end *)
    | LET_REC of binding list * exp
    (* if x then e1 else e2 *)
    | IF of Id.t * exp * exp
  withtype binding = Id.t * term

これは後で改良したいですね。

関数内で定義された変数の持ち上げ

fn z => let w = x + y in ...と言った感じに関数内に既に計算できる式がある場合、 関数が呼び出される度に計算されて効率が良くないのでlet w = x + y in fn z => ...のように関数の外に出してやります。（厳密にはCPSになっていませんが説明のための例なので）

再帰関数などに適用されればループ不変式の追い出しのように振る舞います。

変数定義をif文の中に移動

let x = ... in if y then ... else ...のようにif文の前に依存しない変数の定義があった場合、 if y then let x = ... in ... else let x = ... in ...と言った感じにif文のthen節とelse節の中に入れてしまいます。

以降のデットコード除去でletが除去されればifのどちらかでしか必要の無かった計算を片方だけでしか行わないようにできますし、 then節の中では条件式がtrueになるといった情報を利用してより積極的な定数畳み込みができるようになります。

クロージャ変換

MinCamlに実装されてる最適化やCSE、η簡約ぐらいなら皆さん分かりますよね…？

クロージャ変換も説明の必要は無いと思いますが、関数呼び出し全てにクロージャを使っていては効率が悪いので、 トップレベルにある関数を呼び出すのとクロージャが表す関数を呼び出すのは区別しています。

  (* t *)
  datatype term =
    (* c *)
      CONST of Const.t
    (* x *)
    | VAR of Id.t
    (* ( + ) (x_1, ... , x_n) *)
    | PRIM of Prim.t * Id.t list
    (* (x_1, ..., x_n) *)
    | TUPLE of Id.t list
    (* #n x *)
    | PROJ of int * Id.t
    (* <E, f> *)
    | CLOSURE of Id.t list * Id.t
  (* e *)
  and exp =
    (* x (E, y_1, ..., y_n) *)
      APP of Id.t * Id.t list * Id.t list
    (* c (x_1, ..., x_n) *)
    | APP_CLOS of Id.t * Id.t list
    (* let val x = t in e end *)
    | LET of binding * exp
    (* if x then e1 else e2 *)
    | IF of Id.t * exp * exp
  withtype binding = Id.t * term

  type fundec = Id.t * (Id.t list * Id.t list * exp)
  (* p *)
  (* let val rec f = fn (E, x_11, ..., x_n1) => e and ... in e end *)
  type program = fundec list * exp

仮想マシンコード生成

CPS変換後のプログラムにおいて関数呼び出しは末尾でしか行われないので、 引数が代入されると期待されている変数に値を代入してジャンプするだけで関数呼び出しを実現できます。

クロージャが表している関数の呼び出しでは引数が代入されると期待されている変数が何か分からないので、 とりあえずstack関数が返す変数に代入して呼び出して、呼び出された側に対応して貰います。

あと、クロージャは自由変数のタプルとジャンプ先のアドレスの組として扱います。

それ以外の変換はstraightforwardでしょうか。

ソースコード

ソースコードはGitHubで公開しています。https://github.com/fetburner/Udon

issue、pull req大歓迎です。