当scala开发人员学习io monad时，以及在不可能进行尾部调用优化的递归中通常需要的蹦床技术，我想知道haskell是如何天生避免它的。
我知道haskell是一种懒惰的语言，但是我想知道是否有人可以进一步阐述。
例如，为什么在scala中foreverm stackoverflow不存在？好吧，我可以回答蹦床，我可以找到真正的代码，在图书馆和博客。实际上我自己做了一个基本的蹦床来学习。
哈斯克尔是怎么发生的？有没有一种方法可以让你对懒惰有一点了解，给你一些建议，也许还有一些文档可以帮助你更好地理解它？
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))
}
}
1条答案
按热度按时间btqmn9zl1#
函数式编程通常需要消除尾部调用（否则函数调用的深层链会溢出堆栈）。例如，考虑偶数/奇数分类器的这种（荒谬的低效）实现：
两者都有
even以及odd，每个分支都是一个简单的表达式(true或者false在本例中）不进行函数调用或尾部调用：返回被调用函数的值而不进行操作。如果没有尾部调用消除，调用（可能是循环长度不确定的递归调用）必须使用消耗内存的堆栈来实现，因为调用方可能会对结果进行处理。尾部调用消除依赖于观察调用者对结果不做任何操作，因此被调用函数可以有效地替换堆栈上的调用者。
haskell和其他的post-scheme函数语言运行时基本上都实现了广义的尾部调用消除：尾部调用变成了无条件跳转（想想goto）。著名的steele和sussman系列论文（不幸的是pdf没有存档，但是你可以搜索，例如。
AIM-443(mit或者steele或者sussman被称为“lambda:the ultimate”（它启发了一个编程语言论坛的名称）的函数式编程（tail-call-elimination）讨论了尾部调用消除的含义，以及这意味着函数式编程在解决实际计算问题时实际上是可行的。然而，scala主要针对java虚拟机，其规范（通过设计）有效地禁止了广义尾部调用消除，并且其指令集约束无条件跳转不跨越方法的边界。在某些有限的上下文中（基本上是一个方法的递归调用，编译器可以完全确定调用的是什么实现），scala编译器在发出java字节码之前执行尾部调用消除（理论上可以想象scala native可以执行广义尾部调用消除，但这将导致jvm和js scala的语义中断（据我所知，有些javascript运行时执行通用尾部调用消除，但不是v8）。这个
@tailrec注解，您可能对它有些熟悉，它强制要求编译器能够执行尾部调用消除。蹦床是一种在运行时模拟编译时尾部调用消除的低级技术，特别是在c或scala等语言中。由于haskell已经在编译时执行了尾部调用消除，因此不需要蹦床的复杂性（以及将高级代码写入延续传递样式的要求）。
可以说，haskell程序中的cpu（或者运行时本身，如果传输到js，例如js）实现了蹦床。