molecular coordinates

/var/log/coorde.log

mlmlの実装について

前記事: 自作OCamlコンパイラでセルフホストした - molecular coordinates

mlmlの制作のまとめとしてここに実装の詳細を記しておきます。

mlmlとは

自作OCamlコンパイラです。詳しくは前記事を参照してください。

全体の構成

以下の図にmlmlの構成を示します。

f:id:coorde:20190523180006p:plain

ファイル名を入力として受け取ります(①)。そのファイルをエントリポイントとしてBundlerが必要なソースを集めて一つのASTに纏め、Analysisに渡します(②)。AnalysisがASTに様々な変形を施し、Codegenに渡します(③)。CodegenはASTからアセンブリを生成し、出力します(④)。

依存関係の解決 (Bundler)

mlml/mlml/bundler at develop · coord-e/mlml · GitHub

まず受け取ったファイルに字句解析・構文解析を済ませます。次に構文解析によって作られたASTに対して依存関係の解析を行い、そのファイルが依存しているモジュールを探します。見つかった依存モジュールに対しても同じように解析を行い、下のようなツリー状のデータ構造*1を構築します。

f:id:coorde:20190523183945p:plain
依存関係ツリー (stdlibは省略)

次に、”自身が依存するモジュールが常に自分の前に存在するように"、このツリーを潰して直線状に並べます。(追記: この操作はトポロジカルソートと呼ぶようです。@syobon_hinataさん、ありがとうございます)

f:id:coorde:20190523184045p:plain
直線状になった依存関係 長っ

最後にこの並びに従ってモジュールを並べてやることで、それぞれのモジュールが必要なモジュールを参照可能な状態になった大きなASTが出来上がります。

めでたしめでたし...という感じですが、これは本来コンパイラがやるものではなくてビルドシステムにやらせるのが賢明だと思います。作ってしまったものはしょうがないんですが

識別子の名前解決 (Analysis)

mlml/resolve.ml at develop · coord-e/mlml · GitHub

今回はコード生成器でモジュールを意識したくなかったので、Analysisで名前解決*2を行ってしまうことにしました。私はこの変換を"Resolve"と呼んでいます。

以下のようなOCamlコードを考えます。

module Module1 = struct
  let f x = Printf.printf "Hello from Module1: %s\n" x
  let g () = f "g"  (* (1) *)
end

module Module2 = struct
  let f x = Printf.printf "Hello from Module2: %s\n" x
end

open Module2 ;;
f "mlml" ;;  (* (2) *)
Module1.g ()

ここではソースコード上で表記されている名前(fModule.gなど)を相対パス、変換後(Resolve後)の名前を絶対パスと呼ぶことにしましょう。

さて、このコード内では二回fという相対パスが使われていますが、その二つは実は違う実体を参照していることがわかります。 参照先が明確になるよう書き換えてみると(1)のfModule1.f、(2)のfModule2.fになります。

このように文脈を考慮して参照先を決定し、絶対パスに書き換える操作をResolveでは行っています。

相対パスは文脈によって参照している実体が変わりますが、絶対パスは文脈に関係なく参照先が定まります。そのため、全ての名前を絶対パスに変換してしまえばコード生成器でモジュールの文脈を意識する必要がありません。

参照だけではなく定義の名前も絶対パスに変換すると、変換後のコードは以下のようになります

(* 擬似コード *)
module Module1 = struct
  let Module1.f x = Printf.printf "Hello from Module1: %s\n" x
  let Module1.g () = Module1.f "g"  (* (1) *)
end

module Module2 = struct
  let Module2.f x = Printf.printf "Hello from Module2: %s\n" x ;;
end

open Module2 ;;
Module2.f "mlml" ;;  (* (2) *)
Module1.g () ;;

全ての名前が絶対パスになったので、もうモジュールに関する文脈(module定義やopenなど)は必要ありません。最終的にはそれらが取り除かれ以下のようになります。

(* 擬似コード *)
let Module1.f x = Printf.printf "Hello from Module1: %s\n" x
let Module1.g () = Module1.f "g"  (* (1) *)
let Module2.f x = Printf.printf "Hello from Module2: %s\n" x ;;

Module2.f "mlml" ;;  (* (2) *)
Module1.g () ;;

これでコード生成器内で名前が扱いやすくなりました。

カリー化

mlmlでは複数の引数を受け取る関数をカリー化しており、全ての関数が一つしか引数を受け取りません。

例えば次のOCamlコードを考えます。

let f x y z = x + y + z in
let g = f 1 2 in
g 3

ここではfx, y, zの三引数を受け取る関数として定義されています。これはmlmlでは糖衣構文で*3、脱糖すると以下のコードになります。

let f x = fun y -> (fun z -> x + y + z) in
let g = (f 1) 2 in
g 3

複数引数を受け取る関数を「一つ引数を受け取り、関数を返す関数」として扱うことで、カリー化が実現できます。また、引数を一つだけ考えればよくなるため、後の変換やコード生成が楽になります。

クロージャ変換 (Analysis)

mlml/closure.ml at develop · coord-e/mlml · GitHub

OCamlでは、関数内部で引数だけではなく外にある名前も参照することができます。以下のOCamlコードを考えます。

let a = 10 ;;
let b = 20 ;;
let f x = x + a + b ;;
f 1

関数f内でabが参照されていますが、それは関数の引数(x)ではありません。ここではabのような変数をキャプチャ変数と呼ぶことにします。また、それとは別に、引数やlet式に束縛されていない変数のことを自由変数と呼びます。例えば定義let f x = x + a + bを単体で見たときの自由変数は{a, b}です。

さて、最終的にアセンブリに出力する際、関数内から関数外の変数を参照することはできません*4。そのため、変換によって関数定義から自由変数を取り除く必要があります。この変換をクロージャ変換と呼びます。基本的なアイデアとしては、関数を関数とキャプチャ変数の組として扱うというものになります。

クロージャ変換についてはMinCamlのページでわかりやすく解説されています。

mlmlのクロージャ変換では関数定義のキャプチャ変数をタプルにまとめ、引数を本来の引数とキャプチャ変数のタプルで受け取るように変形します。そして、関数を実体とキャプチャ変数のタプルとして定義し直します。このタプルをクロージャと呼びます。また、関数適用ではクロージャを関数本体とキャプチャ変数のタプルに分解し、それを引数に渡してやることで意図した動作を実現しています。*5

この通りに変換すると先ほどのコードは以下のようになります。*6

let a = 10 ;;
let b = 20 ;;
let f =
  let f (x, (a, b)) = x + a + b in
  f, (a, b)
;;
let (_f, _fv) = f in _f (1, _fv)

変換後のコードに現れる関数定義(let f (x, (a, b)) = x + a + b)には自由変数がなくなっています。これで関数のコード生成が可能になります。

フォーマット文字列 (Analysis)

mlml/format_string.ml at develop · coord-e/mlml · GitHub

OCamlではPrintfもカリー化されており、以下のような扱いをすることができます。

let printer = Printf.printf "%s %d" in
List.iter (printer "hello") [1; 2; 3]

しかし考えてみると、Printfが受け取る引数の数は第一引数として受け取っているフォーマット文字列に依存します。 例えばPrintf.printf "%s"は文字列を一つ受け取る関数ですが、Printf.printf "%d %s"は数値と文字列を受け取る関数です。 これは一見コンパイラマジックでも使わないと実現不可能なように思われます。しかし、フォーマット文字列を関数に変換することでこれを実現することができます。

mlmlでは、フォーマット文字列は「関数を受け取り、その関数を必要な引数を受け取ってフォーマットした結果に適用する関数」に変換されます。

ややこしいので具体例をみていきましょう。

例えば"%s and %d"は、以下のような関数に変換されます。

fun k -> (fun s -> (fun d -> k (s ^ " and " ^ string_of_int d)))

フォーマット文字列自体に文字列を組み立てる機能を持たせる感じです。

そしてprintfを以下のように定義します。

let printf fmt = fmt (fun x -> print_string x)

こうすることで、

printf "%s and %d"

fun s -> (fun d -> print_string (s ^ " and " ^ string_of_int d))

に簡約できることがわかると思います。結果としてカリー化されたPrintfが実現できています。

値の内部表現 (Codegen)

OCamlには構造比較演算子=があります。これは二つの値が構造的に等しいかどうか判定するものです。

例えば(1, (2, 3)) = (1, (2, 3))trueに評価されます。当たり前のようですが、タプルはポインタとして実装されているので単純なcmpでは実現できません。値を再帰的に比較していく必要があります。

しかし、ただ値二つを渡されてもそれらを再帰的に比較することはできません。なぜならそれが数値なのかポインタなのかもわからない*7(=再帰的に比較すべきなのかどうかわからない)上に、ポインタだとしてデータのサイズがわからないとどこまで比較を進めていいのかわからないからです。

そこで、これらの情報を値に埋め込んでいます。

改めてまとめると、埋め込むべき情報は以下の三つです。

  • 数値なのかポインタなのか?
  • ポインタなら、続くデータのサイズ
  • 文字列なのかどうか (文字列を埋め込むとポインタと解釈されかねないので、例外的に扱い直接比較させる)

なお、mlmlでは簡単のためデータを8バイト単位で扱っています。

数値なのかポインタなのか

ほとんどの場合*8ポインタはアラインされているので下位2~3ビットが0になっています。ということで一つ目の「数値なのかポインタなのか?」については"数値の最下位ビットを必ず1にする"という決まりを作ってしまえばうまく区別できそうです。このアイデアocaml*9の実装から得たもので、これがOCamlの整数が1ビット足りない理由だったりします。*10

これを実現するために、数値は全て左シフトしたのち最下位ビット(以下LSBと呼びます)を立てています。(n*2+1、ここではこの状態をmarkedと呼ぶことにします*11 ) 実際に中身を使うときは右シフトすれば元の値が取り出せます。

f:id:coorde:20190524165142p:plain
marked int

いちいち整数を扱う度にこの変換を噛ませるのは大きなオーバーヘッドになりそうですが、意外とそうでもないのがこの表現の面白いところです。 例えばn+mを考えると、求めるmarkedな値は(n+m)*2+1となります。これは(n+m)*2+1=(n+m)*2+2-1=(n*2+1)+(m*2+1)-1と変形できるので、markedな整数同士の加算はadddecの二命令で実装できるわけです!これと同じように減算や乗算、論理否定なども"値を取り出す→計算する→作り直す"の手順を踏まずに少ない命令数で実装できます。最初に考えた人頭いいなあ。

ということで、値のLSBを見れば数値なのかポインタなのか判別できるようになりました。

ポインタに続くデータのサイズ & 文字列なのかどうか

ポインタが指す先の一つ目のデータにデータサイズを格納しています。

ただ、文字列かどうかも判別しなければいけないのでこのデータサイズ用の領域のLSBをこのフラグに使っています。データサイズ領域のLSBが1なら文字列、0ならそれ以外のデータです。

具体例を見ていきましょう。下の図に(1, (2, 3))をmlmlがどう扱うかを示します。背景の色が黒ならLSB=1、白ならLSB=0であることを表しています。

f:id:coorde:20190524165811p:plain
(1, (2, 3))のメモリ配置イメージ

タプルは文字列ではないので、データサイズ領域のLSBは0になっています。

文字列を含む構造は以下のようになります。文字列の長さをデータサイズ領域の次にmarked intとして格納しています。これは文字列長がO(1)で求められると色々と*12便利だからです。

f:id:coorde:20190524170003p:plain
("hello", "mlml world", 5)のメモリ配置イメージ

構造比較の実装

と、いうような感じで値の種類を実行時に判別しています。

構造比較演算子=ランタイムライブラリで実装されています。基本的には値の種類を見て再帰的に構造を比較していく感じです。

各種データ構造の実装

タプルは先ほどの画像で示した通りデータが並んでいるだけです。

ヴァリアントはインデックス付きのタプルとして実装しました。以下の型tを考えます。

type t =
  | A
  | B of int * int
  | C of t

ヴァリアント定義に現れた順番で各コンストラクタにインデックスを振っていきます。上の例ではA→0、B→1、C→2です。 そしてコンストラクタが受け取る値とコンストラクタのインデックスをタプルにした値に評価されるようにします。

let a = A ;;             (* (0, ()) *)
let b = B (10, 20) ;;    (* (1, (10, 20)) *)
let c = C (B (3, 4)) ;;  (* (2, (1, (3, 4))) *)

こうすることで構造比較はタプルとして比較することができますし、パターンマッチはインデックス同士を比較することで実現できます。

レコードはただのタプルとして実装されています。レコードのフィールドと要素のインデックスがコンパイル時に結びついています。以下のコードを考えます。

let t = { value: int; tuple: (int * int) } ;;
let v = { tuple = (2, 3); value = 1 } in
print_int v.value

ここで、型tvaluetupleの二つのフィールドをもつレコード型です。出現順にフィールドにインデックスをつけていきます。ここではvalue→0、tuple→1です。

そしてレコードの値を生成する時に、フィールドのインデックスに従ってタプルに値を配置します。上のコードでは{ tuple = (2, 3); value = 1 }とフィールドの順番が型定義と異なっていますが、インデックスに従って並べ替えられ、タプル(1, (2, 3))に評価されます。

レコードから値を取り出す時にもフィールドのインデックスを利用します。v.valueではvalueは0番目のフィールドなので、タプルvの0番目の要素を取り出すように評価されます。

このように、複雑に思えるデータ構造も単純化してタプルとして実装することができました。

GC (Codegen)

mlmlにはBoehm GCを使用したGCがついています。Boehm GCmallocGC_mallocに変えるだけでお手軽にGCが使えてしまう*13 、本当に最高な優れものです。GCなしだとセルフホストしようとした時にあっという間にメモリを食いつぶしてしまったので、GCが必須でした。

おわり

ここまで読んでくださりありがとうございました。mlmlの実装で凝ったことしている部分はだいたいこんな感じです。

あまり調べもせず思いついた方法に突っ走ってしまう傾向が強かった気がしています。モジュールの扱いはかなり改善の余地があると感じているので次に似たようなことをするときはもう少しマシな実装になるよう前例を調べてみようと思います。ocamlのモジュールはレコードになっているらしい*14

参考資料

mlmlの制作にあたり、以下の資料を参考にしました。

*1:ツリーというか有向グラフやな

*2:なんて呼べばいいかわからないのでそれっぽい呼び方をしました

*3:現実装、脱糖がパーサ内で行われているんですが、ダサいのでどうにかしたい

*4:グローバルに置いたりスタックを異常な使い方をすれば可能ですが、ややこしいので考えません

*5:日本語にすると全然わからない

*6:実際にはf、fvは適用される式に対してfreshになるように選ばれます

*7:型がない!!

*8:調べてみたら怪しくなってきた 実際mallocが返すポインタは大抵アラインされているんですが、仕様で規定はされていないらしい...??

*9:OCamlという言語ではなく公式のocamlコンパイラを指しています、以下lowercaseの場合コンパイラを指しています

*10:いや、OCamlには型あるやんけって感じなんですがどうもGCに使うらしいです

*11:tagged呼びの方が一般的っぽいのかな

*12:libcの関数にmlmlの文字列を渡すとき、ポインタ計算で文字列長が頻繁に必要になる

*13: libgcにリンクしなければいけない、GC_initが必要な場合があるなどありますが

*14:http://no-maddojp.hatenablog.com/entry/2015/06/06/165620