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

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

シャドーイングとは

既存の変数と同名の変数を定義して、そのスコープで既存の変数にアクセスできなくする機能です。 例えば、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:「再帰関数は」と書きましたが、再帰ではない単なる関数呼び出しも同様です。

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

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オプションを使うこともできます

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

連載目次

• 再帰関数のスタックオーバーフローを倒す話 その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.プレフィックスが付いていません

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

連載目次

• 再帰関数のスタックオーバーフローを倒す話 その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:このような関数値のツールチップを表示させると、括弧で囲まれています

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

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

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系統のデリゲート型など