Why does F# impose a low limit on stack size?

Question

I would like to know if there is a fundamental reason for limiting the depth of recursion in F# to 10000 or so, and ideally how to avoid that limit. I think it is perfectly reasonable to write code that uses O(n) stack space, and would be grateful if someone who disagrees could explain why they do. Many thanks. I explain my thinking below.

I don't see that there is any reason for not allowing the stack to grow until the entire available memory is exhausted. It would mean infinite recursion would take longer to notice, but it's not as if we cannot already write programs that consume an infinite amount of memory. I am aware it is possible to reduce stack usage to O(1) using continuations and tail recursion, but I don't particularly see how it is good for me to have to do that all the time. Neither do I see how it helps to have to know when a function is likely to need to process a "large" input (well, by the standards of an 8-bit micro-controller).

I think this is fundamentally different from having to e.g. use accumulating parameters to avoid quadratic time behavior. While that too involves worrying about implementation details, and does not need to be done for "small" inputs, it is also very different in that the compiler cannot trivially remove the problem on its own. It is furthermore different in that slightly complicated O(n) code that would have been O(n^2) if written naively is very substantially more useful than the simple, slow, easy-to-read version. In contrast, continuation-style code has exactly the same memory complexity as the corresponding naive version, but just uses a different kind of memory. This is the sort of a thing the compiler should not make me worry about in this day and age?

While I would "prefer" a theoretical reason for why it is not possible to have a deep stack, we might as well discuss practical aspects too. It seems to me that a stack is a somewhat more efficient way of managing memory than the heap in that it does not require garbage collection and is easily freed? I am not sure I can even see there is a cost to allowing deep stacks. Admittedly, the OS needs to set aside enough virtual space to contain all the memory you might want to use at once in the whole program for every thread's stack. But so what. It's not as if we are likely to run out of the currently common 48-bit limit by doing that, or that hardware manufacturers cannot trivially increase that limit to 64-bits?

There is not that much specific to F# here. I expect the same restriction applies in C#, and don't see that it is any more necessary there, although it is obviously a lot less of a pain in practice when programming in imperative style.

Many thanks for any replies/comments.

EDIT: I wrote a summary of the answers below.

Answer 1

I think this has now had as many answers as it is going to get. Here is a summary:

i) no-one suggested any fundamental reason for a stack-limit lower than the total amount of available memory

ii) the answer that I learned the most form was Brian's (many thanks). I would strongly recommend the blog post that he linked, and the rest of his blog too. I found it more informative than either of the two good books on F# I have. (Having said that, you should probably have a look at what he says about just how straightforward it is to achieve tail recursion in part 6 of the blog posts on catamorphisms https://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six/ before you take the word "marginal" he had used at face value :-) ).

EDIT: Jon Harrop was a very close second. Many thanks.

iii) Svick suggested an easy way of increasing the limit by three orders of magnitude. Many thanks.

iv) Delnan suggested the best practice is to just use folds/maps everywhere, and define those in a tail-recursive way. This is certainly sound advice for lists, but perhaps less applicable when traversing graphs. Either way, many thanks for the suggestion.

v) Joel and Brian suggested some practical reasons for why the limit is a good idea. They were all low-level details that I feel should be well hidden by a high-level language. Many thanks.

Answer 2

By far the most compelling reason for F# to inherit the limitations of .NET in this context is compatibility. Compilers can and do completely eliminate the stack, e.g. the SML/NJ compiler for Standard ML transforms programs into continuation passing style automatically. The two main disadvantages are that it requires a global change to the calling convention that breaks compatibility and that it is substantially less efficient. If F# did this to evade stack overflows then C# interoperability would be a lot harder and F# would be a lot slower.

Another reason why deep stacks are a bad idea is the garbage collector. Stacks are treated specially by GCs because they are guaranteed to be thread local and can shrink without requiring collection. The .NET GC traverses all thread stacks whenever any thread incurs a gen0 collection. Consequently, having just two sleeping threads with deep stacks can make another thread run 10x slower. Imagine how much worse that would be with much deeper stacks. This can be solved by changing the way the GC treats the stacks, essentially turning them into heaps, but that makes stack operations a lot slower.

Answer 3

In most cases the stack wont be an issue if you write your functions to be tail recursive

Answer 4

In theory, anything is possible. You could write a compiler that uses the heap to manage what is traditionally 'stack'.

In practice, performance (especially for fundamentals like 'function calls') matters. We've got a half-century of hardware and operating system tailored/optimized for the finite stack memory model.

This is the sort of a thing the compiler should not make me worry about in this day and age?

Meh. Garbage collection is a big win; managing all your memory is a mostly-needless chore, and many applications can trade-off some performance for the programmer productivity here. But I think few people feel that human-managing of stack/recursion is a huge deal, even in functional language, so the value of letting the programmer off the hook here is, IMO, marginal.

Note that in F# specifically, you can use a CPS workflow that will transform a fair bit of stack into heap and/or tail-calls, with a relatively minor change in programming style/syntax, if you want to go there (see e.g. here).

Answer 5

You can avoid that limit easily: just start a new thread that has a stack as big as you want using an overload of constructor for Thread.

Answer 6

I can think of at least two possible reasons:

(1) On many computer architectures, it's hard to increase the size available for the stack at runtime without moving it somewhere else in the address space. As @svick pointed out in the comments, .NET on 32 bit Windows limits the main thread's stack size to 1MB. Changing the main thread's stack size on Windows requires a change to the .EXE file.

(2) It is FAR, FAR more common for a stack overflow to be caused by a programming error than by actually having code that genuinely needs to exceed the available stack size. A limited stack size is a very useful sentinel to catch programming errors. In 98% of cases, if the stack were allowed to grow to available memory, the first time you'd find out about your programming errors would be when you exhausted available memory.