Kotlin Advenent Calender 2013 に勢いで参加してしまった Ziphil です。
19 日目のエントリーになります。 せっかく Kotlin について何か書くんだし、 Kotlin じゃないとできないようなことについて書きたかったんですが･･･、 いまいち思いつきませんでした! ･･･ということで、 12 月 6 日にリリースされた Kotlin M6.2 での新機能、 末尾再帰最適化についてもう少し詳しくまとめてみようと思います。 少し詳しめに書いたので、 もともとこれについて知ってる人は、 特に得るものはないかもしれません･･･。
さて、 「末尾再帰」 とは、 とあるサブルーチン内の最後の命令として、 他のサブルーチンが呼ばれることです。 つまりは、 こんな感じのコードですね!
fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
if (n < 1) {
return a
}
return fibonacci(n - 1, b, a + b)
}
フィボナッチ数を求めるコードでーす。 if 文で場合分けされているものの、 関数 fibonacci の 1 回分で最後に実行されるのは、 関数 fibonacci そのものになっています。 関数型言語なんか (Scala とか) では、 こういう書き方の方が好まれますね!
で、 この末尾再帰にはちょっとした問題があるんですが･･･。 例として、 fibonacci(4) を考えてみましょうか。 Kotlin は、 4 番目のフィボナッチ数を、 こんな感じで順に計算します。 ･･･あ、 計算するのは JVM ですけど、 Kotlin が計算してるって考えた方がかわいいですよね!
- fibonacci(4)
- fibonacci(3, 1, 1)
- fibonacci(2, 1, 2)
- fibonacci(1, 2, 3)
- fibonacci(0, 3, 5)
- 3
さて、 こんな感じでようやく 3 が得られます。 ちょっとした問題というのは、 この計算の中に潜んでいます。
fibonacci(4) が呼ばれると、 Kotlin は fibonacci(3, 1, 1) を返そうとしますが、 この値は分かっていません。 そこで、 Kotlin は 「fibonacci(3, 1, 1) の値を計算し終わったら、 その値を関数の返り値として返すぞー」 ということを覚えておいて、 fibonacci(3, 1, 1) の値を求めにいきます。 すると、 今度はその結果は fibonacci(2, 1, 2) で、 これも値が分かっていないので、 Kotlin はまた 「fibonacci(2, 1, 2) の値が分かったら、 それを返すぞー」 と覚えておきます。
とまあ、 こんな風に、 再帰的に fibonacci が呼ばれるたびに、 Kotlin は 「あれを求めた結果を返そう」 と頭に覚えるわけですが、 fibonacci(100) を実行しようと言われちゃったら、 もう頭がパンパンになって破裂しちゃうわけですよ。 ちなみに、 こういうのを 「スタックオーバーフロー」 と言ったり言わなかったり･･･。 とにかく、 困りますねー。
そこで、 M6.2 から新しく実装された 「末尾再帰最適化」 が便利なんですね。 これによって、 Kotlin が頭の中に覚えておくべき内容が減って、 fibonacci(100) でも楽々計算できるようになるわけです。 Kotlin がより賢くなるのです。 やったね!
末尾再帰最適化の使い方はこうです。
tailRecursive fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
if (n < 1) {
return a
}
return fibonacci(n - 1, b, a + b)
}
はい、 アノテーション tailRecursive をつけるだけ! 簡単でしょ?
これで本当に頭がパンパンにならずに計算できるようになったのかなぁ? ･･･と疑いの目を向けている方もいるかもしれませんね。 じゃ、 コンパイルされたバイトコードを逆コンパイルしてみましょう。 どうなってるでしょうか。
まずは、 tailRecursive アノテーションをつけず、 最適化をしなかった場合のバイトコードです。 ちなみに、 デフォルト引数の処理は別の関数を介しているみたいで、 その部分は省略したので、 下のコードはデフォルト引数の情報がなくなってます。 あ、 それと、 読みやすいように多少コードを整形してあります。
public static final int fibonacci(int n, int a, int b) {
if (n < 1) {
return a;
} else {
return fibonacci(n - 1, b, a + b);
}
}
･･･見事にそのまんまですね! まあ、 そりゃそうなんですけど。
じゃ、 次に tailRecursive アノテーションをつけて、 最適化をした場合のバイトコードです。 こんな感じー。
public static final int fibonacci(int n, int a, int b) {
do {
if (n < 1) {
return a;
}
b = a + b;
a = b;
n = n - 1;
} while (true);
}
お? do ～ while ループが入ってますねー。 これによって、 「これを計算したらこれを返す」 とかいう無駄な記憶をせずに、 単にループをこなすだけでよくなるわけです。
ちなみに、 末尾再帰最適化をすると、 使用するスタックの量を節約できるだけでなく、 速度も向上するようです。 最適化をする場合としない場合とで、 50 番目のフィボナッチ数を計算してみると、 私の環境では最適化をした方が 40 倍も速いことが分かりました。
ところで、 疑問に思った方もいるんじゃないでしょうか? 末尾再帰してる関数があったら、 Kotlin が自動的に最適化してくれれば良いのにー、 とか。 いちいち tailRecursive とか面倒だよー、 とか。 公式ブログにちゃんと説明が書いてありました。
デバッグのためです。 末尾再帰が最適化された関数では、 実際に再帰呼び出しがされるわけではないので、 デバッガによって、 再帰されていることを示すスタックフレームが残されず、 再帰の前段階におけるローカル変数について詳しく調べることができなくなります。 したがって私たちは、 このことに対する最も普通な解決策は、 それをコード内で明示的に行うことだと思っています。
それともう 1 つ。
安全性のためです。 皆さんがよく知っているように、 コードというものは、 行うだろうと予想される処理を行わないことがありますよね (≧∇≦)。 同じことが末尾再帰に対しても成り立ち、 末尾再帰のような関数呼び出しが、 実はそうでなかったということもよくあります。 これによって、 最適化がなされずパフォーマンスの向上が妥協されてしまいます。 しかし、 tailRecursive アノテーションによって、 コンパイラは、 どの関数呼び出しが最適化されるべきか分かり、 間違いがあった場合は警告を発することができるのです。
･･･ということで、 アノテーションは省略できないようになったわけですね。
さて、 こんな感じで、 Kotlin の末尾再帰最適化について書いてみましたー。 Kotlin を知ったのが最近であるという上に、 この最適化処理を知ったのも最近なので、 至らない部分など多いと思いますが、 温かい目で見守ってください･･･。
