46

メソッドがfinalでない限り、Scalaコンパイラが末尾呼び出しの最適化を適用しないのはなぜですか？

たとえば、これは次のとおりです。

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

結果は

エラー：@tailrec注釈付きメソッドを最適化できませんでした：プライベートでもファイナルでもないため、オーバーライドできます

このような場合にコンパイラがTCOを適用した場合、正確には何がうまくいかないでしょうか。

4

5 に答える 5

56

REPLとの次の相互作用を検討してください。まず、階乗メソッドを使用してクラスを定義します。

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

次に、サブクラスでオーバーライドして、スーパークラスの答えを2倍にします。

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

この最後の電話でどのような結果を期待しますか？あなたは240を期待しているかもしれません。しかし、違います：

scala> (new C2).fact(5, 1)
res13: Int = 7680

これは、スーパークラスのメソッドが再帰呼び出しを行うときに、再帰呼び出しがサブクラスを通過するためです。

240が正解であるようにオーバーライドが機能した場合、ここのスーパークラスで末尾呼び出しの最適化を実行しても安全です。しかし、それはScala（またはJava）の仕組みではありません。

メソッドがfinalとマークされていない限り、再帰呼び出しを行うときにメソッド自体を呼び出さない可能性があります。

そのため、メソッドがfinal（またはプライベート）でない限り、@tailrecは機能しません。

更新：他の2つの回答（ジョンとレックス）も読むことをお勧めします。

于 2011-01-24T18:25:20.637 に答える
23

再帰呼び出しは、スーパークラスではなくサブクラスに対して行われる場合があります。finalそれを防ぎます。しかし、なぜその動作が必要になるのでしょうか? フィボナッチ数列は手掛かりを提供しません。しかし、これは：

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

Pretty 呼び出しが末尾再帰の場合{Set(0, 1),1}、拡張機能が適用されないため、代わりに出力します。

この種の再帰はもっともらしく有用であり、非最終メソッドの末尾呼び出しが許可されている場合は破棄されるため、コンパイラは代わりに実際の呼び出しを挿入します。

于 2011-01-24T18:39:11.417 に答える
7

foo::fact(n, res)あなたのルーチンを示しましょう。baz::fact(n, res)他の誰かがあなたのルーチンをオーバーライドすることを示しましょう。

コンパイラは、セマンティクスがbaz::fact()ラッパーになることを許可し、必要に応じてupcall (?)することができることを伝えていますfoo::fact()。このようなシナリオでは、ルールは、 が再帰する場合、ではなくfoo::fact()アクティブ化する必要があり、 whileは末尾再帰的であり、アクティブ化されない可能性があります。その時点で、末尾再帰呼び出しでループするのではなく、 に戻る必要があるため、巻き戻すことができます。baz::fact()foo::fact()foo::fact()baz::fact()foo::fact()baz::fact()

于 2011-01-24T18:26:06.967 に答える
1

このような場合にコンパイラが TCO を適用すると、正確には何が問題になるのでしょうか?

何も問題はありません。テール コールを適切に削除できる言語であれば、これを行うことができます (SML、OCaml、F#、Haskell など)。gotoScala がサポートしない唯一の理由は、JVM が末尾再帰をサポートしておらず、この場合、末尾位置の自己再帰呼び出しを置換するという Scala の通常のハックが機能しないことです。CLR 上の Scala は、F# と同じようにこれを行うことができます。

于 2013-08-12T21:05:16.300 に答える