Haskell递归和内存使用

Question

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

它看起来像这样:

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语言有什么不同.

Answer 1

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

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

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

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

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

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

Haskell的评价很懒散².简单地说,这意味着当需要该术语的值来做出决定时,它只会费心去评估一个术语.例如,如果我计算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不是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动作,由一系列有序的子动作组成.所以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执行程序可以执行putStrLn(将文本写入控制台),然后继续执行do块的第二部分,这只是:

`main`

这是不是可以作为一个被立即执行IO动作(它不是建立在哈斯克尔喜欢putStrLn和getLine有),所以我们使用的定义右侧评价它main获得:

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

而且我相信你可以看到剩下的工作.

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

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

所以我希望这对你看看发生了什么有很大帮助.基本上,当Haskell计算递归调用时getCommandsFromUser,它已经完成了上一次迭代中生成的所有数据,因此它被垃圾收集.因此,您可以无限期地继续运行此程序,而无需超过固定数量的内存.这只是懒惰评估的直接后果,并且在IO涉及时并没有实质性的不同.

¹我将在前面否认我不太了解Haskell的实际当前实现.但我确实知道实现像Haskell这样的惰性纯语言的一般技巧.我也将尽量避免过多地深入细节,并以直观的方式解释事情是如何运作的.因此,在计算机内部实际发生的一些细节上,这个帐户可能不正确,但它应该向您展示这些东西是如何工作的.

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

³事实上,新名单可以留作"待定"结果,(1 + 1) : originalList直到有人需要知道它是否为空.

Answer 2

这种实现是正确的.

我不认为尾部调用优化实际上是有效的工作.相反,允许它有效工作的是,不管你信不信,IO行为的不变性.您对IO操作是不可变的感到惊讶吗？我刚开始!这意味着什么:getCommandsFromUser是"要做的事情"的配方; 每次评估时getCommandsFromUser,它都会评估相同的配方.(虽然当然不是每次你都遵循这个方法,但你得到的结果却相同!但这完全是执行的不同阶段.)

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