type t (* void *)

ソフトウエアのこととか

OCaml: 型変数の雑い話

これはMLアドベントカレンダーの１日目の記事です。 今年で３年目のアドベントカレンダーですが、あまり埋めるということは意識せず、MLユーザが記事を書いてワイワイするという目的でやっていければいいな、という感じです。

adventar.org

１日目なのでゆるくOCamlコンパイラの型周りの実装の話をしたいと思います。 最近あまり体調が良くなく、小ネタみたいな形です（すみません）。 どこかで喋った覚えもあるので聞いたことがある人がいたらすみません。

OCamlでは型変数は基本的に整数のidで表されています。 それにレベルという概念を導入して、どのネストのletで導入された型変数なのかをわかるようにしている、というのは以前書いたとおりです。

github.com

また型変数がgeneralizeされているかどうを表すためにも利用されていて、Btype.generic_level = 100000000と定義されています。まぁ常識的にこの深さのネストとかやらんやろということで再利用しているんだと思います。

気になるのは、型変数をidという形で整数で表してしまうと、idが衝突するのではないのかということです。例えばcmiファイルからロードする際に他のファイルから型をインポートするときに混じったりということが考えられます。

この手の情報は手軽に見ることができます。compiler-libsさまさまです。 utopかなにかで読み込んで、プリティープリントさせてみましょう。

// 前やったときはできたと思うんですが、なんか今はできませんでした。 // utopまわりで色々変わったのかもしれません、すみません

utop[0]> #require "compiler-libs";;
utop[1]> read_cmi

これを見ると、cmiの世界の中では型変数のidはマイナスの数になっていることがわかります。 これを自分たちの、いまコンパイルしようとしている世界にむけてidを差し替えます。それには型とかモジュールを表すデータ構造をあれそれ置き換えるためのモジュールSubstを利用します。

Subst.typexp: Subst.t -> Types.type_expr -> Types.type_exprは型を表すデータ構造をトラバースして、型変数を見つけたら置き換える関数です.

(* Similar to [Ctype.nondep_type_rec]. *)
let rec typexp s ty =
  let ty = repr ty in
  match ty.desc with
    Tvar _ | Tunivar _ as desc ->
      if s.for_saving || ty.id < 0 then
        let ty' =
          if s.for_saving then newpersty (norm desc)
          else newty2 ty.level desc
        in
        save_desc ty desc; ty.desc <- Tsubst ty'; ty'
      else ty
......

idが負であれば何やら怪しい方法でコピーしています。 for_savingは普通の場合ではfalseです。 ちなみにこのfor_savingというのはこの逆で、型変数のidを外に書き出したりするときにtrueになる変数です。newperstyがidを負になるように置き換えます。

上のようなことが起きるのは、下の関数の中身くらいでです。

read_signature
  read_pers_struct
    acknowledge_pers_struct
      components_of_module'

ちなみにOcamlコンパイラの中身ではモジュールの並び順的にあとのモジュールに入っている関数を利用するために関数のrefみたいなものをたくさん作っており、'がつくものはその印です。

読んでみた感想なのですが、OCamlの型検査周りの実装というのは本当に複雑で、色々手に終えないです。型付けのためのデータ構造が効率のため一時的にしか現れないはずもの(Tlink, Tsubstなど)、といったものなどもありかなり複雑で、やはり関数型言語で書けば可読性が上がるなどといった話は嘘なんだなと強く確信がもてます（この手の話では関数型言語はHaskell、それもGHCしか指さないという話もありますが）。 気づいたらocaml/typingの中に素敵なことにHACKING.adocというファイルができていました。

https://github.com/ocaml/ocaml/blob/trunk/typing/HACKING.adoc

これは本当に素晴らしいことで、突然開発者が交通事故にあっても大丈夫なようにOSSといえども実装をドキュメントとして残していく必要があります。 ソースコードに全て書いてあるなどと言うのは開発者の怠慢で後で読む人に一生懸命考古学させる、ドキュメントを書きましょう。。。

最後に今年の振り返りですが、今年のOCaml活動はコンパイラの同人誌をOCamlで書いたこと・ML勉強会を一応開催できたことは良かったです。 あまり最近OCamlをかけていないのですが、来年度はドンドンやっていきたいと思います！

nomaddo.booth.pm ml-lang.connpass.com

次はポケバさん@pocketberserkerさんです。