~スマートフォン用の表示で見るスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。前回はCPS変換することでスタックオーバーフローが回避できるよやったー!という話でした。今回は、CPS変換じゃスタックオーバーフロー回避できない場合もあるよ、という話をします*1。前提知識は、その1の記事を理解していることと、ILがなんとなくわかることです。読んでいるに越したことはありません。CPS変換のおさらい非末尾再帰の関数を末尾再帰化できる、というのがCPS変換でした。末尾呼び出しの最適化によってスタックが食いつぶされなくなるので、スタックオーバーフローが起きなくなるようにできる、というものでした。2種類の末尾呼び出しの最適化さて、実はF#では末尾呼び出しの最適化は2つのパターンがあります。一つ目はジャンプ命令への書き換えで、もう一つはtail.プレフィックスの付与です。ジャンプ命令への書き換えジャンプ命令への書き換えは、呼び出しをbr系のIL命令に書き換えてしまうものです。1)このようなアキュムレータ変数を使った末尾再帰関数をコンパイルすると、以下のようなILが吐かれます。無条件でIL_0000にジャンプこのコードには、call系の命令がないことが分かります。IL_0000)、これが元のコードだと再帰呼び出し部分に相当します。ILでは分かりにくい、という人向けに、上記ILをF#風言語で表現してみました。accこのように、末尾再帰呼び出しをジャンプ命令に置き換えることで、ループと等価になりました*2。自分自身を末尾で呼び出す再帰関数*3の場合、関数から戻ってきた後にすることがないということは、(引数の状態を更新してから)関数の先頭にジャンプしてもいいと言うことです。tail.プレフィックスの付与tail.プレフィックスの付与は、末尾呼び出しされているcall系の呼び出し命令にtail.というプレフィックスを付けることで、JITコンパイラの最適化によってスタックフレームを消費しないようにしてもらうものです。cont)このような継続渡しスタイルの関数を「末尾呼び出しの生成」オプションをオンにしてコンパイルすると、以下のようなILが吐かれます。無条件でIL_0000にジャンプ基本的な構造は同じですが、少し複雑になっています。アキュムレータ変数による末尾再帰関数の例と同様にF#風の言語で表現してみるとこうなります。1ループの中でcontをネストさせていき、関数の最後でcontに1を渡していることが分かります。再帰部分の処理は、fact@22というクラス*4に行ってしまい、このコードだけでは読み取れなくなりました。fact@22というクラスをまずはF#風の言語で表現してみます。n)このように、本体の処理はInvokeメソッド内に移動しています。InvokeメソッドのILはこのようになっています。実行した結果を返して関数終了さて、ここでfact本体のIL_0006とInvokeのIL_000fを見てみましょう。tail.というILが発行されていることが分かります。このILが発行された後に続くcall系の呼び出しは、JITコンパイラによって現在のスタックフレームを再利用*5するようにして実行されるようになります。2つの最適化の違いなぜ末尾呼び出しの最適化に2種類の方法があるのでしょうか?それは、両者の性質が大きく異なるためです。前者のジャンプ命令に変換する方法ですが、br系の命令はメソッド内の移動にしか使えません。そのため、メソッドをまたぐようなジャンプはできず、CPSで現れるようなラムダ式を表すクラスのメソッドへのジャンプはできません。それに対して、tail.プレフィックスを付与する方法は、call系のメソッドが末尾で呼び出されていれば別のクラスのメソッド呼び出しであろうが有効です。本当に呼び出しが最適化されるかどうかの保証をF#の処理系レベルで担保することができません*6。その1.5でみましたが、コンストラクタ呼び出し(newobj)は末尾呼び出しの最適化対象ではありません*7。そのため、ループごとにコンストラクタ呼び出しが走ることになります。これは、F#ではtail.プレフィックスを用いた最適化よりもジャンプ命令に変換する最適化の方が効率が良いことを意味します。tail.プレフィックスでスタックオーバーフローになる場合tail.プレフィックスが付いているコードであっても、スタックオーバーフローを起こす場合があります。原因はわかっていないのですが、(式木の変換のような)それなりに大きい再帰関数をCPS変換64bitのIIS上で実行というような状況で、リビルド後の初回のアタッチでスタックオーバーフローが起きました。小さくて単純な再帰関数をCPS変換してもオーバーフローは起きませんでした。一般的に32bit環境ではスタックフレームのサイズが64bit環境よりも小さくなるため、スタックオーバーフローを起こしにくくなる可能性はあります。いうことで、特定の条件下ではCPS変換によってスタックオーバーフローを防ぐことができない場合もあるため、F#においてはCPS変換したからと言って完全に安全とは言い切れない、という話でした。「特定の条件」がまだ定かではないので、調査は継続しますが、今のところIISでホストしない場合には再現しませんので、非Webアプリであれば問題ないかもしれません。次回の「その3」がおそらく最後で、ではどうやってスタックオーバーフローを倒せばいいか、の予定です。Blog|ブログを報告する。