F# Data 型プロバイダの内部について #F#

この記事は F# Advent Calendar 2016 の20日目の記事です。

今年発表された PLDI 2016 の論文 "Types from data: Making structured data first-class citizens in F#" [1] と実際の F# Data の実装 [2] を参照し、F# Data の提供する型プロバイダ（JsonProvider など）が標本文書からの型の推測を内部でどのように行っているかを読み解きます。

簡単な例

次のコードは、JSON文書用の型プロバイダ JsonProvider の挙動を表す簡単な例です。

Script1.fsx

#r "path/to/FSharp.Data.dll"

[<Literal>]
let samples = """ 
  [
    { "name": "alice", "age": 22 }, 
    { "name": "bob, "age": 25 }
  ]    
"""
// 標本1:  { "name": "alice", "age": 22 }
// 標本2:  { "name": "bob", "age": 25 }

type Person = FSharp.Data.JsonProvider<samples, SampleIsList = true>
// 標本1から推測される型:  { Name: string, Age: int }
// 標本2から推測される型:  { Name: string, Age: int }
// 標本1, 標本2から推測される型:  { Name: string, Age: int }

let person = Person.Parse(System.Console.ReadLine ())
// person はメンバ Name: string と Age: int を持つ

printfn "name: %s, age: %d" person.Name person.age

型プロバイダは、この例で与えている2つの標本の "型"（スキーマ）をどちらも { Name: string, Age: int } と推測し、2つのプロパティ Name: string と Age: int をもつ目的の型（ここでは Person）を生成します。この一連の処理は、次の表に示すような演算によって実現されます。

[1] での定式化	ライブラリ内の関数	説明
$S$	`inferType`	標本から型を推測する
$[\kern-.5em[ \ \cdot \ ]\kern-.5em]$	`generateJsonType`	推測された型から目的の型を生成する

ライブラリ内の関数として示したものは、$S$ や $[\kern-.5em[ \ \cdot \ ]\kern-.5em]$ に近い処理を行っていると思われるものを筆者が勝手にチョイスしてきました。

今回の例で行くと、標本からの型の推測は次のように行われます。

\begin{align}
S(\textsf{"alice"}) & = \mathsf{string} \\
S(\mathsf{22}) & = \mathsf{int} \\
S(\{ \textsf{Name}: \textsf{"alice"},\ \textsf{Age}: \textsf{22} \}) & = \{ \textsf{Name}: \textsf{string},\ \textsf{Age}: \textsf{int} \} \\
\end{align}

また、$[\kern-.5em[ \ \lbrace \textsf{Name}: \textsf{string},\ \textsf{Age}: \textsf{int} \rbrace \ ]\kern-.5em]$ の結果は以下のようになります。（詳細の説明は省略します。）

\begin{array}{l}
\mathsf{type}\ \mathsf{Person}(x_1 : \mathsf{Data}) = \\
\quad \mathsf{member}\ \mathsf{Name} : \mathsf{string} = \\
\quad \quad \mathsf{convField}(\mathsf{Person}, \mathsf{Name}, x_1, \lambda x_2 \to \mathsf{convPrim}(\mathsf{string}, x_2)) \\
\quad \mathsf{member}\ \mathsf{Age} : \mathsf{int} = \\
\quad \quad \mathsf{convField}(\mathsf{Person}, \mathsf{Age}, x_1, \lambda x_2 \to \mathsf{convPrim}(\mathsf{int}, x_2)) \\
\end{array}

少し複雑な例

しかし現実の世界はもう少し複雑で、次のコードにあるように、標本によって型がまちまちだったりします。[1] にも類似の例があります。

Script2.fsx

#r "path/to/FSharp.Data.dll"

[<Literal>]
let samples = """ 
  [
    { "name": "alice", "age": 22 }, 
    { "name": "bob, "age": 25.5" }, 
    { "name": "carol" }
  ]    
"""
// 標本1:  { "name": "alice", "age": 22 }
// 標本2:  { "name": "bob", "age": 25.5 }
// 標本3:  { "name": "carol" }

type Person = FSharp.Data.JsonProvider<samples, SampleIsList = true>
// 標本1から推測される型:  { Name: string, Age: int }
// 標本2から推測される型:  { Name: string, Age: decimal }
// 標本3から推測される型:  { Name: string }
// 標本1-標本3から推測される型:  { Name: string, Age: option<decimal> }

let person = Person.Parse(System.Console.ReadLine ())
// person はメンバ Name: string と Age: option<decimal> を持つ

match person.Age with
| Some age -> printfn "name: %s, age: %M" person.Name age
| None -> printfn "name: %s" person.Name

このような場合、型プロバイダは、全ての標本をカバーしつつもできるだけ小さい型を推測しようとします。その結果として、この例の場合、型プロバイダにより提供される型 Person のプロパティ Age は型 option<decimal> を持つことになります。こうした複数の標本からの型の推測は、次に示す演算によって実現されます。

[1] での定式化	ライブラリ内の関数	説明
$\mathsf{csh}$	`subtypeInfered`	複数の型の共通部分型を求める

この演算は、値の存在性を考慮した上で、部分型関係 $<:$ に関する上限を求める演算となっています。例えば、$\mathsf{int} <: \mathsf{decimal}$ であることより、 $\mathsf{csh}(\mathsf{int}, \mathsf{decimal}) = \mathsf{decimal}$ です。また、 $\mathsf{csh}(\mathsf{decimal}, \mathsf{null}) = \mathsf{nullable}\langle \mathsf{decimal} \rangle$ です¹。なお、[1] では部分型関係に相当する shape preference relation という関係 $\sqsubseteq$ を定義し、実際にはこの関係に基づいて $\mathsf{csh}$ を定義しています。

実は [1] では数値型として $\mathsf{int}$ と $\mathsf{float}$ しか扱っていませんが、実際の F# Data の実装では下記のように多様な数値型を扱っています。実装では、標本の $\mathsf{0}$ や $\mathsf{1}$ という値から整数型だけでなくブール型も推論可能なよう、工夫されていることがわかります。

\begin{align*}
& \mathsf{float} :> \mathsf{decimal} :> \mathsf{int64} :> \mathsf{int} :> \mathsf{bit} :> \mathsf{bit0} \\
& \mathsf{float} :> \mathsf{decimal} :> \mathsf{int64} :> \mathsf{int} :> \mathsf{bit} :> \mathsf{bit1} \\
& \mathsf{bool} :> \mathsf{bit} :> \mathsf{bit0} \\
& \mathsf{bool} :> \mathsf{bit} :> \mathsf{bit1} \\
\end{align*}

参考文献

T. Petricek, G. Guerra, and D. Syme. Types from data: Making structured data first-class citizens in F#. In Proc. PLDI 2016, pp. 477-490. ACM, 2016.
Github: fsharp/FSharp.Data
F# Data: データアクセス用ライブラリ

$\mathsf{nullable}\langle \cdots \rangle$ は最終的には $\mathsf{option}\langle \cdots \rangle$ と解釈されます。 ↩