21

作为 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))
  }
}
4

2 回答 2

24

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

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)

在evenandodd中，每个分支要么是一个简单的表达式（true或false在这种情况下），它不进行函数调用或尾部调用：被调用函数的值被返回而不被操作。

如果没有尾调用消除，则（可能以无限长度的循环递归）调用必须使用消耗内存的堆栈来实现，因为调用者可能会对结果做一些事情。尾调用消除依赖于观察调用者对结果不做任何事情，因此被调用函数可以有效地替换堆栈上的调用者。

Haskell 和基本上所有其他 post-Scheme 函数式语言运行时都实现了广义的尾调用消除：尾调用成为无条件跳转（想想 GOTO）。著名的 Steele 和 Sussman 论文系列（遗憾的是，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）视为实现蹦床。

于 2021-04-22T02:16:43.160 回答
3

蹦床并不是尾声的唯一解决方案。Scala 需要蹦床，正是因为它运行在 JVM 上，带有 Java 运行时。Scala 语言开发人员无法准确选择其运行时的运行方式或二进制格式。因为他们使用 JVM，所以他们必须忍受 JVM 针对Java而不是针对 Scala 进行优化的所有方式。

Haskell 没有这个限制，因为它有自己的运行时，它自己的二进制格式等。它可以根据 Haskell 语言的语言级结构精确地选择如何在运行时设置堆栈 --- 不是，爪哇一。

于 2021-04-28T19:46:46.873 回答