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

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 2

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