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

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

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

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

результаты в

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

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

Источник

4 ответа

Решение

Рассмотрим следующее взаимодействие с 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(), так что он может раскрутиться сам.

Источник

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

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

Источник

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

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

Источник
Другие вопросы по тегам