tail.の復活
昨日のエントリで、いらない子扱いされてしまって、枕に涙を塗らしていた*1tail.プレフィクス。F♯のコンパイラオプションでは明示しなければ使ったもらえず、以下のようなコードの場合でも、スタックフレームを1個除去できるかどうかだけで、ほぼあんたの居場所ね−からと言われかねない状況だった。
let tailCallSum n=
let rec sum accum n=if n=0L then accum else sum (n+accum) (n-1L)
sum 0L n;;
printfn "%d" (tailCallSum 100);;この場合、再帰するのは内側の”sum”であり、これを、C♯風に無理矢理かくってーと以下のような感じ*2
using System; static class Program { static void Main() { //やってみた感じ、tail.が適用出来そうな場合でも、 //こっちの呼び出しには、tail.は付かない模様。 Console.WriteLine(tailCallSum(100L)); } static long tailCallSum(long n) { //この呼び出しが、tail.になるかどうかだけ。 return sum(0, n); } static long sum(long accum, long n) { //引数を使っちまってますが、その辺はご愛敬。 //モノの見事にループ展開されている。 while (n != 0L) { accum += n--; } return accum; } }
これからわかるように、外側の"tailCallSum"が内側の"sum"を呼び出すときに、tail.が付くかどうかと言うだけで、sumの内部は、昨日と同様なループ展開がされていると。
こうなってしまうと、tail.のありがたみはほぼほぼ無いと言えなくも無い。
復活の狼煙
このまま、本当にいらない子になってしまうのか？と言うと、さに非ず。相互再帰の場合、生きてくるコトがある。
相当に作為的だけど、この関数を相互再帰で書き直してみると以下の通り。
let rec mutalSumA accum n=if n=0L then accum else mutalSumB (n+accum) (n-1L) and mutalSumB accum n=if n=0L then accum else mutalSumA (n+accum) (n-1L);; printfn "%d" mutalSumA 0 100L;; printfn "%d" mutalSumB 0 100L;;
中身は、ご覧の通り全く同じコトをしてるmutalSumAとmutalSumBを相互的に呼び出している。で、このコンパイル結果を先ほどの通り、意訳してC#で書くと以下の通り。
using System; static class Program { static void Main() { //やってみた感じ、tail.が適用出来そうな場合でも、 //こっちの呼び出しには、tail.は付かない模様。 Console.WriteLine(mutalSumA(0L, 100L)); Console.WriteLine(mutalSumB(0L, 100L)); } static long mutalSumA(long accum,long n) { if (n == 0) return accum; return mutalSumB(accum + n, --n); } static long mutalSumB(long accum, long n) { if (n == 0) return accum; return mutalSumA(accum + n, --n); } }
先の例とは異なり、ループ展開されていない。
と言うことは・・・*3
当然、スタックオーバーフローを起こす程度にでかい数食わせてみたくなる。
あたしの環境*4だと、概ね100,000食わせると、落ちてくれることがわかってるので,コンパイラオプションの“tail呼び出しの生成”の有無で実行結果に差が出るか、調べてみた。
let rec mutalSumA accum n=if n=0L then accum else mutalSumB (n+accum) (n-1L) and mutalSumB accum n=if n=0L then accum else mutalSumA (n+accum) (n-1L);; printfn "%d" mutalSumA 0 100000L;; printfn "%d" mutalSumB 0 100000L;;
その結果は、予想通り、“tail呼び出しの生成”がチェックされている場合は、何の問題も無く、実行された。けどチェックを外した場合、StackOverFlowExpceptionが発生してこけた。
