OCamlのlambda IRをいじる(はじめに)
OCamlのコンパイラの話題でよく聞くflambdaという最適化ステップについて資料を読んでいた:
https://ocaml.org/meetings/ocaml/2013/slides/chambart.pdf
スライド5にコンパイラの中間表現のステップと説明が書いてあったのが面白かった。
parse tree: AST typed tree: AST with types lambda: untyped lambda clambda: lambda + closures cmm: simple Clike mach: instruction graph (llvmlike) lin: almost like assembly
とのこと。大体の流れは知っていたものの、はっきりと書いてあるのを読むと勉強になる。
そう言えば昔@no_maddoさんのブログでこんな記事を読んだ:
この記事に出ているとおり、ocamlc
やocamlopt
でコンパイルする場合-dlambda
や-dclambda
といったコンパイラフラグを渡すことで中間表現が出力される。これを眺めていろいろあーだこーだと考えてみたい。
理由としては:
- OCaml使いとしてはどうプログラムがコンパイルされているかをより理解したい
- js_of_ocamlやbucklescriptは中間表現やバイトコードからJSにコンパイルするので、そこについての理解を深めたい
- 実用的なコンパイラの動きを知りたい
- 自作言語の中間表現として使ってみたい
などが全部当てはまる。
とりあえず以下のことを調べてみたい:
- 簡単な
print
だけのプログラム - 変数(モジュールレベル・ローカル)
- 関数(モジュールレベル・ローカル・部分適用)
- 再帰関数
- データ(タプル、リスト、レコード、代数的データ型)
- ミュータブルデータ(ref・array)
- モジュール・ファンクタ
- 複数ファイルにまたがるプログラム
ちなみにここらへんはもちろんコンパイラのバージョンに依存するところが大きい。私が現在使っているのはOCaml 4.11.1である。
何もしないプログラム1
まずはこれだけのプログラムをempty.ml
として保存し、lambda IRに出力してみる:
let () = ()
見ての通り何もしない。
これをocamlopt -c -dlambda empty.ml
でコンパイルすると:
(seq (let (*match*/81 = 0a) 0a) 0a)
こんな出力になる。
初めてこれだけを見るとわかりにくいが、まず大事なポイントとしては
0a
は()
に対応している- モジュールは
(seq ... 0a)
という形にコンパイルされる(...
の中には1個以上のS式が入る) let () = ()
は(let (*match*/81 = 0a) 0a)
にコンパイルされている*match*/xx
というのが左側の()
に対応している。xx
の部分は「変数名がユニークであることを保証する」α変換処理によって振られる数字。(let (.. = .. ...) X)
という形のX
の部分で「変数を束縛した環境で評価するべき式」が入るのだが、このケースだと何も評価する必要がないので()
を表す0a
が入っている
ちなみに最後のポイントに関して、(.. = ..)
で=が中置演算子になっているのはS式から外れてしまって少し悲しい気がする。まあ人が読みやすいようにADTを文字列出力しているだけだからどうでもいいのだけど・・・
何もしないプログラム2
次にこんなプログラムについて考える:
let () = () let () = ()
これはこんな感じに出力される:
(seq (let (*match*/81 = 0a) 0a) (let (*match*/83 = 0a) 0a) 0a)
seq
の中にほぼ同一の要素が増えただけ。*match*/xx
に振られた数字が違っていてユニークな変数名になっているのがポイント。
print_int
次に整数を標準出力に出すプログラム:
let () = print_int 1
(seq (let (*match*/81 = (apply (field 43 (global Stdlib!)) 1)) 0a) 0a)
今まで(*match*/81 = 0a)
だったところの0a
が(apply (field 43 (global Stdlib!)) 1)
に置き換わっている。
ポイントは:
(global X!)
でX
モジュールにアクセス(field n X)
でXモジュールのn
番目のフィールドにアクセス(モジュール以外のデータ構造でも可能)(apply X Y)
で関数Xに引数Yを適用
という流れ。print_int
はStdlib
モジュールのインデックス43に入っている、というのがlambda IRに変換される時点で解決済みなわけだ。なのでprint_int
という変数名・文字列はIRには全く出てこない。
次回
次回はモジュール内で定義された変数がどうlambda IRで扱われるかを見ていく。