詳説コンピュテーション式

コンピュテーション式とは

コンピュテーション式とは、機能を制限したマクロです。 ・・・では投げやりすぎるので、もうちょっとだけ説明を試みると、 「式変形によって言語の用意する構文の意味をカスタマイズできるようにする仕組み」です。 モナド用の構文として紹介されることもありますが、それはコンピュテーション式という仕組みの上でモナドを扱っているだけに過ぎません。

もっとも、コンピュテーション式はモナド用の構文として使うことが一番多いでしょうから、 モナド用の構文と理解しても問題はないでしょう。 また、このような状況を考えると、モナド以外のことにコンピュテーション式を使う場合は、 現状では「これはモナドではありません」という表明をドキュメントなりなんなりでしておくのが無難でしょう。 特に、let!とreturnを提供する場合でコンピュテーション式をモナドではない構文とする場合は、 うるさいくらいその旨を伝えるようにしましょう。 作ったものがモナドっぽいけど確信が持てない・・・という場合にも、「モナドっぽいけど本当にそうかどうかはちゃんと確認してないよ」とか書いておくといいでしょう。 これは、見ず知らずの誰かのためですし、自衛のためでもあります。

このエントリはコンピュテーション式の仕様を、 日本語で出来る限り分かりやすく解説することを試みたナニカです。 コンピュテーション式自体を使ったことがある人を対象に、その変換の仕組みを説明します。 カスタムオペレータがかかわる部分を省いてあるため、仕様書よりも単純化されており、より理解しやすくなっていると思います。 これを読んでから仕様書を読めば、カスタムオペレータ部分を理解するのもそう難しくはないでしょう。

詳説コンピュテーション式

コンピュテーション式は、以下の構文で表されます。

builder-expr { cexpr }

builder-exprは、後述するReturnやBindなどのメソッドを持つ型(以降、ビルダー)をもった式です。 cexprは、通常のF#の文法に加えて、この中でのみ使える記法(let!など)を加えた文法によって書かれた式です。 cexprの中で使える記法は、ビルダーがどんなメソッドを提供しているかによります。 例えば、ビルダーがBindメソッドを提供している場合はcexprの中でlet!が使えますが、 提供されていない場合はlet!は使えません。

builder-exprには通常、後述するビルダーのインスタンス(例えば、asyncなど)を指定しますが、 関数呼び出しの結果やメソッド呼出しの結果としてビルダーが戻ってくるようなコンピュテーション式も当然考えられます。

let x = someCompExprBuilder (a, b) { ... }

これは、コンピュテーション式の動作を使う側で変更したい場合や、 ビルダーが内部に状態を持つなどして使いまわせない場合に有効です。

これを使っている例としては、Basis.Coreの ResultWithZeroBuilderがあります。 これは、コンピュテーション式を使う側でゼロ値を指定することで、 通常のResultBuilderでは提供不可能な構文をサポートしています。

(* xに負の数を指定した場合、Zeroメソッドが呼び出され、
   resultWithZeroに指定した"oops!"がFailureに包まれて返る *)
let f x = resultWithZero "oops!" {
  if x >= 0 then
    return x * 2
}

let x = f 10  (* => Success 20 *)
let x = f -10 (* => Failure "oops!" *)

コンピュテーション式の変換

コンピュテーション式はまず、以下のように変換されます((bは「フレッシュな変数(名前が他とかぶらない変数)」です))。

let b = builder-expr in {| cexpr |}c

ここで、{| ... |}cという表記が出てきますが、これは「その中の式をコア言語の式(つまり通常のF#の式)に変換する」ことを意味します。 似たような表記に、{| ... |}0もありますが、これは「カスタムオペレータが許されるかどうか」が違います。 {| ... |}cの方はカスタムオペレータが許されますが、{| ... |}0の方はカスタムオペレータが許されません。

以降では、話を単純化するためにカスタムオペレータについては省略します。 そのため、cや0といった使い分けはせず、単純に{| ... |}という表記を使いますが、言語仕様を読む際は注意してください。

また、builder-exprは1回しか実行されない点に注意してください。 cexprの変換中にビルダーにアクセスする際は、bを通してアクセスされます。 このルールによって変換の際に使われるオブジェクトは同じものであることが保証されているため、 毎回ビルダーを作るようにすれば、ビルダーの中に状態を持っても大丈夫なのです。

Run, Delay, Quote

ビルダーにRun, Delay, Quoteの各メソッドが実装されている場合、 コンピュテーション式は先ほどの変換の際に、これらのメソッドの呼び出しを差し込みます。

3つとも実装されている場合、以下のように変換されます。

let b = builder-expr
b.Run(<@ b.Delay(fun () -> {| cexpr |}) @>)

変換の順番としては、Delay, Quote, Runの順で変換されます。 もし対象のメソッドがなかった場合は、対応する変換は行われません。

Delay変換

ビルダーにDelayメソッドが存在する場合、cexprの変換した式をラムダ式で囲い、Delayに渡します。

builder-expr { cexpr }

これが、以下のように変換されます。

let b = builder-expr
b.Delay(fun () -> {| cexpr |})

ビルダーにDelayが存在しない場合、b.Delay(fun () -> {| cexpr |})の部分は単に{| cexpr |}となります。

{| cexpr |}に対する変換の結果の式を、delayed-exprとします。 Delayが存在する場合はb.Delay(fun () -> {| cexpr |})、存在しない場合は{| cexpr |}がdelayed-exprです。

Delayは、ここでの変換よりも、他の変換の中で現れる際に重要になってきます。 whileの変換までDelayは出てきませんが、Delayの存在はその時まで頭の片隅にでも置いておいてください。

Quote変換

ビルダーにQuoteメソッドが存在する場合、delayed-exprをコード引用符<@ ... @>で囲みます。

let b = builder-expr
delayed-expr

これが、以下のように変換されます。

let b = builder-expr
<@ delayed-expr @>

ビルダーにQuoteメソッドが存在しない場合、コード引用符で囲わずに、特に変換は行いません。

delayed-exprに対する変換の結果の式を、quoted-exprとします。 Quoteが存在する場合は<@ delayed-expr @>、存在しない場合はdelayed-exprがquoted-exprです。

このように、Quoteメソッドは呼び出されることはありません。 単に、存在すればいいだけのメソッドです。 ビルダーに対する属性にしなかったのは、拡張メソッドでQuoteの機能を後付けできるようにするためでしょうか？

Run変換

ビルダーにRunメソッドが存在する場合、quoted-exprをRunに渡します。

let b = builder-expr
quoted-expr

これが、以下のように変換されます。

let b = builder-expr
b.Run(quoted-expr)

ビルダーにRunメソッドが存在しない場合、特に変換は行いません。

Runは最後に一回だけ呼び出されるメソッドになるので、このメソッドの結果がコンピュテーション式の結果になります。 活用方法としては、Readerモナド用のビルダーに対して、最終的に値を取り出すビルダーを作るようなものが考えられます。

type Reader<'TEnv, 'T> = 'TEnv -> 'T

type ReaderBuilder () =
  ...

(* 普通のreaderコンピュテーション式 *)
let reader = ReaderBuilder ()

type ReaderBuilderWithRun<'TEnv> (env: 'TEnv) =
  ...
  member this.Run(x: Reader<'TEnv, _>) = x env

(* 一番外側で使うと便利なコンピュテーション式 *)
let readerWithRun env = ReaderBuilderWithRun<_> env

変換のルール

仕様書では、

{| cexpr |}c ≡ T (cexpr, [], fun v -> v, true)
{| cexpr |}0 ≡ T (cexpr, [], fun v -> v, false)

が変換のルールとして記載されています((このTは、translateもしくはtranslationの略でしょう))。 T(e, V, C, q)とあった時、

• eは変換されるコンピュテーション式
• Vはこれまでにバインドされた変数群
• Cは変換済みのコンテキスト情報
• qはカスタムオペレータを許すかどうかの真偽値

を表します。 Cの部分に変換されたものが入ると考えましょう。上の変換規則では、まだ何も変換されてないので、fun v -> vと、id関数になっています。

この中で、Vはカスタムオペレータに関係する変換中で使われるもののため、 またqもカスタムオペレータが絡む変換の際に必要になってくるもののため、今回は無視します。 そのため、このエントリでは

{| cexpr |} ≡ T (cexpr, fun v -> v)

という単純化したルールを使います。

returnの変換とyieldの変換

returnの変換は、以下のルールで表されます。

T(return e, C) = C(b.Return(e))

これは、return eがb.Return(e)に変換されることを意味します。

簡単な例を考えてみましょう。

type SimpleBuilder () =
  member this.Return (x) = x

let simple = SimpleBuilder ()

let res = simple { return 10 }

この最後の行を変換してみます*1。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| return 10 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(return 10, fun v -> v)

(* 3. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> v) (b.Return(10)))

(* 4. ラムダ式部分を計算 *)
let res =
  let b = simple
  b.Return(10)

変換できました。

yieldの変換は、

T(yield e, C) = C(b.Yield(e))

と、returnがyieldに、ReturnがYieldになっただけなので、同じステップで変換できます。

return!の変換とyield!の変換

return!の変換は、以下のルールで表されます。

T(return! e, C) = C(b.ReturnFrom(src(e)))

これは、return! eがb.ReturnFrom(src(e))に変換されることを意味します。

src(e)は、ビルダーがSourceメソッドを持っており、 かつ最も内側のForEachがユーザによるもの(変換により生成されたコードではなく、ユーザが書いたコードであるということ)である場合のみ、 b.Source(e)に変換されます。

2番目の条件は仕様書からのものですが、どうも実際の実装はちょっと違っているようです。 コードを軽く眺めただけですが、ForEachとForEachThenJoinOrGroupJoinOrZipClauseのForEach部分とLetOrUseBangの場合に、 ユーザコードかどうかの判定をしているようで、そのほかの部分ではビルダーにSourceメソッドがあればそれを呼び出しているようです。 そのため、return! eはビルダーにSourceメソッドが存在すればb.ReturnFrom(b.Source(e))に、存在しなければb.ReturnFrom(e)に変換されます。

yield!は、ReturnFromではなくYieldFromが使われる以外は同じです。

letの変換

letの変換は以下のルールで表されます。

T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))

これは、returnやreturn!とは異なり、変換後にもT(e, C)形式が出てくるとおり、変換後もさらに変換が行われます。 実際にどう変換されるかを一歩一歩確認していきましょう。

letの変換を追う

returnの時に定義したSimpleBuilderを使い、以下のコンピュテーション式を変換してみます。

let res = simple {
  let a = 10
  return a * 2
}

letの変換規則はこうでした。

T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))

これを使って変換します。 returnの時も言いましたが、変換の途中は有効なF#コードではないことに注意してください。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| let a = 10 in return a * 2 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(let a = 10 in return a * 2, fun v -> v)

(* 3. T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))のルールを適用 *)
let res =
  let b = simple
  T(return a * 2, fun v -> (fun v -> v) (let a = 10 in v))

(* 4. Tの最後の部分を計算 *)
let res =
  let b = simple
  T(return a * 2, fun v -> let a = 10 in v)

(* 5. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> let a = 10 in v) (b.Return(a * 2)))

(* 6. ラムダ式部分を計算 *)
let res =
  let b = simple
  let a = 10
  b.Return(a * 2)

これで変換できました。 ステップ5のコードは、有効なF#のコードにも見えますが、Returnの引数に出てくるaがどこにもないことからもわかる通り、 最終段階まで変換するまでは有効なF#のコードではないことに注意してください。

変換の結果を見ると、let p = e in ceの変換は、ceの部分のみ変換することになります。 これをT(e, C)形式ではなく{| ... |}形式で書くと、

{| let p = e in ce |} = (let p = e in {| ce |})

となります。 特に何も定義しなくても、letはコンピュテーション式の中でも使えるということですね。

let!の変換

let!の変換は以下のルールで表されます。

T(let! p = e in ce, C) = T(ce, fun v -> C(b.Bind(src(e), fun p -> v)))

letの変換を見たので、この変換は分かりやすいですね。 {| ... |}形式で書くと、

{| let! p = e in ce |} = b.Bind(src(e), fun p -> {| ce |})

となります。 このように、let!を使うためにはビルダーにBindメソッドが定義されている必要があります。 Bindメソッドは引数を2つ取り、2番目の引数は関数である必要があることが分かります。 また、eの型とpの型は一致していなくてもいいことも分かります。

eをpに代入するように見える構文のため、Bindメソッドの中では第一引数の値(e)を変換するなどして、 第二引数の関数に渡すようにBindメソッドを実装することがほとんどでしょう。 また、通常はBindメソッドはモナドにおける>>=の定義と同じようなものになるでしょう。

useの変換とuse!の変換

useの変換は以下のルールで表されます。

T(use p = e in ce, C) = C(b.Using(e, fun p -> {| ce |}))

ここまで理解できた人にとっては簡単ですね。

use!も見てみましょう。

T(use! p = e in ce, C) = C(b.Bind(src(e), fun p -> b.Using(p, fun p -> {| ce |})))

ちょっと複雑ですね。 が、順番に見て行けば難しくはありません。

SimpleBuilderにUsing(とBind)を追加してみましょう。

type SimpleBuilder with
  member this.Bind(x, f) = f x
  member this.Using(x, f) =
    printfn "start"
    try f x
    finally printfn "end"

これを変換します。

let res = simple {
  use! a = 10
  return a * 2
}

順番に変換していきます。

(* 1. 全体の変換 *)
let res =
  let b = simple
  {| use! a = 10 in return a * 2 |}

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let res =
  let b = simple
  T(use! a = 10 in return a * 2, fun v -> v)

(* 3. T(use! p = e in ce, C) =
      T(ce, fun v -> C(b.Bind(src(e), fun p -> b.Using(p, fun p -> v))))
      のルールを適用 *)
let res =
  let b = simple
  T(return a * 2, fun v -> (fun v -> v) (b.Bind(10, fun a -> b.Using(a, fun a -> v))))

(* 4. Tの最後の部分を計算 *)
let res =
  let b = simple
  T(return a * 2, fun v -> b.Bind(10, fun a -> b.Using(a, fun a -> v)))

(* 5. T(return e, C) = C(b.Return(e))のルールを適用 *)
let res =
  let b = simple
  ((fun v -> b.Bind(10, fun a -> b.Using(a, fun a -> v))) (b.Return(a * 2)))

(* 6. ラムダ式部分を計算 *)
let res =
  let b = simple
  b.Bind(10, fun a -> b.Using(a, fun a -> b.Return(a * 2)))

変換作業には慣れましたか？

use/use!の注意点

use/use!は、let/let!と意味が似ている(変数を導入する)うえ、Usingのシグネチャがlet!を使えるようにするために必要なBindのシグネチャと同じようなものであるため、 何も定義せずともuseが使え、Usingによってuse!が使えると思ってしまうかもしれません。 しかし、変換規則を見たとおり、useであってもUsingがビルダーに定義されていなければ使えません。 また、Usingの第一引数はuseの場合はuse p = eのeがそのまま、use!の場合はBindの第二引数で渡された関数の引数が入ってくることから、 UsingはそのままBindに相当するような機能*2は持たせられず、単にletやlet!をラップする存在でしかないことが分かります。

useはletに対してUsing機能を付けたもの、use!はlet!に対してUsing機能*3を付けたもの、と考えてください。 通常、Usingの実装は以下のようになるでしょう。

member this.Using(x: #IDisposable, f) =
  try
    f x
  finally
    match x with
    | null -> ()
    | _ -> x.Dispose()

doの変換

doの変換は以下のルールで表されます。

T(do e in ce, C) = T(ce, fun v -> C(e; v))

特に問題はないでしょう。eが実行された後、変換されたceが実行されるだけです。

do!の変換

do!の変換はルールが2つあり、後ろに式が続く場合と、do!より後ろにこれ以上変換する式がなかった場合で変換のされ方が若干異なります。

T(do! e in ce, C) = T(let! () = e      in ce,         C)
T(do! e;,      C) = T(let! () = src(e) in b.Return(), C)

do!より後ろにこれ以上変換する式がなかった場合、return ()が書かれているような動作になります。 do!の変換規則は、let!に変換してからlet!の変換規則を適用するような形になっています。 DRYでいいですね。 それ以外は、特に難しいところはないでしょう。

do!の変換にはlet!が必要となるため、do!を使うためにはBindメソッドがビルダーに必要になります。 また、場合によってはBindメソッドのほかに、Returnメソッドも必要となります。

if-then-elseの変換

2分岐の条件分岐の変換は以下のルールで表されます。

T(if e then ce1 else ce2, C) = C(if e then {| ce1 |} else {| ce2 |})

特に難しくありませんね。 ビルダーに何も定義しなくても、elseを伴うifを使えることが分かります。

if-thenの変換

elseを省略したifの変換は以下のルールで表されます。

T(if e then ce, C) = T(ce, fun v -> if e then v else b.Zero())

elseを持つifとは違い、ビルダーにZeroメソッドが必要なことが分かります。

elseを省略しないifと表記を合わせると、変換規則は以下のようになります。

T(if e then ce, C) = C(if e then {| ce |} else b.Zero())

matchの変換

matchの変換は以下のルールで表されます。

T(match e with pi -> cei, C) = C(match e with pi -> {| cei |})

piはi番目のパターンを表し、ceiはi番目の式を表します。 パターンが複数あった場合は、それぞれが変換されます。

また、何も定義しなくてもmatchは使えることが分かります。

whileの変換

whileの変換は以下のルールで表されます*4。

T(while e do ce, C) = T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))

Whileのほかに、Delayメソッドも必要であることが分かります。 手で変換してみましょう。 ビルダーには、SimpleBuilderの拡張を使います。

type SimpleBuilder with
  member this.While(cond, body) = while cond () do body
  member this.Delay(f) = f ()

変換する対象はこれです。

let f x = simple {
  while x do
    printfn "while"
    return ()
}

変換してみましょう。

(* 1. 全体の変換 *)
let f x =
  let b = simple
  b.Delay(fun () -> {| while x do let () = printfn "while" in return () |})

(* 2. {| cexpr |}形式をT(e, C)形式に変換 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(while x do let () = printfn "while" in return (), fun v -> v))

(* 3. T(while e do ce, C) =
      T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))
      のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(let () = printfn "while" in return (), fun v -> (fun v -> v) (b.While((fun () -> x), b.Delay(fun () -> v)))))

(* 4. Tの最後の部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(let () = printfn "while" in return (), fun v -> b.While((fun () -> x), b.Delay(fun () -> v))))

(* 5. T(let p = e in ce, C) = T(ce, fun v -> C(let p = e in v))のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(return (), fun v -> (fun v -> b.While((fun () -> x), b.Delay(fun () -> v))) (let () = printfn "while" in v)))

(* 6. Tの最後の部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> T(return (), fun v -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in v))))

(* 7. T(return e, C) = C(b.Return(e))のルールを適用 *)
let f x =
  let b = simple
  b.Delay(fun () -> (fun v -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in v))) (b.Return()))

(* 8. ラムダ式部分を計算 *)
let f x =
  let b = simple
  b.Delay(fun () -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in b.Return())))

変換できました。 コンパイル時に行われる変換はここまでですが、これだと結局どうなるのか分かりにくいので、Delayメソッドを展開してみましょう。 Delayメソッドは単に受け取った関数を実行するだけのものとして実装しているので、b.Delay(fun () -> expr)をexprにするだけですね。

(* 内側のDelayを展開 *)
let f x =
  let b = simple
  b.Delay(fun () -> b.While((fun () -> x), let () = printfn "while" in b.Return()))

(* 外側のDelayを展開 *)
let f x =
  let b = simple
  b.While((fun () -> x), let () = printfn "while" in b.Return())

whileを使うためには、このようにWhileメソッドとDelayメソッドが必要です。 が、これで本当に大丈夫でしょうか・・・？ 実際に、fを呼び出したときにどう動くのか見てみます。 falseを渡してみましょう。

(* whileの実装:
  member this.While(cond, body) = while cond () do body *)

(* step 1: 呼び出し *)
f false

(* step 2: fを展開 *)
let b = simple
b.While((fun () -> false), let () = printfn "while" in b.Return())

(* step 3: b.Whileの引数を評価 *)
let b = simple
let arg1 = (fun () -> false)
let arg2 =
  printfn "while"
  b.Return()
b.While(arg1, arg2)

(* step 4: b.Whileを展開 *)
let b = simple
let arg1 = (fun () -> false)
let arg2 =
  printfn "while"
  b.Return()
while arg1 () do
  arg2

なにかおかしいのが分かりますか？ 変換する前のコードを再掲します。

let f x = simple {
  while x do
    printfn "while"
    return ()
}

変換する前のコードは、printfnによる出力はwhileの中にありました。 そのため、直感的にはxがfalseであれば、何も出力されることなくループが終了すると考えてしまいます。 しかし、変換後のコードではwhileの外側に出力が移動してしまいました。 これでは、xにtrueを渡そうがfalseを渡そうが元のwhileの処理が呼び出されてしまいます((さらには、trueを渡したにもかかわらず、whileの中の処理は一回しか実行されません))。 これは使い物になりませんね。

これではまずい場合は、WhileメソッドとDelayメソッドの定義を変更し、Runメソッドを実装することで解決します。

SimpleBuilderを再実装

SimpleBuilderを拡張してきましたが、もう最初らへんのメソッド忘れ気味ですよね。 なので、ここで今までのSimpleBuilderを捨て、新たなSimpleBuilderを定義します。

(* Usingは提供しない *)
type SimpleBuilder () =
  member this.Zero() = Unchecked.defaultof<_>
  member this.Return(x) = x
  member this.Bind(x, f) = f x
  member this.While(cond, body) = while cond () do body () (* body -> body () *)
  member this.Delay(f) = f  (* f () -> f *)
  member this.Run(f) = f () (* new! *)

let simple = SimpleBuilder ()

let f x = simple {
  while x do
    printfn "while"
    return ()
}

fの本体を変換した結果がこちらになります(実際の変換は各自の課題とします)。

let f x =
  let b = simple
  b.Run(b.Delay(fun () -> b.While((fun () -> x), b.Delay(fun () -> let () = printfn "while" in b.Return()))))

今回のビルダーでは、Delayは何もせずに返しますので、b.Delay(fun () -> ...)は単に(fun () -> ...)に展開できます。 展開してみましょう。

(* 内側のDelayを展開 *)
let f x =
  let b = simple
  b.Run(b.Delay(fun () -> b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))))

(* 外側のDelayを展開 *)
let f x =
  let b = simple
  b.Run(fun () -> b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return())))

(* Runも展開してしまう *)
let f x =
  let b = simple
  b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))

展開できました。 Runが必要なのは、Delayを実装すると一番外側も関数にくるまれてしまうため、それを実行しないと全体として関数が戻ってしまうからですね。

元の展開結果と比べてみます。

(* 元の展開結果 *)
let f x =
  let b = simple
  b.While((fun () -> x), let () = printfn "while" in b.Return())

(* 今回の展開結果 *)
let f x =
  let b = simple
  b.While((fun () -> x), (fun () -> let () = printfn "while" in b.Return()))

第二引数部分が関数で包まれたままになりました。 この関数fにfalseを渡すと、最終的には以下のようなコードが実行されることになります。

(* whileの実装:
  member this.While(cond, body) = while cond () do body () *)

let b = simple
let arg1 = (fun () -> false)
let arg2 =
  (fun () ->
    printfn "while"
    b.Return())
while arg1 () do
  arg2 ()

これで、思い通りの結果になりますね。

このように、whileの展開にはWhileメソッドとDelayメソッドのみが必要ですが、現実的にはRunメソッドも実装する必要がある場合が多いです。

ce1; ce2の変換

ce1; ce2の変換は以下のルールで表されます。

T(ce1; ce2, C) = C(b.Combine({| ce1 |}, b.Delay(fun () -> {| ce2 |})))

CombineメソッドとDelayメソッドが必要ですね。 簡単です。

ですが、ce1; ce2の変換は、whileなどを実用的なものにするために必要になるため、非常に重要です。

whileを実用するためのCombine

whileの変換で、「whileの展開にはWhileメソッドとDelayメソッドのみが必要ですが、現実的にはRunメソッドも実装する必要がある場合が多いです」と書きましたが、 実はこれだけではまだ足りません。 今のWhileの実装では、while以降に別のceを置けず、かつwhileの本体はunitを返す必要があります。

member this.While(cond, body) =
  while cond () do
    body () (* while式の本体はunitである必要があるため、bodyの型はunit -> unitのみ許される *)

どうすればいいか。そうですね、Combineです。

type SimpleBuilder () =
  let mutable isExit = false
  member this.Zero() = Unchecked.defaultof<_>
  member this.Return(x) = isExit <- true; x
  member this.Bind(x, f) = f x
  member this.Combine(x, f) = if isExit then x else f ()
  member this.While(cond, body) =
    if not (cond ()) then this.Zero()
    else let x = body () in this.Combine(x, fun () -> this.While(cond, body))
  member this.Delay(f) = f
  member this.Run(f) = isExit <- false; f ()

let simple () = SimpleBuilder ()

isExitとCombineの追加、ReturnとWhileの変更を行いました。 さらに、simpleを関数にしています。 詳しい説明は省きますが、これによって以下のようなコードが書けるようになりました。

let f x = simple () {
  while x do
    return 10
  return 0
}

これで、trueを渡すと10が返り、falseを渡すと0が返ります。 展開や、なぜsimpleを関数にしたのかを考えるのは読者の課題とします。

ちなみに、simpleを関数にしなくても済む方法があります。 それを実装した例がBasis.CoreのOptionBuilderなどで見れます。*5 このエントリは、その時の苦労の反動が書くきっかけとなっています。

よくあるコンピュテーション式の実装では、上のようなwhileの中でreturnするコードを上手く扱えないと思います。 「このコードを扱えるコンピュテーション式を実装しているコードが他にもあるよ！」というものがあったらコメント欄で教えてくれると嬉しいです。

tryの変換

tryの変換は以下のルールで表されます。

T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce |}), fun pi -> {| cei |}))
T(try ce finally e, C) = C(b.TryFinally(b.Delay(fun () -> {| ce |}, fun () -> e)))

ここまで来たら、もはや何も難しいことはありませんね。 ただ、withの変換はちょっと怪しいです。 正しくは多分、こうですね。

T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce |}), function pi -> {| cei |}))

forの変換

forの変換は以下のルールで表されます。

T(for x in e do ce, C) = T(ce, fun v -> C(b.For(src(e), fun x -> v)))
T(for x = e1 to e2 do ce, C) = T(for x in e1 .. e2 do ce, C)

forも難しいところはありません。 下の形式は、上の形式のforに書き換えたうえで変換するようになっていますね。

eの変換

eの変換は以下のルールで表されます。

T(e, C) = C(e; b.Zero())

簡単ですね。 simple { () }や、simple { printfn "hoge" }などは、Zeroの呼び出しを付けて変換されます。

まとめ

他にもカスタムオペレータが絡む変換規則がいくつかありますが、 取りあえずコンピュテーション式の実装でよく使うであろう変換規則の説明は以上です。 ここまで理解できれば、カスタムオペレータが絡む変換規則も理解できるでしょう。

みなさんもコンピュテーション式の変換規則を理解して、色々なコンピュテーション式を作ってみましょう！

付録 変換規則一覧

このエントリで紹介した変換規則の一覧を載せておきます。

(* {| cexpr |}とT(...)の関係 *)
{| cexpr |} ≡ T (cexpr, fun v -> v)
(* return *)
T(return e,  C) = C(b.Return(e))
T(return! e, C) = C(b.ReturnFrom(src(e)))
(* let/let! *)
T(let p  = e in ce, C) = T(ce, fun v -> C(let p = e in v))
T(let! p = e in ce, C) = T(ce, fun v -> C(b.Bind(src(e), fun p -> v)))
(* use/use! *)
T(use p  = e in ce, C) = C(b.Using(e, fun p -> {| ce |}))
T(use! p = e in ce, C) = C(b.Bind(src(e), fun p -> b.Using(p, fun p -> {| ce |})))
(* do/do! *)
T(do e  in ce, C) = T(ce, fun v -> C(e; v))
T(do! e in ce, C) = T(let! () = e in ce, C)
T(do! e;,      C) = T(let! () = src(e) in b.Return(), C)
(* if *)
T(if e then ce1 else ce2, C) = C(if e then {| ce1 |} else {| ce2 |})
T(if e then ce,           C) = C(if e then {| ce  |} else b.Zero())
(* match *)
T(match e with pi -> cei, C) = C(match e with pi -> {| cei |})
(* while *)
T(while e do ce, C) = T(ce, fun v -> C(b.While((fun () -> e), b.Delay(fun () -> v))))
(* ; *)
T(ce1; ce2, C) = C(b.Combine({| ce1 |}, b.Delay(fun () -> {| ce2 |})))
(* try *)
T(try ce with pi -> cei, C) = C(b.TryWith(b.Delay(fun () -> {| ce|}), function pi -> {| cei |}))
T(try ce finally e,      C) = C(b.TryFinally(b.Delay(fun () -> {| ce |}, fun () -> e)))
(* for *)
T(for x in e do ce, C) = T(ce, fun v -> C(b.For(src(e), fun x -> v)))
T(for x = e1 to e2 do ce, C) = T(for x in e1 .. e2 do ce, C)
(* e *)
T(e, C) = C(e; b.Zero())

Delay変換、Quote変換、Run変換は上記規則で表現できないので省略します。

*1:もちろん、変換の途中段階は有効なF#コードではありません

*2:モナドの話をすると、モナドで包まれた値を「はがす」機能

*3:通常は第一引数に対するDispose呼び出し

*4:仕様書上はWhileの第一引数を囲むカッコはありませんが、 このカッコがないとWhileが「ユニットを受け取りタプルを返す関数」を受け取る一引数メソッドと解釈されてしまうため、必要です

*5:id:pocketberserker がコンピュテーション式の実装にStateを用いる - pocketberserkerの爆走で解説記事を書いてくれました！