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