为什么在getOrElse中返回会导致尾递归不可能？

Question

我对以下代码感到困惑:代码是人为的,但我认为它仍然是尾递归的.编译器不同意并产生错误消息:

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    None.getOrElse( return s )
  }
  listSize(l.tail, s + 1)
}

上面的代码如何使尾部回归不可能？为什么编译器会告诉我:

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

类似的代码(return内部map)编译良好:

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    Some(()).map( return s )
  }
  listSize(l.tail, s + 1)
}

即使通过内联获得的代码None.isEmpty编译也很好:

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    if (None.isEmpty) {
      return s
    } else None.get
  }
  listSize(l.tail, s + 1)
}

在另一方面,用稍微修改的地图代码是由编译器拒绝,并且产生错误:

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    Some(()).map( x => return s )
  }
  listSize(l.tail, s + 1)
}

Answer 1

发生这种情况是因为return您的第一个代码片段中的 是非本地代码片段（它嵌套在 lambda 内）。Scala 使用异常来编译非局部return表达式，因此编译器将代码转换为：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    None.getOrElse( return s )
  }
  listSize(l.tail, s + 1)
}

与此类似的东西（用 编译scalac -Xprint:tailcalls）：

def listSize2(l : Seq[Any], s: Int = 0): Int = {
  val key = new Object

  try {
    if (l.isEmpty) {
      None.getOrElse {
        throw new scala.runtime.NonLocalReturnControl(key, 0)
      }
    }

    listSize2(l.tail, s + 1)
  } catch {
    case e: scala.runtime.NonLocalReturnControl[Int @unchecked] =>
      if (e.key == key)
        e.value
      else
        throw e
  }
}

最后一点是，当包装在 try/catch 块中时，递归调用不是尾部调用。基本上，这个人为的例子：

def self(a: Int): Int = {
  try {
    self(a)
  } catch {
    case e: Exception => 0
  }
}

与此类似，这显然不是尾递归：

def self(a: Int): Int = {
  if (self(a)) {
    // ...
  } else {
    // ...
  }
}

在某些特定情况下，您可以对此进行优化（如果不是一个，则减少到两个堆栈帧），但似乎不存在适用于这种情况的通用规则。

此外，return此代码片段中的表达式不是非本地表达式return，这就是可以优化该函数的原因：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    // `return` happens _before_ map `is` called.
    Some(()).map( return s )
  }
  listSize(l.tail, s + 1)
}

上面的代码之所以有效，是因为在 Scala 中，return e它是一个表达式，而不是一个语句。不过，它的类型是Nothing，它是所有内容的子类型，包括Unit => X，它是 map 参数所需的类型。虽然评估非常简单，但在执行e之前就从封闭函数返回map（显然，参数在方法调用之前评估）。这可能会令人困惑，因为您希望map(return e)被解析/解释为map(_ => return e)，但事实并非如此。