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

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 
    } 
} 

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

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

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

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

Несколько возможных причин я вижу для этого является случай, являются:

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

2. в Foo функция mod является потеряется в 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 в себя mod звонки, потому что мой объект является Bar, не Foo, вы должны (и делать) перейти к Bar'smod, а не Foo's.

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

Это ПОДТВЕРЖДЕНИЕ подкласса, когда суперкласс вызывает метод сам по себе, если этот метод был переопределен, это будет вызван метод подкласса.

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

Answer 2

IttayD только что задал этот вопрос ранее сегодня. Ответ заключается в том, что хвостовая рекурсия Foo будет оптимизирована только в том случае, если you can't override mod in subclasses (будь то, потому что класс является окончательным или потому, что этот метод является окончательным или приватным.)