Arantium Maestum

プログラミング、囲碁、読書の話題

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 C­like
mach: instruction graph (llvm­like)
lin: almost like assembly

とのこと。大体の流れは知っていたものの、はっきりと書いてあるのを読むと勉強になる。

そう言えば昔@no_maddoさんのブログでこんな記事を読んだ:

no-maddojp.hatenablog.com

この記事に出ているとおり、ocamlcocamloptコンパイルする場合-dlambda-dclambdaといったコンパイラフラグを渡すことで中間表現が出力される。これを眺めていろいろあーだこーだと考えてみたい。

理由としては:

などが全部当てはまる。

とりあえず以下のことを調べてみたい:

ちなみにここらへんはもちろんコンパイラのバージョンに依存するところが大きい。私が現在使っているのは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_intStdlibモジュールのインデックス43に入っている、というのがlambda IRに変換される時点で解決済みなわけだ。なのでprint_intという変数名・文字列はIRには全く出てこない。

次回

次回はモジュール内で定義された変数がどうlambda IRで扱われるかを見ていく。