Haskell 递归和内存使用 [英] Haskell recursion and memory usage

问题描述

我对用递归替换循环的想法感到满意.我正在摆弄一个宠物项目，我想测试一些文本输入功能，所以我写了一个小命令行界面，它反复要求输入，直到它收到特定的退出命令.

I'm getting comfortable with the idea of replacing loops with recursion. I'm fiddling around with a pet project, and I wanted to test some text input functionality so I wrote up a little command line interface that repeatedly asks for input until it receives a specific quit command.

看起来像这样:

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 的递归调用正在创建一个新的堆栈框架.

This works exactly as expected, but coming from a C/Java background it still tickles the deep, dark, unconscious parts of my brain and makes me want to break out in hives because I can't shake the thought that every single recursive call of getCommandsFromUser being made is creating a new stack frame.

现在，我对 IO、monads、状态、箭头等一无所知.我仍在努力学习 Real World Haskell，我还没有达到那个部分，其中一些代码与我在 Google 上找到的东西的模式匹配.

Now, I don't know anything about IO, monads, state, arrows, etc. yet. I'm still working my way through Real World Haskell, I haven't reached that part yet, and some of this code is pattern matched off things that I found on Google.

此外，我知道 GHC 的全部意义在于它是一个令人抓狂的优化编译器，旨在完成令人难以置信的事情，例如尾递归函数的美丽展开等.

In addition, I know that the whole point of the GHC is that it's a maddeningly optimizing compiler that is designed to do incredible things such as beautiful unrolling of tail recursive functions and the like.

那么有人可以解释一下这个实现是否正确"，如果是的话，请向我解释一下幕后发生的事情，如果它被置于无限数量的人手中，将防止这个程序爆炸猴子?

So can somebody explain whether or not this implementation is "correct", and if so explain to me what is going on behind the scenes that would prevent this program from blowing up if it were put in the hands of an infinite number of monkeys?

我知道尾调用优化是什么.我更关心它在这种情况下是如何工作的，动作和一般功能杂质发生了什么.

I know what tail call optimization is. I'm more concerned about how it works in this case, what with the actions and general functional impurity going on.

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

This question wasn't so much based on the idea that I was confused about how Haskell used the stack and that I was expecting it to work like an imperative language; it was based in the fact that I had no idea how Haskell handled the stack and wanted to know what it was doing differently from traditional C-like languages.

推荐答案

不要太担心堆栈.没有什么基本的东西说函数调用必须使用堆栈帧来实现；这只是实现它们的一种可能技术.

Don't worry quite so much about the stack. There is nothing fundamental that says function calls have to be implemented using stack frames; that is merely one possible technique for implementing them.

即使您拥有堆栈"，也肯定没有说堆栈必须限于可用内存的一小部分.这本质上是一种针对命令式编程的启发式方法；如果您不使用递归作为解决问题的技术，无限递归错误往往会导致非常深的调用堆栈，并且将堆栈大小限制为非常小的值意味着此类程序会很快死亡，而不是消耗所有可用内存和交换然后死了.

Even when you have "the stack", there's certainly nothing that says the stack has to be limited to a small fraction of available memory. That's essentially a heuristic tuned to imperative programming; where you don't use recursion as a problem solving technique, very deep call stacks tend to result from infinite-recursion bugs, and limiting the stack size to something quite small means such programs die quickly instead of consuming all available memory and swap and then dying.

对于函数式程序员来说，当计算机仍有 GB 可用的 RAM 时，让程序终止耗尽"内存以进行更多函数调用是语言设计中的一个荒谬缺陷.这就像 C 将循环限制为任意次数的迭代.因此，即使函数式语言通过使用堆栈来实现函数调用，如果可能的话，也会有强烈的动机避免使用我们从 C 中知道的标准微型堆栈.

To a functional programmer, having a program terminate "run out" of memory to make more function calls when the computer still has gigabytes of RAM available is a ridiculous flaw in the language design. It would be like C limiting loops to some arbitrary number of iterations. So even if a functional language is implementing function calls by using a stack, there would be a strong motivation to avoid using the standard tiny stack we know from C if possible.

事实上，Haskell 确实有一个可以溢出的堆栈，但它不是您熟悉的 C 中的调用堆栈.很可能编写无限的非尾递归函数递归并将消耗所有可用内存而不会达到调用深度限制.Haskell 确实拥有的堆栈用于跟踪需要更多评估才能做出决定的待处理"值(我稍后会详细介绍).您可以在此处详细了解这种堆栈溢出.

In fact, Haskell does have a stack which can overflow, but it's not the call stack you're familiar with from C. It is quite possible to write non-tail-recursive functions which infinitely recurse and will consume all available memory without hitting a limit on call depth. The stack Haskell does have is used to track the "pending" values that need to be evaluated a bit more in order to make a decision (I'll go into this a bit more later). You can read in more detail about this kind of stack overflow here.

让我们通过一个示例来了解如何评估您的代码.¹不过，我将使用一个比您的示例更简单的示例:

Lets work through an example to see how your code could be evaluated.¹ I'll use an even simpler example than yours though:

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

Haskell 的评估是惰性的².简单地说，这意味着它只会在需要该术语的值来做出决定时才费心评估该术语.例如，如果我计算 1 + 1 然后将结果放在列表的前面，它可以作为待定" 1 + 1 在列表³.但是如果我用if来测试结果是否等于3，那么Haskell就需要实际做转1+1的工作进入2.

Haskell's evaluation is lazy². Simplistically, that means it will only bother to evaluate a term when it needs the value of that term to make a decision. For example, if I compute 1 + 1 and then prepend the result of that to the front of a list, it can be left as a "pending" 1 + 1 in the list³. But if I use if to test whether the result was equal to 3, then Haskell will need to actually do the work of turning 1 + 1 into 2.

但如果仅此而已，那就什么都不会发生了.整个程序将被保留为待处理"值.但是有一个外部驱动程序需要知道 main 评估为什么 IO 操作，以便执行它.

But if that's all there was to it, nothing would ever happen. The entire program would just be left as a "pending" value. But there is an outer driver that needs to know what IO action main evaluates to, in order to execute it.

回到例子.main 等于那个 do 块.对于IO，do 块从一系列较小的动作中组成一个大的IO 动作，这些动作必须按顺序执行.所以 Haskell 运行时看到 main 对 input <- getLine 求值，然后是一些它不需要的未求值的东西.这足以知道从键盘读取并调用结果String input.假设我输入了foo".这使得 Haskell 的下一个"IO 操作如下所示:

Back to the example. main is equal to that do block. For IO, a do block makes an a big IO action out of a series of smaller ones, which must be executed in order. So the Haskell runtime sees main evaluating to input <- getLine followed by some unevaluated stuff which it doesn't need yet. That's enough to know to read from the keyboard and call the resulting String input. Say I typed "foo". That leaves Haskell with something like the following as its "next" IO action:

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 需要评估条件.所以我们得到:

Haskell is only looking at the very outermost thing, so this pretty much looks like "if blah blah blah blah ...". if isn't something that the IO-executor can do anything with, so it needs to be evaluated to see what it returns. if just evaluates to either the then or the else branch, but to know which decision to make Haskell is required to evaluate the condition. So we get:

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

允许整个 if 简化为:

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

再说一次，do 给了我们一个 IO 动作，它由一个有序的子动作序列组成.所以 IO 执行器接下来要做的是 putStrLn $"You typed:" ++ "foo".但这也不是 IO 操作(它是一个未评估的计算，应该导致一个).所以我们需要对其进行评估.

And again, do gives us an IO action which consists of an ordered sequence of sub-actions. So the next thing the IO-executor has to do is the putStrLn $ "You typed: " ++ "foo". But that's not an IO action either (it's an unevaluated computation that should result in one). So we need to evalute it.

putStrLn $"You typed:" ++ "foo" 的最外层"部分实际上是$.去掉中缀运算符的语法，这样你就可以像 Haskell runtiem 一样看到它，它看起来像这样:

The "outermost" part of putStrLn $ "You typed: " ++ "foo" is actually $. Getting rid of the infix operator syntax so you can see it the same way the Haskell runtiem does, it would look like this:

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

但是 $ 操作符只是由 ($) f x = f x 定义的，所以立即替换右边给我们:

But the $ operator just defined by ($) f x = f x, so substituting the right hand side immediately gives us:

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

现在通常我们会通过替换putStrLn 的定义来评估它，但它是一个神奇"的原始函数，不能在 Haskell 代码中直接表达.所以它实际上并没有像这样被评估；外部 IO 执行器只知道如何处理它.但是它要求对 putStrLn 的 argument 进行完全评估，所以我们不能将其保留为 (++) "You typed: " "foo".

Now ordinarily we'd evaluate this by substituting in the definition of putStrLn, but it's a "magic" primitive function that isn't directly expressible in Haskell code. So it doesn't actually get evaluated like this; the outer IO-executor simply knows what to do with it. But it requires that the argument of putStrLn be fully evaluated, so we can't leave it as (++) "You typed: " "foo".

实际上有许多步骤可以完全评估该表达式，在列表操作方面通过 ++ 的定义，但让我们跳过它并说它评估为 "您输入了:foo".然后 IO 执行器可以执行 putStrLn(将文本写入控制台)，然后继续执行 do 块的第二部分，即:

There's actually a number of steps to fully evaluate that expression, going through the definition of ++ in terms of list operations, but lets just skip over that and say it evaluates to "You typed: foo". So then the IO-executor can execute the putStrLn (writing the text to the console), and move on to the second part of the do block, which is just:

`main`

这不是可以作为 IO 操作立即执行的东西(它不像 putStrLn 和 getLine 那样内置在 Haskell 中)，所以我们通过使用 main 定义的右侧来评估它:

Which is not something that can be immediately executed as an IO action (it's not built in to Haskell like putStrLn and getLine are), so we evaluate it by using the right hand side of the definition of main to get:

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

而且我相信您可以看到其余部分的去向.

And I'm sure you can see where the rest is going.

请注意，我没有说过任何类型的堆栈.所有这一切都只是构建了一个数据结构，描述了 main 的 IO 操作，以便外部驱动程序可以执行它.它甚至不是一个特别特殊的数据结构；从评估系统的角度来看，它就像任何其他数据结构一样，因此对其大小没有任意限制.

Note that I haven't said anything about any kind of stack. All of this is just building up a data structure describing the IO action that is main, so the outer driver can execute it. It's not even a particularly special data structure; from the point of view of the evaluation system it's just like any other data structure, and so there are no arbitrary limitations on its size.

在这种情况下，惰性求值意味着这个数据结构的生成与它的消耗是交错的(并且它后面部分的生成可以取决于由于消耗它的前面部分而发生的事情！)，所以这个程序可以在恒定的空间中运行.但正如 shachaf 对这个问题的评论所指出的，这并不是删除不必要的堆栈帧的真正优化；这只是懒惰评估自动发生的事情.

In this case lazy evaluation means the generation of this data structure is interleaved with its consumption (and the generation of later parts of it can depend on what happened as a result of consuming earlier parts of it!), and so this program can run in a constant amount of space. But as noted by shachaf's comment on the question, this isn't really an optimization for removing unnecessary stack frames; it's just what happens automatically with lazy evaluation.

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

So I hope that was sufficiently helpful for you to see what's going on. Basically by the time Haskell gets to evaluating the recursive call to getCommandsFromUser, it's already done with all of the data generated within the previous iteration, and so it gets garbage collected. So you can keep running this program indefinitely without needing more than a fixed amount of memory. This is just a straightforward consequence of lazy evaluation, and isn't substantially different when IO is involved.

¹ 我要预先声明，我对当前 Haskell 的实际实现知之甚少.然而，我确实知道实现像 Haskell 这样的惰性纯语言的一般技术.我还将尽量避免深入细节，只以直观的方式解释事物的工作原理.因此，此帐户可能在您计算机内部实际发生的一些细节方面不正确，但它应该向您展示这些事情可以如何工作.

¹ I'm going to disclaim up front that I do not know much in detail about the actual current implementation of Haskell. I do however know general techniques for implementing lazy pure languages like Haskell. I'm also going to try to avoid diving too much into the details, and just explain how things work in an intuitive way. So this account may well be incorrect in some of the fine details of what's actually going on inside your computer, but it should show you how these things can work.

² 语言规范在技术上只是说评估应该是非严格的".我要描述的评估，非正式地称为懒惰"，实际上只是一种可能的非严格"评估策略，但它是您在实践中得到的.

² The language spec technically just says that evaluation should be "non-strict". The evaluation I'm going to describe, which is known as "lazy" informally, is really only one possible "non-strict" evaluation strategy, but it's what you get in practice.

³ 事实上，新列表可以作为 (1 + 1) : originalList 的待处理"结果，直到有人需要知道它是否是空的.

³ And the new list can in fact be left as a "pending" result of (1 + 1) : originalList until someone needs to know whether or not it's empty.

这篇关于Haskell 递归和内存使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！