scala - 为什么 getOrElse 中的 return 使尾递归不可能？

Question

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

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

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

could not optimize @tailrec annotated method listSize: it contains a recursive call not in tail position

类似的代码(在 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)
}

另一方面，稍微修改 map 的代码 是 被编译器拒绝并产生错误:

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

类似于this，这显然不是尾递归:

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) ，但事实并非如此。