OutsideIn(X) と OCaml

Haskell の実装 GHC の新しめのバージョンでは 多相let の型付けが今までの HM (Hindley Milner) 方式から新しい OutsideIn(X) に変わっています。(言語拡張でどうたらあるらしいがシラネ) 詳しい動機はまあいろいろあるみたいですが GADT とか Type family の型推論の効率とか完全性とかそういう方面らしいです。正直両方とも使わないのであまりありがたみがわかりません。で、世の中 Haskell のやることは外でも全て正しいという考えの方がおられまして、 OutsideIn(X) は Haskell で問題ないのだから他でも問題が無いはずだとかおっしゃるわけです。

あんまり科学的な態度じゃないですよね。まあプログラミング言語論のこれは便利だ便利じゃないなんて思想であって自然科学じゃあないので究極的には好き嫌いの問題だと私は思うからまあいいっちゃあいいんですが。

というわけで OutsideIn(X) を OCaml でやったらどうなるか確かめました: https://github.com/camlspotter/ocaml/tree/outsideinx

  • local let は基本 generalization なし
  • let! と書いた場合のみ generalization あり
  • top let は generalization あり
  • NOOUTSIDEINX という環境変数が定義されていると let でも let! でも generalization あり

という実装です。実装は簡単です。ブートストラップで微妙に手間かかりますので一気にはできません。少しづつブートストラップしていく感じ。

ちなみに OCaml で OutsideIn(X) して何がうれしいというと何もありません。OCaml にも GADT があるじゃないか?うんなんかそれは惹玖が OutsideIn(X) 使わなくても上手くなんかいく方法とかを発表するらしいよ。GADT は使わないんで、正直良くわかんないよ俺は。

さてさて、じゃあ let! がどれくらい必要かということですね。 OCaml コンパイラ一式をこの弱い let と let! で make world 通すのにどれだけ変更がいるかってことでまあ計ります。 find . -name *.ml | xargs grep -n 'let!' だすなー:

./stdlib/camlinternalOO.ml:347:  let! undef = fun _ -> raise (Undefined_recursive_module loc) in
./stdlib/arg.ml:110:  let! stop error =
./stdlib/printf.ml:488:  let! get_arg spec n =
./stdlib/scanf.ml:1328:  let! stack f = delay (return f) in
./stdlib/scanf.ml:1329:  let! no_stack f _x = f in
./stdlib/scanf.ml:1381:      let! stack = if skip then no_stack else stack in
./ocamldoc/odoc_info.ml:211:  let! p = Printf.bprintf in
./ocamldoc/odoc_html.ml:509:      let! index_if_not_empty l url m =
./ocamldoc/odoc_html.ml:978:        let! link_if_not_empty l m url =
./camlp4/boot/camlp4boot.ml:927:          let! grammar_entry_create = Gram.Entry.mk in
./camlp4/boot/camlp4boot.ml:10824:          let! grammar_entry_create = Gram.Entry.mk in
./camlp4/boot/camlp4boot.ml:12147:          let! grammar_entry_create = Gram.Entry.mk in
./camlp4/boot/camlp4boot.ml:14093:          let! grammar_entry_create = Gram.Entry.mk in
./camlp4/boot/camlp4boot.ml:14911:          let! grammar_entry_create = Gram.Entry.mk in
./camlp4/boot/camlp4boot.ml:15214:          let! grammar_entry_create = Gram.Entry.mk in
./bytecomp/translmod.ml:695:  let! rec make_sequence fn pos arg =
./typing/typemod.ml:593:  let! transition env_c curr =
./typing/includecore.ml:135:  let! pr fmt = Format.fprintf ppf fmt in
./typing/typecore.ml:1087:  let! bad_conversion fmt i c =
./typing/typecore.ml:1089:  let! incomplete_format fmt =
./ocamlbuild/hygiene.ml:157:            let! fp = Printf.fprintf in
./ocamlbuild/command.ml:361:  let! list = List.fold_right in
./ocamlbuild/rule.ml:255:  let! res_add import xs xopt =
./ocamlbuild/main.ml:52:  let! pp fmt = Log.raw_dprintf (-1) fmt in

おっこれだけしかない!!そうなんですねー、 OCaml でもローカル let bound な名前が polymorphic に使われることはほとんどないのですね。

OCaml で local polymorphism が使われるパターン:

  • 既存の多相型の値の別名をつける: let list = List.fold_right in ...
  • 最後に例外を投げるので返り値が多相: let stop error = prerr_endline error; raise Error in ...
  • カスタム printf : let pp fmt = Log.raw_dprintf (-1) fmt in ...

OCaml コンパイラでは無闇にこのカスタム printf 系が多い。

じゃあ、あんまりないし、OCaml でも OutsideIn(X) 問題ないよね?!という結論に傾きかけますがそれはどうなんかなとわしは思ったね。

上を見たらわかるんだけど let! が必要なのはほとんどの場合、既存の多相関数に別名をつけているところよね。たとえば let! pr fmt = Format.fprintf ppf fmt とか。OCaml 結構こういう使い方します。Haskell だと一部は import Format(fprintf) とかなるところです。

さらに OCaml は Haskell と違って local なコードは local let にするのが好きな文化です。何故か知らないが Haskell の人は結構外に出しちゃいますよね。Haskell なら外に出しちゃうコードが OCaml では外に出さない文化なので問題出ました、とかありそうです。

OCaml は Haskell と違ってコード中に型をほとんど書きません。(.mli には書くけどこれは実装終わってからおもむろに自動生成する方が普通)なので polymorphic な型書けば元の let になるよ!という GHC の方式は受け入れられないと思いますね。なんでここでは let! と書くことで元の挙動に戻すということをやってみたんですが。それでも、今までの let に慣れている人が、こういう時いちいち let かなー let! かなーとか考えなきゃいけないってのはつらいですね。あと、後から let! つけるの大変ですよ結構。型エラーから読み解くいて let! つけていくの、 OCaml コンパイラのブートストラップで実は時間かかりました。この関数が多相的だったら良かったのにね!みたいな親切なコンパイラエラー出すのはできるんかもしれんけど、多分 let 周りの型付けでこれ多相にできたけど OutsideIn(X) だからあきらめたわーみたいな情報をつけなきゃいけない。すごく手間かかりそうですね…

OutsideIn(X) の論文 http://research.microsoft.com/en-us/um/people/simonpj/papers/constraints/jfp-outsidein.pdf では

  • library : 30 packages 94954行で 127行の変更が必要だった
  • 793個の Hackage をコンパイルしなおしたら 95個ができなかった(あるパッケージ自体が問題なくても依存パッケージで問題があれば失敗になる、という一番楽なテストみたい)

らしいんでちょっとやってみたんですが

  • OCamlFind ですでに修正が必要
  • OPAM パッケージは… OASIS が作った setup.ml が入っているとそこで local polymorphism 使っているから自動ビルド絶対無理

ということになり、数字出す前からやる気出ませんね…別に論文書くわけじゃなし。 ちなみに polymorphic variant とか class 使っていると困るかなと思って手で LablGtk2 やってみたんですが 17箇所変更が必要、しかしこれは polymorphic variant も class も関係ありませんでした。結構多いよね。

OCaml に OutsideIn(X) 入れたら既存コードの修正は Haskell より結構大変だと思います。まそれよりなにより OCaml は Backward compatibility を GHC より大切にするから絶対採用できませんね。まあそもそも旨みがないのだから採用する意味も無いが。