Kotlin1.4と末尾再帰と継承

f:id:Juju_62q:20191219010400p:plain

この記事はKotlin Advent Calendar 2019 15日目の記事です。また、OpenSaaS Studio Advent Calendar 2019 18日目の記事としてクロスポストをしています。

GraalVMの話を書くと言いましたが、あれは嘘です。

TL;DR

11/20ごろから Tailrec on open members is deprecated と言う警告が出るようになった
末尾再帰の関数には final 修飾子か拡張にするなどして継承できないようにする必要がある
末尾再帰関数を継承してoverrideした場合にバグが混入する場合がある
Kotlin 1.4以降では末尾再帰関数は継承できない状態にしないとコンパイルできない

ことの始まり

11/21日にInteliJ IDEAのKotlin Pluginを1.3.60へアップデートしました。すると今までなにも出ていなかった末尾再帰関数に Tailrec on open members is deprecated と言う警告が表示されるようになりました。これはなんなんだ。調べてもあまりいい感じの解説記事は出てきません。ちょっと深入りしてみました。

Kotlinにおける末尾再帰

末尾再帰関数は一般的に事実上ループのような実行へ最適化可能であることが知られています。一般的な再帰関数は一見にしてコードの見通しが良いことが多く理解が容易である一方、プログラムのリソース効率はあまり良くありません。これは再帰がスタックにより実現されていることに起因していて、再帰が深くなるごとに引数やローカル変数、プログラムカウンタなどがスタック領域に保存されるのが原因です。

一方、返り値で再帰しているような再帰関数（これを末尾再帰関数と呼ぶ）では再帰呼び出しの際に現在の状態を保持する必要がありません。よってスタック領域に状態を保持せず、ループのようにプログラムを実行することが可能です。

この辺りについては京都大学の授業資料が詳しいので必要に応じてみてください。

www.fos.kuis.kyoto-u.ac.jp

Kotlinでは末尾再帰関数を記述した場合に最適化するための機能が存在します¹。それが tailrec と言う修飾子です。関数の前に tailrec とつけるだけで最適化が行われます。簡単ですね。

では例を見てみます。

tailrec fun gcd(a: Int, b: Int): Int =
    if ( a % b == 0) b
    else gcd(b, a % b)

こんな感じでつけるとまあいい感じにスタック領域を食い潰さず、スタックオーバフローをあまり恐れることなく再帰の実行ができます。つまりループの実行効率の良さと再帰関数の見通しの良さが同時に得られるわけですね。いい話です。

Tailrec on open members is deprecated

話を戻して警告を見ます。

直訳すると、

継承可能な末尾再帰なメンバ（関数やフィールド）は非推奨です

警告の識別子でぐぐるとKotlinのソースコードにぶつかります。

github.com

ソースコードをよむとテストケースがあったりして final を関数につけるなりして、明示的に関数が継承不能なことを表現すれば警告は回避できるみたいです。関数がどのクラスに所属していて、そのクラスが継承可能かどうかと言うのは見ていないみたいです。

なんとなく警告の回避策はわかりました tailrec fun hoge を final tailrec fun hoge としてあげたら当然自明に継承不能になるのでまあなんとなく警告を回避できます。

しかしコードに経緯や経緯は書いて見つけられませんでした。なぜ末尾再帰関数は継承できてはいけないのだろう。。。🤔

例えばこの行をblameしてcommitを炙り出しても、いまいち自分は理解できませんでした。

github.com

理由

Kotlinの言語としての不具合です。

下記は該当ISSUEです

https://youtrack.jetbrains.com/issue/KT-18541/youtrack.jetbrains.com

ISSUEの例をそのまま引用します

tailrecがある場合のコードと実行結果

open class A {
    open tailrec fun foo(count: Int) { // Note: open & tailrec modifiers
        println("A.foo($count)")
        if (count > 0) foo(count - 1)
    }
}

class B : A() {
    override fun foo(count: Int) {
        println("B.foo($count)")
    }
    
    fun callSuperFoo(count: Int) = super.foo(count)
}

fun main(args: Array<String>) {
    B().callSuperFoo(1)
}

---
A.foo(1)
A.foo(0)

tailrecがない場合のコードと実行結果

open class A {
    open fun foo(count: Int) { // Note: open & tailrec modifiers
        println("A.foo($count)")
        if (count > 0) foo(count - 1)
    }
}

class B : A() {
    override fun foo(count: Int) {
        println("B.foo($count)")
    }
    
    fun callSuperFoo(count: Int) = super.foo(count)
}

fun main(args: Array<String>) {
    B().callSuperFoo(1)
}

---
A.foo(1)
B.foo(0)

なるほど。ほぼ同じプログラムなのに結果に違いがありますね。

Javaの世界ではオーバライドされる関数は仮想メソッドとなるのが基本的な挙動です。仮想メソッドは基本的に継承先で書き換えられることが前提となります。よって、 super のように明示的に親クラスのプログラムを呼ぶ行為をしない場合継承先の実体としての関数が動くというのが正しいということになります。今回の例の場合後者の例であるように明示的に super を指定していない二度目の呼び出しの場合 B.foo が呼び出されるのが正しいわけです。

一方、 tailrec 修飾子を使っている実行例ではどちらも A.foo が表示されていると言うことが見て取れます。これは末尾再帰による最適化の結果、ループのような形で処理が行われ、明示的に呼び出していないのにも関わらず仮想関数の呼び出しが行われたというのが原因です。つまり、最適化と仮想関数の概念がコンフリクトした結果Javaの設計した通りの結果が得られなくなったわけですね。

このバグを防ぐために末尾再帰の関数は明示的に継承を禁止するというのがKotlin 1.4の言語仕様として決定されました。原因がわかるとスッキリしますね。めでたしめでたし。

まとめ

末尾再帰関数と仮想関数の概念が絶妙にぶつかってKotlin 1.4以降では末尾再帰関数について明示的に継承を禁止する必要が生まれました。たまに自分が使っている言語の言語使用や、実装のリポジトリを見るのもいいものだなあと思いました。皆さん自分が使っている言語の言語仕様についてどのくらい理解していますか？正直自分はJavaの仮想関数の下りから初めて知ったので今回得たものは非常に多かったなと思いました。たまには言語のリポジトリを眺めるのもいいものですね。