SMLでDynamic(再び) - ::Eldesh a b = LEFT a

この記事は ML Advent Calendar 2014 7日目の記事です。

ここではSMLによるDynamic(あるいはAny)と呼ばれる*1、任意の型の値を保持出来るテクニックを紹介します。

任意の型の値を保持可能な型という内容は以前も紹介したことがあります(2) が、前回紹介した実装では例外を使っており、プログラムの作法またはパフォーマンスに懸念があるかも知れません。プログラマの心理的にもよろしくなさそうです。
この記事では例外を使わずポータブルなコードのみで同等の振る舞いを実現するテクニックを紹介し、実装を理解出来るように解説します。

序/Dynamicの必要性

StandardMLでジェネリックなコードを書こうとすると、型に応じて処理を切り替えるということが一切出来ないことがネックになります。(その代わり型が完全に推論される)
しかしどうしても型によって振る舞いを変えたい場合があり、そういった場合はどこかで妥協する必要が出てきます。

その妥協のひとつの方法として、型と同名の値(or関数)と、そのコンビネータを提供することでユーザに型*2を強制的に指定させる手法が知られています(3)。
この手法は型ごとの振る舞いのデータベースを(暗黙に)構成出来ることが重要ですが、それにはここで紹介する Dynamic を駆使して UniversalType と呼ばれるテクニックを用いることで実現出来ます。

振る舞い

まず簡単なユースケースから見ていきます。
Dynamicは以下のようなシグネチャを持ち、例外を用いた実装と変りません。

structure Dynamic : sig
  type t
  type 'a key : ('a -> t) * (t -> 'a option)

  val mk : unit -> 'a key
  val emb : 'a key -> 'a -> t
  val prj : 'a key -> t -> 'a option
end = ...

t 型に(任意の型の)値を保持させ、'a key を使って対応する型の値を設定または取り出します。
埋め込みと取り出しには emb/prj という名前が付けてありますが、自分でkeyタプルを分解しても同じです。

- structure D = Dynamic;
(* 型タグを作成 *)
- val int : int D.key = D.mk()
- val string : string D.key = D.mk()
- val int_string : (int * string) D.key = D.mk()

- val val0 = D.emb int 314      (* intの値を埋め込み *)
val val0 = - : Dynamic.t

- val get = D.prj int val0      (* int 型の値を問い合わせる *)
val get = SOME 314 : int option (* 入れた値が出てくる *)

- val get = D.prj string val0   (* string 型で問い合わせてみる *)
val get = NONE : string option  (* 入ってない *)

図にしてみました。
それぞれの型に対応するキーを使って Dynamic.t 型の値に問い合わせを行い、値を取り出します。
値を設定した時のキー(型)以外を使って問い合わせるとNONEが返ります。

混成リスト

お約束ですが Dynamic の分かりやすい適用先として、互いに異なる型の値から出来たリスト(混成リスト)の作成があります。
以下の例では int,string,int*string の値からなるリストを構成し、それぞれに対する一般化toStringを定義;適用しています。

- val hlist =
      [D.emb int 256
      ,D.emb string "hello"
      ,D.emb int_string (1414, "good bye.")
      ];
val hlist = [-,-,-] : Dynamic.t list (* いろいろな型の値が入ったリスト *)

- fun maybe _  NONE    n = n ()
    | maybe t (SOME x) _ = t x

- fun IStoString (x,s) = concat["(",Int.toString x,",",s,")"]

- fun toString d = (* Dynamic用toString *)
  maybe Int.toString (D.prj int        d) (fn()=>
  maybe (fn x=>x)    (D.prj string     d) (fn()=>
  maybe IStoString   (D.prj int_string d) (fn()=>
  "unkown type")))
val toString = fn : Dynamic.t -> string

- map toString hlist;
val it = ["256","hello","(1414,good bye.)"] : string list (* それぞれを文字列に変換出来た *)

実装

では実装を示します。
短いですが読んでいきなり理解するのはかなり難しいと思います。

structure Dynamic :> DYNAMIC =
struct
  datatype any = V of {
                    disclose:   unit -> unit,
                    undisclose: unit -> unit
                 }
  type t = any
  type 'a key = ('a -> t) * (t -> 'a option)

  fun mk () =
    let
      val box = ref NONE (* 通信チャネル *)
      fun discloser v () = box := SOME v
      fun undiscloser () = box := NONE
      fun mkV v = (* それぞれが box にアクセスするサンク *)
         V { disclose   = discloser v,
             undisclose = undiscloser }
      fun useV (V {disclose, undisclose}) =
        ( box := NONE;  (* mkV したときと同じ box にアクセスするなら *)
          disclose ();  (* 同じ box に v を書く *)
          let val v = !box (* すぐに取り出す *)
          in undisclose(); v end )
    in
      (mkV, useV)
    end

  fun emb (f,_) = f
  fun prj (_,f) = f
end

見ての通り、例外(やその他怪しい機能)は一切使っていません。
ですがかなり入り組んだリファレンスの使い方をしています。

以下に概念図を書いてみました。

mkとuseVの使う関数が一致している場合、クロージャ内の box を介して通信していることがポイントです。
useVを使う際(=値を取り出す時)、同じ box の実体を共有する場合は、「キーが一致した」ことになり、discloseが書いた値を直後に取り出すことになります。
そうで無い場合は、useVに渡したdiscloseが値を設定したものとは異なる box の実体に値を設定しているため、box に何も設定されていないままの値、つまり NONE が取り出されます。

box に実際に値が書かれるのは useV 内で値を取り出す直前だということに注意して下さい。ユーザが埋め込んだ(embした)値は mkV の返すクロージャに含まれています。