re:僕にとってMaybe / Nullable / Optional が、どうしてもしっくりこないわけ。

C# Java etc

元ネタ: 僕にとってMaybe / Nullable / Optional が、どうしてもしっくりこないわけ。 - 亀岡的プログラマ日記

OOPの文脈で見ると、元の記事が言っていることもわからなくはないのですが、対象が広すぎていろいろと不正確になってしまっているので、ちょっとまとめてみます。

元の記事が対象にしているのは、Maybe / Optional / Nullableの3つです。 対応する型を持つ言語を見てみると、下記のようになります。

これらは、「値がないこと」を表すもの、という見方では同じですが、それぞれ異なる価値観の元に作られています。

Maybe/OptionalとNullable

これらはすべて型パラメータを取ります*1。 しかし、この中でNullableだけは型パラメータに値型のみという制約が付きます。 これは、C#のNullableは他のものとかなり性質が違うことを意味しています。 元の記事では並べて書かれていましたが、そもそもNullableに関してはここに並べるべきものではありません。

C#のNullable

C#のNullableは、値型にもnullが使いたいという動機で導入された機能です。 そのため、NullableはMaybeやOptionalと違って、むしろnullを積極的に使えるようにするための機能と言えるでしょう。 これによってC#の上ではNullableを使うことでコード上の見た目だけに関しては、値型でもnullが使えるように見せています。 見た目だけの話であれば、SwiftのOptionalと同じように型名の後ろに?が付くため、同じような言語機能に見えますが、実際には全くの別物と考えたほうがいいでしょう。

JavaのOptional

JavaのOptionalは、メソッドの戻り値として使うことが想定されているらしく、引数やフィールドに使うことは想定されていないそうです。 JavaのOptionalは参照型なので、Optional自体がnullになりうるという点を考えると、引数に使うべきではないというのもある程度納得できます*2。

Javaでは現状、型パラメータに指定できるのは参照型だけであり、nullになりうるのも参照型だけです。 そのため、JavaのOptionalはC#のNullableと違って、(戻り値としての)nullを排除しよう(少なくとも、減らそう)という動機で導入されたとみていいでしょう。

SwiftのOptional

SwiftのOptionalは、Javaと名前は同じですが、より言語の仕組みに根差しています。 Javaでは、Optional<T>型の変数にT型の値を代入できません。

Integer i = 42;
Optional<Integer> x = i; // コンパイルエラー

それに対して、Swiftではそれが可能です。

var i: Int = 42
var x: Optional<Int> = i // OK
// Optional<Int>はInt?とも書ける

SwiftではOptionalではない型にnull*3は代入できません。 ですが、Optionalという仕組みによって今までの知識からあまり外れない書き方でnullを扱えるようになっています。

HaskellのMaybe

HaskellのMaybeは実装としてはSwiftのOptionalに一番近くなっています。 ただ、他の言語と違ってHaskellではそもそも他の言語のようなnullはなく、Swiftのように既存言語ユーザーを取り込むために「今までの知識からあまり外れない書き方」というのも求めていません。 結果だけ見ると、JavaのOptionalと同じように、Maybe t型の変数にt型の値は代入できません。

Nullのダメな理由

元記事では、「Nullは何がダメなんだっけ？」について、

  1. Nullは型ではない
  2. あるメソッドがNullになるかどうかの判断ができない

が挙げられています。 細かい点ですが、ここにも誤解があります。

(少なくともJavaでは)Nullは型を持つ

まず、Javaの話であればnullは型を持っています*4。 そのため、「ClassHogeのnull」という表現は、少なくともJavaにおいては正確ではなく、正確には「ClassHoge型に暗黙変換されたnull」とでもなるでしょうか。 詳しくは言語仕様を参照してください。

ここで言いたかったのはおそらく、「nullはどんな型にも変換できてしまう」ということでしょう。

あるメソッドの結果(もしくは変数)がNullかどうかの判断が型だけからできない

これも細かいですが、あるメソッド(の結果)がNullになるかどうかの判断ができないというのは、正確には「型を見ただけでは」できないのであり、元記事中にあるように、if文によって実行時にはチェックできます。

本題

さて、ここからが本題です。 元記事では、Optionalが解決するのは2だけ、としていますが・・・

Javaの場合

JavaのOptionalでは、Optional<T>型とT型は全くの別物であり、相互に暗黙変換できません。 そのため、

  1. (nullに相当する)Optional.empty()はOptional型の変数にしか入れることはできない*5
  2. あるメソッドの結果がOptional.empty()になりうるかどうか型だけで判断できる

となります。

Swiftの場合

SwiftのOptionalは、Optional<T>型の変数にT型の値を代入できますが、その逆はできません。 そのため、

  1. (nullに相当する)nilはOptional型の変数にしか入れることはできない
  2. あるメソッドの結果がnilになりうるかどうか型だけで判断できる

となります。

Haskellの場合

HaskellのMaybeは、Maybe t型とt型は全くの別物であり、相互に暗黙変換できません。 そのため、

  1. (nullに相当する)NothingはMaybe型の変数にしか入れることはできない
  2. ある関数の結果がNothinsになりうるかどうか型だけで判断できる

となります。

元記事が言いたかったこと

このように、OptionalもしくはMaybeは、1も2も解決できています。 これは十分なメリットであり、このメリットだけでもOptional/Maybeは有用です。

ただ、元記事を見ると、

本当に解決したいのは「Nullに型独自の処理をさせたい」なので、残ったままです

とあります。 つまり、本当に問題にしていたのは、「型Aの値がない場合と型Bの値がない場合で別の処理をさせたい」となります。

if文相当の処理を書く必要性

Optional/Maybeを使ったコードで頻繁にif相当の処理を書いてしまっている場合、それはそもそもOptional/Maybeの使い方を間違っている可能性が大きいです。 リストを操作する関数にリストを返す関数が多く含まれるのと同じように、あるいはTaskを返す関数を内部で呼び出している関数がTaskを返す関数になるのと同じように、Optional/Maybeを返す関数を内部で呼び出している関数は、その関数の戻り値もOptionalになることがよくあります。 この場合、if相当の処理を書くのは間違っています。

// Javaだと思う(Swiftは書いたことないので)
Optional<User> user = findUser(pred);
if (user.isPresent()) {
    // 何かする
    return Optional.of(何か処理の結果);
} else {
    return Optional.empty();
}

例えば、「何かする」の部分がuserの中身を使った関数を呼び出すような処理の場合、

// 値がなかった場合のことは気にしない
return findUser(pred).map(user -> 何かする関数(user)); // ラムダ式を使わずに直接関数を渡す、でも可

のようになるでしょう。 mapの他にも、様々なメソッドが用意されているため、ifによる分岐に頼る場面は少なくなります。 Haskellの場合、do構文によってさらに複雑な例でもすっきり書けますが、それはまた別の話。

手続き的には見えない

さて、上のコードが手続き的に見えるでしょうか？ 呼び出し側はOptionalのチェックを行っておらず、コードも短く簡潔です。

ではオブジェクト指向プログラミングではどのようになるでしょうか？ Userに対してNullObjectを用意して、このようになるでしょう。

public interface User {
    戻り値の型 何かする処理();
}
public class UserImpl implements User {
    @Override
    public 戻り値の型 何かする処理() {
        // 何かする
        return 何かした結果;
    }
    // ...
}
public class EmptyUser implements User {
    @Override
    public 戻り値の型 何かする処理() {
        return 戻り値の型のNullObject;
    }
    // ...
}

// 呼び出し側は意識しない(意識できない)
return findUser(pred).何かする処理();

呼び出し側だけ見ると、Optionalのときとそんなに変わってませんよね*6。 つまり、元のコードも手続き的には見えないと言っていいでしょう。

NullObjectをちゃんと使いたい、というよりは、Optionalをどう使うか考えたい

OOPの文脈で、どこまでOptionalを使えばいいのかというのはよくわかりません。 Optionalを使うと、どうしてもコードはOOPから離れて行ってしまうという感覚は確かにあります。 どのあたりでバランスを取るのがいいのかはケースバイケースでしょうし、一般化できるものではないと思っています。

コメント欄では id:kyon_mm が(やはりOOPの文脈で)

Optionを返していいのはむしろprivateやprotected的なものだけだと思っていて、それ以外はオブジェクトだったり、バリアント（判別共用体）的な感じで返すのが「オブジェクトとやり取りをしていて、それぞれに責務が割あたっている」といえるのではないだろうか。と思っています。

と言っています。 これはこれで一つの態度ではありますが、基本的なライブラリでは Optional を返す関数*7というのはもっと積極的に作られることになると思います。

FPに軸足を置くか、OOPに軸足を置くかは、対象の性質やメンバーのスキル等によって決めていくしかないでしょう。 ただし、間違ったOptionalの使い方をもって「しっくりこない」というのであれば、まずはOptionalの正しい使い方を学び、実践すべきです。 そのための言語としては、F#なんていかがでしょうか。

*1:Javaは取らなくても許されるとかいう細かい話は置いといて。

*2:フィールドに使うべきではない理由はよくわかりませんが

*3:Swiftではnilだが、この記事ではnullで統一

*4:ただし、その型の変数やフィールドを作ることはできない

*5:Objectは無視します

*6:findUserがnullを返す可能性は考慮しなくていいのかという点はここでは考慮しない

*7:もしくは、Optionalを返す関数を受け取る関数

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

.NET IL C# F#

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を駆使して作られたシステムはヤバいです。 こいつらを置き換えるためには、例えば下記のようなものが使えます。

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

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

まとめ

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

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

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

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

C# F#

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

シャドーイングとは

既存の変数と同名の変数を定義して、そのスコープで既存の変数にアクセスできなくする機能です。 例えば、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

F#

連載目次

はじめに

再帰関数のスタックオーバーフローを倒す話 その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:「再帰関数は」と書きましたが、再帰ではない単なる関数呼び出しも同様です。

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

F#

連載目次

はじめに

再帰関数のスタックオーバーフローを倒す話 その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式のネストになっています

ProjectScaffoldを使ってみた

F#

最近公開した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オプションを使うこともできます