OCaml: どうやってファンクタをコンパイルしているのか

小ネタ。OCamlの複雑な機能の中にファンクタというものがあります。
これをどういうふうにコンパイルしているのか見てみましょう。

結論からいうと、

OCamlのモジュールというのはただのレコードである。
ファンクタはレコードを受け取ってレコードを返すまさに関数である

です。

コード例

実際のファンクタを使ったコードを見て、これがどういうふうに中間コードで表現されるのか見てみましょう。

module type S = sig
  type t
  val f : t -> t
end

module Make (M: S) = struct
  let h1 = (M.f, M.f)
  let h2 = (M.f, M.f)
end

module M1 = struct
  type t = int
  let f x = x
end

module M2 = Make(M1)

このコードは、ファンクタMakeをつくって、これにモジュールM1を渡してモジュールM2を作るというだけのコードです。これをocamlopt -c -dclambda ./foo.mlというコンパイルコマンドでコンパイルしてみて、 clambdaという中間コードで見てみましょう。

(let
  (Make/1014
     (closure
       (fun camlFoo__Make_1014 1  M/1011
         (let
           (h1/1012 (makeblock 0 (field 0 M/1011) (field 0 M/1011))
            h2/1013 (makeblock 0 (field 0 M/1011) (field 0 M/1011)))
           (makeblock 0 h1/1012 h2/1013))) ))
  (seq (setfield_imm 0 (global camlFoo!) Make/1014)
    (let (f/1016 (closure  (fun camlFoo__f_1016 1  x/1017 x/1017) ))
      (setfield_imm 3 (global camlFoo!) f/1016))
    0a
    (let (M1/1018 (makeblock 0 (field 3 (global camlFoo!))))
      (seq (setfield_imm 1 (global camlFoo!) M1/1018)
        (let
          (M2/1021 (apply* camlFoo__Make_1014  (field 1 (global camlFoo!))))
          (seq (setfield_imm 2 (global camlFoo!) M2/1021) 0a))))))

読む時の注意点:

中間コードはLisp的な気持ちで読む, 想像せよ
気になったらasmcomp/{printclambda.ml,clambda.ml}読んでどの表現に対応してるのか調べる
想像するのが嫌だったらZinc reportでも読みましょーねー http://caml.inria.fr/pub/papers/xleroy-zinc.pdf
letはまさに名前に値を束縛する構文
makeblockはこのコンストラクタのあとに続く要素が並んだヒープに確保される配列みたいなものを作る構文
補足するとOCamlでは大体の値は１ワードに揃えられている
fieldはレコードにアクセスするためのコンストラクタ。
例えばfield 0 M/1011はレコードM/1011の0番目の要素を取り出せという意味
setfield_immはレコードのn番目に要素をセットするコンストラクタ
globalはおそらくグローバルな値を取り出してくるコンストラクタ。
あとでグローバルな値に関してはアドレスに置換されるのだろう
seqはまさに逐次実行を表す
apply*は関数適用

上のことがわかれば十分理解できます。上の中間コードにコメントを書いて解説をしてみます！

(let
  (Make/1014 ; ファンクタMakeの定義、ただの関数ですね〜〜〜
     (closure
       (fun camlFoo__Make_1014 1  M/1011
         (let
            ; (field 0 M/1011)でMから関数fのポインタを取り出してmakeblockでその組みを表すブロックを作る
           (h1/1012 (makeblock 0 (field 0 M/1011) (field 0 M/1011))
            h2/1013 (makeblock 0 (field 0 M/1011) (field 0 M/1011)))
            ; ファンクタが返すレコードを作る
           (makeblock 0 h1/1012 h2/1013))) ))
; 作ったMakeファンクタをグローバルなブロックcamlFoo(このファイルが作るファイルはレコードになる)にセット
(seq (setfield_imm 0 (global camlFoo!) Make/1014)
    ; M1の中の関数fの定義
    (let (f/1016 (closure  (fun camlFoo__f_1016 1  x/1017 x/1017) ))
    ; 定義した関数fをグローバルなレコードcamlFooの３番目にセット
      (setfield_imm 3 (global camlFoo!) f/1016))
    0a
    ; レコードM1を作る、そのレコードは先頭に0, 次にfの関数ポインタが入ってる
    (let (M1/1018 (makeblock 0 (field 3 (global camlFoo!)))) ;
    ; レコードM1をcamlFooの1番目にセット
      (seq (setfield_imm 1 (global camlFoo!) M1/1018)
        (let
           ; M1を関数Make(ファンクタで表現されたもの)に渡して関数適用
          (M2/1021 (apply* camlFoo__Make_1014  (field 1 (global camlFoo!))))
           ; それをcamlFooの2番目にセットする
          (seq (setfield_imm 2 (global camlFoo!) M2/1021) 0a))))))

ちなみにOCamlの低レベルではタプルもレコードもモジュールも要素を持つヴァリアントも区別されません。だいたいmakeblockで作られて、makeblock label elem1 elem2 ...のように先頭にラベルがついてて要素が続くような構造として定義されているようです。

モジュール、タプル、レコードの違いは大雑把に言って型付けだけだということですね。

この事がわかると第一級モジュールなんかも型付けやエスケープ解析などはともかく低レベルでの表現というのはあまり難しくなさそうだなーという想像が出来ますね。
ちなみにOCamlでは第一級モジュールが存在し、動的にモジュールが作られる可能性があるのでコンパイル時にDefunctorizationすることが出来ません。
MLtonに関する発表スライドなんかを見ていると彼らはファンタクを展開しているようですが。。。

type t (* void *)

ソフトウエアのこととか

OCaml: どうやってファンクタをコンパイルしているのか