为什么哈斯克尔不需要蹦床？

Question

Scala开发人员学习IO单元体，因此一般的蹦床技术对于不可能进行尾调用优化的递归是必要的，我想知道Haskell是如何避免它的。

我知道Haskell是一种懒惰的语言，但是我想知道是否有人可以再详细说明一下。

例如，为什么ForeverM stackoverflow不在Scala中运行？好吧，我可以回答蹦床，我可以找到实际的代码，在图书馆和博客。我自己居然实现了一个基本的蹦床来学习。

在哈斯克尔是怎么发生的？有没有一种方法可以把懒惰的情绪释放出来，给出一些指示，也许是一些有助于更好地理解懒惰的文档？

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和几乎所有其他后方案函数语言运行时都实现了广义的尾部调用消除：尾部调用变成了一个无条件的跳转（想想GOTO）。Steele和Sussman的著名系列论文（不幸的是PDF没有归档，但您可以搜索，例如AIM-443(MIT或Steele或Sussman可能需要））被称为“Lambda：The Ultimate”（这启发了编程语言论坛的名称），讨论了尾部调用消除的含义，以及这意味着函数式编程实际上可以解决现实世界的计算问题。

然而，Scala主要针对Java虚拟机，该虚拟机的规范（通过设计）有效地禁止了广义尾部调用消除，并且该虚拟机的指令集限制无条件跳转不跨越方法的边界。在某些有限的上下文中（基本上是方法的递归调用，编译器可以绝对确定调用的是什么实现），Scala编译器在发出Java字节码之前执行尾部调用消除（理论上可以想象Scala本机可以执行广义尾部调用消除，但这会导致JVM和JS Scala的语义中断（一些JavaScript运行时执行广义尾部调用消除，但据我所知不是V8））。您可能对@tailrec注释有些熟悉，它强制要求编译器能够执行尾部调用消除。

Trampolining是一种在运行时模拟编译时尾调用消除的低级技术，特别是在C或Scala这样的语言中。由于Haskell已经在编译时执行了尾调用消除，因此不需要像蹦床一样的复杂性（以及将高级代码编写成延续传递风格的要求）。

您可以将Haskell程序中的CPU（或者运行时本身（如果转换到JS））看作是实现一个蹦床。