为什么 Scala 不使用 try/catch 优化尾调用? [英] Why won't Scala optimize tail call with try/catch?

问题描述

在 最近的 StackOverflow 回答中，我给出了以下递归代码:

def retry[T](n: Int)(fn: => T): T = {尝试 {fn} 抓住 {情况 e 如果 n >1 =>重试(n - 1)(fn)}}

如果我添加 @tailrec 注释，我得到:

<块引用>

无法优化@tailrec 注释的方法重试:它包含一个递归调用不在尾部位置.

我能够破解尾递归替代方案，但我仍然想知道为什么这没有优化.为什么不呢?

解决方案

要进行尾递归优化，必须将其转换为以下内容:

def retry[T](n: Int)(fn: => T): T = {开始:尝试 {fn} 抓住 {情况 e 如果 n >1 =>n = n - 1转到开始}}

当它执行GOTO 循环时，它必须离开catch 块的作用域.但是在原来的递归版本中，递归调用的执行仍然在catch块内.如果语言允许这可能会改变代码的含义，那么这将不是有效的优化.

从评论中与 Rex Kerr 的讨论来看，这是 Scala 中的行为保留转换(但仅当没有 finally 时).很明显，Scala 编译器还没有识别出 catch 块的最后一次调用，其中没有 finally 处于尾调用位置.

In a recent StackOverflow answer, I gave the following recursive code:

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

If I add the @tailrec annotation, I get:

Could not optimize @tailrec annotated method retry: it contains a recursive call not in tail position.

I was able to hack a tail-recursive alternative, but I still wonder why this didn't optimize. Why not?

解决方案

To be tail-recursion optimized, this has to be transformed into something like the following:

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

When it executes the GOTO to loop, it has to leave to scope of the catch block. But in the original recursive version, the execution of the recursive call is still within the catch block. If the language allows that this could ever potentially change the meaning of the code, then this wouldn't be a valid optimization.

EDIT: From discussion with Rex Kerr in the comments, this is a behaviour-preserving transformation in Scala (but only when there is no finally). So apparently it's just that the Scala compiler doesn't yet recognise that the last call of a catch block where there is no finally is in a tail-call position.

这篇关于为什么 Scala 不使用 try/catch 优化尾调用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！