Скала и хвост рекурсия

Question

Существуют различные ответы о переполнении стека, которые объясняют условия, при которых возможна хвостовая рекурсия в Scala .Я понимаю ограничения и как и где я могу воспользоваться хвостовой рекурсией.Часть, которую я не понимаю, заключается в том, почему существует ограничение на частные или конечные методы.

Я не исследовал, как компилятор Scala на самом деле преобразует рекурсивную функцию в нерекурсивную на уровне байт-кода, нодавайте предположим, что он делает что-то вроде следующего.У меня есть класс Foo с рекурсивной функцией mod:

class Foo {
  def mod(value: Int, denom: Int): Int = {
    if(denom <= 0 || value <= 0) 0
    else if(0 <= value && value < denom) value
    else mod(value - denom, denom)
  }
}

Это базовая функция по модулю, которая, как мне кажется, компилятор Scala переводит в какую-то псевдо-Java-Scala, например:

class Foo {
  def mod(value: Int, denom: Int): Int = {
    if(denom <= 0 || value <= 0) return 0
    while(value > denom) value -= denom
    return value
  }
}

(я могу поверить, что я испортил этот перевод, но я не думаю, что детали важны ..)

Так что теперь предположим, что я подкласс Foo:

class Bar extends Foo {
  def mod(value:Int, denom: Int): Int = 1
}

Что мешает этому работать?Когда у JVM есть Foo/Bar и вызывается mod, почему возникает проблема с разрешением функции mod, которую следует использовать.Почему это отличается от ситуации, когда базовая функция нерекурсивна?

Вот несколько возможных причин, по которым я вижу это:

1. дляпо какой-то причине реализация компилятора Scala не справляется с этим (достаточно справедливо, если это так. Если да, есть ли планы изменить это?)

2. в Foomod функция превращается в mod-non-recursive во время компиляции, поэтому Foo на самом деле не имеет mod метода для переопределения.

Answer 1

Я только что ответил, но давайте возьмем ваш собственный пример. Допустим, вы определили этот класс Foo и сделали его доступным в виде файла JAR.

Затем я получаю этот файл Jar и расширяю ваш Foo следующим образом:

class Bar extends Foo {
  def mod(value:Int, denom: Int): Int = {
    Logger.log("Received mod with "+value+" % "+denom)
    super.mod(value, denom)
}

Теперь, когда Foo's mod вызывает себя, потому что мой объект Bar, а не Foo, вы должны (и делаете) перейти к Bar's mod, а не к Foo-х.

И поскольку это правда, вы не можете оптимизировать его так, как показали.

ДОГОВОР подкласса заключается в том, что когда суперкласс вызывает метод для самого себя, если этот метод был переопределен, это будет метод подкласса, который нужно вызвать.

Объявляя метод private, делающий его final или класс - или даже делая рекурсивную функцию вместо метода, все гарантируют, что вам потенциально не придется переходить к реализации подкласса.

Answer 2

IttayD только что задал этот вопрос сегодня утром. Ответ заключается в том, что хвостовая рекурсия Foo будет оптимизирована только в том случае, если вы не можете переопределить мод в подклассах (будь то потому, что класс является финальным, или потому что метод является финальным или закрытым.)