Haskell递归和内存使用-Java 学习之路

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

它看起来像这样：

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 回答

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

即使你有“堆栈”，也没有什么说堆栈必须限制在可用内存的一小部分 . 这本质上是一种启发式调整到命令式编程;你不使用递归作为解决问题的技术，非常深的调用堆栈往往是由无限递归错误引起的，并且将堆栈大小限制为非常小的意味着这样的程序快速死亡而不是消耗所有可用内存和交换然后奄奄一息 .

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

实际上，Haskell确实有一个可以溢出的堆栈，但它从C中熟悉它 . 很有可能编写非尾递归函数，这些函数无限递归并将消耗所有可用内存而不会限制调用深度 . Haskell所拥有的堆栈用于跟踪需要进行更多评估的"pending"值，以便做出决定（稍后我会详细介绍） . 您可以更详细地阅读这种堆栈溢出here .

让我们通过一个例子来看看你的代码是如何被评估的 . 我会使用比你更简单的例子：
```
main = do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main
```
Haskell的评价是懒惰的 . 简单地说，这意味着当需要该术语的值来做出决定时，它只会费心去评估一个术语 . 例如，如果我计算 1 + 1 然后将其结果添加到列表的前面，则可以将其保留为list3中的"pending" 1 + 1 . 但是如果我使用 if 来测试结果是否等于3，那么Haskell实际上需要将 1 + 1 转换为 2 .

但如果这就是它的全部，那么什么都不会发生 . 整个程序将保留为"pending"值 . 但是有一个外部驱动程序需要知道IO动作 main 的计算结果，以便执行它 .

回到例子 . main 等于 do 块 . 对于 IO ， do 块在一系列较小的块中产生一个很大的 IO 动作，必须按顺序执行 . 所以Haskell运行时看到 main 评估为 input <- getLine 后跟一些未评估的东西，它不足以知道从键盘读取并调用结果 String input . 我输入"foo" . 这使得Haskell具有类似以下内容的"next" IO 动作：
```
if "foo" == "quit"
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main
```
Haskell只关注最外层的东西，所以这看起来很像“ if 等等等等等等等等 . ” 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" 的"outermost"部分实际上是 $ . 摆脱中缀运算符语法，以便您可以像Haskell runtiem一样查看它，它看起来像这样：
```
($) putStrLn ((++) "You typed: " "foo")
```
但 ($) f x = f x 运算符只是由 ($) f x = f x 定义，因此立即替换右侧给我们：
```
putStrLn ((++) "You typed: " "foo")`
```
现在通常我们通过替换 putStrLn 的定义来评估它，但它在Haskell代码中可以直接表达 . 所以它实际上并没有像这样评估;外部IO执行程序只知道如何处理它 . 但它需要完全评估 putStrLn 的参数，因此我们不能将其保留为 (++) "You typed: " "foo" .

实际上有很多步骤可以完全评估该表达式，在列表操作方面通过 ++ 的定义，但是我们可以跳过它并说它的计算结果为 "You typed: foo" . 那么IO执行程序可以执行 putStrLn （将文本写入控制台），然后转到 do 块的第二部分，这只是：
```
`main`
```
哪个不能立即作为 IO 动作执行（它不是内置于Haskell中，如 putStrLn 和 getLine ），所以我们通过使用 main 定义的右侧来获得：
```
do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main
```
而且我相信你可以看到其余的去向 .

请注意，我没有说过任何类型的堆栈 . 所有这些只是构建一个描述 IO 动作 main 的数据结构，因此外部驱动程序可以执行它 . 它's not even a particularly special data structure; from the point of view of the evaluation system it'就像任何其他数据结构一样，因此对其大小没有任何限制 .

在这种情况下，延迟评估意味着这个数据结构的生成与其消耗交错（并且它的后续部分的生成可以取决于消耗它的早期部分所发生的事情！），因此该程序可以在恒定的空间 . 但正如shachaf对这个问题的评论所指出的那样，这并不是删除不必要的堆栈帧的优化;这就是懒惰评估自动发生的事情 .

所以我希望这对你有所帮助，看看发生了什么 . 基本上，当Haskell计算递归调用 getCommandsFromUser 时，'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'与 IO 有很大不同 .

我也会尽量避免过多地潜入细节，并以直观的方式解释事情是如何运作的 . 因此，在计算机内部实际发生的一些细节上，此帐户可能不正确，但它应该向您展示这些内容如何工作 .

2技术上的语言规范只是说评估应该是"non-strict" . 评估我在实践中得到了什么 .

3事实上，新列表可以保留为 (1 + 1) : originalList 的结果，直到有人需要知道它是否为空 .
回复于 2024-04-20T13:32:26+08:00
1

这种实现是正确的 .

我不认为尾部调用优化确实能使这项工作高效运行 . 相反，允许它有效工作的是，不管你信不信，IO行为的不变性 . 您对IO操作是不可变的感到惊讶吗？我刚开始！这意味着什么： getCommandsFromUser 是"things to do"的食谱;每次评估 getCommandsFromUser 时，它都会评估相同的配方 . （虽然当然不是每次你都遵循食谱而得到相同的结果！但这完全是执行的不同阶段 . ）

这样做的结果是 getCommandsFromUser 的所有评估都可以共享 - GHC只是将一份食谱保存在内存中，而该食谱的一部分包括一个指向食谱开头的指针 .

回复于 2024-04-20T13:32:26+08:00
31

据我所知，你应该忘记TCO：而不是询问递归调用是否在尾部位置，考虑保护递归 . This answer我认为是对的 . 您也可以查看Data and Codata上的帖子来自总是有趣且具有挑战性的"Neighborhood of Infinity"博客 . 最后查看Space Leak Zoo .

EDIT ：我'm sorry the above doesn'直接提出关于一元行动的问题;我'm interested to see other answers like DanielWagner'具体解决了IO monad问题 .

回复于 2024-04-20T13:32:26+08:00
7

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

IO inside

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

Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell

回复于 2024-04-20T13:32:26+08:00

Haskell递归和内存使用

4 回答

相关问题