2015-04-14

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

異論は認める。

2014-12-14

2つのOptionalで分岐する

Java F#

僕のOptional<>の使い方がカッコワルイ。 - 谷本心 in せろ部屋にある最後の例ですが、 2つのOptionalの組み合わせによって処理を分岐させるコードが幾つか載っています。 ifで書いた例を見てみましょう。

public String hello(Optional<String> name1, Optional<String> name2) {
    if (name1.isPresent()) {
        if (name2.isPresent()) {
            return call(name1.get(), name2.get());
        } else {
            return call1(name1.get());
        }
    } else {
        if (name2.isPresent()) {
            return call2(name2.get());
        } else {
            return call();
        }
    }
}

まとめると、こんな感じでしょうか。

name1	name2	呼び出すメソッド
値有り	値有り	2引数call
値有り	Empty	call1
Empty	値有り	call2
Empty	Empty	0引数call

これ、F#だったらmatch式を使えば分かりやすく書けます。

let hello name1 name2 =
  match name1, name2 with
  | Some name1, Some name2 -> call(name1, name2)
  | Some name1, None -> call1(name1)
  | None, Some name2 -> call2(name2)
  | None, None -> call()

JavaのOptionalにもしmatchメソッドが実装されていれば、こんな感じに書けるんですけどね。

public String hello(Optional<String> name1, Optional<String> name2) {
    return name1.match(
        n1 -> name2.match(n2 -> call(n1, n2), () -> call1(n1)),
        () -> name2.match(n2 -> call2(n2), () -> call())
    );
}

Optionalのような型を導入するのであれば、やはりmatch式のようなもの*1が欲しくなりますね、という話でした。

*1:あとついでにモナド用の構文も・・・

2014-12-14

Effective Visual F# Power Tools

さてさて、またもや他人のAdvent Calendarに乗っかったネタです。今日は、Visual F# Power Tools の紹介というF# Advent Calendar 2014の11日目の記事です。

VFPTの基本的な便利な機能は元記事を参照いただくとして、このエントリでは更に進んだ使い方等を紹介します。

シンタックスのカラーリングのカスタマイズ

シンタックスのカラーリングはカスタマイズできます。カスタマイズは、VS自体のオプションの左のペインから環境、フォントおよび色と選択し、表示項目のF#から始まる項目です。

f:id:bleis-tift:20141213235647p:plain

カスタマイズできる項目は以下の通りです。

F# Escaped Characters
F# Functions / Methods
F# Modules
F# Mutable Variables / Reference Cells
F# Patterns
F# Printf Format
F# Quotations
F# Types
F# Value Types

この中でおすすめなのが、「F# Mutable Variables / Reference Cells」です。これを設定することで、mutableな変数やref型の変数に色が付き、どこで再代入を使っているかが一目瞭然になります。

f:id:bleis-tift:20141214000302p:plain

スコープもちゃんと認識していますね。ちなみに、setterがあるプロパティなんかも、Mutable Variablesとみなされて色が付きます。

他には、「F# Escaped Characters」と「F# Printf Format」も便利です。上のコードでも、printf系の関数のフォーマットに色が付いているのが分かります。「F# Quotations」も人によっては便利でしょう。「F# Patterns」は、便利かどうかは微妙ですが、設定してあります。

f:id:bleis-tift:20141214085050p:plain

SomeとNoneに色がついているのや、自動実装プロパティのFailedに色がついているのが分かります。

自動実装とタスクリストコメント

元記事ではインターフェイスの自動実装と判別共用体ケースの自動実装に触れられていますが、もう一つ、レコードのスタブ生成機能もあります。これら自動実装系の機能と、タスクリストコメント*1を合わせる技をadacolaさんが呟いています。

Visual F# Power ToolsのCode GenerationをUncompilable Codeにして内容を(* TODO 自動生成のまま未実装 *)みたいにしておくと、タスク一覧で自動生成したままの箇所が一覧できてよさげ
— adaco (@adacola) November 8, 2014

これは是非設定しておくといいでしょう。

failwith "oops!" (* TODO : Not implemented yet *)

このように設定しておけば、(Uncompilable Codeと言いつつ)コンパイル可能で、かつタスク一覧に「TODO : Not implemented yet」と表示されるようになります。

f:id:bleis-tift:20141214091608p:plain

便利！

その他の機能

元記事では触れられていない機能をざっくり紹介します。

ドキュメンテーションコメントの自動生成

///<までタイプするとドキュメンテーションコメントのひな形を生成してくれます。地味ですが、ドキュメンテーションコメントを書くときに便利です。

VFPTとは関係ありませんが、F#ではドキュメンテーションコメントの中身がsummaryだけであれば、summaryを省略できるという便利機能があります。

/// とても素晴らしい変数です。
let x = 42

これも知っていると便利なので使っていきましょう。

ソースコードの整形

整形してくれます。あんまり使ったことはありません。

もちろん、VSの整形のショートカットで呼び出せます。使う人は使う機能かも？

ナビゲーションバー

便利機能です。この機能を有効にするには、VSを管理者権限で立ち上げてから「Navigation bar」のチェックボックスをチェックし、VSを再起動する必要がありますので注意してください*2。

この機能を有効にすると、エディタの上にナビゲーションバーが表れて、選択した型やメンバに簡単にジャンプできるようになります。上の画像で、「Program」とか「g」とか表示されているのが分かります。

参照箇所のハイライト

便利機能です。カーソルを置いている変数や関数と同じものを参照している箇所をハイライトしてくれます。

インデントガイド/Depth colorizer

便利機能です。F#はインデントに意味のある言語なので、インデントガイドを出してくれると色々と捗ります。

上の画像でも、インデントガイドが確認できます。

NavigateTo

便利機能です。Ctrlキーを押しながらカンマキーを押すと起動できます。起動したら、型名とか関数名とか適当にタイプしてみてください。そういうことです。

フォルダ機能

最近使ってません。プロジェクトが巨大になればお世話になることでしょう。

openしていない名前空間の解決

便利機能です。Hogeを含むモジュールがあった時に、Hoge.piyoとかやってHogeまでカーソルを持っていくと、スマートタグが表れるのでCtrl+.で起動してEnterです。

未使用宣言のグレーアウト

使っていない変数や関数などをグレーアウトしてくれます。不安定なので現状ではOffにしておくといいでしょう。次のバージョンではもうちょっと改善される予定です。

未使用openのグレーアウト

使っていないopenをグレーアウトしてくれます。不安定なので現状ではOffにしておくといいでしょう。次のバージョンではもうちょっと改善される予定です。

メタデータに移動

便利機能です。ソースを持っていないコードのシグネチャ等を確認する際、この機能がない時代はオブジェクトブラウザを使ったりしていましたが、F12で確認できるようになりました。

タスクリストコメント

便利機能です。この機能は実装にも関わったので、思い入れもある機能です。タスク一覧ウィンドウを開いて、(ユーザータスクではなく)「コメント」を選ぶと、TODOコメントなどが一覧できます。

オプションからカスタマイズ可能で、「環境」、「タスク一覧」と辿ると設定画面になります。「名前」の欄に「XXX」とか入れて、追加ボタンを押すとトークンリストに追加されます。このUIは非常にわかりにくいと思うんですが、まぁVS標準の機能だし仕方ない。

VFPTの今後

次のバージョン

次のバージョンでは、細かい点が修正され、目立った新機能は追加されないようです。

New folderダイアログがリストアされない問題を修正
大きなソリューションでの「全ての参照の検索」機能のパフォーマンスを改善
Goto Metadataで表示されるコードにエラーが表示される問題のいくつかを修正
これ以上自動生成するものがないスマートタグを表示しないように変更
printf系関数のフォーマットの色付けをユーザ定義のものまで拡張
ソースが存在する構造体への移動がメタデータへの移動になる問題を修正

今後載るかもしれない機能

コメントの折り畳み機能がもしかしたら載るかもしれないです。

機能追加の要望方法

GithubのIssuesではなく、VFPTのUser Voiceに投稿してください。 Voteもできるので、気になった機能があればVoteするといいでしょう。幾つかピックアップして紹介します。

クラスビューでのコードナビゲーション

Feaure Request: Code Navigation Using Class View で提案されています。

ナビゲーションバーは一つのファイルであれば便利だけど、クラスビューであればプロジェクト全体をナビゲートできて便利だよね、という提案です。

ローカルで閉じたIDisposableでletを使っていた場合にuseを使うよう提案

Suggest to use use instead of let for local IDisposable valuesで提案されています。

IDisposableを実装した型にletを使っていた場合、それをuseを使うように提案してくれるような機能の提案です。実装されれば有用そうですが、ローカルで閉じているかどうかのチェックって簡単にできるんでしょうか・・・

式の型の表示

Show type annotation on expressionで提案されています。

Scala-plugin for Intellij ideaで実装されている機能のようですね。あると便利なのは間違いないでしょう。

推論された型の表示

Display inferred types above declarationで提案されています。

コンパイラによって推論された型を、定義の上に(CodeLensのように)表示する機能の提案です。コメントでは結構散々な言われようですが、これ、実装されればめちゃくちゃ便利だと思うんですよ。

CodeLens APIが公開されていないようなので、CodeLensっぽくできるかどうかわからないかつ、公開されたとしても関数内関数は結局自作になりそうなので、全部自作してしまえばいいじゃん、と思うんですが果たして。エディタ上にCodeLensのように行じゃない行(?)を差し込めるのかどうかが問題だと思うんですが、教えてVS拡張に詳しい人！

まとめ

VFPTを使いこなして楽しくF#でプログラミングしましょう！

*1:これも実はVFPTの機能で、生のVSだとF#でタスクリストすら使えません。

*2:再起動自体はほかの機能も必要ですが、管理者権限でVSを立ち上げる必要があるのはこの機能のみです

2014-12-12

コンピュテーション式の変形後を覗き見るを改良する

さてさて、気になるネタがまた増えたようです。コンピュテーション式の変形後を覗き見るというエントリがF# Advent Calendar 2014の10日目の記事として公開されました。 Quoteを差し込んで、Runで表示する、というのは面白いアイディアですね。

だが俺の前でコンピュテーション式の変換を扱ったのが運の尽きだ！添削をくらうがいい！

・・・同僚だからってやりたい放題ですね。

変換に必要なメソッド

変換対象が

let ret = simple {
  let x = 10
  return x
}

程度であれば、必要なメソッドはReturnだけです。 BindもReturnFromも不要です。

ですが、消してしまってはあまりにも単純なので、 Bindを使う例を扱えるようにしましょう！

変換対象はこうなります。

let res = simple {
  let! x = 10
  return x
}

このコードがコンパイルできるようにするために必要なコンピュテーションビルダーの定義はこれです。

type SimpleBuilder () =
  member __.Return(x) = x
  member __.Bind(x, f) = f x

let simple = SimpleBuilder ()

手動で変換する

では、このコードを変換していきます。

let res = simple {
  let! x = 10
  return x
}

一番外側はいいでしょう。

let res =
  let b = simple in
  {| let! x = 10 in return x |}

let!の変換

{|と|}に挟まれた部分(cexpr)がlet! ...という形をしているので、 let!の変換規則を最初に適用します。

let b = simple in
T(return x, fun v -> C(b.Bind(10, fun x -> v)))

Bindの呼び出しが出てきました。

returnの変換

Tの最初の引数(変換対象)がreturn xという形をしているので、 returnの変換規則を適用します。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

Returnの呼び出しが出てきました。これ以上変換すべき個所はありませんので、手動変換はここまでです。ビルダーにはBindもReturnも適切に定義されているため、コンパイル可能です。

変換を出力する

さて、元の記事ではSimpleBuilderを弄って変換の様子を出力するようにしていました。同じ方法だと面白くないので、この記事では別の方法を取ってみることにします。その前に、Quoteについて突っ込んでおきます。

Quote変換

Quoteは元記事でも使っていますが、その定義は

member this.Quote(x) = x

と、あたかも式木がxとして渡されてそれをそのまま返しているように見えます。しかし、実際はQuoteメソッドは呼び出されることはありません。ただ単に、Quoteという名前で定義されてさえいればいいのです。そのため、紛らわしさを無くす意味でもQuoteの実装は、

member __.Quote() = ()

としておいた方がいいと思います。

コンピュテーションビルダーに機能を後付けする

さて、コンピュテーションビルダーに対する機能の追加ですが、方法としては以下のものがあるでしょう。

コンピュテーションビルダーの書き換え
既存のコンピュテーションビルダーを継承して機能を追加
型拡張として機能を追加
拡張メソッドとして機能を追加

1つ目の方法が元記事のやり方です。一番シンプルですが、コードがない場合にはこの方法は選べません。

2つ目の方法は、面倒ですしそれほど説明すべき点もないので省略します。

3つ目と4つ目の方法を今回紹介します。

型拡張として機能を追加

コンピュテーション式の変換は、コードの表現しか見ておらず、実現方法は問題にしていません*1。そのため、ビルダーに対してメソッドを呼び出せるようになっていれば、コンピュテーションビルダーにメソッドが定義されている必要はありません。

型拡張でQuote機能を追加する例を見てみましょう。

open FSharp.Quotations.Evaluator

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

この型拡張を適当なモジュールに入れ、そのモジュールをopenするかどうかでexprを出力するかどうかを切り替えれるようになります。しかし、ビルダーにQuoteメソッドを追加してRunの引数の型をExpr<_>型にしてしまい、 Runメソッドの中で引数をそのまま返してしまうと、コンピュテーション式利用側はExpr<_>を受け取ることになってしまいます。これでは、元のコードをコンパイルできなくなってしまいます。

そこで、FSharp.Quotations.Evaluatorというライブラリを使います。このライブラリは、F#のコードクォートを実行するためのライブラリです。 Runメソッドの最後でEvaluateを呼び出し、 QuoteでExpr<_>にしたものをまた戻します*2。

拡張メソッドとして機能を追加

型拡張ではなく、もちろん拡張メソッドとして定義することもできます。

open System.Runtime.CompilerServices
open FSharp.Quotations.Evaluator

[<Extension>]
type SimpleBuilderExtension private () =
  [<Extension>]
  static member Quote (_: SimpleBuilder) = ()
  [<Extension>]
  static member Run(_: SimpleBuilder, expr: Quotations.Expr<_>) =
    // ここにexprを出力するコードを書く

    // 式木を実行するために、FSharp.Quotations.Evaluatorを使用
    expr.Evaluate()

少々面倒なので、型拡張でいいですね。一応、できるということで。

exprを出力するコード

少し改良していますが、基本的には元の記事と同じです。

open Microsoft.FSharp.Quotations.Patterns
open System.Collections.Generic

module Printer =
  let mutable private i = 0
  let private valueMap = Dictionary<obj, string>()
  let printKnownVar obj =
    if obj = box simple then
      "simple"
    else
      "unknown_var"
  let printValues () =
    valueMap
    |> Seq.sortBy (fun kv -> kv.Value.Substring(2) |> int)
    |> Seq.map (fun kv -> sprintf "let %s: %s = %s" kv.Value (kv.Key.GetType().Name) (printKnownVar kv.Key))
  let rec print (expr: Quotations.Expr) =
    match expr with
    | Call (Some receiver, m, args) ->
        (* インスタンスメソッド呼び出しを文字列化 *)
        let receiver = print receiver
        let args = List.map print args |> String.concat ", " (* reduceじゃなくてconcatでOK *)
        sprintf "%s.%s(%s)" receiver m.Name args
    | Value (obj, typ) ->
        (* 値を文字列化 *)
        if typ = typeof<SimpleBuilder> then
          (* 値が辞書にあったらそれを変数として扱うように変更 *)
          match valueMap.TryGetValue(obj) with
          | true, name -> name
          | false, _ ->
              let name = sprintf "$b%d" i
              i <- i + 1
              valueMap.Add(obj, name)
              name
        else
          string obj
    | Lambda (arg, Let(var, value, body)) when arg.Name = print value ->
        (* 単純なラムダ式を文字列化 *)
        (* Expr<_>の表現力の問題によって、Lambdaではラムダ式すべてを表現できない。
           例えば、ラムダ式の引数部分でパターンマッチできるが、
           Expr<_>のLambdaはargがVarなので、Letと組み合わせることでこれを再現している模様。 *)
        let arg = var.Name
        let body = print body
        sprintf "(fun %s -> %s)" arg body
    | Var v ->
        (* 変数を文字列化 *)
        v.Name
    | _ ->
        (* 対応できない式木はエラーにするように変更 *)
        failwithf "%A is not supported." expr

type SimpleBuilder with
  member __.Quote () = ()
  member __.Run(expr: Quotations.Expr<_>) =
    let exprStr = Printer.print expr
    let values = Printer.printValues ()
    values |> Seq.iter (printfn "%s")
    printfn "%s" exprStr
    expr.Evaluate()

改良した点としては、

変数を出力するようにした
実装を洗練
Runの結果を変えないように、式木を実行するようにした

というところです。

実行してみる

拡張を施したモジュールをopenすると、既存のコンピュテーション式の挙動が変わり、 Printer.printの結果が出力されるようになります。

let res = simple {
  let! x = 10
  return x
}

このコードを実行してみると、このような出力が得られます。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

結果比較

手動変換した結果はこうでした。

let b = simple in
b.Bind(10, fun x -> b.Return(x))

そして、QuoteによってExpr<_>にしたものを文字列化したのがこれです。

let $b0: SimpleBuilder = simple
$b0.Bind(10, (fun x -> $b0.Return(x)))

完全に一致！！！

まとめ

コンピュテーション式がどんな風に変換されるのか見るために、 Quoteで式木化してF#コードに文字列化するのはいいアイディアでした。この記事では、以下のことをやりました。

Bindを必要な例に変更
既存のコンピュテーションビルダーに機能を追加する方法
出力されるコードに何も手を加えなくても手動変換の結果とほとんど同じになるようなExpr<_>の出力

Expr<_>の限界*3はありますが、これを推し進めれば、かなり良い感じに色々なコンピュテーション式の変換結果を出力できるようになりそうです。

今年もF# Advent Calendarは豊作ですね！素晴らしいです。

*1:ダックタイピング的、とも言えるでしょう。

*2:Delayを定義している場合は、更にユニットを渡す必要があります。

*3:match式がIfThenElseに落ちるなど

2014-12-09

クラスのコンストラクタ呼び出し時にプロパティも同時に初期化する

これはF# Advent Calendar 2014の9日目の記事(ピンチヒッター)です。昨日の記事はねのさんによるFSharperならこう書く(A Poker Game Program) #FsAdventでした。この記事を勝手に添削したエントリも、よろしければ合わせてどうぞ。何度も言いますが、コードが読みやすくて書き換えが大変楽でした。

さて、今日はF# のネタリストから、クラスのコンストラクタ呼び出し時にプロパティも同時に初期化する方法です。 Advent Calendarのネタに困っている人は、参考にしてみるといいかもしれません。

F#のプロパティ

F#のプロパティの定義は、複数の書き方があります。 C#の自動実装プロパティに初期値を持たせた書き方もサポートしていますので、今回はそれを使いましょう。

type Class(x: int) =
  member val Name = "" with get, set

これで、C#での

public class Class
{
    readonly int x;
    public string Name { get; set; }

    public Class(int x)
    {
        this.x = x;
        this.Name = "";
    }
}

に大体対応します。ヤバい短さですね。

コンストラクタ呼び出し時にプロパティも同時に初期化したい

上のように作ったクラスを生成する際に、C#ではオブジェクト初期化子という構文を使って、プロパティも同時に設定できます。

var c = new Class(10) { Name = "hoge" };

便利ですね！実は(?)、これと同じことがF#でもできます。

let c = Class(10, Name="hoge")

これだけです！

これは、F#での名前付き引数とまったく同じ構文ですね。なので、当然(?)これらは混ぜることができます。

let c1 = Class(x=10, Name="hoge")
let c2 = Class(Name="hoge", x=10)

素晴らしい！

本日は以上です。明日は、ざっきーさんの番ですね！

Scalaについて

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

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

nullとNone

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

()

Nothing

Nil

余談:object

まとめ

連載目次

はじめに

継続とは

継続を無名関数で表す

無名関数でletを代用する

継続渡しスタイル(CPS)

末尾呼び出し

末尾呼び出しの最適化

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

階乗をCPS変換

CPS版のfact'をラップする

おまけ

sum関数

オリジナル

letで書き換え

CPS!

max関数をCPS変換

オリジナル

letで書き換え

CPS!

find関数をCPS変換

オリジナル

letで書き換え

CPS!

map関数をCPS変換

オリジナル

letで書き換え

CPS!

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

オリジナル

letで書き換え

CPS!

シンタックスのカラーリングのカスタマイズ

自動実装とタスクリストコメント

その他の機能

ドキュメンテーションコメントの自動生成

ソースコードの整形

ナビゲーションバー

参照箇所のハイライト

インデントガイド/Depth colorizer

NavigateTo

フォルダ機能

openしていない名前空間の解決

未使用宣言のグレーアウト

未使用openのグレーアウト

メタデータに移動

タスクリストコメント

VFPTの今後

次のバージョン

今後載るかもしれない機能

機能追加の要望方法

クラスビューでのコードナビゲーション

ローカルで閉じたIDisposableでletを使っていた場合にuseを使うよう提案

式の型の表示

推論された型の表示

まとめ

変換に必要なメソッド

手動で変換する

let!の変換

returnの変換

変換を出力する

Quote変換

コンピュテーションビルダーに機能を後付けする

型拡張として機能を追加

拡張メソッドとして機能を追加

exprを出力するコード

実行してみる

結果比較

まとめ

F#のプロパティ

`null`と`None`

`()`

`Nothing`

`Nil`

余談:`object`