什么是“有效尾递归”？

Question

《FP in Scala》第七章讲解如何创建用于处理并发的纯函数式库。为此，它定义了一种类型

type Par[A] = ExecutorService => Future[A]

以及一组有用的函数，如fork函数

def fork[A] (a: => Par[A]): Par[A] = 
 es => es.submit(new Callable[A] {
  def call = a(es).get
 })

其中一项练习涉及到具有以下签名的函数序列。

def sequence[A](ps: List[Par[A]]): Par[List[A]]

使用foldRight的解决方案很直接。然而，作者还包括了另外两个版本作为答案，其中一个陈述如下：

// This implementation forks the recursive step off to a new logical thread,
// making it effectively tail-recursive. However, we are constructing
// a right-nested parallel program, and we can get better performance by 
// dividing the list in half, and running both halves in parallel. 
// See `sequenceBalanced` below.
def sequenceRight[A](as: List[Par[A]]): Par[List[A]] = 
  as match {
    case Nil => unit(Nil)
    case h :: t => map2(h, fork(sequenceRight(t)))(_ :: _)
  }

我不太确定“有效地尾递归”是什么意思。从fork的定义中可以清楚地看出它接受一个按名称传递的参数，因此map2(h, fork(sequenceRight(t)))(_ :: _)不会评估第二个参数（直到提供执行器服务）。但这并不能告诉我它为什么“有效地尾递归”。

- Rupam Bhattacharjee

Answer 1

我们来看一个List(a, b, c)，在传递给 sequenceRight 后，它将变成：

map2(
  a,
  fork(
    map2(
      b,
      fork(
        map2(
          c,
          fork(unit(Nil)
        )(_ :: _)
      )
    )(_ :: _)
  )
)(_ :: _)

这并不是真正的尾递归，编译器无法将其视为尾递归。然而，当你评估它将如何执行时:

- `fork` 会将传递给它的任何内容变为异步，因此它会立即返回。 - `map2` 实现不会阻塞执行，直到执行 `fork` 来应用传递给 `map2` 的函数，而是会异步地将在 `fork` 中计算出的结果转换为要插入的值。 - 由于递归是异步完成的，将事物发布到 ExecutorService 并将操作添加到 `Future` 中让你可以像跳板一样处理 ExecutorService+Future。

因此实际发生的是：

- `sequenceRight(List(a,b,c))` 调用 `map2(a,fork(sequenceRight(List(b,c))(_::_)))` - `a` 将在完成时完成，但我们现在就可以将其保持为值。 - `fork(sequenceRight(List(b,c)))` 已经被调度了，但我们并没有等待它完成，我们已经可以将其传递。 - 我们可以创建一个 `Future`，它将组合上述 2 个结果（并返回它），而不需要等待任何一个完成！ - 因此，这个 `Future` 立即返回！它仍在运行，但这个调用已经完成！ - 递归创建的 `Future` 也是同样的情况。 - 一旦 `c` 和 `fork(unit(Nil))` 完成，就会计算出 `rResult :: Nil`。 - 这允许完成 `bResult :: cResult :: Nil`。 - 最终结果的计算也因此得以进行。

换句话说，尾递归是指将递归调用重写为 while 循环以避免堆栈溢出。但如果递归调用返回异步内容，则回溯被移动到 ExecutionServices 和 Futures 的观察者中，因此它们隐藏在堆中。从这个角度来看，它们解决了与尾递归调用相同的堆栈溢出问题，因此“本质上”它们可能被认为是有些相似的。

- Mateusz Kubuszok

---

感谢您详细的回答，非常有帮助！正如您在最后一段指出的那样，关键点在于堆栈是分配在当前线程还是由执行器服务分配给其他线程（因为每个线程都会获得JVM提供的自己的堆栈）。由于fork确保是后者，因此对于调用map2的线程来说，不需要承担分配堆栈帧以存储中间结果的负担，因此对于调用线程来说，它变成了“有效地尾递归”。 - Rupam Bhattacharjee

Answer 2

这绝对不是尾递归，我认为他们知道这点 - 这就是为什么他们加上了“有效地” :).

他们所指的是这个实现不会在递归调用时为堆栈创建额外的帧，这是正确的，因为这些调用是异步发生的，正如你所指出的。

现在，这种情况是否真值得称为“递归”是一个好问题。我不认为有一个单一的公认答案。我个人倾向于“是”，因为递归的定义“引用自身”确实包括了这种情况，而我真的不知道如何定义它，以便异步调用被排除在外，但尾递归不被排除。

顺便说一句，我不是非常精通JavaScript，但我听说“异步递归”这个术语在那里被广泛使用。

- Dima