Почему Scala не оптимизирует хвостовой вызов с помощью try / catch?

В недавнем ответе StackOverflow я дал следующий рекурсивный код:

def retry[T](n: Int)(fn: => T): T = {
  try {
    fn
  } catch {
    case e if n > 1 =>
      retry(n - 1)(fn)
  }
}

Если я добавлю аннотацию @tailrec, я получу:

Не удалось оптимизировать повторную попытку аннотированного метода @tailrec: он содержит рекурсивный вызов не в хвостовой позиции.

Мне удалось взломать альтернативу с хвостовой рекурсией, но я все еще удивляюсь, почему она не оптимизировалась. Почему нет?


try-catch scala tail-recursion
person leedm777    schedule 22.11.2011    source источник
comment
Если (n ›1) - действительно? Не n ›0 или n› = 1? А что будет, если n == 1 (== 0)?   -  person user unknown    schedule 23.11.2011
comment
@user unknown - Очевидно, вы передаете общее количество попыток, а не количество повторных попыток.   -  person Rex Kerr    schedule 23.11.2011

Ответы (3)


arrow_upward
10
arrow_downward

Чтобы оптимизировать хвостовую рекурсию, это должно быть преобразовано во что-то вроде следующего:

def retry[T](n: Int)(fn: => T): T = {
  START:
    try {
      fn
    } catch {
      case e if n > 1 =>
        n = n - 1
        GOTO START
    }
}

Когда он выполняет цикл GOTO to, он должен выйти в область действия блока catch. Но в исходной рекурсивной версии выполнение рекурсивного вызова все еще находится в блоке catch. Если язык допускает, что это может когда-либо потенциально изменить смысл кода, то это не будет допустимой оптимизацией.

РЕДАКТИРОВАТЬ: Из обсуждения с Рексом Керром в комментариях, это преобразование Scala, сохраняющее поведение (но только когда нет finally). Таким образом, очевидно, что компилятор Scala еще не распознает, что последний вызов блока catch, в котором нет finally, находится в позиции хвостового вызова.

person Ben    schedule 22.11.2011
comment
Слишком много предположений, слишком много ложных. Байт-код - это не проблема. Байт-код даже не понимает блоки catch, а только цель для исключений в блоке try. Спецификации обработки исключений не влияют на это преобразование; просто попробуйте переписать его как цикл while! - person Rex Kerr; 23.11.2011
comment
@Rex Я рад, что меня поправит кто-то, кто знает больше о байт-коде Java, но я сформулировал это как предположение. Я не уверен, что понимаю ваше последнее замечание. Преобразование хвостовой рекурсии заключается в автоматическом переписывании кода во что-то вроде цикла while, а хвостовая рекурсия, имеющая место в блоке catch, явно мешает компилятору сделать это. Либо это просто функция, которая не была реализована, либо спецификации для обработки исключений действительно влияют на это преобразование. Или я вас неправильно понял? - person Ben; 23.11.2011
comment
Это функция, которая еще не реализована. Нет случая, когда поведение могло бы отличаться, если бы вы переместили прыжок за пределы блока catch (при условии правильной логики) в этом случае. Эквивалентный итеративный код var i = n; while(true) { try { return(fn) } catch { case e if i>1 => i -= 1; } }. - person Rex Kerr; 23.11.2011

arrow_upward
7
arrow_downward

Я не думаю, что список реализованных преобразований для перевода кода в хвостовую рекурсивную форму включает обход блоков обработки исключений. Это особенно сложно, даже если вы можете привести (как и у вас) примеры того, где это должно быть законно. (Есть много случаев, которые выглядят законными, но не являются (например, если есть блок finally) или требуют значительно более сложных правил наматывания / разматывания.)

person Rex Kerr    schedule 22.11.2011

arrow_upward
2
arrow_downward

Я нашел это решение в другом месте на SO. По сути, используйте return с fn, чтобы, если fn вернул без исключения, ваша функция тоже. Если fn вызывает выброс и исключение соответствует условию n > 1, то исключение игнорируется и рекурсивный вызов происходит после блока catch.

@tailrec
def retry[T](n: Int)(fn: => T): T = {
  try {
    return fn
  } catch {
    case e if n > 1 => // fall through to retry below
  }
  retry(n - 1)(fn)
}
person Landon Kuhn    schedule 15.12.2016