2015-04-24

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

連載目次

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

はじめに

再帰関数のスタックオーバーフローを倒す話その1ではCPS変換について、再帰関数のスタックオーバーフローを倒す話その1.5では末尾呼び出しについて、再帰関数のスタックオーバーフローを倒す話その2では2種類の末尾呼び出しの最適化について話しました。

今回は、継続渡しスタイルがつらい人*1をモナドで救う話をします。最初にネタバレすると、結局F#では救われないことになりますが。まぁ、これはあくまでその1のおまけとして読んでください。

前提知識は、上記記事(特にその1)を理解していることです。

継続渡しスタイルつらい話

階乗を求める関数factを考えましょう。

let rec fact n =
  if n = 0I then 1I
  else
    n * (fact (n - 1I))

これを使って、nの階乗とmの階乗の和を求める関数は、このように書けます。

let f n m =
  let factN = fact n
  let factM = fact m
  factN + factM

このfactを継続渡しスタイルにしたfactCpsを考えてみます。

let rec factCps n cont =
  if n = 0I then 1I |> cont
  else
    factCps (n - 1I) (fun pre ->
    n * pre |> cont)

これを使って、同様にnの階乗とmの階乗の和を求める関数を書くと、こうなります。

let fCps n m cont =
  factCps n (fun factN ->
  factCps m (fun factM ->
  factN + factM |> cont))

元の普通のF#コードに比べると、このコードをすらっと読み下せる人は格段に減ります。このコードをすらっと書ける人となるとさらに減ります。

このあたりが継続渡しスタイルのつらいところです。

コンピュテーション式が世界を救う

階乗を求める関数を使った2つのコードをちょっと並べてみましょう。

(* 普通のやつ *)
let f n m =
  let factN = fact n
  let factM = fact m
  factN + factM

(* CPS版 *)
let fCps n m cont =
  factCps n (fun factN ->
  factCps m (fun factM ->
  factN + factM |> cont))

その1でもみましたけど、letのネスト*2がfunのネストになっています。コンピュテーション式の変換規則を知っている人であれば、これはそのままlet!の変換規則に見えるでしょう。

そうです、継続渡しスタイルはコンピュテーション式の後ろに隠すことができるのです！

継続もにゃど

type ContinuationBuilder() =
  member __.Return(x) = (fun cont -> x |> cont)
  member __.Bind(cpsFun, rest) = (fun cont -> cpsFun (fun x -> rest x cont))

let cont = ContinuationBuilder()

さぁ準備は整いました！ contコンピュテーション式を使ってfCpsを書き直してみます。

(* contコンピュテーション式版 *)
let fCps n m = cont {
  let! factN = factCps n
  let! factM = factCps m
  return factN + factM
}

これなら、継続渡しスタイルの関数でも使える気がしませんか？

注目すべき点はいくつかあります。まずは、fCpsから引数が一つ減ったように見えるようになりました。実際は減っていないんですが、contコンピュテーション式を使う限り、隠された引数を意識する必要はありません。

次に、factCpsは最後の引数として継続を受け取るはずなのに、あたかもそんな引数ないかのように呼び出しているように見えます。これがcontコンピュテーション式の力で、継続を引き回す処理はContinuationBuilderのBindの中に隠蔽されています。

let! factN = factCps n
...

は

cont.Bind(factCps n, fun factN -> ...)

のように展開されます。

member __.Bind(cpsFun, rest) = (fun cont -> cpsFun (fun x -> rest x cont))

Bindの定義はこのようになっており、factCps nの部分はcpsFunが受け取ります。このcpsFunの部分にfactCps nを埋め込んでみると・・・

factCps n (fun factN -> ...)

と、どこかで見たことのある形が現れますね。このように、継続渡しスタイルの関数に継続を渡す部分は、Bindが裏でやってくれるのです。

これで継続渡しスタイルもこわくない！

factCpsをcontコンピュテーション式で書き直す

ここまで来たらfactCpsも書き直してしまいましょう。

let rec factCps n cont =
  if n = 0I then 1I |> cont
  else
    factCps (n - 1I) (fun pre ->
    n * pre |> cont)

これがこうです！

let rec factCps n = cont {
  if n = 0I then
    return 1I
  else
    let! pre = factCps (n - 1I)
    return n * pre
}

だいぶ普通のコードっぽく読めるようになったのではないでしょうか？しかし、これには罠があります。

contコンピュテーション式の罠

このfactCpsに50000Iとid関数を渡して起動すると、スタックオーバーフローが起きます。なぜこのようなことが起こるのでしょうか？ factCpsのコンピュテーション式を展開してみましょう。

let rec factCps n =
  let b = cont
  if n = 0I then
    b.Return(1I)
  else
    b.Bind(factCps (n - 1I), (fun pre -> b.Return(n * pre)))

あれれ、factCpsの再帰呼び出し部分が末尾じゃなくなってます！そらスタックオーバーフロー起きるわー。 Bindにinlineを付けてみましょう。

Bindのinline化

ContinuationBuilderを修正します。

type ContinuationBuilder() =
  member __.Return(x) = (fun cont -> x |> cont)
  member inline __.Bind(cpsFun, rest) = (fun cont -> cpsFun (fun x -> rest x cont))

let cont = ContinuationBuilder()

これで、factCpsは以下のように展開されるようになります。

let rec factCps n =
  let b = cont
  if n = 0I then
    b.Return(1I)
  else
    let f = factCps (n - 1I)
    (fun cont -> f (fun x -> b.Return(n * x) cont))

factCpsが！ラムダ式の！外にいる！！！これはもうどうしようもありませんね。

まとめ

ということで、継続渡しスタイルのつらみをコンピュテーション式で軽減する話でした。そして、継続渡しスタイルの末尾再帰関数をコンピュテーション式を使って書き直すと、末尾再帰にならずに死ぬ、という話もしました。みなさん、注意しましょう。

*1:読めない、書けない

*2:letがネストしているように見えないかもしれませんが、let式のネストになっています

2015-04-22

ProjectScaffoldを使ってみた

最近公開したF#の式木の実行器であるFSharp.Quotations.Compilerですが、これを作るためにProjectScaffoldを使ってみたのでその知見の共有です。

ProjectScaffoldとは

ProjectScaffoldは、F#のプロジェクトを作る際の「足場」を用意してくれるツールです。このツールを使ってプロジェクトを作ると、

Paketを使った外部ライブラリの管理
FAKEを使ったビルドやデプロイ
FSharp.Formattingを使ったドキュメントの作成

と言ったことが簡単に行えるようになります。また、F#でデファクトスタンダードなディレクトリ構成や設定になるので色々と考えなくていい*1ので楽ができます。

ProjectScaffoldについては、yukitosさんがF# Project Scaffoldを使ってプロジェクトを作成するという素晴らしい記事を書いてくれているので、まずはそれを参考にするのがいいでしょう。

ProjectScaffoldで気を付けなければいけないこと

で、ここからが本題で、実際に使ってみて分かったことなどです。

READMEとリリースノートが固定化されている

プロジェクトが作られた直後のREADMEとリリースノートは、ProjectScaffoldのものそのままになっています。プロジェクトを作る際に起動するコマンドの中で、少なくともREADMEのひな形を作るのに十分な情報を渡しているにもかかわらず、作ってくれません。

そのまま公開すると残念なことになるので注意しましょう。

ライセンスが固定化されている

これは結構な罠で、選択肢もなしにUnlicenseというライセンスファイルが付いてきます。注意しましょう。

ちなみに、FQCではCC0を選んだため、別にUnlicenseのままでもそんなに変わらない気もしますが、それでもライセンスはある程度選択式にしてほしいところです。

.NET Frameworkのバージョンが固定化されている

これも選択肢はなく、.NET Framework 4.0、Target FSharp Core Version 4.3というちょっと古いバージョンで固定されています。

場合によっては上げたり下げたりを手動でやる必要があり、ちょっと面倒です。

Paketの扱い

ProjectScaffoldを使うと、Paketというパッケージ管理ツールを使うことになります。これはNuGetのラッパー+αなツールなんですが、 (Paketを使わずに)NuGetを使うとビルドが壊れます。しかも、壊れたのが分かるのはFAKE側でビルドしたときで、 Visual Studio上でビルドしている限り分かりません(し、git cleanなどをしないとFAKE側で成功するのでタチが悪いです)。

ProjectScaffoldを使う場合、NuGetを直接使うのはやめましょう。 VS上から行える「NuGet参照の追加」も、便利ですがやめましょう。外部のライブラリを使う際は、面倒でもコマンドプロンプトを立ち上げ、 paket.exeコマンドをたたいて追加するようにします。

ちなみにこのpaket.exeですが、どうやらpaket.bootstrapper.exeが最新版を拾ってくるようになっているようです。なので、もし.paketフォルダ内になければ、build.cmdを叩きましょう。そうすれば落ちてきます。ネットワークにつながっていない場合は・・・つながるところでやりましょう。

FsUnitとの相性が悪い

ProjectScaffoldはデフォルトでNUnit2.6.4を使うのですが、これが何やらFsUnit1.3.0.1と相性が悪いようです。 FsUnitを使いたい場合は一旦NUnitとNUnit.Runnersを削除し、バージョンを指定したうえでもう一度導入してからFsUnitを導入しましょう。

.paket\paket.exe remove nuget NUnit
.paket\paket.exe remove nuget NUnit.Runners
.paket\paket.exe add nuget NUnit version 2.6.3 -i
.paket\paket.exe add nuget NUnit.Runners version 2.6.3 -i
.paket\paket.exe add nuget FsUnit -i

ここで、-iオプションを使っているので、プロジェクト毎にインストールするかどうか聞かれます。 Enterキーを押さなくてもnかyを押すだけで進むので注意してください*2。

FAKEの扱い

ProjectScaffoldを使うと、FAKEというビルドツールを使うことになります。デフォルトで用意されているターゲットに不満を感じたのですが、詳細は忘れました。たしか、ターゲット間の依存の設定が不十分で、あるターゲットを単独で実行したら失敗した、とかそんな感じだったと思います。

また、Paketと同じくVisual Studioとの連携は全くありませんので、こちら側で色々なことをやり過ぎるのはお勧めしません。 MSBuildでできることはMSBuildでやった方がいいと思います。

ドキュメントのリリース

デフォルトで用意されているReleaseDocsターゲットを使えば、ドキュメントをGitHub Pagesとして公開してくれます。この時に、tempディレクトリにgh-pagesというディレクトリを作り、そこにgh-pagesブランチをチェックアウトする、という方法なので、プロジェクトのルートディレクトリを汚さないという利点があります。しかし、これを知らないと「あれ？公開処理っぽいの走ったのにリポジトリに変更がない？」と疑問に思うかもしれないので、別ディレクトリで処理が行われる、というのは知っておくといいでしょう。ルートディレクトリでも、git remote updateするなりすればちゃんと落ちてきます。

追記: 別ディレクトリにcloneしてくるので、globalのGitの設定が取られてきます。ので、リポジトリ別の設定が完全に無視されてしまいます。これによって、会社のアカウントでドキュメントがコミットされてしまうなどの事故が起こり得ます。

まとめ？

色々言いましたが、便利は便利なので、 GitHubでF#の何かを作って公開したい、と考えている人は積極的に使っていくといいでしょう。 GitHub以外のサポートは弱いので、GitHubは嫌だ、という人は改造するなりPR投げるなりするといいでしょう。 Git以外のバージョン管理のサポートはないので、Gitは嫌だ、という人は以下略。

*1:例えば、上述のツールを使った際の.gitignoreを用意してくれたりします

*2:projectオプションを使うこともできます

2015-04-20

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

F# IL

連載目次

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

はじめに

再帰関数のスタックオーバーフローを倒す話その1の続きです。前回はCPS変換することでスタックオーバーフローが回避できるよやったー！という話でした。今回は、CPS変換じゃスタックオーバーフロー回避できない場合もあるよ、という話をします*1。前提知識は、その1の記事を理解していることと、ILがなんとなくわかることです。その1.5に対する深い理解は不要ですが、読んでいるに越したことはありません。

CPS変換のおさらい

非末尾再帰の関数を末尾再帰化できる、というのがCPS変換でした。そして、末尾呼び出しの最適化によってスタックが食いつぶされなくなるので、スタックオーバーフローが起きなくなるようにできる、というものでした。

2種類の末尾呼び出しの最適化

さて、実はF#では末尾呼び出しの最適化は2つのパターンがあります。一つ目はジャンプ命令への書き換えで、もう一つはtail.プレフィックスの付与です。

ジャンプ命令への書き換え

ジャンプ命令への書き換えは、呼び出しをbr系のIL命令に書き換えてしまうものです。例えば、

let rec fact acc n =
  if n = 0 then acc
  else fact (acc * n) (n - 1)

このようなアキュムレータ変数を使った末尾再帰関数をコンパイルすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.1          // 1番目の引数(n)のload
IL_0002: brtrue.s IL_0006 // loadした値が0以外(0: false, 0以外: true)ならIL_0006にジャンプ

IL_0004: ldarg.0          // 0番目の引数(acc)のload
IL_0005: ret              // loadした値を返して関数終了

IL_0006: ldarg.0          // 0番目の引数(acc)のload
IL_0007: ldarg.1          // 1番目の引数(n)のload
IL_0008: mul              // loadした2つの値を乗算(acc * n)・・・(1)
IL_0009: ldarg.1          // 1番目の引数(n)のload
IL_000a: ldc.i4.1         // 定数1をload
IL_000b: sub              // loadした2つの値を減算(n - 1)・・・(2)
IL_000c: starg.s n        // (2)の結果を引数nにstore
IL_000e: starg.s acc      // (1)の結果を引数accにstore
IL_0010: br.s IL_0000     // 無条件でIL_0000にジャンプ

このコードには、call系の命令がないことが分かります。その代わりに、最後に無条件で先頭にジャンプしており(br.s IL_0000)、これが元のコードだと再帰呼び出し部分に相当します。

ILでは分かりにくい、という人向けに、上記ILをF#風言語で表現してみました。

let fact acc n =
  while n <> 0 do
    let tmp = acc * n
    n <- n - 1
    acc <- tmp
  acc

このように、末尾再帰呼び出しをジャンプ命令に置き換えることで、ループと等価になりました*2。

自分自身を末尾で呼び出す再帰関数*3の場合、関数から戻ってきた後にすることがないということは、(引数の状態を更新してから)関数の先頭にジャンプしてもいいと言うことです。

tail.プレフィックスの付与

tail.プレフィックスの付与は、末尾呼び出しされているcall系の呼び出し命令にtail.というプレフィックスを付けることで、 JIT コンパイラの最適化によってスタックフレームを消費しないようにしてもらうものです。例えば、

let rec fact n cont =
  if n = 0 then 1 |> cont
  else fact (n - 1) (fun pre -> pre * n |> cont)

このような継続渡しスタイルの関数を「末尾呼び出しの生成」オプションをオンにしてコンパイルすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.0          // 0番目の引数(n)をload
IL_0002: brtrue.s IL_000e // loadした値が0以外(0: false, 0以外: true)ならIL_000eにジャンプ

IL_0004: ldarg.1          // 1番目の引数(cont)をload・・・(1)
IL_0005: ldc.i4.1         // 定数1をload・・・(2)
IL_0006: tail.            
// (1)でloadした関数値に(2)でloadした値を渡して実行
IL_0008: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000d: ret              // 実行した結果を返して関数終了

IL_000e: ldarg.0          // 0番目の引数(n)をload
IL_000f: ldc.i4.1         // 定数1をload
IL_0010: sub              // loadした2つの値を減算(n - 1)・・・(3)
IL_0011: ldarg.0          // 0番目の引数(n)をload・・・(4)
IL_0012: ldarg.1          // 1番目の引数(cont)をload・・・(5)
// (4)でloadした値と(5)でloadした値を渡してfact@22オブジェクトを生成
IL_0013: newobj instance void class Sample/fact@22<!!a>::.ctor(int32, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !0>)
IL_0018: starg.s cont     // 生成したオブジェクトを引数contにstore
IL_001a: starg.s n        // (3)の結果を引数nにstore
IL_001c: br.s IL_0000     // 無条件でIL_0000にジャンプ

基本的な構造は同じですが、少し複雑になっています。アキュムレータ変数による末尾再帰関数の例と同様にF#風の言語で表現してみるとこうなります。

let fact n cont =
  while <> 0 do
    let tmp = n - 1
    cont <- fact@22(n, cont)
    n <- tmp
  cont 1

ループの中でcontをネストさせていき、関数の最後でcontに1を渡していることが分かります。再帰部分の処理は、fact@22というクラス*4に行ってしまい、このコードだけでは読み取れなくなりました。 fact@22というクラスをまずはF#風の言語で表現してみます。

type fact@22<'a> (n: int, cont: int -> 'a) =
  inherit FSharpFunc<int, 'a>()

  override __.Invoke(pre) = cont (pre * n)

このように、本体の処理はInvokeメソッド内に移動しています。 InvokeメソッドのILはこのようになっています。

IL_0000: nop
IL_0001: ldarg.0 // 0番目の引数(this)をload
// loadしたオブジェクト(this)のフィールドcontをload・・・(1)
IL_0002: ldfld class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !0> class Sample/fact@22<!a>::cont
IL_0007: ldarg.1 // 1番目の引数(pre)をload
IL_0008: ldarg.0 // 0番目の引数(this)をload
// loadしたオブジェクト(this)のフィールドnをload
IL_0009: ldfld int32 class Sample/fact@22<!a>::n
IL_000e: mul     // loadした2つの値を乗算(pre * this.n)
IL_000f: tail.
// (1)でloadした関数値(this.cont)に乗算結果を渡して実行
IL_0011: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !a>::Invoke(!0)
IL_0016: ret     // 実行した結果を返して関数終了

さて、ここでfact本体のIL_0006とInvokeのIL_000fを見てみましょう。 tail.というILが発行されていることが分かります。

このILが発行された後に続くcall系の呼び出しは、 JIT コンパイラによって現在のスタックフレームを再利用*5するようにして実行されるようになります。

2つの最適化の違い

なぜ末尾呼び出しの最適化に2種類の方法があるのでしょうか？それは、両者の性質が大きく異なるためです。

まず、前者のジャンプ命令に変換する方法ですが、 br系の命令はメソッド内の移動にしか使えません。そのため、メソッドをまたぐようなジャンプはできず、CPSで現れるようなラムダ式を表すクラスのメソッドへのジャンプはできません。

それに対して、tail.プレフィックスを付与する方法は、 call系のメソッドが末尾で呼び出されていれば別のクラスのメソッド呼び出しであろうが有効です。しかし、tail.プレフィックスはJIT コンパイラ任せなため、本当に呼び出しが最適化されるかどうかの保証をF#の処理系レベルで担保することができません*6。

また、その1.5でみましたが、コンストラクタ呼び出し(newobj)は末尾呼び出しの最適化対象ではありません*7。そのため、ループごとにコンストラクタ呼び出しが走ることになります。これは、F#ではtail.プレフィックスを用いた最適化よりもジャンプ命令に変換する最適化の方が効率が良いことを意味します。

まとめると、

最適化方法	適用可能場所	処理系での保証
ジャンプ命令での置き換え	自己末尾再帰	できる
`tail.`プレフィックスの付与	末尾再帰一般	できない

となります。

tail.プレフィックスでスタックオーバーフローになる場合

tail.プレフィックスが付いているコードであっても、スタックオーバーフローを起こす場合があります。まだ原因はわかっていないのですが、

(式木の変換のような)それなりに大きい再帰関数をCPS変換
64bitのIIS上で実行

というような状況で、リビルド後の初回のアタッチでスタックオーバーフローが起きました。 2回目以降のアタッチではスタックオーバーフローが起きませんし、小さくて単純な再帰関数をCPS変換してもオーバーフローは起きませんでした。

また、32bitのIISでは試していませんが、一般的に32bit環境ではスタックフレームのサイズが64bit環境よりも小さくなるため、スタックオーバーフローを起こしにくくなる可能性はあります。

ということで、特定の条件下ではCPS変換によってスタックオーバーフローを防ぐことができない場合もあるため、 F#においてはCPS変換したからと言って完全に安全とは言い切れない、という話でした。「特定の条件」がまだ定かではないので、調査は継続しますが、今のところIISでホストしない場合には再現しませんので、非Webアプリであれば問題ないかもしれません。次回の「その3」がおそらく最後で、ではどうやってスタックオーバーフローを倒せばいいか、の予定です。

*1:その1で「その2はコンピュテーション式の話になる予定です」と書きましたが、その話は2.5で使用と思います

*2:ちなみに、コンパイラの最適化オプションがオンでもオフでも、ジャンプ命令への書き換えは行われるようです

*3:以降、自己末尾再帰と呼ぶことにします

*4:F#のラムダ式はクラスとして実現されています

*5:現在のスタックフレームを破棄して新しいスタックフレームをそこに作る

*6:ジャンプ命令への書き換えはコンパイル時の最適化であり、tail.プレフィックスの付与はランタイム時の最適化と言えるでしょう

*7:実際に、IL_0013の直前にはtail.プレフィックスが付いていません

2015-04-15

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

F# IL

連載目次

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

はじめに

前回は、CPS変換によって再帰関数のスタックオーバーフローを回避する方法を紹介しました。その中で、「末尾呼び出し」という言葉が出てきましたが、詳細については触れませんでした。この記事では、本題からはちょっと脇道に逸れて、F#においては何が「末尾」で何が最適化の対象となる「呼び出し」なのかを説明します。

前提知識として、上記記事を理解していることと、一部についてはILがなんとなくわかることです。大部分はILについて知らなくても読めるはずです。

末尾

再帰関数のスタックオーバーフローを倒す話その1 では、末尾の説明でこのようなプログラムを扱い、

let example x =
  if f1 x then f2 x
          else 10 + f3 x

f1, f2, f3のうち、f2のみが末尾呼び出しされていると説明しました。

これは間違ってはいませんが、 F#で「末尾」とみなされる位置、みなされない位置というのは自明ではありません。そこで、F#で「末尾」とみなされる位置、みなされない位置について掘り下げてみていきます。

ちなみに、ここで調べた結果はあくまで現在の実装について述べたものであり、仕様として末尾が明示されているわけではありませんので、将来変更される可能性はあります。

調べ方

F#の仕様書の Expressionsの章に出てくる式について、関数を呼び出した際にtail.ILプレフィックスが付くかどうかを調べます。ちなみにこれは、VS2013 / F#3.1.2で調査した結果であり、過去バージョンや将来のバージョンでは結果が変わる可能性がある点に注意してください。

(* これらの関数が定義されている前提 *)
let f x y = x + y
let g x = f x 1
let h = g

F#での末尾一覧

blockで囲まれた式の末尾

let ``block`` () = (h 2)

blockは、(と)で囲まれた式で、囲まれた中の式の末尾は末尾です。

begin-endで囲まれた式の末尾

let ``begin-end`` () = begin h 2 end

begin-endは、beginとendで囲まれた式で、囲まれた中の式の末尾は末尾です。

delayedの`lazy`に続く式の末尾

let ``delayed`` () = lazy (h 2)

delayedはlazyキーワードで始まる式で、lazyの後ろの式の末尾は末尾です。

functionの本体部分の式の末尾

let ``function`` () = List.map (fun x -> h x)

functionはfunキーワードで始まる式で、本体部分の式の末尾は末尾です。

matching functionの各本体部分の式の末尾

let ``matching function`` () = List.map (function 1 -> h 0 | x -> h x)

matching functionはfunctionキーワードで始まる式で、各本体部分の式の末尾は末尾です。

sequential executionの後ろ側の式の末尾

let ``sequential execution`` () = ignore (h 1); h2

sequential executionは;もしくは改行で区切られた式の並びで、後ろ側の式の末尾は末尾です。

matchの各分岐の式の末尾

let ``match`` x = match x with 1 -> h 0 | x -> h x

matchはmatchキーワードで始まる式で、各分岐の式の末尾は末尾です。

conditionalの`then`の式の末尾と`else`の式の末尾

let ``conditional`` cond = if cond then h 1 else h 2

conditionalはifキーワードで始まる式で、thenの式の末尾とelseの式の末尾は末尾です。

ただし、elseのないconditionalの場合は、thenの式の末尾だとしても末尾にはならないようです。

[<MethodImpl(MethodImplOptions.NoInlining)>]
let uf x = h x |> ignore

let ``conditional 2`` cond = if cond then uf 1

この関数を最適化あり、末尾呼び出しの生成ありでビルドすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.0
IL_0002: brfalse.s IL_000c

IL_0004: ldc.i4.1
IL_0005: call void Sample::uf(int32)
IL_000a: nop
IL_000b: ret

IL_000c: ret

tail.が付いていません。

末尾っぽいが末尾ではないもの

assignment

let ``assignment`` () =
  let mutable x = 1
  x <- h 2

当然と言えば当然ですが、h 2の結果をxに代入する必要があるため、末尾ではありません。

tuple

let ``tuple`` () = (h 1, h 2)

System.Tupleのコンストラクタ呼び出しが隠れているため、末尾ではありません。このように書き換えるとわかりやすいでしょう。

let ``tuple`` () = System.Tuple.Create(h 1, h 2)

try/with

let ``try/with`` () = try h 1 with _ -> h 2

例外処理ブロックを抜けるためにはILレベルではleaveが必要なため、 tryやwithの中の式は末尾ではありません。

try/finally

[<MethodImpl(MethodImplOptions.NoInlining)>]
let uf x = h x |> ignore

let ``try/finally`` () = try h 1 finally uf 2

finallyブロックを抜けるためにはILレベルではendfinallyが必要なため、 finallyの中の式は末尾ではありません。

determinstic disposal

let ``determinstic disposal`` () =
  use x = { new IDisposable with member __.Dispose() = () }
  h 2

useはtry/finalyが隠れていますので、これも末尾ではありません。

例えば上のコードは、以下のようなコードに書き換え可能です。

let ``determinstic disposal`` () =
  let x = { new IDisposable with member __.Dispose() = () }
  let mutable result = 0
  try
    result <- h 2
  finally
    if x != null then
      x.Dispose()
  result

最適化される呼び出しとされない呼び出し

ここまでで「末尾」は分かりました。では、F#において、末尾呼び出し最適化の対象となる「呼び出し」をきちんと理解していると言えるでしょうか？

ここでは、F#における「末尾呼び出し最適化によって最適化される呼び出し」について掘り下げてみていきます。

ここで調べた結果もあくまで現在の実装について述べたものであり、仕様として最適化される呼び出しが明示されているわけではありませんので、将来変更される可能性はあります。

最適化される呼び出し

関数呼び出し

f x

関数呼び出しが末尾の位置にある場合、その呼び出しは最適化されます。これが最適化されなかったら困りますよね。

メソッド呼び出し

x.M(y)

メソッド呼び出しが末尾の位置にある場合、その呼び出しは最適化されます。 F#での関数はメソッドとして実装されているので、関数呼び出しが最適化されるのであればこちらが最適化されない理由はないでしょう。

関数値の起動

let g = f
g x

関数を直接呼び出さず、(部分適用などを行って)値として扱う場合、内部ではFSharpFunc<'T, 'U>型として表現されます*1。

このような場合でも、末尾の位置で関数値を起動している場合、その呼び出しは最適化されます。安心して部分適用できますね。

演算子

x + y

演算子をユーザ定義している場合、それは関数やメソッドで実装することになるため、末尾の位置で演算子を適用している場合はその呼び出しは最適化されます。

最適化されない呼び出し

コンストラクタ呼び出し

C(x)

コンストラクタの呼び出しが末尾の位置にあっても、その呼び出しは最適化されません。コンストラクタの呼び出しはnewobjというILが発行されるのですが、このILに対してtail.プレフィックスは付けれないのです。そのため、コンストラクタの呼び出しが絡むと必ずスタックが消費されることになります。 F#ではコンストラクタの呼び出しがされることが分かりにくい部分が幾つかあるので、これは罠になる場合があります。

コンストラクタ内でのコンストラクタ呼び出し

type C (res: int) =
  new (acc: int, n: int) =
    if n = 0 then C(acc)
    else C(acc * n, n - 1)

  member __.Result = res

コンストラクタ内で他の(自分もしくは親の)コンストラクタを呼び出す場合、newobjではなくcallvirtなどのcall系のILが発行されます。しかし、これもtail.プレフィックスは付かないようです。 IL的にはここにtail.プレフィックスを付けても問題ないようなので、もしかすると将来この挙動は変わるかもしれません(し、変わらないかもしれません)。

*1:このような関数値のツールチップを表示させると、括弧で囲まれています

2015-04-14

Scalaのnull/Nothing/Nil/Noneはやりすぎなのか？

Scala

Twitterしてたら目に入ったので軽く。

f:id:bleis-tift:20150414225326p:plain
Javaにおけるnull。これまでとこれから

この後のスライドで、

Scalaにおける「何もないもの」の分類はやり過ぎ感はある

と言われているんですが、ある程度は誤解に基づく意見だよなぁこれは、ということを言っておこうかなと。

Scalaについて

日本では説明が不要なくらいScalaって有名になってると思うんですが一応。 ScalaはJVMの上で動作する、(クラス指向の)オブジェクト指向プログラミングと関数型プログラミングを融合させた言語です。そして、Scalaのコア機能はどちらかというとオブジェクト指向プログラミング寄りです。オブジェクト指向プログラミングをベースに、関数型の色々なものを実現している感じです*1。

オブジェクト指向プログラミング的な機能として真っ先に思いつくのは何でしょうか？割と上位の方に、「継承」とか「型階層」とか来るんじゃないでしょうか？ Scalaは、継承とか型階層といったものと、関数型的なものを良い感じに融合させています。

そして、ScalaはJavaとの親和性をそれなりに考えて作られています。 Scalaの機能が豊富なので、どうしても親和性を犠牲にしなければならないけなかった部分もありますが、ある程度はJavaの諸々に融和させることに成功しているように思います。

Scalaにおける「何もない」を表すものたち?

Scalaで汎用的に「何もない」を表すために使えるものはいくつかあります。これが混乱の元になっている例をいくつか見たことがありますが、その多くはScalaの「何もない」を表すものを本来よりも多く考えてしまうことが原因になっているように思えます。

上の資料もその一つで、以下のものを「何もない」を表すものとして挙げています。

null
Nothing
Nil
None

これらを「何もない」を表すものとして一緒くたにするのは間違っていると言い切ることはできませんが、やめた方がいいでしょう。

Scalaにおける「何もない」を表すものたち

`null`と`None`

「何もない」を表すものとして考えるべきは、通常この2つだけです。

null
None

nullは「Javaとの親和性」の要求から来ており、Noneは関数型から来ています。使い分けの指針は簡単、「基本的にはNone(というかOption)を使い、Javaとの境界ではnullも考慮する」です。

ScalaではIntなどの数値もオブジェクトとして扱えますが、これらはAnyValという型を継承しています。そして、JavaでのObjectに相当する型として、AnyRefがあり、このAnyValとAnyRefの共通の親としてAny型があります。

nullはAnyRefという型を継承している型の変数には代入できますが、AnyValを継承したInt型の変数には代入できません。しかし、Option型はAnyValを継承していようがAnyRefを継承していようが使えるため、無理をしてnullを使う理由はScalaではありません*2。

その他勘違いされやすいけど違うものたち

`()`

「何もない」ではなく「1つしかない」を表すUnit型というのもあります。 Booleanでさえ2つあるのに、1つしかなくていったい何に使うんだ・・・と思いますか？であれば、nullだって実は1つしかないですよね。

nullも()も1つか値がありませんが、nullがAnyRefを継承したどんな型の値としても使えるのに対して、 ()はUnit型の値としてしか使えません。

・・・ますます何のためにあるのか分からなくなるかもしれませんが、簡単です。これは、JavaやC++やC#で言うところのvoidと同じような使い方をします。 JavaやC++やC#のvoid型は値を持っていませんが、なぜ持っていないのでしょうか？

たぶん歴史的な経緯があるんでしょうけど、多相性*3を入れるなら、 voidも他の型と同じように使えた方が嬉しいのです。にもかかわらず、これらの言語はvoidを特別扱いしています。 voidが他の型と同じように値を持ち、returnで返すものがあったなら共通化できたにも関わらず、そうなっていないため残念なことになっている例はたくさんあります*4。

Scalaではそうなっておらず、「値に意味がないこと」をUnit型の()という唯一の値で表すことで、特別扱いを不要にしているのです。 0bitの情報と考えていいでしょう。情報量ゼロ。

`Nothing`

さて次はNothingです。これは id:kmizu さんのブログに詳しいです。

scala.Nothingは何のためにあるのか

簡単にまとめると、

例外を投げる式の型
空のコレクションの要素型

として使います。最初のうちはそうそう明示することがない型ですし、一般的なコーディングでの「何もない」を表す型ではありません。

「何もない」をコード上で表すためにnullやNoneと言った値を使ったのとは違い、Nothingは値すらないのです。これをnullやNoneとひとくくりに表すのは混乱の元となるだけですから、やめましょう。 Nothingは型を合わせるためだけに使う、と思っておけばいいはずです。

`Nil`

最後にNilです。が、他のものがある程度汎用的で広い範囲を相手にしていたのに対して、これはとても狭い範囲のものを相手にします。これは単に「空のリスト」を表すオブジェクトです。歴史的経緯によって(主にRubyなどを知っている層からすると)紛らわしい名前になっていますが、そこは間違えて使ってもScalaは静的型付き言語なので、コンパイラさんが教えてくれます。

空のリストを「値がないこと一般」を表すように使うこともできますが、そんな設計はScalaをはじめ、多くの言語ではしないでしょう。わざわざひとまとめにする必要はありません。

余談:`object`

あと、スライドではNil型、None型としていましたが、 Scala言語の文脈ではこれらは型ではなく(シングルトン)オブジェクトです。「型」とは言わないほうがいい気がします。

追記:

@bleis val a: None.type = None とかできる(Nilも同様)ので、Noneが型であることは一応間違いではないですね。確かに一般的に"None型"って言い方はあまりしないし、あのスライドの作者がそのあたり変に勘違いしてそうなのは同意ですが
— Kenji Yoshida (@xuwei_k) 2015, 4月 14

すっかり忘れていましたが、型を取ることはできますね。

まとめ

Scalaでコード上で「何もないもの」を表したい場合は基本的にはNoneを使う。他の言語を知っていると紛らわしく思える名前が出てきても、それらは別物なので気にしない。コンパイラを頼れば問題ない。

こんなところで。

*1:F#もオブジェクト指向プログラミングと関数型プログラミングできますが、F#は関数型に軸を置き、両者を融合させるのではなくある程度独立したものとして扱っています

*2:とここでは断言していますが、もちろんパフォーマンスが重大な問題になるような場合には使うこともあるでしょう。が、そういうのはあくまで例外です。基本はOptionを使います

*3:ジェネリックやテンプレート

*4:C#で言うならSystem.FuncとSystem.Actionの2系統のデリゲート型など

2015-03-12

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

再帰関数のスタックオーバーフローを倒す話を何回かに分けてします。

連載目次

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

はじめに

継続渡しスタイルもしくは継続渡し形式(Continuation Passing Style、以降CPS)という言葉を聞いたことがあるでしょうか。今日はCPSの話をします。前提知識は、F#のみです。

継続とは

CPSの前に、まずは継続の話です。継続と言っても、継続的インテグレーションとか継続的デリバリとはまったく、これっぽっちも関係ありませんのでそういう話題を期待した人は回れ右。これらの文脈では継続は「繰り返し」とかそんな風な意味を含んでいますが、今回扱う継続は「続き」とかそんな意味ととらえてください。

続きったって何の続きだ、となるわけですが、ざっくり説明すると、

「プログラムのある瞬間を考えたときに、その瞬間より後に実行される処理」

が継続です。

プログラムのデバッグでブレークポイントを貼って処理をブレークしたときに、「そのあとに実行される処理」ってあるじゃないですか。あれをプログラミングの対象にしてしまおう、というような話だと思ってください。

let x = f 42 (* ここでブレークして、fから戻ってきた状態(fは実行済み) *)
printfn "%d" x

コメントに書いたような状態だと思ってください。このときに、継続は

+---------+
| let x = | f 42
|         +------+
| printfn "%d" x |
+----------------+

この枠で囲われた部分です。 =の左側が計算されてからその結果が右側の変数xに設定されるので、let x =の部分も継続に含めています。

さて、これをプログラミングの対象にするにはどうすればいいでしょう？

継続を無名関数で表す

一つの方法として、プログラムを変形して継続を無名関数で表す、というのがあります。やってみましょう。

f 42 |> (fun x ->
printfn "%d" x)

上のコードとこのコードが同じ動作をすることは分かるでしょうか。

先ほどはletの一部分が継続に含まれていたので、プログラミングの対象に出来なさそうでした。それに対して、このコードでは先ほどの例と同じ継続は

          +-----------+
  f 42 |> | (fun x -> |
+---------+           |
| printfn "%d" x)     |
+---------------------+

この枠で囲われた部分です(|>演算子は使わないこともできるので含めていません)。これなら、この関数自体をプログラミングの対象に出来ますね！

(* もはや値としての関数でしかない *)
let cont = (fun x -> printfn "%d" x)

これだけだとありがたみがさっぱりですが、継続は関数として表せる、ということがわかりました。

無名関数でletを代用する

先ほどの変形によって、letが消えたのに気づいたでしょうか？ letによって導入していた変数は、継続を表す無名関数の引数に変わりました。 letを無名関数で表すことは後で重要になってくるので、もう少し詳しく見てみましょう。

このようなプログラムがあったとします。

let x = f 42
let y = g x
let z = h y
printfn "%A" (x, y, z)

これをletを使わずに無名関数だけで書いてみます。

f 42 |> (fun x ->
g x |> (fun y ->
h y |> (fun z ->
printfn "%A" (x, y, z) )))

f 42より後ろを表す継続はf 42の戻り値をxとして引数で受け取ります。そして、g xより後ろを表す継続はg xの戻り値をyとして引数で受け取ります。 h yより以下略。

このように、継続を起動した(継続を表す関数を呼び出した)側の結果は、引数として受け取り、その継続の中で使えます。

継続渡しスタイル(CPS)

fとgとhがそれぞれこのような関数だったとしましょう。

let f x = x / 2    // int -> int (intを受け取ってintを返す関数)
let g x = x + 10   // 同上
let h x = string x // int -> string (intを受け取ってstringを返す関数)

これを元にして、各関数が「自身の処理をした後の継続cont*1」を受け取れるようにしてみます。

let fCont x cont = x / 2 |> cont    // int -> (int -> 'a) -> 'a (intと「intを受け取って何か('a)を返す関数」を受け取って何か('a)を返す関数)
                                    // 元の関数での戻り値は、第二引数で渡される関数の引数になっている
let gCont x cont = x + 10 |> cont   // 同上
let hCont x cont = string x |> cont // int -> (string -> 'a) -> 'a (intと「stringを受け取って何か('a)を返す関数」を受け取って何か('a)を返す関数)
                                    // 元の関数での戻り値は、第二引数で渡される関数の引数になっている

このように、「自身の処理をした後の継続」を受け取る関数のことを、「継続渡しスタイルの関数」と言います。

元の関数では結果はそのまま呼び出し元に返していましたが、このバージョンではcontに結果を渡しています。 contは「自身を処理した後の継続」ですから、それに結果を渡すことによって、contの中で結果が使えるようにするためです。

fContはどうやって使えばいいでしょうか？ fであれば、例えばこのように使っていました。

let res = f 10
...

fContはこのように使います。

fCont 10 (fun res ->
...)

「無名関数でletを代用する」で見たような書き方になっていますね。「無名関数でletを代用する」では、|>演算子を使って順番を入れ替えていましたが、継続渡しスタイルの関数を使う場合は不要です。

このように、継続渡しスタイルの関数を使って継続を渡すプログラミングスタイルが、「継続渡しスタイル(CPS)」です。

fCont 42 (fun x ->
gCont x (fun y ->
hCont y (fun z ->
printfn "%A" (x, y, z) )))

ここからは継続が関数として表せると何が嬉しいかを説明するための準備となることを説明します。

末尾呼び出し

末尾呼び出しというのは、関数を呼び出した後に結果を戻す以外にすることがないような関数呼び出しのことを言います*2。さて、ではf1, f2, f3の中で末尾呼び出しされている関数はどれでしょうか？

let example x =
  if f1 x then f2 x
          else 10 + f3 x

答えは、f2だけです。

f1が末尾呼び出しじゃないというのは、f1を呼び出した後にthen節かelse節を実行する必要があることから分かります。

f2の後にelseがあるように思えるかもしれませんが、then節とelse節は二者択一であり、then節が選ばれたときにはelse節は実行されません。 then節ではf2を呼び出した後は何もすることなくその結果を戻すだけなので、f2は末尾呼び出しです。

f3の呼び出しは、その結果を使って10と加算するという処理がf3から戻ってきたときに必要です。そのため、f3は末尾呼び出しではありません。

何が「末尾」になるのかは今回は横道なので深入りはしませんが、別の機会に(F#については)まとめようと思います。

末尾呼び出しの最適化

末尾呼び出しは「関数から戻ってきた後に結果を戻す以外にすることがないような関数呼び出し」でした。何もすることがないのなら、関数呼び出しじゃなくて、単なるジャンプ命令に置き換えてしまえばスタックを消費しなくなっていいよね！というのが末尾呼び出しの最適化です*3。

これが嬉しいのは、例えば再帰関数が末尾呼び出しになっている場合です*4。このような再帰を末尾再帰と言ったりします。末尾呼び出しが最適化されないと、再帰の回数が積み重なるとスタックオーバーフローを起こしてしまいます。末尾呼び出しが最適化されることで、再帰の回数が積み重なってもスタックオーバーフローが起こらなくなるため、再帰の回数が多くなり得る関数は末尾呼び出しの最適化がかかるように末尾再帰の形に変形することがあります。式木の変形など、単純に書くと末尾再帰にならない再帰は山のようにあるので、末尾再帰の形に変形する方法は重要です。

あ、一応言っておくと、末尾呼び出しの最適化がかかるかどうかは言語や処理系によって違いますので、末尾再帰に変形したからと言ってスタックオーバーフローが起きなくなることが保証されるわけではありません。自分の好きなあの言語、あの処理系、末尾呼び出しの最適化がかかるかどうか調べておくといいでしょう。

CPS変換による末尾再帰関数への変換

さて、話を継続に戻します。 CPSに変形(CPS変換)することで、自動的に末尾再帰の関数が手に入るのです！なぜそうなるのかを見てみましょう。

継続渡しスタイルの関数と、それを使うプログラムです。

let fCont x cont = x / 2 |> cont
let gCont x cont = x + 10 |> cont
let hCont x cont = string x |> cont

let program () =
  fCont 42 (fun x ->
  gCont x (fun y ->
  hCont y (fun z ->
  printfn "%A" (x, y, z) )))

継続渡しスタイルの関数は、継続を末尾呼び出ししているのが一目で分かります。では、継続渡しスタイルの関数を使っている側はどうでしょうか。こちらも、それぞれの関数は末尾呼び出しになっています。インデントを追加するとわかりやすいでしょう。

let program () =
  // fContの呼び出しは、program関数の末尾で行われている
  // gContなどの呼び出しは、関数でくるまれた中にいるその場では呼び出されない
  fCont 42 (fun x ->
    // gContの呼び出しは、fContの継続の末尾で行われている
    // hContなどの呼び出しは、関数でくるまれた中にいるのでその場では呼び出されない
    gCont x (fun y ->
      // hContの呼び出しは、gContの継続の末尾で行われている
      hCont y (fun z ->
        printfn "%A" (x, y, z)
      )
    )
  )

継続渡しスタイルの関数では、関数の最後は「継続を表す関数に結果を渡す」ことになりますし*5、継続渡しスタイルの関数を呼び出す場合もやはり末尾呼び出しになります。そのため、再帰部分を継続渡しスタイルで書けば自動的に末尾呼び出しになるのです。

つまり、末尾再帰ではない再帰関数をCPS変換したら末尾再帰関数になり、末尾呼び出しの最適化がかかります。ようやく、CPS変換のうれしさが分かるところまで来ました。では、末尾呼び出しになっていない再帰関数をCPS変換してみましょう。

階乗をCPS変換

簡単な例として、階乗からやってみます。まずは、末尾再帰ではないfactの定義です。

let rec fact = function
| n when n = 0I -> 1I
| n -> n * (fact (n - 1I))

bigintが定数パターンとして使えないのでwhenを使っているのがちょっと残念ですが、それ以外は普通のコードです。この関数は、再帰呼び出しをした後にその結果とnの値を掛けているため、末尾再帰になっていません。そのため、この関数に50000Iを渡すとスタックオーバーフローが起きました。

これを、まずは再帰呼び出し部分をletを使った形に書き換えます。 letを使った形にするとCPS変換しやすくなるので、慣れないうちはまずはletを使った形に変形するところから始めるといいでしょう。

let rec fact n =
  if n = 0I then 1I
  else
    let pre = fact (n - 1I)
    n * pre

次に、これをCPSに書き換えます。まずは、継続を引数contとして受け取るようにします。

(* 変換途中 *)
let rec fact' n cont =
  if n = 0I then 1I
  else
    let pre = fact' (n - 1I)
    n * pre

contは継続なので、fact'の処理の結果を渡してあげることでfact'の後ろの処理を実行します。こうでしょうか？

(* 変換途中: elseがおかしい *)
let rec fact' n cont =
  if n = 0I then 1I |> cont
  else
    let pre = fact' (n - 1I)
    n * pre |> cont

これはコンパイルが通りません。 fact'は第二引数として継続を受け取るため、preはfact'の結果ではなく関数になってしまっています。そこで、fact'を呼び出した後の処理(n * pre |> cont)をfact'に渡す無名関数の中に入れてしまいます。

(* 変換完了！ *)
let rec fact' n cont =
  if n = 0I then 1I |> cont
  else
    fact' (n - 1I) (fun pre ->
    n * pre |> cont)

letで導入される変数を無名関数の引数として導入する形にするのは、今まで何回か見てきているので大丈夫でしょう。これで無事、CPS変換できました！しかしこのままでは元の関数と同じ使い方ができません。「スタックオーバーフローしなくなりましたが、代償として継続を渡す必要ができました！」では駄目でしょう。そこで、CPSな関数をラップする関数を用意します。

CPS版のfact'をラップする

さて、fact'を外から呼び出す場合、contには何を渡せばいいでしょうか？それを考える前に、fact'のシグネチャを確認してみましょう。

val fact' :
  n:System.Numerics.BigInteger ->
    cont:(System.Numerics.BigInteger -> 'a) -> 'a

System.Numerics.BigIntgerの別名としてbigintがあるので、これを使って書き直すと、

val fact' : n:bigint -> cont:(bigint -> 'a) -> 'a

こうです。ここから分かるのは、

継続を表す関数contには、fact'が計算した結果が渡される
継続を表す関数contは、任意の結果型を返せる
継続を表す関数contが返した型が、fact'全体の結果型になる

です。 1つ目は、今まで見てきた通りのことです。継続には結果が渡されます。 2つ目と3つ目に注目してください。今まで、一番外側(一番深い部分)の継続では、printfnによる出力を行っていました。

fact' 5 (fun res ->
printfn "%d" res)

今まで通りならこんな感じです。これを上の3つに当てはめてみると、

resにはfact'が計算した結果が入っている
printfn "%d" resはfact'が計算した結果を出力して、unitを返す
fact'に渡した継続がunitを返すので、fact'の呼び出し全体としてもunitを返す

となります。ということは、CPS変換された関数から値を取り出すには、継続に渡された結果をそのまま返せばいいということになります。これは、継続としてid関数を渡せばいい、ということですね。

let res = fact' 5 id
printfn "%d" res

つまりこれを関数化すれば、factのユーザは中でCPS変換された関数に実装が変わってもなにも気にしなくていいわけです。

let fact n = fact' n id

fact'を外から使わせないようにするために、関数内関数にしてもいいでしょう。

let fact n =
  let rec fact' n cont =
    if n = 0I then 1I |> cont
    else
      fact' (n - 1I) (fun pre ->
      n * pre |> cont)
  fact' n id

これで変換完了です。実際にこれを試したい人は、プロジェクトのプロパティから「末尾呼び出しの生成」をオンにしてください(Releaseモードであればデフォルトでオンのはずです)。また、fsiであれば設定不要で試せます。この関数には、50000Iを渡してもスタックオーバーフローは起こしません。 CPS変換をしたことによって、末尾再帰になり、末尾呼び出しの最適化がかかったようです。

スタックオーバーフローするような再帰を書いてしまったときに、CPS変換を行えばスタックオーバーフローを回避できるようになります。他にも回避する方法はあります*6が、 CPS変換は慣れてしまえばほとんど機械的に行えるので、自分の道具箱に入れておいてもいいでしょう。

その2はコンピュテーション式の話になる予定です。

おまけ

ここからはおまけです。もしくはボーナスステージ。色々な関数をCPS変換してみましょう。

sum関数

オリジナル

let rec sum = function
| [] -> 0
| x::xs -> x + (sum xs)

letで書き換え

let rec sum xs =
  match xs with
  | [] -> 0
  | x::xs ->
      let pre = sum xs
      x + pre

CPS!

let rec sum xs cont =
  match xs with
  | [] -> 0 |> cont
  | x::xs ->
      sum xs (fun pre ->
      x + pre |> cont)

あ、id渡すラッパー関数は自明なので書きません。

max関数をCPS変換

オリジナル

let rec max = function
| [x] -> x
| x::xs ->
    let pre = max xs
    if pre < x then x
               else pre

letで書き換え

letで書き換え自体は不要だけど、functionをmatchにしておく。

let rec max xs =
  match xs with
  | [x] -> x
  | x::xs ->
      let pre = max xs
      if pre < x then x
                 else pre

CPS!

let rec max xs cont =
  match xs with
  | [x] -> x |> cont
  | x::xs ->
      max xs (fun pre ->
      if pre < x then x   |> cont
                 else pre |> cont)

find関数をCPS変換

オリジナル

let rec find pred = function
| [] -> failwith "not found."
| x::xs -> if pred x then x
                     else find pred xs

letで書き換え

let rec find pred xs =
  match xs with
  | [] -> failwith "not found."
  | x::xs ->
      if pred x then x
                else
                  let res = find pred xs
                  res

CPS!

let rec find pred xs cont =
  match xs with
  | [] -> failwith "not found."
  | x::xs ->
      if pred x then x |> cont
                else find pred xs cont (* (fun res -> res |> cont)なので、単にcontを渡せばいい *)

map関数をCPS変換

オリジナル

let rec map f = function
| [] -> []
| x::xs -> (f x) :: (map f xs)

letで書き換え

let rec map f xs =
  match xs with
  | [] -> []
  | x::xs ->
      let y = f x
      let ys = map f xs
      y::ys

CPS!

let rec map f xs cont =
  match xs with
  | [] -> [] |> cont
  | x::xs ->
      let y = f x
      map f xs (fun ys ->
      y::ys |> cont)

これは、map自体のCPS変換です。 fがCPS変換された関数の場合は、

let rec map f xs cont =
  match xs with
  | [] -> [] |> cont
  | x::xs ->
      f x (fun y ->
      map f xs (fun ys ->
      y::ys |> cont))

こうですね。

フィボナッチ関数をCPS変換

オリジナル

let rec fib = function
| 0 | 1 -> 1
| n -> fib (n - 1) + fib (n - 2)

letで書き換え

let rec fib n =
  match n with
  | 0 | 1 -> 1
  | n ->
      let pre1 = fib (n - 1)
      let pre2 = fib (n - 2)
      pre1 + pre2

CPS!

let rec fib n cont =
  match n with
  | 0 | 1 -> 1 |> cont
  | n ->
      fib (n - 1) (fun pre1 ->
      fib (n - 2) (fun pre2 ->
      pre1 + pre2 |> cont))

*1:contはcontinuationの略です。継続を表す変数名には他にもkなどが使われたりします。

*2:再帰関数のことを扱う場合が多いですが、再帰関数でなくとも末尾呼び出しと言えます。

*3:自分自身のスタックを再利用したり、ループに変形したりというやり方もありますが、どの方法でもスタックを消費しないという効果は同じです。

*4:他にも、Chain of Responsibilityパターンを適用した際に大量のオブジェクトがchainを構成する場合など、再帰しない場合でもうれしい場面はあります。

*5:例外を投げるとか、継続を捨てるとかは無視します。

*6:アキュムレータ変数を使う方法や、ループに書き換える方法などが使えます。

2015-01-13

なごやかJava ゆるふわテストツール編で発表してきた

Test

テストの自動化を考える前に from bleis tift

発表してきました。

テストツール編なのに、Javaにもテストツールにも関係のない、テスト自体の話です。それなりに反応は良かったかな？

資料作ってる時に、盛り込み過ぎだったので資料から抜いたものを独立して別の資料にしたので、時間があったらそっちも発表しようかなー、と思っていたんですが、なかったので公開だけしておきます。

効果の低いテストの話 from bleis tift

異論は認める。

連載目次

はじめに

継続渡しスタイルつらい話

コンピュテーション式が世界を救う

継続もにゃど

factCpsをcontコンピュテーション式で書き直す

contコンピュテーション式の罠

Bindのinline化

まとめ

ProjectScaffoldとは

ProjectScaffoldで気を付けなければいけないこと

READMEとリリースノートが固定化されている

ライセンスが固定化されている

.NET Frameworkのバージョンが固定化されている

Paketの扱い

FsUnitとの相性が悪い

FAKEの扱い

ドキュメントのリリース

まとめ？

連載目次

はじめに

CPS変換のおさらい

2種類の末尾呼び出しの最適化

ジャンプ命令への書き換え

tail.プレフィックスの付与

2つの最適化の違い

tail.プレフィックスでスタックオーバーフローになる場合

連載目次

はじめに

末尾

調べ方

F#での末尾一覧

blockで囲まれた式の末尾

begin-endで囲まれた式の末尾

delayedのlazyに続く式の末尾

functionの本体部分の式の末尾

matching functionの各本体部分の式の末尾

sequential executionの後ろ側の式の末尾

matchの各分岐の式の末尾

conditionalのthenの式の末尾とelseの式の末尾

末尾っぽいが末尾ではないもの

assignment

tuple

try/with

try/finally

determinstic disposal

最適化される呼び出しとされない呼び出し

最適化される呼び出し

関数呼び出し

メソッド呼び出し

関数値の起動

最適化されない呼び出し

コンストラクタ呼び出し

コンストラクタ内でのコンストラクタ呼び出し

Scalaについて

Scalaにおける「何もない」を表すものたち?

Scalaにおける「何もない」を表すものたち

nullとNone

その他勘違いされやすいけど違うものたち

()

Nothing

Nil

余談:object

まとめ

連載目次

はじめに

継続とは

継続を無名関数で表す

無名関数でletを代用する

継続渡しスタイル(CPS)

末尾呼び出し

末尾呼び出しの最適化

CPS変換による末尾再帰関数への変換

階乗をCPS変換

CPS版のfact'をラップする

おまけ

sum関数

オリジナル

letで書き換え

CPS!

delayedの`lazy`に続く式の末尾

conditionalの`then`の式の末尾と`else`の式の末尾

`null`と`None`

`()`

`Nothing`

`Nil`

余談:`object`