Optionに見るコンピュテーション式のつくり方

またの名を入門コンピュテーション式(嘘

この記事は、「コンピュテーション式ってどうやって作ればいいの？」に対する自分なりの回答です。

matchのネスト

optionを返す3つの関数f, g, hがあったとします。 で、このような処理がしたいとしましょう。

let niceFunction (arg1, arg2, arg3) =
  match f arg1 with
  | Some x ->
      match g arg2 with
      | Some y ->
          match h arg3 with
          | Some z ->
              Some (x, y, z)
          | None -> None
      | None -> None
  | None -> None

この関数は、3つの関数すべてが成功したときだけ、その結果をまとめて成功として返しています。 それ以外は何もせずに失敗として返しています。

このように、「すべて成功したときだけ計算したい」という状況はよく起こります。 例えば、fがDBから何か取得する関数、gがファイルシステムからファイルを取得する関数、hがネットワークから何か取得する関数だとして、 これらすべてが成功したらそれらの情報を使って何か処理がしたい、というケースが考えられます。

これを毎回書くのはだるいですし、計算のもとになるソースが増えれば増えるほど、matchがネストしていきます。 どうにかできないでしょうか？

コードの「形」の共通部分

ここで注目してほしいのは、このコードの構造が再帰構造になっている点です。

match <expr> with
| Some <v> ->
    +----------------+
    | 全体と似た構造 |
    +----------------+
| None -> None

このように、Someの場合の処理に、全体の構造に似た形が再び現れることが分かります。 まずは、この部分をカスタマイズできるように関数の引数として渡せるようにしてみましょう。

コードの再帰構造の関数化

<expr>の部分と、Someの場合に行う処理を引数に取ればよさそうです。 また、Someの場合に行う処理では、Someが持っている値も必要になるため、関数の引数として渡すことにします。

let matchSome target procForSome =
  match target with
  | Some v -> procForSome v
  | None -> None

この関数は、procForSomeに渡す関数の中で再びmatchSome関数が呼び出されることを想定しています。 これを使うと、最初のコードはこう書けます。

let niceFunction (arg1, arg2, arg3) =
  matchSome (f arg1) (fun x ->
  matchSome (g arg2) (fun y ->
  matchSome (h arg3) (fun z ->
    Some (x, y, z)
  )))

無名関数のネストはありますが、疑似的にフラットに出来ました。 gとhの間に何か挟まってきても、

let niceFunction (arg1, arg2, arg3) =
  matchSome (f arg1) (fun x ->
  matchSome (g arg2) (fun y ->
  matchSome (hoge (arg1, arg2, arg3)) (fun w ->
  matchSome (h arg3) (fun z ->
    Some (x, y, w, z)
  ))))

なんとか対処できます。 ただ、末尾の閉じカッコはどんどん増えていきます。 どうにかならないでしょうか・・・

無名関数によるletの除去

さて、ちょっと話題を変えて、letを除去する方法を考えてみましょう。

let x = 2
let y = "aaa"
let z = [0..x]
printfn "%A" (x, y, z)

F#で変数を導入したい場合に真っ先に思い浮かぶのがletです。 しかし、他にも変数が導入できるものがあります。 関数の引数です*1。

let x = 42
printfn "%A" x

このコードを無名関数を使って書き直すと、

(fun x -> printfn "%A" x) 42

となります。 これを参考に、最初のコードを書き替えてみます。

(fun x -> (fun y -> (fun z -> printfn "%A" (x, y, z)) [0..x]) "aaa") 2

これでは読めないので、|>を使ってさらに変形します。

2      |> (fun x ->
"aaa"  |> (fun y ->
[0..x] |> (fun z ->
  printfn "%A" (x, y, z))))

2をxに入れ、"aaa"をyに入れ、[0..x]をzに入れ、本体を実行しているように見えませんか？

コンピュテーション式の導入

さて、話を元に戻しましょう。

let niceFunction (arg1, arg2, arg3) =
  matchSome (f arg1) (fun x ->
  matchSome (g arg2) (fun y ->
  matchSome (hoge (arg1, arg2, arg3)) (fun w ->
  matchSome (h arg3) (fun z ->
    Some (x, y, w, z)
  ))))

このコードの末尾部分のカッコをどうにかしたいのでした。 そして、letは無名関数で除去できる、ということを見ました。

では、無名関数をletで除去できないでしょうか・・・？ これは残念ながらできません。 ですが、コンピュテーション式を使えばlet!という構文を使うことで可能になります。 let!は、簡単にはコンピュテーションビルダーのBindメソッド呼び出しに変形されます。

builder {
  let! v = expr
  ...
}

このコードは、

builder.Bind(expr, (fun v -> ...))

このように変形されます。

ここで、matchSome関数を思い出してください。

let matchSome target procForSome =
  match target with
  | Some v -> procForSome v
  | None -> None

この関数、Bindが要求する形に似ていますね。 実は、matchSome関数は、ほとんどそのままBindとして使えます。

では、コンピュテーションビルダーを定義してみましょう。

type OptionBuilder() =
  member __.Bind(x, f) = matchSome x f
  member __.Return(x) = Some x

let option = OptionBuilder()

これを使えば、元のコード

let niceFunction (arg1, arg2, arg3) =
  matchSome (f arg1) (fun x ->
  matchSome (g arg2) (fun y ->
  matchSome (h arg3) (fun z ->
    Some (x, y, z)
  )))

は、こう書き直せます。

let niceFunction (arg1, arg2, arg3) =
  option {
    let! x = f arg1
    let! y = g arg2
    let! z = h arg3
    return (x, y, z)
  }

フラットになりました！

このように、コンピュテーション式はある種のネスト構造をフラットに(読みやすく、かつ編集しやすく)書けるようにする機能を持ちます*2。

コンピュテーション式を作るには

自分でコンピュテーション式を作ろうとする場合、その「同じような構造がネストしている」ことを発見できねばなりません。 というか順番が逆で、「同じような構造がネストしている」のがだるいからコンピュテーション式でフラットにするのであって、コンピュテーション式が作りたいからそのような構造を見つけるのではないです。

で、先人はいくつも「同じような構造がネストしている」パターンを見つけてくれており、それぞれに名前まで付けてくれています。

例えば、上で例にした'a optionを対象にしたものは、MaybeモナドやOptionモナドとして広く知られています。 コンピュテーション式を作れるようになるための近道、それは色々なモナドを理解し、そのコンピュテーション式を実際に作ってみることです。

余談

モナドさえ理解できればコンピュテーション式は作れるようになるか、というとそういうわけではありません。 コンピュテーション式はモナド以上のことができてしまうため、モナドだけわかってもすべての機能の実装はできません(し、間違った実装を提供してしまいます)。

また、全然モナドじゃないコンピュテーション式も作れます。 作れますが、それが実用的になることはそうそうないでしょう。 コンピュテーション式の基本、それはモナドです。

*1:forやmatchも変数は導入できますが、ここではこれらを使っても意味がないので無視します

*2:それだけではないんですが、基本はこれです

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 {
  yield 10
  yield 20
}

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

type ListBuilder () =
  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 cond then
    return 10
  return 20
}

とあり、cond によって

cond の値	結果
true	Some 10
false	Some 20

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

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

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

Delayの実装方法その2

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

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

let option = OptionBuilder()

option {
  if true then return 10
  printfn "hello"
  return 20
}

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

let b = option
b.Combine(
  (if true then b.Return(10) else b.Zero()),
  b.Delay(fun () -> printfn "hello"; b.Return(20)))

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

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

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

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

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

let option = OptionBuilder()

let res =
  option {
    if true then return 10
    printfn "hello"
    return 20
  }

printfn "%A" res

実行結果:

<fun:res@41>

！？！？

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

let b = option
b.Combine(
  (if true then b.Return(10) else b.Zero()),
  b.Delay(fun () -> printfn "hello"; b.Return(20)))

正しくはこうです。

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

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

Runの実装

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

let b = option
b.Run(
  b.Delay(fun () ->
    b.Combine(
      (if true then b.Return(10) else b.Zero()),
      b.Delay(fun () -> printfn "hello"; b.Return(20)))))

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

member __.Run(f) = f ()

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

いい感じのOptionBuilder

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

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

ListBuilder再考

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

let xs = list {
  if false then
    printfn "hello"
    yield 10
  yield 20
}

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

let b = list
b.Delay(fun () ->
  b.Combine(
    (if false then printfn "hello"; b.Yield(10) else b.Zero()),
    b.Delay(fun () -> b.Yield(20))))

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

let xs = list {
  yield 10
  printfn "hello"
  yield 20
}

この例では、[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 'a list =
  | []         (* ゼロ値 *)
  | (::) of 'a * 'a list

type 'a option =
  | None       (* ゼロ値 *)
  | Some of '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")>]
type Async<'T> =
    P of (AsyncParams<'T> -> FakeUnitValue)

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

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

member Zero : 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 cond1 then printfn "if1"
  if cond2 then printfn "if2"
  return "str"
}

おぉ、便利っぽい！

ZeroとCombineの罠

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

async {
  if true then
    return ()
  return "str"
}

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

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

let b = async
b.Delay(fun () ->
  b.Combine(
    (if true then 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 {
  if true then
    return "str1" (* ここにstringは置けない。unitである必要がある *)
  return "str2"
}

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

• コンピュテーション式の実装にStateを用いる
• コンピュテーション式におけるreturnとyield
• 継続を使ってOptionコンピュテーション式を実装する
• 継続渡しスタイルを使ってListコンピュテーション式を実装する
• F#のコンピュテーション式
• yieldとreturnの話

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

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

• FSharpx.ExtrasのMonad.fsのMaybeBuilder
• ExtCoreのcontrol.fsのMaybeBuilder
• Visual F# PowerToolsのUtils.fsのMaybeBuilder
• Basis.CoreのComputationExpr.fsのOptionBuilder

FSharpx.Extras

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

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

maybe {
  if true then
    return () (* ??? *)
  return 10
}

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

maybe {
  if true then
    return 10 (* compile error *)
  return 20
}

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

ExtCore

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

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

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

maybe {
  if true then
    return 10 (* compile error *)
  return 20
}

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

maybe {
  if true then
    return () (* ??? *)
  return 10
}

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

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 {
  if true then
    return ()
  return 10
}

(* Some 10 *)
option {
  if true then
    return 10
  return 20
}

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

member this.Zero() = None, Continue
member this.Combine((x: _ option, cont), rest: unit -> _ option * FlowControl) =
  match cont with
  | Break -> x, Break
  | Continue -> if x.IsSome then x, Break else rest ()

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

• コンピュテーション式の実装にStateを用いる
• コンピュテーション式におけるreturnとyield
• F#のコンピュテーション式
• yieldとreturnの話

まとめ

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

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

皆さんがコンピュテーションビルダーを書く場合で、Combine を提供したくなったときにこのエントリを思い出していただければありがたいです。 いやぁ、コンピュテーション式は楽しいなぁ。

*1:セミコロンは改行とインデントで置き換え可能

*2:一部意図的に間違っていますが、そのあたりは後述します

*3:さらに、シグネチャファイルによってただ一つのデータコンストラクタも外部には隠ぺいされている

あなたの知らないF#についての7つの事柄

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

タイトルは釣りで、今回はMicrosoft/visualfsharpリポジトリをウォッチしている中で見つけた個人的に面白かったIssueを取り上げます。

名前空間内でのprivateの意味

現状のF#では、名前空間内でprivateを使った場合に、privateっぽくない挙動を示します。

同じプロジェクト内に、M1.fs, M2.fs, M3.fsを下記の内容のように作ってください。

(* M1.fs *)
namespace NS

module private M1 =
  let x = 10

(* M2.fs *)
namespace NS

module M2 =
  let x = M1.x (* OK *)

(* M3.fs *)
namespace NS.Child

module M3 =
  let x = NS.M1.x (* OK *)

このように、名前空間内にprivateなモジュール(もしくは型)を作っても、同一アセンブリの同一名前空間以下にある型からはアクセスできるのです。 今後のバージョンでは、同一ファイルではない場合に警告になるように変更されるようです。 この挙動に依存している場合、privateではなくinternalを使うように変更しておくといいでしょう。

元ネタ: Suggestion: restrict "private" for items in namespaces to mean "private to the namespace declaration group"

未使用変数の誤検知

F#3.0からは、コンパイルオプションに--warnon:1182を付けることで未使用変数を警告扱いにできるようになっています。

extern指定したメソッドの引数に対する誤検知

extern指定したメソッドの引数を未使用変数として誤検知します。

type ControlEventHandler = delegate of int -> bool

[<DllImport("kernel32.dll")>]
extern void SetConsoleCtrlHandler(ControlEventHandler callback, bool add)
(* --warnon:1182してコンパイルすると、callbackとaddが未使用変数として検知されてしまう *)

これはバグなので、今後のリリースで修正されると思われます。 「(警告をエラー扱いにしている等の理由で)今回避したいんだ！」というときは、識別子を_で始めればOKです。

type ControlEventHandler = delegate of int -> bool

[<DllImport("kernel32.dll")>]
extern void SetConsoleCtrlHandler(ControlEventHandler _callback, bool _add)
(* --warnon:1182してコンパイルしても、_から始まる識別子は除外されるので警告にならない *)
(* ただし、FSharpLintを使っている場合"_を識別子に含めるな！"という警告を出すようになる *)

元ネタ: External function arguments flagged as unused

クエリ式での誤検知

クエリ式でも誤検知します。

(* for xの位置でxが使われていないという警告が出る *)
let res =
  query { for x in [1;2;3] do
          where (x > 2)
          select 1 }

(* 同上 *)
let res =
  query { for x in [1;2;3] do
          let y = x
          select y }

(* これは出ない *)
let res =
  query { for x in [1;2;3] do
          where (x > 2)
          select x }

元ネタ: Query expressions and --warnon:1182

プライマリコンストラクタの引数の型注釈

プライマリコンストラクタの引数に型注釈を付けないと、意図しない推論結果を引き起こします。

type ISomeInterface = interface end
type C1() = interface ISomeInterface
type C2() = interface ISomeInterface

type SomeClass<'a when 'a :> ISomeInterface> (value) =
  member x.Value : 'a = value

  (* 警告「型変数'b'は型''a'に制約されました」 *)
  member x.Method(newValue: 'b when 'b :> ISomeInterface) =
    SomeClass<'b>(newValue)

let x = SomeClass<C1>(C1()) (* OK *)
let y = x.Method(C1()) (* OK *)
let z = x.Method(C2()) (* コンパイルエラー *)

Methodに明示的に型引数を付けてみましょう。

(* コンパイルエラー「この束縛に関する1つまたは複数の明示的クラスまたは関数型の変数は、他の型に制限されているため、ジェネリック化できませんでした。」 *)
member x.Method<'b when 'b :> ISomeInterface>(newValue: 'b) =
  SomeClass<'b>(newValue)

駄目みたいです。

プライマリコンストラクタの引数には常に型注釈を付けるようにしましょう。

type SomeClass<'a when 'a :> ISomeInterface> (value: 'a) =
  member x.Value = value

  member x.Method(newValue: 'b when 'b :> ISomeInterface) =
    SomeClass<'b>(newValue)

元ネタ: Bug in the type checker with type variables

ジェネリックメソッドの制限

現状のF#では、ジェネリックメソッドは第一級の値として使えません。

module M =
  let f<'a>() = ()

type C =
  static member M<'a>() = ()

let x = M.f<int> (* OK *)
let y = C.M<int> (* コンパイルエラー「予期しない型引数です」 *)

() |> M.f<int> (* OK *)
() |> C.M<int> (* コンパイルエラー *)

元ネタ: Provided methods with static params can't be used as first-class function values

リスト式(や配列式)の型推論のコーナーケース

下記のコードのコンパイル結果は一貫性がないように見えます。

let f (xss: 'a seq seq) = ()

f [ [ 'c' ] ] (* OK *)

let charListList = [ [ 'c' ] ]
f charListList (* コンパイルエラー「型'char list list'は型'seq<seq<'a>>'と互換性がありません」 *)

F#では、リスト(や配列)の要素の型がリスト式(や配列式)の型チェックよりも前に分かっている場合、各要素をその要素型にアップキャストを試みます。 これは、継承を考慮すると仕方なかった選択のようです。

例えば、型Widgetを継承したLabelとButtonがあったとします。

let xs: Widget list = [ Label(); Button() ] (* OK *)

これは、リスト式[ Label(); Button() ]の型チェック前にこのリスト式の型がWidget listになるとわかっている(xsに型注釈が付いている)ため、リスト式の各要素はWidget型にアップキャストされます。 そのため、このコードはコンパイルが通ります。 ではこちらはどうでしょう？

let xs = [ Label(); Button() ] (* コンパイルエラー「この式に必要な型はLabelですが、ここでは次の型が指定されています Button」 *)

これは、リスト式の型チェック前に型がわかっていないので、コンパイルエラーです。

さて、これで元のコードがなぜ一貫性がないように見えたかがわかります。 元のコードを再掲します。

let f (xss: 'a seq seq) = ()

f [ [ 'c' ] ] (* OK *)

let charListList = [ [ 'c' ] ]
f charListList (* コンパイルエラー「型'char list list'は型'seq<seq<'a>>'と互換性がありません」 *)

一回目のfの呼び出しでは、引数の型が「'a seq seq」になることがわかっています。 一番外側のseqの要素の型は、'a seqになることがわかっている、ということです。 実際に渡している要素は[ 'c' ]であり、これはchar list型です。 char list型はchar seq型にアップキャスト可能(listはseqを実装している)ため、コンパイルが通るわけです。

二回目のfの呼び出しでは、リスト式ではなくいったん変数に入れたものを渡そうとしています。 charListListの型はその名前通り、char list listです。 リスト式ではないので要素型のアップキャストは行われず、'a seqという型を期待しているところにchar listがくるため、コンパイルエラーになるのです。

これを回避するためには、フレキシブル型を使います。

let f (xss: seq<#seq<'a>>) = () (* 'a #seq seq とは書けないっぽい *)

f [ [ 'c' ] ] (* OK *)

let charListList = [ [ 'c' ] ]
f charListList (* OK *)

フレキシブル型の表記(#seq<'a>)は型制約のあるジェネリック型('b when 'b :> seq<'a>)の略記法です。 これによって、seq<'a>の代わりにその派生型も許されるようになったため、char list list型の変数も渡せるようになりました。

元ネタ: Possible inconsistency in type unification

メソッド(もしくはコンストラクタ)呼び出しの特別ルール

obj(もしくは'a)を1つ取るメソッドがあり、ほかにオーバーロードの候補がない場合、コンパイルできなさそうでできるコードが書けます。

type C =
  static member M(x: obj) = ()

C.M() (* OK *)

え、引数は？と思うかもしれませんが、引数は()が渡っています。 この特別扱いルールは、

• 引数が1つのみ
• オーバーロードされてない

場合のみに有効です。 そのため、オーバーロードを追加するとこのコードは通らなくなります。

type C =
  static member M(x: obj) = ()
  static member M(x: int, y: int) = ()

C.M()   (* コンパイルエラー *)
C.M(()) (* OK *)

このルール、何か嬉しい場合があるんでしょうか・・・

元ネタ: Implicit class constructor with a single obj argument could be called without argument which will pass null as argument

まとめ

今まで知らなかった言語仕様とかに気付かされることが多いので、登録されたIssueを読んでみると面白いです。 Resolution By Designタグが付けられたIssueがまずはおススメです。

F#のクラス(の主に定義する部分)についてまとめ

この記事はF# Advent Calendar 2015の5日目の記事です。 4日目は@n_enotの「F# でTDDした話 前編？」でした。

※業務連絡。F# Advent Calendar 2015の参加者の皆さん、今年は登録順ではなく、申請順になってしまっているようなので、イベントページに登録はしたけどまだ書く日付が決まっていない方は、イベントページを編集して書きたい日に自分の名前を書いておくようにしましょう。

関数型の何かと思った？

残念、クラスベースオブジェクト指向プログラミングの話でしたー。

今までF#のクラス定義に関する機能がよくわかっていなかった(まともに使ってこなかった、といってもいい)ので、ちょっとまとめつつ勉強してみました。 基本的に、言語仕様の「8.6 Class Type Definitions」をまとめた内容になっています。 より実践的な方向から再構成しているので、仕様書よりも読みやすく意義も伝わりやすいかな、と思います*1。

クラス定義の基本

F#でのクラス定義は次のようになっています。

type 型名 =
  class
    クラス本体
  end

F#では、クラスは何もしなくてもシリアライズ可能です。 シリアライズ不可能にする場合、AutoSerializable(false)属性を与える必要があります。

class/endの省略

通常、class/endは省いて定義します。

Class属性によるclass/endの省略

Class属性をつけると、class/endは不要です。

[<Class>]
type 型名 =
  クラス本体

Classのほかに、Interface属性やStruct属性もあります。 列挙型は構文が全く違うためか、Enum属性はありません。

ただ、これから説明する方法によるclass/endの方が便利なので、Class属性は個人的にはあまり使いません。

クラス固有の要素によるclass/endの省略

下記の要素を持つ場合、class/endは不要です。

• プライマリコンストラクタ(primary constructors)
• 追加オブジェクトコンストラクタ(additional object constructors)
• 関数定義(function definitions)
• 値定義(value definitions)
• 非抽象メンバー(non-abstract members)
• 引数付きの継承宣言(inherit declarations that have arguments)

これらの詳しい説明は、それぞれの要素の説明の際に合わせてします(関数定義は引数があるかどうかだけなので、この記事では値定義としてまとめます)。 とりあえずは、「ほとんどの場合でclass/endは省略でき、コンパイルエラーになったらclass/endを書くかClass属性をつける」と覚えてしまって大丈夫です。

コンストラクタの定義

F#には、コンストラクタは次の2種類があります。

• プライマリコンストラクタ(primary constructor)
• 追加オブジェクトコンストラクタ(additional object constructor)

プライマリコンストラクタ

プライマリコンストラクタは、型名の後ろに引数リストを書くことで定義します。

type 型名 (引数リスト) =
  クラス本体

この引数リストには、識別子か、型指定した識別子しか書けません。 例えば、

type SomeClass (x: int, y) = ...

はOKですが、

type SomeClass ((x1, y1), (x2, y2)) = ...

のように、複雑なパターンは書けません(コンパイルエラーになる)。 複雑なパターンが書きたい場合は、値定義(value definition)を使います。

type SomeClass (p1, p2) =
  let (x1, y1) = p1
  let (x2, y2) = p2
  ...

クラスの本体部分に書かれたメンバー定義(追加オブジェクトコンストラクタ含む)以前の部分は、プライマリコンストラクタの本体部分とみなせます。 これらのコードはプライマリコンストラクタの呼び出し時に実行されます。 letのほかにdoも使えます。

type SomeClass () =
  let x = 10
  do printfn "%d" x

この例では、SomeClassを生成するたびに10と表示されます。 他の部分のdo束縛と違い、ここでのdoは省略できない点に注意してください。

プライマリコンストラクタの補佐としての追加オブジェクトコンストラクタ

基本的にはプライマリコンストラクタを使えばいいですが、主に2つ以上のコンストラクタが提供したい場合には追加オブジェクトコンストラクタを定義します。

例えば、intの値を2つ保持するクラスAが定義したいとします。 この場合、プライマリコンストラクタを使って

type SomeClass (x: int, y: int) =
  ...

とすることになりますが、yの方は大体のケースで0固定だ、という場合、プライマリコンストラクタ以外にコンストラクタが欲しくなります。 こういう場合に追加オブジェクトコンストラクタを使います。

type SomeClass (x: int, y: int) =
  new (x) = SomeClass(x, 0)
  ...

このように、newキーワードを使うことで追加オブジェクトコンストラクタを定義できます。 追加オブジェクトコンストラクタでは、本体の最後の式としてコンストラクタを呼び出す必要があります*2。

コンストラクタの呼び出し後に何か副作用のあるような処理がしたい場合、thenを使います。

type SomeClass (x: int, y: int) =
  new (x) =
    printfn "プライマリコンストラクタを呼び出します。"
    SomeClass(x, 0)
    then
      printfn "プライマリコンストラクタが呼び出されました。"

それ以外の役割の追加オブジェクトコンストラクタ

継承が絡んでくるので、まず先に継承についてを説明します。

継承

継承はinheritキーワードを使い、値定義よりも前に宣言します。

type SomeBaseClass (x: int) = do ()
type SomeSubClass () =
  inherit SomeBaseClass(10)

  let someValue = 20

クラスがプライマリコンストラクタを持つ場合、継承するクラス名に続けてそのクラスのコンストラクタに渡す引数を書きます。 上の例では、SomeBaseClassのコンストラクタを引数10で呼び出しています。 値定義など、継承宣言よりも後ろに書く必要のある変数等は使えないので注意してください。

また、継承宣言を省略すると、暗黙的にobjが継承されます。 明示的にobjを継承した場合とbase(基底クラスのメンバーへの参照)の挙動が微妙に異なりますが、気にする場面は出てこないでしょう。

基底クラスの異なるコンストラクタが呼びたい場合に使う追加オブジェクトコンストラクタ

プライマリコンストラクタを持つ場合、すべてのコンストラクタは継承宣言で同時に呼び出される単一の基底クラスのコンストラクタが呼び出されます。 これでは困ったことになる場合があります。 例えば、基底クラスがシリアル化コンストラクタを提供しており、派生クラスもシリアル化可能にしたい独自の状態を持っている場合などです。 この場合、派生クラスは通常のコンストラクタとシリアル化コンストラクタで別々の基底クラスのコンストラクタを呼ぶ必要があります。

type ParseException (row: int, col: int) =
  inherit FormatException("failed to parse")

  new (info: SerializationInfo, context: StreamingContext) =
    (* ここで基底クラスのシリアル化コンストラクタを呼びたいけど呼べない！ *)

プライマリコンストラクタを提供せずに、すべてを追加オブジェクトコンストラクタにすることで、これが実現できます。 まず、プライマリコンストラクタを提供しない場合、inherit宣言に引数リストを付けれなくなります。

type ParseException =
  inherit FormatException
  ...

次に、プライマリコンストラクタが無くなったことによって保持できなくなったrowとcolをvalとしてフィールド化します。 valは値定義のletと比べられることも多いですが、letはあくまでプライマリコンストラクタに付属するものに対して、valはメンバー(フィールド)です。 そのため、プライマリコンストラクタを定義しないとletは使えません(今回の例ではletは使えない、ということです)。 letはフィールドになるとは限りませんが、valは常にフィールドになりますし、値定義ではなくメンバー定義のため、すべての値定義(do含む)よりも後ろに書く必要がある点に注意してください。 valは宣言と同時に初期値を持たせることはできませんが、(DefaultValue属性の付かない)valは、そのすべてをすべてのコンストラクタで初期化することが求められます*3。 これは、プライマリコンストラクタを持つ場合はDefaultValue属性の付かないvalは定義できないことを意味します*4。

type ParseException =
  inherit FormatException

  val Row: int
  val Col: int
  ...

valは既定ではpublicなので、先頭を大文字にしてみました。

さて、本題の追加オブジェクトコンストラクタです。 これまでは追加オブジェクトコンストラクタでは他のコンストラクタを呼び出していました(delegate construction)が、基底クラスを呼び出すためには明示的構築(explicit construction)を行う必要があります。

type ParseException =
  inherit FormatException

  val Row: int
  val Col: int

  new (row, col) =
    { inherit FormatException("failed to parse"); Row = row; Col = col }

  new (info: SerializationInfo, context: StreamingContext) =
    let r = info.GetInt32("Row")
    let c = info.GetInt32("Col")
    (* F#ではセミコロンは改行に置き換え可能 *)
    { inherit FormatException(info, context)
      Row = r
      Col = c }

  (* ISerializableの実装は後で *)

このように、追加オブジェクトコンストラクタを使うことで、基底クラスの異なるコンストラクタが呼び出せるようになります。 ちなみに、オブジェクト構築後に副作用のある処理を実行したい場合は、thenを使います。

インターフェイスの実装

F#には空のインターフェイスの指定か、インターフェイスの明示的実装しかありません。

空のインターフェイスの指定

空のインターフェイスの指定は

type SomeClass () =
  interface IEmptyInterface

のように書きます。

インターフェイスの明示的実装

インターフェイスを実装するには、クラス名に続けてwithを書き、その後にインターフェイスの持つメンバーの実装を書きます。

type ParseException =
  inherit FormatException

  val Row: int
  val Col: int

  new (row, col) =
    { inherit FormatException("failed to parse"); Row = row; Col = col }

  new (info: SerializationInfo, context: StreamingContext) =
    let r = info.GetInt32("Row")
    let c = info.GetInt32("Col")
    { inherit FormatException(info, context); Row = r; Col = c }

  interface ISerializable with
    member x.GetObjectData(info, context) =
      base.GetObjectData(info, context)
      info.AddValue("Row", x.Row)
      info.AddValue("Col", x.Col)

インターフェイスの実装では、すでにインターフェイスで型が明示されるため、すべてのメンバーで型を指定する必要がないのも特徴です。

可視性

F#では至る所で不変が既定になっているため、可視性が設定できるものはpublicが既定と思ってかまいません(一部の例外の方を覚えればよい)。 もちろん、可視性はカスタマイズ可能ですので、可視性を狭めることは可能です。

また、追加オブジェクトコンストラクタの項でも書きましたが、letはプライマリコンストラクタの一部であるため、letには可視性を設定できません。 コンストラクタ内で作ったローカル変数くらいに思っておいた方が無難でしょう。

クラス自身の可視性

クラス自身の可視性は、typeとクラス名の間に書きます。

(* 型をinternalに制限 *)
type internal SomeClass () = do ()

プライマリコンストラクタの可視性

プライマリコンストラクタの可視性は、クラス名と(の間に書きます。

(* 型はpublicのまま、プライマリコンストラクタをinternalに制限 *)
type SomeClass internal () = do ()

クラス自身とプライマリコンストラクタの両方に可視性を設定すると、一行に2つの可視性が書かれることになります。

(* 型はinternalに、プライマリコンストラクタはprivateに制限 *)
type internal SomeClass private () = do ()

追加オブジェクトコンストラクタの可視性

追加オブジェクトコンストラクタの可視性は、newと(の間に書きます。

type SomeClass (x: int) =
  new internal () = SomeClass(0)

自己参照

プライマリコンストラクタでの自己参照

プライマリコンストラクタで自分自身(いわゆるthis)のメンバーを使いたい場合、プライマリコンストラクタの引数リストの閉じかっこと=の間にasを使って書きます。

(* 名前はthisでもxでもなんでもいい(ここではself) *)
type SomeClass () as self =
  ...

ただ、これを実際に使ったことがあるのは、型プロバイダーを実装する時くらいでしょうか・・・

追加オブジェクトコンストラクタでの自己参照

追加オブジェクトコンストラクタで自分自身のメンバーを使いたい場合、引数リストの閉じかっこと=の間にasを使って書きます。

type SomeClass (x: int) =
  (* 名前はthisでもxでもなんでもいい(ここではself) *)
  new () as self = ...

こちらは実際に使ったことはないかもしれません・・・

Tips

有効な値を持たないクラス定義

Phantom Typeで使うだけの、タグとして型が必要な場合があります。 その場合は値が不要ですので、値を持たない型で十分です。

type Hoge = class end

と定義すると、F#ではデフォルトでnullが無効なため、有効な値がない型が簡単に作れます*5。

書けていないトピック

• 抽象クラスの定義
• 構造体の定義
• インターフェイスの定義
• 列挙型の定義(不要かも)
• メンバーの定義

いつか書く。

まとめ

オブジェクト指向プログラミング的な機能をあまり使ってこなかったため、今回初めて知ったことがかなりありました。 この記事だけを読むといろいろ面倒に見えますが、実際に書いてみると、よくあるケースを簡潔に書けるようにするためにいろいろと考えられていることがわかりました。 それでも、レコードや判別共用体を使った方が楽な面も多いですから、クラスはF#では基本的には脇役になってしまいますが、知っておくといつか役に立つことがあるかもしれません。 ということで今回はこの辺で。

*1:仕様書の一部分、書いてる人が意義を分かっていなさそうな部分がある・・・

*2:たまに、プライマリコンストラクタを呼び出す必要がある、としている説明を見かけますが、誤りです。ほかの追加オブジェクトコンストラクタでもいいですし、自分自身を呼び出しても構いません

*3:そうしない場合はコンパイルエラー

*4:さらに、mutableも必要になってきます。というか、mutableもつけないと常にゼロ値を表すフィールドになってしまって、意味がないので禁止されているのだと思います。エラーメッセージだけからはわかりにくいですが・・・

*5:Unchecked.defaultofは考えないものとします

ChalkTalk CLR – 動的コード生成技術（式木・IL等）に行ってきた

centerclr.doorkeeper.jp

直前で定員を増やしてもらえたので、参加できました。

会自体について

内容は主にILの話と式木の話で、ディスカッションというよりは講義に近い感じでした。 個人的にはディスカッション寄りの会を期待していたのですが、知識レベルにばらつきがあったのと、初めての取り組みということで仕方ないのかな、と。 次回以降で、もしディスカッション寄りの会をやりたいなら、「この本を読了しており内容についてもある程度理解していること」とかにした方がより濃い内容のディスカッションができると思います。 聴講のみの席も用意すると、「ディスカッションに参加するのは怖いけど話は聞きたい」って人も参加できますし*1。

最初にKPTをして今回の方向性を決めよう、という試みは面白くはありましたが、会の最初にKも何もないので、KPTにとらわれずに「知りたいこと」「議論したいこと」みたいな分類から始めればいいんじゃないかなぁ、と思いました。 ポジションペーパーを用意してもらって、軽く自己紹介でもいい気はします。

会の内容について

IL

ILについては、ILの存在意義的な話から始まり、C#のコードがどのようなILに落ちるのかをIL Spyを使って見たり、出力されたILがどのように実行されるのかを図にして追ったりする内容でした。 「DebugでコンパイルしてもReleaseでコンパイルしても吐かれるILにさほど差は出ない」と説明があったときには、「C#で構造が大きく変わることは見たことないけど、(nopは置いといても)発行されるILはそれなりに変わるよ！」とか、「F#の場合は構造も結構がらりと変わるよ！」って突っ込みを入れようかと思いましたが自重しました。 最初のKPTでそういう会じゃないというのはわかったので、それを考えると最初のKPTはある程度効果があったと思います。

それと、最初は OpCodes を参考にすればいいでしょうが、ある程度ちゃんとやるなら Standard ECMA-335 は手元に置いておきましょう。

ILはどうやって学べばいいのか？という話の流れで、ILをどうやってデバッグすればいいのか、という話になったので、「生成するIL(が生成するdll)にデバッグ情報埋め込めるから、それすればデバッグできるよ」という話と、「IL Support extension使えばC#(やVBやF#)とILをいい感じに統合できるしデバッグもできるよ」という話をしました。 が、後者のデモ(実際にILをデバッグする例)のせいで前者がちゃんと伝わっていない気がします。こっちもデモすればよかったんですが、手持ちがF#のコード例のみだったので自重したのがいけなかったか・・・ 詳細については、メタプログラミング.NET を熟読しましょう。5.4.2です。Kindle版は安いのでおすすめです。

式木

式木については、木構造の話からはじめ、C#の式木は今や式だけじゃなくて文も扱うよ、という話などをしました。 思うに、式木の使い方っていくつかに分類されて、それぞれで目的がバラバラだからわかりにくいんじゃないでしょうか？

• 式木を別の構造に移しかえる(最終的にはCompileしてデリゲートに落として.NET上で実行)
• 式木を別の構造に移しかえた上で何らかの直列化をする(最終的にはSQLなどになって何らかのミドルウェア上で実行など)
• 式木を走査して情報を取り出す(最終的には.NET上のオブジェクト)

LINQ to EntitiesなどでRDBを使う例は上記の2番目に、メタ情報を取得するために式木を使うことでコードの変更に強くなるよ、という例は上記の3番目に当たるわけです。 ここら辺をひとまとめにして「式木の使い道」で説明しちゃうと分かりにくいのかな、と思ったり。 このあたりはちょっとした図を作るといいのかなぁ・・・

Excel方眼紙について

最初に行ったKPTに、「Excel方眼紙を駆逐する」というものがありました。 それを受けて、メッセージを実行時にExcelから取ってくる仕組みを式木を使って実装した、という話があったんですが、ここは声を大にして言いたい。

それ、Excelから脱却してないじゃん！むしろExcelの活用の話じゃん！！！

はい。 まぁ、そもそも「Excel方眼紙の駆逐」が何を指しているのかあいまいだ、という問題があります。

• Excel方眼紙なんて不要だから開発現場から全撤廃するべきだ
• Excel方眼紙を納品しなければならないのは仕方ないけど、プログラマに使わせるのは非効率だからすべてのExcel方眼紙は別の何かから生成されるべきだ
• Excel方眼紙を納品しなければならないのは仕方ないけど、プログラマに使わせるのは非効率だからプログラマがExcel方眼紙に触れなくてもいい環境を作るべきだ
• Excel方眼紙を使うのは仕方ないけど、それとプログラムの対応付けを手でやるのは非効率だから自動化すべきだ

ざっと思いついただけでもこんな感じで、上に行くほど駆逐の意味合いが強く、下に行くほど弱いです。 このなかで、メッセージを実行時にExcelから取ってくる仕組みは一番下であり、これより弱いものはちょっと思い浮かびません。 と言うわけで、Excel方眼紙を駆逐する、というテーマについてであれば、もっと強いものがほしいと思うのでした。

個人的な取り組みとしては、1ソース(外部DSL)から複数の成果物を出力する方法でプログラマがExcel方眼紙を触る必要性をある程度軽減できないかな、ということでTableDslというものを作っています(色々あって停滞中)。 社内ツールになりますが、メッセージ一覧も同様の考え方でプログラマがExcel方眼紙を触らなくていいようにしているもの(こっちは内部DSL)も作ってます。 汎用的な仕組みとしては、F# TypeProviderを使ってExcel方眼紙を扱うライブラリを作っている(いた？)のですが、これは今風に書き直したいところです。 これらは2番目の方向性ですね。

3番目の方向性としては、これまた社内ツールとして結合テストの実行を支援するツールがあります。 これは4番目の方向性と似ていますが、「対応付け」でどちらかがどちらかを強く意識する必要がなくなる点で異なります。対応付けを2段階にし、途中にツールがくることでより明確に役割が分離されます。

2, 3, 4番目の方向性で使うのは、ExcelファイルのIOができるライブラリになります。

• NPOI
• EPPlus
• ClosedXml

などが候補になります。COMオートメーション？知らない子ですね。

Excel VBA

ある意味Excel方眼紙よりも面倒なのが、Excel VBAです。 1セル1文字とか無茶なことをしていない場合、Excel方眼紙をプログラム上で扱うのはそれほど面倒ではないですが、Excel VBAを駆使して作られたシステムはヤバいです。 こいつらを置き換えるためには、例えば下記のようなものが使えます。

• Excel-DNA *2
• FCell

FCellのデモ動画は強烈なので見てみるといいでしょう。

いいですか、駆逐すべきはExcel方眼紙よりもExcel VBAです。

まとめ

• IL Support布教できてよかった
• 動的生成されたILのデバッグのデモすればよかった
• Excel方眼紙よりもExcel VBAを駆逐したい

*1:一応補足しておきますが、そういう形式で開催しろ、と言っているわけではない

*2:いつの間にかCodePlexからGithubに移動してた・・・

シャドーイングとイミュータブルプログラミング

シャドーイングのない言語と、イミュータブル中心のプログラミング(以下イミュータブルプログラミング)の相性って悪いのでは？と思ったのでブログに残しておきます。

シャドーイングとは

既存の変数と同名の変数を定義して、そのスコープで既存の変数にアクセスできなくする機能です。 例えば、F#ではシャドーイングができるので、

let f x =
  if x % 2 = 0 then
    (* 引数のxをシャドーイング *)
    let x = -1
    printf "%d, " x
  (* スコープが抜けたので、引数のxを表示 *)
  printfn "%d" x

f 10    (* => -1, 10 *)
f 11    (* => 11 *)

となります。

シャドーイングのない言語、例えばC#では同じことはできないので、別の名前を付けるか、再代入で回避することになります*1。

public void F(int x)
{
    if (x % 2 == 0)
    {
        var otherX = -1;
        Console.Write("{0}, ", otherX);
    }
    Console.WriteLine(x);
}

シャドーイングの使い道

シャドーイングの使い道としては、例えば以下のようなものがあります。

• ミュータブルな変数の範囲の制限
• イミュータブルプログラミングでの状態変数の受け渡し

ミュータブルな変数の範囲の制限

F#にはミュータブルな変数があります。 ですが、一般的なF#プログラマは極力ミュータブルな変数を使いません。 どうしてもミュータブルな変数が使いたくなったとしても、ある時点以降では再代入が行われないと分かっているなら、ミュータブルな変数をシャドーイングすることで、以降で誤って再代入できないことをコンパイラに保証させることができます。

let mutable x = 10
(* xに再代入する場合があるコード *)
...

(* ここからはxに再代入しない *)
let x = x
...

イミュータブルプログラミングでの状態変数の受け渡し

イミュータブルプログラミングしていると、ある変数をクローンして一部分を書き換えた値を作り出すというコードが結構出てきます。 このような場合にシャドーイングを使えば、更新前のいらなくなった変数にアクセスできなくなるため安心してコーディングできます。

let f newKey cache =
  let cache = cache.Clone(key = newKey)
  g cache (* このcacheはシャドーイングされた方のキャッシュ *)

しかし、シャドーイングのない言語ではこれはできません。 簡単に取れる回避策としては、イミュータブルプログラミングを一部捨てて、引数に再代入するか、新しい名前を付けるかです。

public SomethingResultType F(Cache cache, Key newKey)
{
    var newCache = cache.Clone(key: newKey);
    return G(newCache);
}

これは新しい名前を付けた場合です。 しかしこの場合、

public SomethingResultType F(Cache cache, Key newKey)
{
    var newCache = cache.Clone(key: newKey);
    return G(cache);
}

のように間違えて元の変数を使ってしまえます。 というか、仕事で実際に使ってしまいました。 シャドーイングさえあればこんなミスはしませんでした*2し、同じものを表すのに別の名前を付けなければならないのはそもそも違和感があります。

もう一方の「再代入」で回避する方法は、一部とはいえイミュータブルプログラミングを捨てることになるので、他の回避策がある場合に取りたくはありません。 あまりイミュータブルとミュータブルを行ったり来たりしたくないですしね。

ということで、シャドーイングのない言語はイミュータブルプログラミングと相性が悪いのではないでしょうか？*3 シャドーイングがない言語では、イミュータブルプログラミングを全面的に採用するのはあきらめたほうがいいな、というのが現時点での考えです。

*1:ただし、そうそうないが、既存の変数と新しい変数の型が違う場合は再代入では対応できない場合もある

*2:typoしてシャドーイングしたつもりができていなかった、ということもあり得ますが・・・

*3:Stateモナド等を使って状態変数を隠すというのも考えられなくはないですが、シグネチャ壊しちゃうのでいろいろ面倒

再帰関数のスタックオーバーフローを倒す話 その3

連載目次

• 再帰関数のスタックオーバーフローを倒す話 その1
  • CPSとCPS変換の話
• 再帰関数のスタックオーバーフローを倒す話 その1.5
  • F#での「末尾」についての話
• 再帰関数のスタックオーバーフローを倒す話 その2
  • .NETにおける末尾最適化の方法についての話
• 再帰関数のスタックオーバーフローを倒す話 その2.5
  • 継続モナドと、F#の残念さの話
• 再帰関数のスタックオーバーフローを倒す話 その3 ← 今回
  • すべてをあきらめて再帰をwhileに書き直す方法の話

はじめに

再帰関数のスタックオーバーフローを倒す話 その2の続きで、最後です。 前回はCPS変換じゃスタックオーバーフローが回避できない場合もあるよという話でした。 前提知識は、F#と、スタックについてです。 これまではCPSの話を中心にしてきましたが、この記事ではCPSの知識とか不要です。

F#で再帰関数によってスタックオーバーフローが起きる場合に、それを回避する方法としてはその1で見たように、CPS変換するというのがあります。 しかし、この方法はその2で見たように完全ではありません。

そのほかの方法としては、CPSではない形で末尾再帰にする方法が考えられます。 CPSでない形で末尾再帰にすれば、tail.ILプレフィックスによる方法ではなく、ループに変換されることによる最適化が効くようになるので、スタックオーバーフローを防げます。 しかし、CPS変換はほとんど機械的に末尾再帰に書き換え可能でしたが、CPS変換を使わずに末尾再帰に書き換えるのは常人にはつらいものがあります。

どうしようもないので、最後の手段です。 コンパイラは単純な再帰しかループに変換してくれませんが、人間なら・・・人間なら再帰をループに変換できるのでは？

ということで、再帰関数のスタックオーバーフローを倒すために、再帰関数をループで書き直してしまいましょう！ イミュータブル？関数型言語？なにそれおいしいの？？？

再帰をwhileで書き換える

では、どうやって再帰をwhileで書き換えればいいのでしょうか？ 簡単な例から見ていきましょう。

末尾再帰関数をwhileで書き換える

末尾再帰関数は簡単にwhileに書き換え可能です。

let fact n =
  let rec fact' acc = function
  | 0 -> acc
  | n -> fact (acc * n) (n - 1)

  fact' 1 n 

アキュムレータ変数を使った階乗の計算をする関数です。 これをwhileで書き換えると例えばこうなります。

let fact n =
  let mutable n = n   (* 書き換え可能変数で引数をシャドーイング *)
  let mutable acc = 1 (* fact' 1 nに相当。accの初期値を設定 *)
  while n <> 0 do     (* ループ判定には、元の再帰関数の終了条件の否定を書く *)
    acc <- acc * n    (* fact (acc * n) (n - 1)のうち、計算の主体をaccに再代入 *)
    n <- n - 1        (* fact (acc * n) (n - 1)のうち、終了条件に関わる部分をnに再代入 *)
  acc                 (* ループを抜けた際にaccに結果が入っている *)

手順は大体以下の通りです。

1. 終了条件判定のための変数をmutableで作る
2. 結果格納用の変数をmutableで作り、初期値を入れておく
3. 再帰関数の終了条件の否定をwhileのループ判定にする
   • ループを続行する条件なので、終了条件の否定になる
   • 複数の終了条件がある場合は、&&でつなぐ(一つでも再帰の終了条件を満たせば脱出 → 一つでもループの続行条件を破れば脱出)
4. whileの中には再帰部分を書く
   1. 再帰で計算していた部分をコピーして、結果格納用の変数に結果を再代入
   2. 終了条件判定の更新をしていた部分をコピーして、終了条件判定のための変数に結果を再代入

このように無事書き換えられましたが、F#ではこのような末尾再帰関数をわざわざループに書き換える必要性はないです。 だってこの程度ならコンパイラがやってくれますからね。

呼び出しスタックが必要な再帰をwhileで書き換える

末尾再帰ではない再帰は、簡単にはループに変換できません。 なぜなら、再帰呼び出しから戻ってきた後に何らかの計算が必要なため、 どこかにそれを計算するための情報を取っておかないといけないからです。

例えば、末尾再帰ではない階乗を計算する関数を考えてみます。

let rec fact n =
  match n with
  | 0 -> 1
  | _ -> n * fact (n - 1)

この関数はnが0ではないときに再帰後に計算が必要なので、末尾再帰版の手順ではwhileに書き換え不可能です。 この種の関数をwhileで書き換えるにはどうしたらいいでしょうか？*1

まずは、末尾呼び出しではない再帰関数がどのようにして実現されているかを見てみましょう。

末尾呼び出しではない再帰関数について

末尾呼び出しではない再帰関数は、呼び出し元の情報(環境)を呼び出しスタックとして保持することで、 再帰呼び出しから戻ってきた後でもその後の処理を実行できるようにしています。

let rec fact n =
  match n with
  | 0 -> 1
  | _ -> n * fact (n - 1)

この場合、fact 2を呼び出すと、まず呼び出しスタックに1つ環境が積まれます。

+----------------+
| fact { n = 2 } |
+----------------+

nが0ではないのでn * fact (n - 1)のブランチが実行されます。 ここでfactを再帰的に呼び出していますが、この呼び出しが終わった後にその結果とこの環境でのnを乗算する必要がありますが、 その情報を呼び出しスタックに積んでおくことでそれを可能にしています。

fact呼び出しがあるため、スタックに新しい環境が積まれます。

+----------------+
| fact { n = 1 } |
+----------------+
| fact { n = 2 } |
+----------------+

またもやn * fact (n - 1)のブランチが実行されるので、呼び出しスタックに新しい環境が積まれます。

+----------------+
| fact { n = 0 } |
+----------------+
| fact { n = 1 } |
+----------------+
| fact { n = 2 } |
+----------------+

nが0の場合、1のブランチが実行されます。 こちらのブランチでは再帰呼び出しはしていないので、新たな環境が呼び出しスタックに積まれることはありません。

逆に、関数呼び出しが完了するため呼び出しスタックが消費されます。

+----------------+
| fact { n = 1 } |
+----------------+
| fact { n = 2 } |
+----------------+

この状態でfact 0の呼び出し元だったn * (fact 0)が実行されます。 nは呼び出しスタックに積まれた先頭の環境を参照すると1と分かるので、fact 0の結果と乗算し、結果は1になります。 乗算後に必要な計算はないため、呼び出しスタックが消費されます。

+----------------+
| fact { n = 2 } |
+----------------+

同様に、2 * 1が実行され、結果は2になります。 最終的にfact 2の結果として2が得られました。

このように、再帰関数は呼び出しスタックを使って実現されています*2。 この呼び出しスタックにはサイズの上限があり、それを超えてしまった際に発生するのがスタックオーバーフローエラーです。

呼び出しスタックをプログラマが管理する

上で見た呼び出しスタックは、実行環境が用意してくれるスタックのため、ユーザからは扱えません。 これをプログラマが管理することで、再帰呼び出しと同じ動作をwhileとして再現できます。

let fact n =
  (* 自前で呼び出しスタック相当のものを用意 *)
  let stack = System.Collections.Generic.Stack<int>()
  let mutable n = n
  (* 処理すべきデータをすべてスタックに積む *)
  while n <> 0 do
    stack.Push(n)
    n <- n - 1
  let mutable res = 1 // 初期値
  (* スタックがなくなるまで処理する *)
  while stack.Count <> 0 do
    res <- res * stack.Pop() // 処理本体
  res

この書き換えの戦略では、処理すべきデータをスタックに積むフェーズと、 スタックからデータを取っていって実際に処理するフェーズに分けています。 この戦略は処理すべきデータの総量が簡単にわかる場合のみに使える方法です。

最初に処理すべきデータの総量は分からないことが多いので、 スタックからデータを取ってはスタックに積む必要があるかどうかを確認していく、 という戦略を取ることが多くなるでしょう。

let fact n =
  (* 自前で呼び出しスタック相当のものを用意 *)
  let stack = System.Collections.Generic.Stack<int>()
  stack.Push(n)
  let mutable res = 1 // 初期値
  (* スタックが空になるまでループする *)
  while stack.Count <> 0 do
    (* Popした結果によって処理を分岐 *)
    match stack.Pop() with
    | 0 -> () (* スタックに積まれた値が0ならこれ以上処理はしない *)
    | nonZero ->
        (* スタックに積まれた値が0以外なら、その値-1をスタックに積み、 結果を更新 *)
        stack.Push(nonZero - 1)
        res <- res * nonZero // 処理本体
  res

この戦略では、ループ中で分岐によって新しい値をスタックにpushするかしないかが分かれています。 このように、スタックに積まれている値によっては新しい別の値をスタックに積むという戦略をとると、 たいていの再帰はwhileに変換できます。

相互再帰をwhileで書き換える

式木の変換などは、相互再帰によって実現されている場合があります。 相互再帰を直接whileに変換するのは難しいので、まずは相互再帰を自己再帰に書き換えてやるのがいいでしょう。

let isEven n =
  let rec isEven' n =
    match n with
    | 0 -> true
    | nonZero -> isOdd (nonZero - 1)
  and isOdd n =
    match n with
    | 0 -> false
    | nonZero -> isEven' (nonZero - 1)

  isEven' n

相互再帰の自己再帰への書き換えには、関数を表す判別共用体を導入します。

type RecFunc =
  | CallIsEven of int
  | CallIsOdd of int

let isEven n =
  let rec loop = function
  | CallIsEven n ->
      match n with
      | 0 -> true  (* isEven'を0で呼び出した場合に相当 *)
      | nonZero -> loop (CallIsOdd (nonZero - 1))  (* isEven'を0以外で呼び出した場合に相当 *)
  | CallIsOdd n ->
      match n with
      | 0 -> false (* isOddを0で呼び出した場合に相当 *)
      | nonZero -> loop (CallIsEven (nonZero - 1)) (* isOddを0以外で呼び出した場合に相当 *)

  loop (CallIsEven n) (* 最初はisEven'を呼び出していたので、CallIsEvenを渡す *)

あとは、この関数をこれまでの知識を元にしてwhileに書き換えます。 今回は単純な例なので、スタックを自分で管理せずに書き換え可能です。

type RecFunc =
  | CallIsEven of int
  | CallIsOdd of int

let isEven n =
  let mutable data = CallIsEven n (* 最初はisEven'を呼び出していたので、CallIsEvenを渡す *)
  let mutable res = true
  let mutable isCont = true
  while isCont do
    match data with
      (* isEven'を0で呼び出した場合に相当 *)
      (* 0は偶数なので、resにtrueを入れ、isContをfalseにして次のループに入らないようにする *)
    | CallIsEven 0 ->
        res <- true
        isCont <- false
      (* isEven'を0以外で呼び出した場合に相当 *)
      (* 次のループで処理するdataを新たに作るだけ *)
    | CallIsEven n ->
        data <- CallIsOdd (n - 1)
      (* isOddを0で呼び出した場合に相当 *)
      (* 0は奇数ではないので、resにfalseを入れ、isContをfalseにして次のループに入らないようにする *)
    | CallIsOdd 0 ->
        res <- false
        isCont <- false
      (* isOddを0以外で呼び出した場合に相当 *)
      (* 次のループで処理するdataを新たに作るだけ *)
    | CallIsOdd n ->
        data <- CallIsEven (n - 1)
  res

相互再帰を自己再帰に書き換えてしまえば、今まで見た方法を使ってwhileに書き換え可能です。

まとめ

結局、F#でスタックオーバーフローを完全に解決するためには、

• CPSではない形の末尾再帰に書き換える
• それが難しい場合、whileで書き換える

という悲しい結果に終わりました。 さらに、継続モナドをコンピュテーション式で実装するとスタックオーバーフローしてしまう、という悲しい現実もわかりました。

このような悲しい現実と向き合って実装した(実装している)のがFSharp.Quotations.Compilerです。 stackとwhileによって、F#の式木をILに変換しています。

この一連のシリーズは、このライブラリを作るにあたって得た知見(の大きく分けて片方の部分)を公開するために書きました。 もう片方の部分(IL生成周りの知見)についても、やる気が起きたらまとめようと思います。

とりあえず、疲れたのでこの辺で・・・

*1:もちろんこの例では簡単に末尾再帰関数に書き換え可能なので、末尾再帰関数にしてしまうのが一番手っ取り早いでしょう。しかし、簡単には末尾再帰に書き換えれないものも多いので、その場合にどうすればいいかを考えていきます。

*2:「再帰関数は」と書きましたが、再帰ではない単なる関数呼び出しも同様です。