ぐるぐる～

この広告は、90日以上更新していないブログに表示しています。

2015-12-17

Combine Deep Dives

この記事はF# Advent Calendar 2015の17日目の記事です。

今日はコンピュテーション式のCombine について取り上げます。

詳説コンピュテーション式をある程度理解していると分かりやすいかもしれません。

内容を簡単にまとめると、

Delay の中で受け取った関数を実行する場合、副作用を考慮したときに問題が起こらないか考えること
ゼロ値がある型でCombine を実装するときは、Delay の中で受け取った関数を実行せずに、Combine の中で実行すること
ゼロ値がない型でCombine を実装するときは、Combine の実装はBind に流し、Zero はM<unit> を返すように実装すること

です。

Combineの目的

Combine は、コンピュテーション式の2つの式を繋ぐために使います。コンピュテーション式中の変換対象となる式をce プレフィックスで表す場合、ce1; ce2 という式*1はCombine を使って下記のように変換されます。

(* bはビルダークラスのインスタンス *)b.Combine(ce1の変換結果, b.Delay(fun()-> ce2の変換結果))

あれあれ、Delay というメソッドが出てきました。このように、Combine を使うためにはDelay を実装する必要があります。

Delayの実装

Delay をどうするかは、2通りの方法があります。まずは、単純な方法から見てみます。

Delayの実装方法その1

Combine の引数としては、ce1 の変換結果とce2 の変換結果がそのまま渡されるのがとりあえずわかりやすい気がしませんか？そういうことにしておくと、Delay の実装はこう決まります。

(* 引数の関数を実行するだけ *)member __.Delay(f)= f()

こうすることで、Combine にはce1 の変換結果とce2 の変換結果がそのまま渡されます。この実装方針を取った場合、Combine のシグネチャはMSDNのコンピュテーション式のページにあるように、

M<'T>*M<'T>->M<'T>

または

M<unit>*M<'T>->M<'T>

となるでしょう。実際に具体例でみてみます。

listの場合

'a list のCombine を考えてみます。

list{  yield10  yield20}

とあったとき、望む結果が[10; 20] だとすると、Combine が意味するのはリスト同士の結合、つまりList.append です。実装してみましょう。

typeListBuilder()=  member __.Yield(x)=[x]  member __.Delay(f)= f()  member __.Combine(xs, ys)=List.append xs ys

この場合、Combine のシグネチャは'a list * 'a list -> 'a list になります。

optionの場合

'a option のCombine を考えてみます。

option{if condthen    return10  return20}

とあり、cond によって

`cond` の値	結果
`true`	`Some 10`
`false`	`Some 20`

となってほしいとします。この場合、Combine が意味するのはmatch による分岐です。else の伴わないif にはZero も必要なので、実装します。

typeOptionBuilder()=  member __.Return(x)=Some x  member __.Zero()=None  member __.Delay(f)= f()  member __.Combine(x, y)=match xwith|Some x->Some x|None-> y

この場合、Combine のシグネチャは'a option * 'a option -> 'a option になります。

Delayの実装方法その2

上のDelay の実装、無名関数でくるんだものをそのまま実行しており、Delay の存在意義が分かりません。無名関数でくるんだ結果をDelay に渡すことなどせずに、直接Combine に渡してくれ、と思ってしまっても仕方ありません。

では、なぜDelay なんてものがCombine の変換に出てくるのでしょうか？上で実装したOptionBuilder を使って、上のDelay の実装には問題があることを見てみます。

letoption=OptionBuilder()option{iftruethen return10  printfn"hello"  return20}

このコードはSome 10 を返しますが、「hello」も表示されてしまいます。コンピュテーション式の部分を変換してみると、次のようになります*2。

let b=optionb.Combine((iftruethen b.Return(10)else b.Zero()),  b.Delay(fun()-> printfn"hello"; b.Return(20)))

Delay は受け取ったラムダ式をそのまま実行するように実装しましたので、Combine を呼び出す前にラムダ式の中の式が実行されてしまうのです。これを避けるためには、Delay に渡ってきた関数は実際に必要になるまで実行を遅延する必要があります。

この方針で実装したOptionBuilder は下記のとおりです。

typeOptionBuilder()=  member __.Return(x)=Some x  member __.Zero()=None  member __.Delay(f)= f(* ここでは実行せず、渡された関数をそのまま返す *)  member __.Combine(x, rest)=match xwith|Some x->Some x|None-> rest()(* xがNoneのときのみ、渡された関数を実行する *)

この場合、Combine のシグネチャは'a option -> (unit -> 'a option) -> 'a option となり、MSDNに書いてあるシグネチャとは異なるものになります。まぁ、通常のシグネチャと言っている通り、別に必ずその通りにしなければいけないわけではないので、そういうものだと思ってください。横道にそれますが、別にCombine の実装の結果の型を'a list option にしてしまってもいいのです。変換された結果がコンパイル可能であれば、どんなシグネチャにしても構いません(ただしそういう実装にすると、Combine をネスト出来なくなり、とても使いにくくなりますが)。

さぁではこれで実行してみましょう！

letoption=OptionBuilder()let res=option{iftruethen return10    printfn"hello"    return20}printfn"%A" res

実行結果:

<fun:res@41>

！？！？

res の型が関数になっちゃってますね。これは、Delay を実装するとコンピュテーション式全体もDelay でくるまれるように変換されるのが原因です。上の方でコンピュテーション式の変換結果をこう書きましたが、

let b=optionb.Combine((iftruethen b.Return(10)else b.Zero()),  b.Delay(fun()-> printfn"hello"; b.Return(20)))

正しくはこうです。

let b=option(* 一番外側もDelayされる *)b.Delay(fun()->  b.Combine((iftruethen b.Return(10)else b.Zero()),    b.Delay(fun()-> printfn"hello"; b.Return(20))))

最初のDelay の実装では渡された関数をDelay の中で実行していたので問題になりませんでしたが、今回のDelay の実装は渡された関数をそのまま返すため、最終的な結果が関数になってしまうのです。さて困った・・・

Runの実装

この問題は、コンピュテーションビルダーにRun を実装することで解決できます。コンピュテーションビルダーにRun が実装されていると、一番外側のDelay のさらに外側にRunメソッド呼び出しが挟まれます。つまり、このように変換されることになります。

let b=optionb.Run(  b.Delay(fun()->    b.Combine((iftruethen b.Return(10)else b.Zero()),      b.Delay(fun()-> printfn"hello"; b.Return(20)))))

Run にはDelay の結果が渡されることから、Run の実装をこうすればいいでしょう。

member __.Run(f)= f()

これで、望みの動きをするOptionBuilder が手に入りました。

いい感じのOptionBuilder

typeOptionBuilder()=  member __.Return(x)=Some x  member __.Zero()=None  member __.Delay(f)= f  member __.Combine(x, rest)=match xwith|Some x->Some x|None-> rest()  member __.Run(f)= f()

あとはBind やReturnFrom などを提供していきましょう。

ListBuilder再考

ListBuilder のCombine はOptionBuilder のような考慮は不要なのでしょうか？考えてみましょう。例えば、以下のようなコードはどうなるべきでしょうか？

let xs=list{iffalsethen    printfn"hello"    yield10  yield20}

「hello」とは表示されずに、[20] が返ってきてほしいですよね。このコンピュテーション式の変換結果を見てみましょう。

let b=listb.Delay(fun()->  b.Combine((iffalsethen printfn"hello"; b.Yield(10)else b.Zero()),    b.Delay(fun()-> b.Yield(20))))

このように、printfn はif 式の中にあるため、単純なDelay の実装で何も問題ありません。

let xs=list{  yield10  printfn"hello"  yield20}

この例では、[10; 20] が返ってきてほしいため、やはりprintfn も実行されるべきでしょう。これらのことから、ListBuilder は最初の実装で十分、ということになります。seq を再実装したい場合は最初の実装では不十分ですが、これがなぜかを考えるのは読者への課題としておきましょう。

もう一つのCombine

Combine の通常のシグネチャは、

M<'T>*M<'T>->M<'T>

または

M<unit>*M<'T>->M<'T>

でした。しかし、今まで見てきたものはすべて前者の派生形であり、後者は出てきませんでした。後者の第一引数側がunit になるようなCombine はどういうときに出てくるのでしょうか？

今までの例の共通点

今まで見てきたのは、list とoption でした。この2つの共通点はいくつかありますが、ここではゼロ値を持つ点が重要です。list の場合は[] (空リスト)が、option の場合はNone がゼロ値です。型の定義を見てみると分かりやすいです。

type 'alist=|[](* ゼロ値 *)|(::)of 'a* 'alisttype 'aoption=|None(* ゼロ値 *)|Someof 'a

このように、ゼロ値とそれ以外の場合でデータコンストラクタが別になっているのが分かります。これらゼロ値は、'a がなんであろうが使えます。

さて、ではこのような「ゼロ値」がないような型を考えてみます。

Async

F#で非同期計算を表す型であるAsync<'T> を見てみます。この型はlist やoption と違って、データコンストラクタが1つしかありません*3。

(* https://github.com/Microsoft/visualfsharp/blob/2d413fb940aa1677688454c50b8ec05cd3b6f78f/src/fsharp/FSharp.Core/control.fs#L584より *)[<NoEquality;NoComparison>][<CompiledName("FSharpAsync`1")>]typeAsync<'T>=Pof(AsyncParams<'T>->FakeUnitValue)

そのため、ゼロ値はありません。(ちなみに、FakeUnitValue はunit がIL的にはvoid に落ちてしまうため末尾最適化の対象にならない(tail. プレフィックスが発行されない)問題を回避するために導入された型であり、unit と思ってもらって構いません)

しかし、AsyncBuilder はZeroメソッドを次のシグネチャで提供しています。

memberZero :unit->Async<unit>

Async<unit> 型の値はゼロ値ではありません。例えば'a option のNone は実際の型がint option だとしてもstring option だとしても使えます。ある意味、ジェネリックな値として振る舞うのです。

それに対して、AsyncBuilder のZeroメソッドはAsync<'a> ではなくAsync<unit> を返します。このZeroメソッドの定義に意味はあるのでしょうか？Zero 単体ではわかりにくいので、Combine も見てみます。

let sequentialA p1 p2=    bindA p1(fun()-> p2)(* snip *)member b.Combine(p1, p2)= sequentialA p1 p2

引数の順番に注意する必要がありますが、なるほどBind に落ちるんですね。bindA の第二引数の関数が受け取る型がunit になっている点に注目してください。つまり、p1 の型はAsync<unit> である必要があります。Combine の型がAsync<unit> * Async<'T> -> Async<'T> になりました！さらに、Zeroメソッドの戻り値の型とCombine の第一引数の型が一致していることから、両者を組み合わせて使えることがわかります。

このように、ゼロ値が用意されていない(できない)型の場合に、M<unit> * M<'T> -> M<'T> というバージョンのCombine を提供すると、便利な場合があります。Combine の第一引数側を無視して、第二引数側を常に返すようなイメージですね。また、その場合はZeroメソッドはM<unit> 型の値を返すように定義します。

ということで、AsyncBuilder ではこういうコードがコンパイルできます。

async{if cond1then printfn"if1"if cond2then printfn"if2"  return"str"}

おぉ、便利っぽい！

ZeroとCombineの罠

ただ、注意点として、このようなコードもコンパイルできてしまいます。

async{iftruethen    return()  return"str"}

「え、型はどうなってるの？」と思った方、return という単語のイメージに引きずられています。F#のreturn は別にコンピュテーション式全体の型を決めるわけではありません。AsyncBuilder でのCombine は、第一引数側を無視して、第二引数側を常に返すようなイメージでした。第一引数側はAsync<unit> になっているため、Combine によって無視(厳密には無視しているわけではないが・・・)されて、第二引数側が返されます。直観と反している気はしますが、そういうものです。

展開結果を見ればもう少し納得しやすいかもしれません。

let b= asyncb.Delay(fun()->  b.Combine((iftruethen b.Return()else b.Zero()),(* 第一引数側の結果にかかわらず *)    b.Delay(fun()->      b.Return("str"))))(* 第二引数側の結果が使われる *)

こういうビルダーを使うときは、return () と書かないほうが無難でしょう。unit を受け取るReturn をオーバーロードして、Obsolete 属性でコンパイルエラーにする、とかできるかもしれませんのでそういうビルダーが作りたくなった際に参考にしてください。

returnできない罠

型の問題ではなく、「え、return したのにその後ろのコードが実行されるの？」と思った方、return という単語のイメージに引きずられています。F#のreturn は別にその時点で結果を返すようなものではありません。単にビルダーのReturnメソッドが呼び出されるだけであり、Return 自体は実行の流れを制御できません。

AsyncBuilder のZeroメソッドが返す値はゼロ値ではありませんでした。また、Combine の第一引数がAsync<unit> に固定されているため、

async{iftruethen    return"str1"(* ここにstringは置けない。unitである必要がある *)  return"str2"}

とは書けません。コンパイルエラーになります。このあたりを解決するために、Stateを使ったり継続を使ったりできるかもしれませんが、Async では未検証です。気になった方は以下のリンク群をどうぞ。

F#のコンピュテーション式を提供するライブラリ事情

yieldとreturnの話でも調べたのですが、現在の状況を調べてみました。調べたのは下記のコードです。

FSharpx.Extras

まず、Delay の実装ですが、これは受け取った関数を実行せずにそのまま返しています。そのため、Combine の中で第二引数を実行することになります。しかし、これをOption.bind にそのまま渡しているため、Combine の第一引数の型がunit option に固定化されてしまっています。せっかくZeroメソッドが'a option のゼロ値であるNone を返しているにもかかわらず、これでは宝の持ち腐れです。

ということで、このようなコードのコンパイルが通ってしまいます。

maybe{iftruethen    return()(* ??? *)  return10}

さらに、Combine の実装が第一引数としてunit option を要求するため、下記のコードはコンパイルが通りません。

maybe{iftruethen    return10(* compile error *)  return20}

これではZeroメソッドの戻り値をNone にしている意味が全くありません。

ExtCore

前回調査時はZero が返す値がSome () でしたが、そこはNone に修正されていました。しかし、Combine がオーバーロードされているうえ、シグネチャもおかしい・・・

memberDelay:(unit-> 'Toption)->(unit-> 'Toption)memberCombine:unitoption* 'Toption-> 'Toption(* 使われないオーバーロード *)memberCombine:unitoption*(unit-> 'Toption)-> 'Toption(* 実際はunit optionではなく'Tではないジェネリック型になっているけど、     Delayの呼び出しが第二引数に渡されるため、実質unitになる *)

Delay の実装が受け取った関数をそのまま返す実装になっているため、最初のCombine のオーバーロードは使われません。しかも、FSharpx.Extras同様にCombine の実装がBind を呼び出しているため、やはり下記コードはコンパイルできません。

maybe{iftruethen    return10(* compile error *)  return20}

Zero の実装も意味がなく、やはり下記コードはコンパイルが通ってしまいます。

maybe{iftruethen    return()(* ??? *)  return10}

なかなかの迷走ぶりです。

Visual F# PowerTools

Visual F# PowerToolsが持っているMaybeBuilder は、過去のバージョンのExtCoreからコピーしてきたものです。そのため、Zero がSome () になっており、Delay は渡された関数を実行しており、Combine はunit option * 'T option -> 'T option 版になっています。Zero とCombine の整合性は取れていますが、ゼロ値を使っていないのが微妙です。また、Delay が実行を遅延しないバージョンなので、副作用と一緒には使えません。

まぁ、このMaybeBuilder はVFPTの内部のみでしか使われない想定のため、それほど問題ではないでしょう。

Basis.Core

最近全然更新してませんが、このライブラリはそもそも巷のライブラリのコンピュテーションビルダーがことごとくダメ実装だったから作ったライブラリなので、これまで見てきたような問題はありません。

(* コンパイルエラー *)option{iftruethen    return()  return10}

(* Some 10 *)option{iftruethen    return10  return20}

ただし、while の中でのreturn できるようにStateを使った実装をしているため、Zero もCombine もこれまで見てきたものとは全然違うシグネチャおよび実装になっています。

member this.Zero()=None,Continuemember this.Combine((x:_option, cont), rest:unit->_option*FlowControl)=match contwith|Break-> x,Break|Continue->if x.IsSomethen x,Breakelse rest()

この実装についての話は、(再掲になりますが)下記のURLをどうぞ。

まとめ

Combine を中心にいろいろなことを見ました。

Combine の目的
Combine 実装に絡むDelay の実装2通り
- 単純なDelay の実装の罠
- もう一つのDelay の実装とRun
単純なDelay の実装で十分なケース (ListBuilder)
第一引数としてM<unit> を取るCombine について
- ゼロ値について
- ゼロ値がない場合(Async<'T>)のCombine とその罠
  - return () 出来てしまう
  - return x 出来ない
コンピュテーション式を提供するライブラリのCombine
- 大体のライブラリが何かしら問題を抱えている