コンピュテーション式におけるreturnとyield

今日、id:htid46 とF#の話をしつつ帰った時のまとめです。

前提条件

次の2つのエントリを読んでいることが前提です。

  1. 詳説コンピュテーション式 - ぐるぐる~
  2. コンピュテーション式の実装にStateを用いる - pocketberserkerの爆走

returnとyieldの変換規則

先日のエントリでも書いたように、ReturnとYield、ReturnFromとYieldFromは全く同じ変換のされ方をします。

T(return e, C) = C(b.Return(e))
T(yield e,  C) = C(b.Yield(e))
T(return! e, C) = C(b.ReturnFrom(src(e)))
T(yield! e,  C) = C(b.YieldFrom(src(e)))

つまり、ReturnもYieldも同じ実装にしたとしても、コンパイルは通ります。 ということは、そのコンピュテーション式により合うと思う方を実装すればいい・・・?

returnの意味とyieldの意味の違い

ところで、returnyieldではそれを使ったコードの持つ意味が違うように思えます。 例として、listコンピュテーション式を作ったとしましょう。

let f x = list {
  if x = 0 then
    return -1
  return 1
}
let g x = list {
  if x = 0 then
    yield -1
  yield 1
}

let f0, f1 = (f 0, f 1)
let g0, g1 = (g 0, g 1)

さて、f0, f1, g0, g1のそれぞれの値は、どうなっていてほしいでしょうか?

こうなっていることを期待しませんか?

val f0 : int list = [-1]
val f1 : int list = [1]
val g0 : int list = [-1; 1]
val g1 : int list = [1]

つまり、returnはそこで処理を打ち切るけど、yieldは打ち切らない、という違いがあるように思うのです。 これ、C#で考えてみた場合、yield breakyield returnの関係に似ていませんか?

F#にはyield breakがない

そういえばありませんでした。 が、OptionBuilderでの実装を使うと、returnyield breakの代わりになるのでは!?

ということで、こういう実装を考えてみました。

open System
open Basis.Core.ComputationExpr

(* 最初にpredを満たさなかった要素は結果に含めるtakeWhileの別バージョン *)
module Seq =
  let takeWhileButFirst pred xs = seq {
    let cont = ref true
    use itor = (xs :> _ seq).GetEnumerator()
    while itor.MoveNext() && !cont do
      let x = itor.Current
      if not (pred x) then
        cont := false
      yield x
  }

type ListBuilder internal () =
  member this.Zero() = [], Continue
  (* returnはBreak、yieldはContinue *)
  member this.Return(x) = [x], Break
  member this.ReturnFrom(xs: _ list) = xs, Break
  member this.Yield(x) = [x], Continue
  member this.YieldFrom(xs: _ list) = xs, Continue
  (* fしていって、Breakが出たら後ろは捨てる(isBreakをtrueにしたうえでfalseを返す) *)
  member this.Bind(xs, f: _ -> _ list * FlowControl) =
    let isBreak = ref false
    let res =
      xs
      |> Seq.map f
      |> Seq.takeWhileButFirst (function _, Continue -> true | _ -> isBreak := true; false)
      |> Seq.collect fst
      |> Seq.toList
    (res, if !isBreak then Break else Continue)
  (* Continueだったらrestを実行してappend、Breakだったらrestは捨てる *)
  member this.Combine((x: _ list, cont), rest: unit -> _ list * FlowControl) =
    match cont with
    | Break -> x, Break
    | Continue -> let rest, cont = rest () in List.append x rest, cont
  (* 以降、OptionBuilderと型以外は同じ定義 *)
  member this.While(guard, f) =
    if not (guard ()) then this.Zero()
    else let x = f () in this.Combine(x, fun () -> this.While(guard, f))
  member this.For(xs: #seq<_>, f) =
    this.Using(
      xs.GetEnumerator(),
      fun itor -> this.While(itor.MoveNext, fun () -> f itor.Current))
  member this.Delay(f: unit -> _ list * FlowControl) = f
  member this.Run(f) = f () |> fst

let list = List.ListBuilder()

Bindは複雑ですが、まぁ、こんなもんでしょう。 最初に出てきたBreakは結果に含めたいので、takeWhileではなく別バージョンを定義して呼び出しています。

Combineも難しくはないでしょう。

ミソは、Return系とYield系で、タプルの第二要素が違う点です。 こうしてみると、シグネチャや変換規則が同じなだけで、ReturnとYieldは別のものだという感じがしませんか?

C#yield breakは式をとれないため、yield returnしてからyield breakする必要がありました。 ですが、今回実装したlistコンピュテーション式は、return exprとすることで値を返しつつ処理を抜けることができます。 ちなみに、C#でのyield breakがしたい場合は、return! []とでもするといいでしょう。

カスタムオペレータが使えたら素敵!

queryコンピュテーション式のheadなどのように、yieldBreakのようなカスタムオペレータが作れれば、よりそれっぽいと思いませんか?

・・・が、これは出来ません。 先日は簡単のために省略したqというパラメータを覚えているでしょうか? これは、「その中でカスタムオペレータが使えるかどうか」を示すフラグです。 通常、yieldBreakしたいのはifの中ですが・・・お気づきですね。 最後のパラメータがqです。

T(if e then ce1 else ce2, V, C, q) = Assert(not q); C(if e then {| ce1 |}0 else {| ce2 |}0)

ifを使うためには、qfalseである必要があります。 つまり、カスタムオペレータが使えない場所にしかifは書けないんですね。残念・・・

ちなみに、elseを伴わないifは、elseを伴うifに変換されたうえでさらに変換が走るので、結局上のAssert(not q)から逃れることは出来ません。 無念・・・

最後に

returnの挙動をどうするのがいいのか、実は2通り考えたんですが、どういう方針で行けばいいのか指針がないのでつらかったです。 yield breakをまねる、という方針があったのでよかったのですが、それがなかった場合はもう一方の(実装が楽な方)を実装してしまっていたでしょうね。 たぶん、それがなかったら今回のエントリの挙動ではなく、簡単な方を実装して済ませていたと思われます。

さて、もう一つの挙動はどんなものでしょうか。 これは読者への課題にしますね!