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

Question

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

Например, это:

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

приводит к

ошибка: не удалось оптимизировать аннотированный метод @tailrec: он не является ни частным, ни конечным, поэтому может быть переопределен

Что именно может пойти не так, если компилятор применил TCO в таком случаекак это?

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

Пусть foo::fact(n, res) обозначает вашу рутину. Пусть baz::fact(n, res) обозначает чье-то переопределение вашей рутины.

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

Answer 4

Популярный и принятый ответ на этот вопрос на самом деле вводит в заблуждение, потому что сам вопрос сбивает с толку. В ОП не проводится различие между 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.

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

Answer 5

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

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