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

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

17 голосов
/ 23 ноября 2011

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

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

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

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

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

Ответы [ 3 ]

10 голосов
/ 23 ноября 2011

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

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

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

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

7 голосов
/ 23 ноября 2011

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

2 голосов
/ 15 декабря 2016

Я нашел это решение в другом месте на 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)
}
...