scala - 为什么 Haskell 不需要蹦床？

Question

作为 Scala 开发人员学习 IO Monad，因此一般来说 Trampolining 的技术对于无法进行尾调用优化的递归来说是必需的，我想知道 Haskell 似乎是如何自然地避免它的。
我知道 Haskell 是一种懒惰的语言，但是我想知道是否有人可以进一步详细说明。
例如，为什么 ForeverM stackoverflow 不在 Scala 中？好吧，我可以回答蹦床，我可以在库和博客中找到执行此操作的实际代码。我实际上自己实现了一个基本的蹦床来学习。
它在 Haskell 中是如何发生的？有没有办法稍微解开懒惰，提供一些指示，也许还有有助于更好地理解它的文档？

sealed trait IO[A] {

.....


  def flatMap[B](f: A => IO[B]): IO[B] =
    FlatMap[A,B](this, f) // we do not interpret the `flatMap` here, just return it as a value
  def map[B](f: A => B): IO[B] =
    flatMap[B](f andThen (Return(_)))

}
case class Return[A](a: A) extends IO[A]
case class Suspend[A](resume: () => A) extends IO[A]
case class FlatMap[A,B](sub: IO[A], k: A => IO[B]) extends IO[B]

......

@annotation.tailrec
def run[A](io: IO[A]): A = io match {
  case Return(a) => a
  case Suspend(r) => r()
  case FlatMap(x, f) => x match {
    case Return(a) => run(f (a))
    case Suspend(r) => run(f( r()))
    case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
  }
}

Answer 1

函数式编程通常需要消除尾调用(否则函数调用的深层链会溢出堆栈)。例如，考虑这个偶数/奇数分类器的(效率极低的)实现:

def even(i: Int): Boolean =
  if (i == 0) true
  else if (i > 0) odd(i - 1)
  else odd(i + 1)

def odd(i: Int): Boolean =
  if (i == 0) false
  else if (i > 0) even(i - 1)
  else even(i + 1)

在这两个 even和 odd ，每个分支要么是一个简单的表达式(在这种情况下是 true 或 false)，它不进行函数调用或尾部调用:被调用函数的值被返回而不被操作。
如果没有尾调用消除，则(可能以无限长度的循环递归)调用必须使用消耗内存的堆栈来实现，因为调用者可能会对结果做一些事情。尾调用消除依赖于观察调用者对结果不做任何事情，因此被调用函数可以有效地替换堆栈上的调用者。
Haskell 和基本上所有其他 post-Scheme 函数式语言运行时都实现了广义的尾调用消除:尾调用成为无条件跳转(想想 GOTO)。著名的 series of Steele and Sussman papers (不幸的是，PDF 没有被归档，但您可以搜索，例如 AIM-443(可能需要 mit 或 steele 或 sussman))称为“Lambda:The Ultimate”(这激发了这个名字的编程语言论坛)讨论了尾调用消除的含义以及这意味着函数式编程实际上对于解决现实世界的计算问题是可行的。
然而，Scala 主要针对 Java 虚拟机，其规范(通过设计)有效地禁止通用尾调用消除，其指令集约束无条件跳转不跨越方法的边界。在某些有限的上下文中(基本上是一个方法的递归调用，其中编译器可以绝对确定正在调用什么实现)，Scala 编译器在发出 Java 字节码之前执行尾部调用消除(理论上可以想象 Scala Native 可以执行泛化尾调用消除，但这将需要 JVM 和 JS Scala 的一些语义中断(一些 JavaScript 运行时执行通用的尾调用消除，尽管据我所知不是 V8))。 @tailrec注释，您可能对它有些熟悉，它强制要求编译器能够执行尾调用消除。
Trampolining 是一种在运行时模拟编译时尾调用消除的低级技术，尤其是在 C 或 Scala 等语言中。由于 Haskell 在编译时执行了尾调用消除，因此不需要蹦床的复杂性(以及将高级代码编写为连续传递样式的要求)。
您可以将 Haskell 程序中的 CPU(或运行时本身，如果转译为，例如 JS)视为实现蹦床。