OCamlオブジェクトの結合を型付きPPXで

直前の記事の応用編。

オブジェクトの型理論の歴史

型理論の世界では、オブジェクトの型理論が (主にC++やJavaの隆盛に呼応して？) '90年代前後によく研究されており、大堀先生のレコード多相 (SML# に実装されている) とか Wand, Rémy の Row types というのがある (その一種が OCaml に実装されている)。私はこのトピックについて詳しくないが、近年でもプログラミング言語系のトップカンファレンスの一つである POPL'19 にも row types の結果を統合する内容の論文が出ていて、歴史的経緯はそのあたりからも伺うことができる。

J. Garrett Morris and James McKinna, Abstracting extensible data types: or, rows by any other name. POPL '19.

OCaml におけるオブジェクトの結合 (ができないこと)

ところで OCaml のオブジェクトはそれなりに柔軟でカッコイイのだが、使っていると不満も出てくる。
その一つは、オブジェクト(レコード)の結合 (concatenation) ができないことである。たとえば

let hello_obj = 
  object 
    method hello = print_endline "Hello!" 
  end

というオブジェクトは <hello: unit> という型をもつが、こいつと、型 <goodbye:unit> をもつ

let goodbye_obj = 
  object 
    method goodbye = print_endline "Goodbye!"
  end

を「混ぜて」、型 <hello:unit; goodbye:unit> を持つオブジェクトを合成できても良いはずである。

そのような演算子は OCaml には無いので、プログラマは手動でそのような合成をしなければならない。

let hello_goodbye =
  object
    method hello = hello_obj#hello
    method goodbye = goodbye_obj#goodbye
  end

上の POPL'19 の言語である Rose にはそのような演算が存在するのだが、これを OCaml に導入するのは人類にはまだ難しそうだ。

型付きPPX によるオブジェクトの結合 (?)

ここでは、上の型付きPPXの練習台として、オブジェクトの結合を OCaml で実装することを考える。

たとえば上の hello と goodbye の結合は

let hello_goodbye =
  [%concat] hello_obj goodbye_obj

のようにできるようにしたい。もちろん、任意の文脈でオブジェクトを結合する（たとえば静的にはフィールドが確定しないオブジェクトを結合することはできない）ことはプリプロセッサでは不可能だろう（後述）が、上に書いたような既にフィールドの存在/非存在が分かっているオブジェクト同士の結合であればプリプロセッサレベルでもできるはずだ。型さえ分かれば。

というわけでやってみた。以下の ppx_concat がそれだ。やっつけで作ったのでとても不完全な実装だが、上に書いた例くらいは動作する。

基本的なプロジェクトの構造は 型付きPPXに関するメモ - toward the typed ppx そのままである。

ここでやっているのは、型付きの構文木に対して詳細なケースアナリシスを追加したことである。
以下の部分で、式 cocnat arg1 arg2 を見つけたら、その型を詳細に調べて上述の変換を呼び出すようにしている。

src/ppx_concat.ml

let tyexp_to_exp _env (super:Untypeast.mapper) =
  fun self (texp : Typedtree.expression) ->
    match texp.exp_desc with
    | Texp_apply({exp_desc=Texp_ident(_,{txt=Lident("concat");_},_);_}, 
        [(_lab1, Some arg1);
         (_lab2, Some arg2)]) ->
          concat (super.expr self) arg1 arg2
    | _ -> 
      super.expr self texp

ここで Texp_apply が関数適用である。concat (arg1) (arg2) という式にマッチするようになっており、 (_lab1, Some arg1) と (_lab2, Some arg2) がそれぞれ arg1 と arg2 の構文木に対応する。 _lab1, _lab2 は関数のラベルで、ここでは無視している。

concat (super.expr self) arg1 arg2 の部分で、arg1, arg2 の型を調べつつ上述したような構文木を生成している。ここで (super.expr self) は型付きの構文木を型なしに戻す関数を渡している (Untypeast; 前回の記事参照)

以下がそのコードだ。

src/ppx_concat.ml

let concat untyp_f (arg1:Typedtree.expression) (arg2:Typedtree.expression) =
  let flds1 = fields ~loc:arg1.exp_loc arg1.exp_type 
  and flds2 = fields ~loc:arg2.exp_loc arg2.exp_type 
  in
  let has_dup = List.exists (fun x -> List.exists (fun y -> x=y) flds1) flds2 in
  if has_dup then
    error arg2.exp_loc (Format.asprintf "duplicate fields:%a@." Ocaml_common.Printtyp.type_expr arg2.exp_type)
  else begin
    let mths1 obj = List.map (fun f -> make_method f (make_call obj f)) flds1
    and mths2 obj = List.map (fun f -> make_method f (make_call obj f)) flds2
    in
    let loc = Location.none in
    Ast_helper.Exp.let_
      Nonrecursive
      [Ast_helper.Vb.mk [%pat? obj1] (untyp_f arg1);
       Ast_helper.Vb.mk [%pat? obj2] (untyp_f arg2);]
      (Ast_helper.Exp.object_ @@ 
        Ast_helper.Cstr.mk 
          [%pat? _]
          (mths1 [%expr obj1] @ mths2 [%expr obj2]))
  end

まず、関数fields で、各オブジェクトのフィールド名のリストを抽出して flds1, flds2 に束縛している（この関数の中で、オブジェクト型が列変数 .. を含んでいた場合にエラーを出すようにしている）。関数 fields では、 OCaml の内部の型を表していて扱いづらい typexp から Printtyp.tree_of_typexp でユーザーフレンドリーな型を抽出して、そこからフィールド名を取っている。

次に、has_dup でフィールド名の重複の有無を調べ、重複がある場合にはエラーとしている。

さらに、新しいオブジェクトのメソッドのリストを mths1 mths2 で生成する。これは、メソッド名とメソッド本体の式をとる make_method という関数を使っている。メソッド本体は、合成対象のオブジェクトの同じメソッドを呼ぶという実装になっていて、これは make_call 関数でできている。ここで、元のオブジェクトの構文木（正確にはそれを let で束縛した変数）を引数 obj で取るようにしている。
make_method と make_call のどちらも小さな関数である。

src/ppx_concat.ml

let make_method fld exp =
  Ast_helper.Cf.method_ (Location.mknoloc fld) Public (Cfk_concrete(Fresh, exp))

let make_call exp fld =
  Ast_helper.Exp.send exp (Location.mknoloc fld)

最後に、

• Ast_helper.Exp.let_ で arg1, arg2 (を untyp_f で型なしに変換したもの) を変数 obj1, obj2 に束縛し、
• Ast_helper.Exp.object_ で上述したメソッドのリスト mths1, mths2 からなるオブジェクトを生成している。

Ast_helper.Cstr とかについて

PPX を書くには OCaml の構文の階層構造 (主に式とか) を知っている必要がある。
それさえ分かれば metaquot が使えない状況下でも Ast_helper を使えばわりと簡単に構文木を構築できる。
たとえば Ast_helper.Cstr はクラスの構造を作るモジュール (class structure?) である。同様に Ast_helper.Cf.method_ はクラスのフィールドのうちメソッドを作るものだろう。そのあたりを parsetree.mli とか ast_helper.mli とか を眺めて直観を得るとよい。 VSCode でブラウジングしていくのがやりやすいと思う。

こんなことができる

ほぼ当たり前の動きだが、動作例を

にコメントで書いておいた。

今のところの制限

この PPX は思いっきり型を変える。具体的には、素の構文木から暫定的に型推論された < .. > という型を <hello:unit; goodbye:unit> のような結合後の型に変える。このため色々と制限が生まれるだろう。
たとえば変更後の型情報を利用してさらに concat するのは現状では無理だ。
ナイーブに考えると concat を一つ処理するたびに型付けをやり直す必要がある。

限界

これはプリプロセッサによる結合なので自ずと限界がある。たとえば

let f x y = concat x y

みたいな式は x と y のフィールドがわからないので結合できない。このような式は、上の実装では x と y の型が < .. > に推論されることを利用して拒否している。一方、上述の Morris & McKinna の論文ではこのようなオブジェクトの結合も可能になっている。 OCaml のオブジェクトはハッシュテーブルなのでコンパイル方式の制限はないと思われ (そのかわり遅い)、遠い未来に結合可能なオブジェクトが導入される未来を夢見ておきたい (型にフィールドの非存在を表す情報を入れる必要があり、なかなか複雑になりそうなので、そんな未来は来ないような気もするが)。