"effectively tail recursive" 是什么意思？

Question

Scala 中 FP 的第 7 章介绍了如何创建用于处理并发的纯函数库。为此，它定义了一个类型

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)))(_ :: _) 不会评估第二个参数（直到提供执行程序服务）。但这并没有告诉我它是如何以及为什么“有效地进行尾递归”的。

Answer 1

让我们来点 List(a, b, c)。传入sequenceRight后会变成：

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

这根本不是尾递归，编译器不能将其视为一个。但是，当您评估它的执行方式时：

fork 会让你传递给它的任何东西异步，所以它会立即 return，
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 来组合上面两个的结果（和 return 它），而不用等待它们中的任何一个完成！
因此，Future 立即被 return 编辑！它仍然在运行，但是这个调用已经结束了！
同样适用于递归创建的Futures
一旦 c 和 fork(unit(Nil)) 完成，就会计算 rResult :: Nil
这允许完成 bResult :: cResult :: Nil
这最终允许计算最终结果

换句话说，尾递归指的是递归调用被重写到while循环中以避免堆栈溢出。但是，如果同步进行递归调用，则堆栈溢出只是一个问题。如果你正在 return 进行一些异步操作，那么回溯将被推送给 ExecutionServices 和 Futures 的观察者，因此它们隐藏在堆中。从这个角度来看，它们解决了与尾递归调用相同的堆栈溢出问题，因此“在精神上”它们可以被认为有些相似。

Answer 2

这肯定不是尾递归，我想，他们知道这一点——这就是为什么他们添加了“有效”:)。

他们的意思肯定是此实现不会在堆栈上为递归调用创建额外的帧，这是事实，因为正如您指出的那样，这些调用是异步发生的。

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

顺便说一句，我不是Javascript方面的专家，但我听说术语“异步递归”在那里使用得相当广泛。

"effectively tail recursive" 是什么意思？

What is meant by "effectively tail recursive"?

functional-programming

scala