Почему компилятор Scala не применяет оптимизацию хвостового вызова, если метод не является окончательным?

Рассмотрим следующее взаимодействие с 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

Теперь давайте переопределим его в подклассе, чтобы удвоить ответ суперкласса:

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, он может не вызывать себя при выполнении рекурсивного вызова.

Вот почему @tailrec не работает, если метод не является окончательным (или закрытым).

ОБНОВЛЕНИЕ: я рекомендую также прочитать два других ответа (Джона и Рекса).

Рекурсивные вызовы могут быть к подклассу, а не к суперклассу; 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}, поскольку расширение не применялось бы.

Поскольку этот вид рекурсии весьма полезен и будет уничтожен, если будут разрешены хвостовые вызовы неокончательных методов, компилятор вместо этого вставляет реальный вызов.

Пусть foo::fact(n, res) обозначает вашу рутину. Пусть baz::fact(n, res) будет обозначать чью-то отмену вашего распорядка.

Компилятор сообщает вам, что семантика позволяет baz::fact() быть оболочкой, которая МОЖЕТ вызвать (?) foo::fact(), если захочет. В таком сценарии правило состоит в том, что foo::fact(), когда он повторяется, должен активировать baz::fact(), а не foo::fact(), и, хотя foo::fact() является хвостовым рекурсивным, baz::fact() не может быть. В этот момент вместо того, чтобы зацикливаться на хвостовом рекурсивном вызове, foo::fact() должен вернуться к baz::fact(), чтобы он мог раскрутиться.

Что именно пошло бы не так, если бы компилятор применил совокупную стоимость владения в таком случае?

Ничего плохого не случится. Любой язык с надлежащим исключением хвостовых вызовов сделает это (SML, OCaml, F #, Haskell и т. Д.). Единственная причина, по которой Scala этого не делает, заключается в том, что JVM не поддерживает хвостовую рекурсию, и обычный прием Scala по замене саморекурсивных вызовов в хвостовой позиции на goto в этом случае не работает. Scala в среде CLR может делать это так же, как F #.

Популярный и общепринятый ответ на этот вопрос на самом деле вводит в заблуждение, потому что сам вопрос сбивает с толку. OP не делает различий между tailrec и TCO, и ответ не касается этого.

Ключевым моментом является то, что требования для tailrec более строгие, чем требования для TCO.

Аннотация tailrec требует, чтобы хвостовые вызовы выполнялись для одной и той же функции, тогда как TCO можно использовать для хвостовых вызовов любой функции.

Компилятор может использовать TCO на fact, потому что есть вызов в хвостовой позиции. В частности, он может превратить вызов к fact в переход к fact, настроив стек соответствующим образом. Не имеет значения, что эта версия fact не совпадает с функцией, выполняющей вызов.

Таким образом, принятый ответ правильно объясняет, почему незавершенная функция не может быть tailrec, потому что вы не можете гарантировать, что хвостовые вызовы относятся к той же функции, а не к перегруженной версии функции. Но это неправильно подразумевает, что использовать TCO в этом методе небезопасно, хотя на самом деле это было бы совершенно безопасно и было бы хорошей оптимизацией.

[Обратите внимание, что, как объяснил Джон Харроп, вы не можете реализовать TCO на JVM, но это ограничение компилятора, а не языка, и не связано с tailrec]

И для справки, вот как можно избежать проблемы, не применяя метод final:

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

    loop(n, 1)
  }
}

Это работает, потому что loop - это конкретная функция, а не метод, и ее нельзя переопределить. Эта версия также имеет преимущество удаления ложного параметра result на fact.

Это шаблон, который я использую для всех рекурсивных алгоритмов.