30

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

它看起来像这样：

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、monads、状态、箭头等一无所知。我仍在通过 Real World Haskell 工作，我还没有达到那部分，并且其中一些代码与我在 Google 上找到的东西的模式匹配。

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

那么有人能解释一下这个实现是否“正确”，如果是的话，可以向我解释一下幕后发生的事情，如果它被放在无数只猴子的手中，它会阻止这个程序爆炸吗？

我知道什么是尾调用优化。我更关心它在这种情况下的工作原理，以及正在发生的动作和一般功能杂质。

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

4

4 回答 4

40

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

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

对于函数式程序员来说，当计算机仍然有千兆字节的 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.

但如果这就是它的全部，那么什么都不会发生。整个程序将仅保留为“待定”值。但是有一个外部驱动程序需要知道 IO 操作main的评估结果，以便执行它。

回到例子。main等于那个do块。对于IO，一个块由一系列较小的动作do组成一个大动作，这些动作必须按顺序执行。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-executor 可以做任何事情的，因此需要对其进行评估以查看它返回的内容。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由有序的子动作序列组成的动作。所以 IO 执行器接下来要做的就是putStrLn $ "You typed: " ++ "foo". 但这也不是一个IO动作（它是一个未评估的计算，应该导致一个）。所以我们需要评估它。

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

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

但是$刚刚由 定义的运算符($) f x = f x，所以立即替换右侧给我们：

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

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

实际上有许多步骤可以完全评估该表达式，通过++列表操作的定义，但让我们跳过它并说它评估为"You typed: foo". 那么 IO-executor 可以执行putStrLn（将文本写入控制台），并继续执行该do块的第二部分，即：

`main`

这不是可以立即作为IO动作执行的东西（它不像 Haskell 那样内置在里面putStrLn）getLine，所以我们使用 to 定义的右侧来评估它main：

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

我相信你可以看到其余部分的去向。

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

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

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

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

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

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

于 2012-12-09T12:31:52.813 回答
9

这个实现是正确的。

我不认为尾调用优化真的是使这项工作有效的一点。相反，不管你信不信，让它高效工作的是 IO 操作的不变性。您对 IO 操作是不可变的感到惊讶吗？我一开始是！这意味着：getCommandsFromUser是“要做的事情”的秘诀；并且每次您评估getCommandsFromUser时，它都会评估相同的配方。（当然，不是每次你按照食谱做的都会得到相同的结果！但这完全是执行的不同阶段。）

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

于 2012-12-09T01:41:24.760 回答
4

据我了解，您应该忘记 TCO：与其询问递归调用是否处于尾部位置，不如考虑受保护的递归。这个答案我认为是对的。您还可以从总是有趣且具有挑战性的“无限邻域”博客中查看有关数据和 Codata的帖子。最后看看Space Leak Zoo。

编辑：很抱歉，以上内容没有直接解决您关于单子动作的问题；我有兴趣看到像 DanielWagner 这样专门针对 IO monad 的其他答案。

于 2012-12-09T01:41:59.797 回答
1

涉及到 IO 并不重要。你可以在 Haskell wiki 中阅读它：

IO里面

或者，为了更深入地体验 Haskell 的 IO：

处理尴尬的小队：Haskell 中的一元输入/输出、并发、异常和外语调用

于 2012-12-09T10:55:26.317 回答