logo标签列表

Haskell递归和内存使用

memoryrecursionfunctional-programminghaskell
31

我逐渐习惯于用递归取代循环的思路。最近在搞一个小项目，想测试一下文本输入功能，于是我写了一个简单的命令行界面，它会不断地询问输入内容直到接收到特定的退出命令。

代码大致如下：

getCommandsFromUser = do
    putStrLn "Enter command: "
    keyboardInput <- getLine
    let command = map toLower keyboardInput
    if command == "quit"
        then 
            putStrLn "Good-bye!"
        else do
            -- stuff
            -- more stuff
            putStrLn ("Sending command: " ++ commandURI)
            simpleHTTP $ getRequest commandURI
            getCommandsFromUser

main = do
    getCommandsFromUser

这个代码的运行结果与预期完全一致，但是作为一个C/Java背景的人，它仍然触动了我大脑深处、黑暗无意识的部分，让我想狂吐，因为我无法摆脱“getCommandsFromUser的每一个递归调用都创建了一个新的栈帧”的思想。

现在，我还不知道IO、monad、state、arrow等方面的知识。我还在阅读《Real World Haskell》，尚未达到那部分内容，而且一些代码是根据我在谷歌上搜索到的东西进行模式匹配的。

此外，我知道GHC的整个重点在于它是一个疯狂优化的编译器，旨在执行如美丽展开尾递归函数之类的不可思议的操作。

那么，有人可以解释一下这个实现是否“正确”，如果是的话，请解释一下背后发生了什么事情，以避免该程序在无数只猴子手中崩溃？

我知道什么是尾调用优化。我更关心的是在这种情况下它是如何工作的，特别是涉及到操作和一般的函数不纯性。

我的问题不是基于我对Haskell如何使用堆栈感到困惑，也不是我期望它像命令式语言一样工作；而是因为我不知道Haskell如何处理堆栈，想知道它与传统的类C语言有何不同。

1
我建议您在这里或者在网络上查找“尾递归优化”。这是一个普遍的编译器/语言概念，不仅由Haskell编译器实现，还有GCC等其他编译器也支持。 - Thomas M. DuBuisson
6
严格解释尾递归优化（TCO），我们不能确定它是否适用于(>>=)右侧的内容。实际上，对于许多单子而言，它并不适用。但在IO中，我们会非常小心地确保它适用。@ThomasM.DuBuisson - Carl
@ThomasM.DuBuisson 正如原问题所述，我熟悉尾调用优化及其工作原理的一般概念。 我正在询问的是在Haskell中的应用，特别是在这种（单子、不纯）情况下的使用。 - Doug Stephen
8
在评估非严格语言（例如Haskell）时，“尾调用优化”并不是一个有意义的短语。评估以完全不同的方式进行；“TCO”是默认的，而不是真正的“优化”。请注意不要改变原来的意思。 - shachaf
4个回答
43
不必过于关注栈。没有什么本质的要求函数调用必须使用栈帧来实现；那只是一种可能的技术实现方式。
即使你有“栈”，也没有什么规定栈必须限制在可用内存的一小部分上。这基本上是一种针对命令式编程进行调优的启发式方法；在命令式编程中，如果不使用递归作为问题解决技巧，则非常深的调用堆栈往往会导致无限递归错误，并且将栈大小限制为相当小的东西意味着这样的程序会迅速死亡而不是消耗所有可用的内存和交换空间然后死亡。
对于函数式程序员来说，在计算机仍然有几GB的RAM可用时，让程序因“内存不足”而终止以进行更多的函数调用是一种荒谬的语言设计缺陷。这就像C将循环限制为某个任意的迭代次数一样。因此，即使一个函数式语言使用栈来实现函数调用，如果可能的话，也会有强烈的动机避免使用我们从C中知道的标准小栈。
实际上，Haskell确实有一个可以溢出的栈，但它不是你从C熟悉的调用堆栈。可以编写非尾递归函数，这些函数会无限递归并消耗所有可用内存而不会达到调用深度的限制。Haskell所拥有的栈用于跟踪需要评估一些值以便做出决策的“待处理”值（稍后我将详细介绍这种情况）。关于这种类型的栈溢出，您可以在这里阅读更多详细信息。
让我们通过一个示例来看看如何评估您的代码。1 我会使用比您的代码更简单的示例：
main = do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

Haskell的求值是惰性的2。简单来说，这意味着它只会在需要一个术语的值来做出决策时才去评估这个术语。例如，如果我计算1 + 1然后将结果作为列表的前缀添加到列表中，它可以被保留为“挂起”的1+1。3但是如果我使用if测试结果是否等于3，那么Haskell将需要实际执行将1 + 1转换为2的工作。

但如果只有这些，什么都不会发生。整个程序将只剩下一个“挂起”值。但是有一个外部驱动程序需要知道main评估为什么IO操作，以便执行它。

回到这个例子。 main等于那个 do 块。对于IO，do块将一系列较小的IO操作组成一个大的IO操作，必须按顺序执行。因此，Haskell运行时看到main评估为input <- getLine后跟一些尚未评估的内容，它目前不需要。这足以知道从键盘读取并调用生成的String input。假设我输入了“foo”。那么这将使Haskell有以下类似内容作为其“下一个”IO操作：

if "foo" == "quit"
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

Haskell只看到了最外层的东西，所以这基本上看起来像是“if blah blah blah blah ...”。if对于IO执行程序来说无法做任何事情，因此需要对其进行评估以查看其返回值。 if 只会计算出 then 或 else 分支之一，但为了知道要做出哪个决定，Haskell需要评估条件。所以我们得到：

if False
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

这使得整个if语句可以简化为：

do
    putStrLn $ "You typed: " ++ "foo"
    main

再次强调，do 命令会给我们一个由子命令有序组成的 IO 动作（action）。所以，IO 执行器需要执行的下一步是 putStrLn $ "You typed: " ++ "foo"。但这也不是一个 IO 动作（它是一个未求值的计算结果，应该最终得到一个动作）。因此，我们需要对其进行求值。

putStrLn $ "You typed: " ++ "foo" 的“最外层”部分实际上是 $。为了使您能够像 Haskell 运行时一样清晰地看到它，我们需要消除中缀运算符语法，它应该是这个样子：

($) putStrLn ((++) "You typed: " "foo")

但是，$ 运算符只是由 ($) f x = f x 定义的，因此立即用右侧进行代换，我们得到:

putStrLn ((++) "You typed: " "foo")`

通常情况下，我们会通过替换putStrLn的定义来评估它，但它是一种“魔法”原始函数，在Haskell代码中不能直接表达。 所以它不会像这样被评估; 外部IO执行器只需知道如何处理它。 但它要求putStrLn的参数被完全评估，因此我们不能将其保留为(++)"You typed: " "foo"。

实际上，需要多个步骤才能完全评估该表达式，需要经过在列表操作中使用++的定义，但让我们跳过这些细节并说它评估为"You typed: foo"。 然后，IO执行器可以执行putStrLn（将文本写入控制台），然后转到do块的第二部分，即：

`main`

这不是像 putStrLn 和 getLine 一样内置于 Haskell 中立即执行的 IO 操作，因此我们通过使用 main 的定义的右侧来评估它:

do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

我相信你能看出接下来的内容发展方向。

需要注意的是，我并没有提到任何关于堆栈的东西。所有这些都只是构建一个描述main的IO操作的数据结构，以便外部驱动程序可以执行它。它甚至不是一个特别特殊的数据结构。从评估系统的角度来看，它就像任何其他数据结构一样，因此对其大小没有任何任意的限制。

在这种情况下，惰性评估意味着生成该数据结构与其消耗交错（并且生成其后续部分可能取决于消耗其先前部分所产生的结果！），因此此程序可以在恒定的空间中运行。但是如shachaf在问题评论中指出的那样，这并不是用于删除不必要的堆栈帧的优化；它只是惰性评估自动发生的结果。

所以我希望这足够有助于您了解正在发生的事情。基本上，当Haskell开始评估对getCommandsFromUser的递归调用时，它已经完成了上一次迭代内生成的所有数据，因此会进行垃圾回收。因此，您可以无限期运行此程序，而不需要超过固定量的内存。这仅仅是惰性评估的直接结果，在涉及IO时并没有实质性区别。

1我要提前声明，我对Haskell的实际当前实现并不了解。但是我知道实现像Haskell这样的惰性纯语言的一般技术。我也将尝试避免过多地深入细节，并以直观的方式解释事情的工作原理。因此，这个描述可能在计算机内部实际发生的某些详细信息方面不正确，但它应该向您展示这些事情如何可以工作。

2语言规范技术上只说评估应该是“非严格”的。我要描述的评估（通俗称为惰性）实际上只是一种“非严格”的评估策略之一，但它是实践中得到的。

3而新列表实际上可以作为(1 + 1)：originalList的“待定”结果保留，直到有人需要知道它是否为空。

10

这个实现是正确的。

我认为尾递归优化并不是使其高效工作的关键点。相反，允许它高效工作的是IO操作的不可变性。你会惊讶IO操作是不可变的吗？我起初也是！这意味着这个操作：getCommandsFromUser 是一个“要做的事情”的配方；每次评估 getCommandsFromUser时，它都会评估为相同的配方。（当然，每次按照配方操作，你得到的结果可能并不相同！但那完全是执行的不同阶段。）

这样的结果是，所有对于getCommandsFromUser 的评估都可以共享—— GHC只在内存中保留一个配方的副本，其中一部分配方包括一个指针指回配方的开头。

那么赋值怎么办呢？假设在“do stuff”注释块内有一个“let foo = bar”的语句（我的运行代码中确实有这个语句，并且它是基于命令行输入的）。这让我回到了我最初关于堆栈帧的问题。我想我理解你概念上的意思，而且我并不是不理解可能存在的机制使其工作；我只是想知道这些机制是什么，因为我觉得它非常有趣。为什么我调用一百万次getCommandsFromUser后不会溢出堆栈呢？ - Doug Stephen
4
@DougStephen 好的，你的困惑部分来自于不理解Haskell如何使用栈，我猜想。在Haskell中，函数调用不会添加堆栈帧，而是由嵌套thunk（一种惰性计算方式）产生堆栈帧。也许看一下这个问题可能会对你有所帮助：链接。我认为它很好地说明了命令式程序员期望如何使用堆栈和GHC实际上如何使用堆栈之间的差异。 - Daniel Wagner
@DanielWagner，这正是我在寻找的东西。我想我没有很好地表达我的问题；这不是混淆的问题，而是我不知道，正在寻找一个好的解释。现在你已经说了，堆栈帧与thunks相关联在直觉上是有意义的。非常感谢！ - Doug Stephen
我相信尾调用与此有关。如果getCommandsFromUser不是do符号中的最后一项，那么IO评估需要保持堆栈（以便“指向后面”），而不仅仅是指向开头。我不明白这与不可变性有什么关系。 - Bergi
4
据我了解，你应该忘掉TCO（尾递归消除）：不要问一个递归调用是否在尾部位置，而是要考虑“受保护的递归”。我认为这个答案是正确的。你还可以看看“无限邻域”博客上关于数据和协程的文章。最后，查看空间泄漏动物园。 编辑: 对不起，以上内容没有直接回答你有关单子操作的问题；我很感兴趣看到其他的答案，比如DanielWagner的答案，它专门涉及IO单子。
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接