Haskell recursion and memory usage

Question

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.

It looks something like this:

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 

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.

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.

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.

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.

Answer 1

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.

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.

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'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.

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.

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

Which allows the whole if to be reduced to:

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

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.

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") 

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

putStrLn ((++) "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".

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` 

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.

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.

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.

---

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.

---

¹ 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.

³ 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.