type t (* void *)

関数型言語や英語学習の事とか。

OCaml: 中間言語をダンプするオプションたち

この記事はML Advent Calendar 20153日目のために書かれました。

短いライトな話を。ocamlにはコンパイラ開発者のデバッグ用にドキュメント化されてあいオプションがいくつかあります。 これは中間言語のダンプを吐かせる機能です。OCamlコンパイラを理解するのに役に立ちます。

[~] ocamlopt --help
Usage: ocamlopt <options> <files>
Options are:
... 略
  -dsource  (undocumented)
  -dparsetree  (undocumented)
  -dtypedtree  (undocumented)
  -drawlambda  (undocumented)
  -dlambda  (undocumented)
  -dclambda  (undocumented)
  -dcmm  (undocumented)
  -dsel  (undocumented)
  -dcombine  (undocumented)
  -dcse  (undocumented)
  -dlive  (undocumented)
  -dspill  (undocumented)
  -dsplit  (undocumented)
  -dinterf  (undocumented)
  -dprefer  (undocumented)
  -dalloc  (undocumented)
  -dreload  (undocumented)
  -dscheduling  (undocumented)
  -dlinear  (undocumented)
  -dstartup  (undocumented)
... 略

このダンプを読むためには各フェイズの中間言語の定義を自分で読む必要がありますが、だいたいわかりやすく出来ているので見ればわかります。とくにOCamlに興味がなくてもコンパイラを勉強している人には有意義なはずでです。

普通は機械語に近い中間言語ではなく、高級言語に近い部分を読むので十分です。
例として-dclambdaをつけてパターンマッチをどうやってコンパイルしているのか見てみましょう。

正確な定義はclambdaの定義ここprimitiveの部分を読む必要があります。

下のプログラムを例に考えてみます

type t1 = A of int | B of int * t1
type t2 = {x: int; y:int}

let f = function
| A i -> i
| B (i, A j) -> i + j
| B (i, B (j, x)) -> i + j

let x =
  f @@ B (1, B (2, A 3))

let y = {x=1; y=2}

出力結果は下のとおりです。

 1  seq
 2   (let
 3     (f/1014
 4        (closure 
 5          (fun camlTest__f_1014 1  param/1028
 6            (switch param/1028 
 7            case tag 0: (field 0 param/1028)
 8            case tag 1:
 9              (let
 10               (match/1029 (field 1 param/1028) i/1016 (field 0 param/1028))
 11               (switch match/1029 
 12               case tag 0: (+ i/1016 (field 0 match/1029))
 13               case tag 1: (+ i/1016 (field 0 match/1029)))))) ))
 14    (setfield_imm 0 (global camlTest!) f/1014))
 15  (let
 16    (x/1021
 17       (apply* camlTest__f_1014 
 18         "camlTest__3"=block(1,1,"camlTest__2"=block(1,2,"camlTest__1"=block(0,3)))))
 19    (setfield_imm 1 (global camlTest!) x/1021))
 20  (setfield_imm 2 (global camlTest!) "camlTest__4"=block(0,1,2)) 0a)

f/1014は関数fの事です(すべてα変換されている)。 これの中身を見る前にヴァリアントとレコードの表現を見て行きましょう。

fの引数のt1型ヴァリアントは18行目で、t2型のレコードは20行目で作られています。

18 "camlTest__3"=block(1,1,"camlTest__2"=block(1,2,"camlTest__1"=block(0,3)))

20 block(0,1,2)

ヴァリアントもレコードも同じ構造で、この中間言語ではブロックと呼ばれるもので表されているようです。
ブロックは平らに要素が並ぶ構造をしていて、おそらく各々の要素はユニフォームに表現されます。

ブロックの最初の要素はタグです。t1型のヴァリアントだとAのタグは0, Bのタグは1で表されています。
レコードのタグは必ず0のようですね。
20行目のblock(0,1,2)を見るとレコードの要素が並んでいる様子を見ることができます。

さて関数f/1014を見てみましょう。 この関数はまず引数param//1020の中身を見てタグで分岐しています。

case tag 0: (field 0 param/1020)

の部分は| A i -> iに該当します。 param/1020のタグが0であるとき、このレコードの0番目のフィールドに (すなわちint型のパラメータのこと)アクセスして取り出しています。

それ以降の行を読んでみるとわかるのですが ネストしているパターンマッチも普通にswitchをネストして使っているわけですね。