<p>I'm writing a register- and stack-based virtual machine. My goal is to have something easy to use and general purpose, so I abstain from any form of hardware limitation in its design. Since my VM's stack is implemented with a high-level data structure (the <a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.stack-1?view=net-8.0" rel="noreferrer">Stack</a> provided by .NET), there is no theoretical limitation on its size. Knowing that I am able to define a stack of indeterminate size (limited only by hardware) my question is whether or not I should limit the stack size for my VM.</p>
<p>I see the following theoretical advantages to an infinite stack size:</p>
<ul>
<li>No overflow can occur ;</li>
<li>Deep recursion is possible.</li>
</ul>
<p>I also see the following disadvantages:</p>
<ul>
<li>An overflow is sometimes a sign that there are things to improve in the underlying code (typically a recursion that should be changed to a loop or with continuations) which the VM will then no longer raise;</li>
<li>A VM stack of indeterminate size can massively overflow and slow down the computer (in the extreme case).</li>
</ul>
<p>For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.</p>
<p>So, given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?</p>

<interpreters><stack><virtual-machine>
Should a virtual machine stack have a limited size?
CC BY-SA 4.0
2024-03-12T18:50:36.000Z
Welcome to PLDI Stack Exchange! This question is soliciting design tradeoffs but does not define what a good answer is. I advise you to refine it so it describes a specific implementation problem to be solved, as detailed in the [help/on-topic].
Ginger
CC BY-SA 4.0
2024-03-12T18:52:26.373Z
I think it should have *some* minimum below the RAM limit, because otherwise an infinite recursion will slow your system and take longer to overflow, and in practice, operations which use a lot of stack size are usually non-ideal (you shouldn't be doing `O(n)` stack recursion if your function can be implemented with a tail call). You can make the limit higher than C though, like 512 MB (what Haskell used to use).
tarzh
CC BY-SA 4.0
2024-03-12T18:57:47.537Z
But it depends on whether the language is suited more or less towards recursion, and maybe there are other factors for smaller stack sizes I'm not aware about. In practice I've rarely seen Stack Overflows which weren't infinite recursion (or overly large so that the algorithm would take too long to compute if it didn't terminate). And when I did, I think it made sense to rewrite the algorithm to use tail recursion or something else anyways. Maybe it's less expensive to write your own "stack" in a function that needs to recurse a lot.
tarzh
CC BY-SA 4.0
2024-03-12T21:21:26.507Z
@Ginger Thanks for pointing that out, I've edited the question to try and meet expectations, I hope it will.
Foxy
CC BY-SA 4.0
2024-03-12T23:59:14.280Z
I'll note that "possible" is correct: in C# neither the language nor the runtime guarantee that unbounded recursions will result in a stack overflow; the compiler may rewrite to heap-allocated continuations and the runtime may make tail calls. Nor do they make any guarantees as to how much short-lifetime storage (aka "stack") is available to a program. Do you see these design choices as strengths to emulate or weaknesses to address in your proposed language / runtime?
Eric Lippert
CC BY-SA 4.0
2024-03-14T09:56:05.250Z
It should have a *fixed* size, so that it operates consistently on all host platforms/implementations
flumperious
CC BY-SA 4.0
2024-03-15T12:55:27.177Z
Note 'fixed' also means that you want it to be independent of later changes. If you make it, e.g. 8KiB, someone _will_ use 8191B and then get annoyed down the line when a later bugfix makes your implementation use an extra 4B internally.
TLW
CC BY-SA 4.0
2024-03-19T22:46:54.443Z
@flumperious: Could be difficult if you support a variety of platforms. If you set that size small enough that your language can run programs on an Arduino, it's going to be a very frustrating limitation for someone running on a big server with a terabyte of RAM.
Nate Eldredge
CC BY-SA 4.0
2024-03-21T12:05:32.147Z
Stack sizes stay small (8MB for x86/64) even on high end servers/supercomputers (unless you're talking about ones specialised for a recursive algorithm), its more often a problem the other way round, e.g. porting java to arduino would be difficult/impossible (from cursory googling, it seems to be implemented in hardware extention boards)
flumperious
CC BY-SA 4.0
2024-03-27T17:04:01.943Z
Technically speaking, a 16 exabyte (maximum addressable memory with 64 bits) stack is “limited”.
dan04
<p>Yes, you should limit the stack size (as well as all other data structures, i.e. heap or whatever you have), unless it is for some reason incredibly hard to do (e.g. huge overhead in processing time).</p>
<p>No, you do not <em>have</em> to make the user (programmer) care too much about it. You can achieve this by setting the default limit to an &quot;unreachable&quot; maximum (i.e., 2^64-1 or whatever is a convenient big number - many programming languages/libraries have a constant like MAX_LONG or something like that).</p>
<p>Yes, you should make this user-configurable. You do not know all use-cases for your application in the future, and an application that uses potentially unlimited memory can be hard to maintain. For example, when deploying a container in Kubernetes, you always declare a maximum RAM limit outside of the executable, in the Kubernetes declaration for your deployment. You also try to get away with as little RAM as possible to allow the orchestrator to distribute the deployments amongst a given amount of nodes efficiently.</p>
<p>When your application exceeds that amount of RAM, it will immediately and unavoidably be force-killed by Kubernetes. If you have a way to set your maximum stack size, the programmer can make an educated guess and set that maximum sufficiently small to avoid his app being killed in this manner. Of course he then can run out of stack space by reaching that limit internally, but your programming language can then spit out a meaningful error message, giving the programmer a working chance to fix the issue.</p>
<p>This is just an example; the same applies of course if your program is simply started on some user's PC. Nobody wants any random program to potentially grab all memory and bring the PC to swap (or kill <em>other</em> random programs just because they unfortunately requested more memory after yours had filled the available RAM fully).</p>

CC BY-SA 4.0
2024-03-15T12:20:32.430Z
2024-03-15T12:20:32.430Z
AnoE
<blockquote>
<p>given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?</p>
</blockquote>
<p>Great question, let me first nitpick and say that &quot;unbounded&quot; is intended for &quot;infinite&quot; here. <em>No stack ever has an infinite size.</em></p>
<p>For the purposes of this discussion I'd like to distinguish between an <em>infinite</em> recursion, where a bug in a recursive algorithm means that it <em>never</em> reaches its base case, and a <em>finite but unbounded</em> recursion, where the depth of the recursion is equal to the size <em>at runtime</em> of the data passed in; we recurse on every node in a linked list, and so if we want a thousand, a million, a billion calls all we have to do is pass in a list of a thousand, a million, a billion items.</p>
<p>I can maybe give you some insights into how we would consider this question when designing a general-purpose language like C# for a general-purpose runtime like the .NET CLR.</p>
<blockquote>
<p>For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.</p>
</blockquote>
<p>Yes, but let's again be precise about C#, since that's what I know best. &quot;Possible&quot; is correct. The CLR specification does not say what size the &quot;short term memory pool&quot; is, and it does not put any particular limit on the depth of calls. Nor does it guarantee that unbounded calls <em>will</em> blow the stack. The CLR reserves the right to optimize tail calls, and historically has done so with... <a href="https://github.com/dotnet/runtime/issues/2191" rel="nofollow noreferrer">mixed results at best let's say.</a></p>
<p>And of course C# has closed-over locals, coroutines, lots of ways that activations don't form stacks, so continuation information can be stored on the long term pool at the discretion of the compiler.</p>
<p>But I'm getting ahead of myself. Let's talk a bit about your typical Windows implementation of the CLR and how both manage the stack. Do forgive occasional simplifications where the messy details are not relevant for your purposes.</p>
<p>The CLR spec does not require any particular implementation strategy as far as stack management is concerned, but the Microsoft implementations typically do the following: IL is JIT-compiled into machine code, and that machine code is what you'd expect. The temporary storage pool is implemented as a bunch of pages called &quot;the stack&quot;, one stack per thread. The stack holds activation frames for unlifted locals that were not optimized into registers, and continuations in the form of return addresses. (And continuations for exception control flow and so on.)  Frame size is limited in the CLR and I don't recall what the limit is, but it's large enough that you're not going to hit it in reasonable code.</p>
<p>Windows commits 4MB per thread (on 64 bit processes; 1MB for 32 bit processes) to page file and faults them into RAM as they are hit. A special page at the top is set to produce a different fault when it is hit; when that fault happens the CLR issues a stack overflow exception. This exception can be caught, but it cannot be ignored; it is re-thrown automatically. (If the top page is faulted a second time, Windows terminates the process, but in practice the process almost always completes.)</p>
<p>Windows allows for threads to have stacks larger or smaller than the default, but it is rare indeed for line-of-business (LOB) programmers to change that limit from the default of 4MB / 1MB.</p>
<p>Some relevant consequences of this implementation decision are:</p>
<p>FIRST: The JIT compiler can generate optimized code quickly; we have many many decades of experience generating code that reifies activation and continuation onto the stack. Common CPUs instruction sets are highly tuned for this pattern.  <strong>The performance penalty of managed code vs native code is relatively small.</strong></p>
<p>SECOND: The maximum call depth for &quot;normal&quot; calls -- not tail calls, not coroutines, and so on -- is small. Typically some thousands of calls. Worse, since frame sizes vary depending on the choices of both the C# and JIT compilers, there is no set call depth limit, unlike, say, some implementations of Python. A program with unbounded &quot;normal&quot; recursion <em>will</em> crash when given data of sufficient size. <strong>Correct .NET programs that do finite but unbounded recursions are fragile when given deep data structures at runtime.</strong></p>
<p>THIRD: Truly infinite recursions -- the base case never runs -- typically crash your program with an unrecoverable exception. <strong>Buggy programs fail fast.</strong></p>
<p>What were the effects of these consequences on the design of C#, a language specifically designed to appeal to professional LOB developers familiar with the C++ family of languages looking for a safer alternative?</p>
<p>Remember, the &quot;design&quot; part of language design is about <em>making reasonable compromises in a world with many incompatible goals.</em></p>
<p>First consequence: Performance</p>
<p>For better or worse, the original dev teams knew that .NET 1.0 and C# 1.0 were going to be heavily judged by a few speed benchmarks. <strong>Keeping the perf penalty of managed code very small was an absolute hard requirement.</strong></p>
<p>You might think, ok, we've got an absolute requirement, so, where's the tradeoff? We've still got to think about the down sides and figure out if they are so down that they're ship-killing, and if not, how to mitigate them.</p>
<p>Second consequence: fragility of &quot;unbounded&quot; recursive programs</p>
<p>This is <strong>horrible</strong>. C# is general purpose, it runs on clients and servers, there are critical business processes written in it, it's got to be robust.</p>
<p>But due to the first consequence, language designers are in a cleft stick not of our own devising. We've <em>already</em> traded robustness for performance in the design of Windows and the CLR. We need to make language design choices in this environment.</p>
<p>Fortunately, C# programmers were assumed to program like traditional C/C++ programmers, with arrays and loops, not like Schemers with their fancy &quot;lists&quot; and &quot;recursion&quot;. (Those Schemers are always up to something suspicious.)</p>
<p>The situation is <em>bad</em>, but the vast majority of OOP LOB programmers aren't ever <em>going</em> to write a program with unbounded recursion on immensely deep data structures. Their programs will work as intended, and run fast, so we can live with this bad situation, and make sure the design of the language appeals to these traditional procedural / OOP programmers.</p>
<p>Third consequence: infinite recursion programs fail fast.</p>
<p>No one cares.</p>
<p>Not one bit.</p>
<p>OK, we cared, but let me explain.  How does a bug get to a customer?</p>
<ul>
<li>The developer thinks a bug</li>
<li>Then types it into a code editor</li>
<li>Then compiles it</li>
<li>Then tests it</li>
<li>Then reviews and commits it</li>
<li>Then nightly tests don't find the bug</li>
<li>And so on, and the bug ships to customers.</li>
</ul>
<p>Each time the bug makes it another step along this path the cost of the fix goes up 10x.</p>
<p>LOB language designers take this seriously! Designing languages, development environments and testing systems that enable developers to identify the bug earlier rather than later is goodness.</p>
<p>What about infinite recursion bugs? Again, not finite but unbounded recursion, where programs are fragile when given large inputs. &quot;You forgot the base case&quot; bugs, where the recursion never bottoms out even on small inputs. Do we care that this fails fast?</p>
<p>No. These kinds of bugs rarely ship to customers because they rarely survive the &quot;test it&quot; phase! An unbounded recursion is just like an infinite loop. Any test case that exercises that code path is going to misbehave badly enough that the test won't pass.</p>
<p>Given the choice between &quot;fail fast and shut down cleanly&quot; and &quot;grind to a halt, chew up memory, never complete&quot; would we <em>prefer</em> &quot;fail fast&quot;? Yes! The fact that we get this is certainly a &quot;nice to have&quot;.  But &quot;nice&quot; is not anywhere close to a high priority for this language design if we're making real tradeoffs.</p>
<hr />
<p>I know that was a very long answer but trading off performance vs robustness is a <em>fundamental</em> design problem for a runtime, and loop-centric vs recursion-centric is a <em>fundamental</em> design problem for many languages, so you are very right to think carefully about this question.</p>
<p>If you're building a functional style language for developers expecting to have unbounded but finite deep recursion on very large data structures, then limiting your virtual stack, or reifying an unbounded virtual stack as very-bounded Windows stack are probably bad ideas -- unless you are also going to work hard on tail recursion or continuation passing style or other fun rewrites.</p>
<p>If you have strict high performance requirements (particularly when compared with tightly optimized machine code) then the .NET Stack class is unlikely to butter any parsnips. Thinking about this now is not a premature optimization; it's ensuring that the requirement is more likely to be met. But maybe your requirements aren't that high.</p>

CC BY-SA 4.0
2024-03-13T04:54:19.663Z
2024-03-18T17:45:01.387Z
2024-03-18T17:45:01.387Z
Eric Lippert
CC BY-SA 4.0
2024-03-15T05:59:53.043Z
Excellent answer, especially in your cleanup of the terminology. But one nit related to that: I think when you say "tail calls," you actually mean "tail call optimisation," right?
cjs
CC BY-SA 4.0
2024-03-15T18:29:35.480Z
off-topic, but is the Windows default stack size really 1 MB, not 1 MiB?  Or is that just an issue of wanting to write in words not numerals, and like any sane person not wanting to write ["mebibytes"](https://en.wikipedia.org/wiki/Byte#Multiple-byte_units), or something really verbose like one million, forty-eight thousand, five hundred and seventy six?  Or is it actually 1MiB including the 4K guard page or something, or even ~48 KiB of guard pages leaving about 1 MB?
Peter Cordes
CC BY-SA 4.0
2024-03-15T18:46:24.520Z
(Trying to answer that question, I found docs like https://learn.microsoft.com/en-us/windows/win32/procthread/thread-stack-size which just use MB when perhaps they meant MiB so that's no help.  They do talk about 64 KB granularity, with a capital K implying KiB.  And some comments on [Why is stack size in C# exactly 1 MB?](https://stackoverflow.com/q/28656872) talking about 1572864 = 1.5 MB and 1,048,576 = 1 MB.)
Peter Cordes
CC BY-SA 4.0
2024-03-15T23:58:50.080Z
@cjs: By a tail call I mean that when the last thing a workflow does is call a method and return its result, then an implementation may choose to re-use the existing stack frame for the new call. Whether a tail call is an optimization or not depends on your cost function!
Eric Lippert
CC BY-SA 4.0
2024-03-16T00:02:43.353Z
@PeterCordes: I had forgotten that it was 4MB on 64 bit processes; I was misremembering. I've fixed the text. Thanks
Eric Lippert
CC BY-SA 4.0
2024-03-18T04:09:11.047Z
I understand a "tail call" to be e.g. `...; CALL foo; RETURN` and "tail call optimisation" to be the conversion of that to `...; GOTO foo` or similar. (This is in pseudo-assembly; obviously the optimisation may need to get a bit more sophisticated in higher-level languages.)
cjs
CC BY-SA 4.0
2024-03-18T17:44:18.183Z
@cjs: Oh, I understand the distinction you're making now, thanks for clarifying. Yes, I meant specifically optimized tail calls. I'll clarify the text.
Eric Lippert
<p>Consider what will happen when a user's program has a bug causing infinite recursion. If your call stack has a bounded size, then their program will raise a runtime error due to overflowing the call stack. If it does not, then their program will raise a runtime error <em>or worse</em> due to running out of memory.</p>
<p>Either way, there is in practice a limit, but in the second case the limit is less predictable, and in the second case running into the limit causes more problems. This is why implementations like CPython which don't use the &quot;real&quot; stack, still impose an explicit limit on the stack size.</p>
<p>It's worth keeping in mind that out of all programs which overflow the stack, the vast proportion of them do so by recursing infinitely due to the programmer's mistake. So even allowing the stack to use all available memory won't help these programs. If you want to support the few programmers who want to intentionally use deep call stacks, you could allow them to opt in via something like Python's <a href="https://docs.python.org/3/library/sys.html#sys.setrecursionlimit" rel="noreferrer"><code>sys.setrecursionlimit</code></a>.</p>

CC BY-SA 4.0
2024-03-12T19:45:12.830Z
2024-03-12T19:45:12.830Z
kaya3
CC BY-SA 4.0
2024-03-12T21:29:13.460Z
it seems reasonable to have general mechanisms for space accounting.  it seems unreasonable and arbitrary to have a mechanism restricted only to the stack
Moonchild
CC BY-SA 4.0
2024-03-12T21:49:47.117Z
@Moonchild Why unreasonable? The stack is an area of memory which can be exhausted very quickly if a program exhibits infinite recursion (a common programming mistake), and which otherwise rarely needs to exceed a moderate limit. In most programs, allocating a lot of memory is not clearly a mistake, but an excessive stack depth is. There are also mechanisms to limit heap usage, of course (e.g. Java's `-Xmx` flag), but a mechanism which only limits the stack is useful because it can be configured more easily according to the number of frames, rather than absolute space.
kaya3
CC BY-SA 4.0
2024-03-12T21:57:46.797Z
I have no idea why somebody would care about the difference between a small number of large stack frames and a large number of small stack frames—the effect is the same.  another thing: 'raise a runtime error _or worse_' surely, the implementation should ensure it can recover equally gracefully from all sorts of memory exhaustion (likely with a mechanism such as a backup heap)
Moonchild
CC BY-SA 4.0
2024-03-12T22:14:04.510Z
CPython stack frames have, I think, a fixed size (eight references to heap-allocated objects), so really the number of stack frames is the only thing you  need to worry about when managing the size of the stack. The default size is by far large enough for any normal program that's not abusing recursion.
chepner
CC BY-SA 4.0
2024-03-12T22:25:24.820Z
@Moonchild The difference is that a programmer can much more easily know how big of a stack limit should be sufficient for their program, without having to figure out what that translates to in bytes. If your recursive function is going to call itself 10,000 levels deep then a maximum recursion depth of 11,000 is definitely plenty.
kaya3
CC BY-SA 4.0
2024-03-12T23:22:15.817Z
Would you agree with the similar argument for loops?  That is: infinite loops are a common bug, so every time we go through a loop again we should update a counter and if that ever exceeds the "loop size", raise a runtime error rather than allowing the program to potentially do something even worse.  If you would not agree with it, what is different in your mind between looping control flows and recursive control flows?
Eric Lippert
CC BY-SA 4.0
2024-03-12T23:25:54.687Z
And what about languages with coroutines that store continuations off the stack? Infinite recursions are common in those languages too, but the stack will never overflow. Should such languages implement a call depth limit to detect potential infinite recursions and raise a runtime error rather than allow the program to do something worse?
Eric Lippert
CC BY-SA 4.0
2024-03-12T23:29:43.503Z
To be clear, because it's hard to convey intent in comments, I am really very interested in the *design* insights here. Programming language design is about balancing between competing principles, and you are putting a high value on a particular principle: that some "wrong" programs that cannot be detected at compile time *should* be reliably detected at runtime. What, if anything, makes infinite recursions so bad compared to other kinds of non-terminating control flows? That's the thrust of my comments.
Eric Lippert
CC BY-SA 4.0
2024-03-12T23:56:37.067Z
@EricLippert The difference is that in the typical case, infinite recursion of regular functions will necessary consume more and more memory until the program fails, so it is just a question of whether to have it fail with a stack overflow error or less gracefully with an out-of-memory error. This reasoning clearly doesn't apply in several cases ─ notably TCO (in which case recursive calls don't grow the stack), stackless coroutines, or regular infinite loops that don't involve function calls ─ but a stack size limit doesn't affect those cases anyway.
kaya3
CC BY-SA 4.0
2024-03-12T23:59:30.473Z
@Moonchild *"surely, the implementation should ensure it can recover equally gracefully from all sorts of memory exhaustion"* ─ that is not so simple. In Java for example, it is much easier to recover from a `StackOverflowError` than it is to recover from an `OutOfMemoryError`, because when the former is caught the stack has already been unwound, whereas when the latter is caught, no memory has necessarily been reclaimed and any new allocation could cause another error.
kaya3
CC BY-SA 4.0
2024-03-13T00:00:24.597Z
stack overflow is a type of out-of-memory condition, and there is no reason to treat it nonuniformly.  if you can recover more gracefully from stack overflows than from other out-of-memory conditions, then you should improve your handling of other out-of-memory conditions
Moonchild
CC BY-SA 4.0
2024-03-13T00:01:13.023Z
there exist languages and implementations that have made suboptimal design choices.  no one disputes this
Moonchild
CC BY-SA 4.0
2024-03-13T00:01:21.563Z
@Moonchild I just explained the reason to treat it non-uniformly - in one case, the fact that you caught the exception means that memory has been reclaimed, in the other, it hasn't. In a garbage-collected language, you cannot simply reclaim heap allocations which there are still live references to just because you ran out of memory ─ that's not the result of a suboptimal design choice.
kaya3
CC BY-SA 4.0
2024-03-13T00:03:39.413Z
in common lisp, or in general any language with an effect handler or condition system, 'catching' an 'exception' happens _before_ the stack is unwound, and this is quite generally useful.  for example, if an allocation—whether 'stack' or 'heap'—fails, then you could attempt to handle this by evicting entries from some cache, making space for the new allocation, and then transparently recovering
Moonchild
CC BY-SA 4.0
2024-03-13T00:03:56.137Z
and I already proposed the use of a backup heap
Moonchild
CC BY-SA 4.0
2024-03-13T00:05:50.590Z
Fun fact, in C# -- unlike some languages -- catching a stack overflow exception after unwinding the stack does not mean that suddenly you've got your stack back and everything is happy. Stack overflow exceptions are rethrown after being handled if I recall correctly.
Eric Lippert
CC BY-SA 4.0
2024-03-13T00:06:17.150Z
@Moonchild Then in Common Lisp, both types of error are equally difficult to handle, since your handler must ensure not to make any new allocation. If like most languages you don't need to keep regular stack frames alive after they have exited with an exception, then you can make stack overflows easier to handle, but you can't do the same for heap overflows.
kaya3
CC BY-SA 4.0
2024-03-13T00:16:23.427Z
@EricLippert *"you are putting a high value on a particular principle: that some "wrong" programs that cannot be detected at compile time should be reliably detected at runtime"* ─ That is not a principle I've stated here. My argument is that runaway recursion is going to cause a runtime error regardless, so it's better for the program to fail without first allocating all the memory the program is allowed to allocate.
kaya3
CC BY-SA 4.0
2024-03-13T00:16:24.087Z
Anyway, getting back to the design considerations, I'm still not sure I'm understanding the difference you're getting at, and I think it's because we're coming at the design question from sort of opposite viewpoints. My viewpoint is: bounded recursion on what you call "normal calls" is a *bad* thing that we accept because we trade it for *good performance for typical programs*. Your viewpoint seems to be that bounded recursion is a *good* thing because *erroneous programs should fail fast*.
Eric Lippert
CC BY-SA 4.0
2024-03-13T00:17:25.007Z
Ah our comments passed each other there. :) To be clear I'm not arguing that any of these principles are right or wrong, but rather that we should understand what the principles are that we're trading off between. Thanks for clarifying.
Eric Lippert
CC BY-SA 4.0
2024-03-13T17:09:02.113Z
@kaya3 "The stack should have a limited size because it can be exhausted very quickly" is circular reasoning.
Criticize SE actions means ban
CC BY-SA 4.0
2024-03-13T17:17:43.133Z
@user253751 No it isn't. The stack can be exhausted very quickly by runaway recursion regardless of what the limit is; and the speed at which it is exhausted is irrelevant to my argument except to say that overflowing faster is *better*. Also please do not put quotation marks around things which are not quotes.
kaya3
CC BY-SA 4.0
2024-03-13T19:44:52.707Z
Well hold on, there's no prima facia reason why a stack should be exhausted quickly by a runaway recursion. A 64 bit architecture could reserve a billion trillion byte stack no problem and hitting the guard page is going to take a while.  (You couldn't on *Windows* due to limitations of the virtual memory manager, but other operating systems are not Windows.)
Eric Lippert
CC BY-SA 4.0
2024-03-13T20:34:56.533Z
@EricLippert I'm not interested in hypothetical scenarios like that, not least because (as I said) my argument doesn't actually depend on the phrasing "very quickly" at all. user253751 is just plucking something out of context. If runaway recursion would *slowly* overflow the stack (while using up more of the machine's available memory) then that makes it even more beneficial to impose a moderate limit on the stack depth so that that doesn't happen.
kaya3
CC BY-SA 4.0
2024-03-14T01:32:15.577Z
@EricLippert - A function that recurses into itself twice (consider a family tree parser, or even a JSON generator/parser) each round will make 2^64 calls in just 64 steps. Now, your 64bit CPU only has 2^64 addresses (not necessarily bytes because thre are CPUs where each address point to a 2,4 or 8 bytes of RAM) and in 64 steps that funciton will definitely use up more than all available memory. Just because YOUR family does not have 2^64 people in it does not mean some junior dev cannot accidentaly procedually create one in code.
slebetman
CC BY-SA 4.0
2024-03-15T12:37:33.220Z
@slebetman not sure what point you're making, but such a function won't need more than 64 stack frames. It'll only use up lots of memory if it allocates memory that continues living after each recursive call has returned, in which case, I guess it's probably on the heap?
Ben Millwood
<p>Stack limits permit a virtual machine to handle stack overflows within the language.  If you don't provide one, then the consequences of a stack overflow can only be handled by the underlying language.  This is analogous to the difference between providing exception handling or merely requiring everyone to call exit() to terminate a program if an exceptional behavior occurs.</p>
<p>If it's at all remotely possible that others might implement their own version of the virtual machine, defining this behavior in the language is likely preferable.  Otherwise every implementation may have their own quirky behaviors.  &quot;Unspecified behavior&quot; is a powerful tool for language creation, but it's also a crutch that leads to lots of incompatible behaviors.</p>

CC BY-SA 4.0
2024-03-13T03:51:25.013Z
2024-03-13T03:51:25.013Z
Cort Ammon
CC BY-SA 4.0
2024-03-13T05:04:41.887Z
This is an excellent point but I'll note that a stack limit just makes it *easier* to handle such user overflows. VM authors can handle user-code-induced stack faults in a variety of ways, none of which are pleasant, even in managed code. I wrote the stack overflow code for JScript in 1994 that had to work on both Windows 3.1 and Windows 95 without ever crashing Internet Explorer, so you kids today with your rock music can get off my lawn.
Eric Lippert
CC BY-SA 4.0
2024-03-13T19:51:25.957Z
Correction, 1996, not 1994, I was an intern in 1994!
Eric Lippert
<p>In the face of language implementations where the stack cannot have unbounded size, algorithms which could otherwise be cleanly expressed become contorted, and must use mechanisms like explicit stacks or continuation-passing style, obscuring the flow of control and computation.  This is not very nice.</p>
<blockquote>
<p>a stack that may grow to infinity (for example, with a non-optimized recursion that never ends) takes up a lot of memory and might slow down computer operation (if we take an extreme case)</p>
</blockquote>
<p>If you need a lot of memory, then you need a lot of memory; the question is simply where and how you allocate it.  I could as easily say:</p>
<blockquote>
<p>a heap that may grow to infinity takes up a lot of memory and might slow down computer operation (if we take an extreme case)</p>
</blockquote>

CC BY-SA 4.0
2024-03-12T19:02:46.437Z
2024-03-12T19:02:46.437Z
Moonchild
CC BY-SA 4.0
2024-03-13T19:27:46.890Z
I have little to add to this. Recursive implementations are often the most straightforward. There is no inherent reason these "should" instead be using loops or continuations when they can use a suitable call stack just as well; it's just complicating the implementation. I feel all the people who argue that recursion should be crippled may be leaning too heavily on the imperative side of things. What would they say if I limited their loops to 16k iterations, or their arrays to 16k elements "in case you have an infinite loop or an array that is getting too large"?
Luatic
# Should a virtual machine stack have a limited size?
Posted by: username_0 on 2024-03-12
I'm writing a register- and stack-based virtual machine. My goal is to have something easy to use and general purpose, so I abstain from any form of hardware limitation in its design. Since my VM's stack is implemented with a high-level data structure (the [Stack](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.stack-1?view=net-8.0) provided by .NET), there is no theoretical limitation on its size. Knowing that I am able to define a stack of indeterminate size (limited only by hardware) my question is whether or not I should limit the stack size for my VM.

I see the following theoretical advantages to an infinite stack size:

* No overflow can occur ;
* Deep recursion is possible.

I also see the following disadvantages:

* An overflow is sometimes a sign that there are things to improve in the underlying code (typically a recursion that should be changed to a loop or with continuations) which the VM will then no longer raise;
* A VM stack of indeterminate size can massively overflow and slow down the computer (in the extreme case).

For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.

So, given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?
**Tags:** interpreters stack virtual-machine
> **Comments:**
> **username_1**: Welcome to PLDI Stack Exchange! This question is soliciting design tradeoffs but does not define what a good answer is. I advise you to refine it so it describes a specific implementation problem to be solved, as detailed in the [help/on-topic].  
> **username_2**: I think it should have *some* minimum below the RAM limit, because otherwise an infinite recursion will slow your system and take longer to overflow, and in practice, operations which use a lot of stack size are usually non-ideal (you shouldn't be doing `O(n)` stack recursion if your function can be implemented with a tail call). You can make the limit higher than C though, like 512 MB (what Haskell used to use).  
> **username_2**: But it depends on whether the language is suited more or less towards recursion, and maybe there are other factors for smaller stack sizes I'm not aware about. In practice I've rarely seen Stack Overflows which weren't infinite recursion (or overly large so that the algorithm would take too long to compute if it didn't terminate). And when I did, I think it made sense to rewrite the algorithm to use tail recursion or something else anyways. Maybe it's less expensive to write your own "stack" in a function that needs to recurse a lot.  
> **username_0**: @Ginger Thanks for pointing that out, I've edited the question to try and meet expectations, I hope it will.  
> **username_3**: I'll note that "possible" is correct: in C# neither the language nor the runtime guarantee that unbounded recursions will result in a stack overflow; the compiler may rewrite to heap-allocated continuations and the runtime may make tail calls. Nor do they make any guarantees as to how much short-lifetime storage (aka "stack") is available to a program. Do you see these design choices as strengths to emulate or weaknesses to address in your proposed language / runtime?  
> **username_4**: It should have a *fixed* size, so that it operates consistently on all host platforms/implementations  
> **username_5**: Note 'fixed' also means that you want it to be independent of later changes. If you make it, e.g. 8KiB, someone _will_ use 8191B and then get annoyed down the line when a later bugfix makes your implementation use an extra 4B internally.  
> **username_6**: @flumperious: Could be difficult if you support a variety of platforms. If you set that size small enough that your language can run programs on an Arduino, it's going to be a very frustrating limitation for someone running on a big server with a terabyte of RAM.  
> **username_4**: Stack sizes stay small (8MB for x86/64) even on high end servers/supercomputers (unless you're talking about ones specialised for a recursive algorithm), its more often a problem the other way round, e.g. porting java to arduino would be difficult/impossible (from cursory googling, it seems to be implemented in hardware extention boards)  
> **username_7**: Technically speaking, a 16 exabyte (maximum addressable memory with 64 bits) stack is “limited”.  
---
## 5 answers
### Answer by username_3 on 2024-03-13. Score: 17 | Accepted answer
> given that a stack implemented in a virtual machine interpreter is able to have an infinite size, why would we limit its capacity or not?

Great question, let me first nitpick and say that "unbounded" is intended for "infinite" here. *No stack ever has an infinite size.*

For the purposes of this discussion I'd like to distinguish between an *infinite* recursion, where a bug in a recursive algorithm means that it *never* reaches its base case, and a *finite but unbounded* recursion, where the depth of the recursion is equal to the size *at runtime* of the data passed in; we recurse on every node in a linked list, and so if we want a thousand, a million, a billion calls all we have to do is pass in a list of a thousand, a million, a billion items.

I can maybe give you some insights into how we would consider this question when designing a general-purpose language like C# for a general-purpose runtime like the .NET CLR.

> For example, Python, C# and Java (to name but a few) are all languages compiled in a stack-based VM where overflow is possible.

Yes, but let's again be precise about C#, since that's what I know best. "Possible" is correct. The CLR specification does not say what size the "short term memory pool" is, and it does not put any particular limit on the depth of calls. Nor does it guarantee that unbounded calls *will* blow the stack. The CLR reserves the right to optimize tail calls, and historically has done so with... [mixed results at best let's say.](https://github.com/dotnet/runtime/issues/2191)

And of course C# has closed-over locals, coroutines, lots of ways that activations don't form stacks, so continuation information can be stored on the long term pool at the discretion of the compiler.

But I'm getting ahead of myself. Let's talk a bit about your typical Windows implementation of the CLR and how both manage the stack. Do forgive occasional simplifications where the messy details are not relevant for your purposes.

The CLR spec does not require any particular implementation strategy as far as stack management is concerned, but the Microsoft implementations typically do the following: IL is JIT-compiled into machine code, and that machine code is what you'd expect. The temporary storage pool is implemented as a bunch of pages called "the stack", one stack per thread. The stack holds activation frames for unlifted locals that were not optimized into registers, and continuations in the form of return addresses. (And continuations for exception control flow and so on.) Frame size is limited in the CLR and I don't recall what the limit is, but it's large enough that you're not going to hit it in reasonable code.

Windows commits 4MB per thread (on 64 bit processes; 1MB for 32 bit processes) to page file and faults them into RAM as they are hit. A special page at the top is set to produce a different fault when it is hit; when that fault happens the CLR issues a stack overflow exception. This exception can be caught, but it cannot be ignored; it is re-thrown automatically. (If the top page is faulted a second time, Windows terminates the process, but in practice the process almost always completes.)

Windows allows for threads to have stacks larger or smaller than the default, but it is rare indeed for line-of-business (LOB) programmers to change that limit from the default of 4MB / 1MB.

Some relevant consequences of this implementation decision are:

FIRST: The JIT compiler can generate optimized code quickly; we have many many decades of experience generating code that reifies activation and continuation onto the stack. Common CPUs instruction sets are highly tuned for this pattern. **The performance penalty of managed code vs native code is relatively small.**

SECOND: The maximum call depth for "normal" calls -- not tail calls, not coroutines, and so on -- is small. Typically some thousands of calls. Worse, since frame sizes vary depending on the choices of both the C# and JIT compilers, there is no set call depth limit, unlike, say, some implementations of Python. A program with unbounded "normal" recursion *will* crash when given data of sufficient size. **Correct .NET programs that do finite but unbounded recursions are fragile when given deep data structures at runtime.**

THIRD: Truly infinite recursions -- the base case never runs -- typically crash your program with an unrecoverable exception. **Buggy programs fail fast.**

What were the effects of these consequences on the design of C#, a language specifically designed to appeal to professional LOB developers familiar with the C++ family of languages looking for a safer alternative?

Remember, the "design" part of language design is about *making reasonable compromises in a world with many incompatible goals.*

First consequence: Performance

For better or worse, the original dev teams knew that .NET 1.0 and C# 1.0 were going to be heavily judged by a few speed benchmarks. **Keeping the perf penalty of managed code very small was an absolute hard requirement.**

You might think, ok, we've got an absolute requirement, so, where's the tradeoff? We've still got to think about the down sides and figure out if they are so down that they're ship-killing, and if not, how to mitigate them.

Second consequence: fragility of "unbounded" recursive programs

This is **horrible**. C# is general purpose, it runs on clients and servers, there are critical business processes written in it, it's got to be robust.

But due to the first consequence, language designers are in a cleft stick not of our own devising. We've *already* traded robustness for performance in the design of Windows and the CLR. We need to make language design choices in this environment.

Fortunately, C# programmers were assumed to program like traditional C/C++ programmers, with arrays and loops, not like Schemers with their fancy "lists" and "recursion". (Those Schemers are always up to something suspicious.)

The situation is *bad*, but the vast majority of OOP LOB programmers aren't ever *going* to write a program with unbounded recursion on immensely deep data structures. Their programs will work as intended, and run fast, so we can live with this bad situation, and make sure the design of the language appeals to these traditional procedural / OOP programmers.

Third consequence: infinite recursion programs fail fast.

No one cares.

Not one bit.

OK, we cared, but let me explain. How does a bug get to a customer?

* The developer thinks a bug
* Then types it into a code editor
* Then compiles it
* Then tests it
* Then reviews and commits it
* Then nightly tests don't find the bug
* And so on, and the bug ships to customers.

Each time the bug makes it another step along this path the cost of the fix goes up 10x.

LOB language designers take this seriously! Designing languages, development environments and testing systems that enable developers to identify the bug earlier rather than later is goodness.

What about infinite recursion bugs? Again, not finite but unbounded recursion, where programs are fragile when given large inputs. "You forgot the base case" bugs, where the recursion never bottoms out even on small inputs. Do we care that this fails fast?

No. These kinds of bugs rarely ship to customers because they rarely survive the "test it" phase! An unbounded recursion is just like an infinite loop. Any test case that exercises that code path is going to misbehave badly enough that the test won't pass.

Given the choice between "fail fast and shut down cleanly" and "grind to a halt, chew up memory, never complete" would we *prefer* "fail fast"? Yes! The fact that we get this is certainly a "nice to have". But "nice" is not anywhere close to a high priority for this language design if we're making real tradeoffs.

---

I know that was a very long answer but trading off performance vs robustness is a *fundamental* design problem for a runtime, and loop-centric vs recursion-centric is a *fundamental* design problem for many languages, so you are very right to think carefully about this question.

If you're building a functional style language for developers expecting to have unbounded but finite deep recursion on very large data structures, then limiting your virtual stack, or reifying an unbounded virtual stack as very-bounded Windows stack are probably bad ideas -- unless you are also going to work hard on tail recursion or continuation passing style or other fun rewrites.

If you have strict high performance requirements (particularly when compared with tightly optimized machine code) then the .NET Stack class is unlikely to butter any parsnips. Thinking about this now is not a premature optimization; it's ensuring that the requirement is more likely to be met. But maybe your requirements aren't that high.
> **Comments:**
> **username_9** (2024-03-15): Excellent answer, especially in your cleanup of the terminology. But one nit related to that: I think when you say "tail calls," you actually mean "tail call optimisation," right?  
> **username_10** (2024-03-15): off-topic, but is the Windows default stack size really 1 MB, not 1 MiB?  Or is that just an issue of wanting to write in words not numerals, and like any sane person not wanting to write ["mebibytes"](https://en.wikipedia.org/wiki/Byte#Multiple-byte_units), or something really verbose like one million, forty-eight thousand, five hundred and seventy six?  Or is it actually 1MiB including the 4K guard page or something, or even ~48 KiB of guard pages leaving about 1 MB?  
> **username_10** (2024-03-15): (Trying to answer that question, I found docs like https://learn.microsoft.com/en-us/windows/win32/procthread/thread-stack-size which just use MB when perhaps they meant MiB so that's no help.  They do talk about 64 KB granularity, with a capital K implying KiB.  And some comments on [Why is stack size in C# exactly 1 MB?](https://stackoverflow.com/q/28656872) talking about 1572864 = 1.5 MB and 1,048,576 = 1 MB.)  
> **username_3** (2024-03-15): @cjs: By a tail call I mean that when the last thing a workflow does is call a method and return its result, then an implementation may choose to re-use the existing stack frame for the new call. Whether a tail call is an optimization or not depends on your cost function!  
> **username_3** (2024-03-16): @PeterCordes: I had forgotten that it was 4MB on 64 bit processes; I was misremembering. I've fixed the text. Thanks  
> **username_9** (2024-03-18): I understand a "tail call" to be e.g. `...; CALL foo; RETURN` and "tail call optimisation" to be the conversion of that to `...; GOTO foo` or similar. (This is in pseudo-assembly; obviously the optimisation may need to get a bit more sophisticated in higher-level languages.)  
> **username_3** (2024-03-18): @cjs: Oh, I understand the distinction you're making now, thanks for clarifying. Yes, I meant specifically optimized tail calls. I'll clarify the text.  
---
### Answer by username_11 on 2024-03-12. Score: 13
Consider what will happen when a user's program has a bug causing infinite recursion. If your call stack has a bounded size, then their program will raise a runtime error due to overflowing the call stack. If it does not, then their program will raise a runtime error *or worse* due to running out of memory.

Either way, there is in practice a limit, but in the second case the limit is less predictable, and in the second case running into the limit causes more problems. This is why implementations like CPython which don't use the "real" stack, still impose an explicit limit on the stack size.

It's worth keeping in mind that out of all programs which overflow the stack, the vast proportion of them do so by recursing infinitely due to the programmer's mistake. So even allowing the stack to use all available memory won't help these programs. If you want to support the few programmers who want to intentionally use deep call stacks, you could allow them to opt in via something like Python's [`sys.setrecursionlimit`](https://docs.python.org/3/library/sys.html#sys.setrecursionlimit).
> **Comments:**
> **username_12** (2024-03-12): it seems reasonable to have general mechanisms for space accounting.  it seems unreasonable and arbitrary to have a mechanism restricted only to the stack  
> **username_11** (2024-03-12): @Moonchild Why unreasonable? The stack is an area of memory which can be exhausted very quickly if a program exhibits infinite recursion (a common programming mistake), and which otherwise rarely needs to exceed a moderate limit. In most programs, allocating a lot of memory is not clearly a mistake, but an excessive stack depth is. There are also mechanisms to limit heap usage, of course (e.g. Java's `-Xmx` flag), but a mechanism which only limits the stack is useful because it can be configured more easily according to the number of frames, rather than absolute space.  
> **username_12** (2024-03-12): I have no idea why somebody would care about the difference between a small number of large stack frames and a large number of small stack frames—the effect is the same.  another thing: 'raise a runtime error _or worse_' surely, the implementation should ensure it can recover equally gracefully from all sorts of memory exhaustion (likely with a mechanism such as a backup heap)  
> **username_13** (2024-03-12): CPython stack frames have, I think, a fixed size (eight references to heap-allocated objects), so really the number of stack frames is the only thing you  need to worry about when managing the size of the stack. The default size is by far large enough for any normal program that's not abusing recursion.  
> **username_11** (2024-03-12): @Moonchild The difference is that a programmer can much more easily know how big of a stack limit should be sufficient for their program, without having to figure out what that translates to in bytes. If your recursive function is going to call itself 10,000 levels deep then a maximum recursion depth of 11,000 is definitely plenty.  
> **username_3** (2024-03-12): Would you agree with the similar argument for loops?  That is: infinite loops are a common bug, so every time we go through a loop again we should update a counter and if that ever exceeds the "loop size", raise a runtime error rather than allowing the program to potentially do something even worse.  If you would not agree with it, what is different in your mind between looping control flows and recursive control flows?  
> **username_3** (2024-03-12): And what about languages with coroutines that store continuations off the stack? Infinite recursions are common in those languages too, but the stack will never overflow. Should such languages implement a call depth limit to detect potential infinite recursions and raise a runtime error rather than allow the program to do something worse?  
> **username_3** (2024-03-12): To be clear, because it's hard to convey intent in comments, I am really very interested in the *design* insights here. Programming language design is about balancing between competing principles, and you are putting a high value on a particular principle: that some "wrong" programs that cannot be detected at compile time *should* be reliably detected at runtime. What, if anything, makes infinite recursions so bad compared to other kinds of non-terminating control flows? That's the thrust of my comments.  
> **username_11** (2024-03-12): @EricLippert The difference is that in the typical case, infinite recursion of regular functions will necessary consume more and more memory until the program fails, so it is just a question of whether to have it fail with a stack overflow error or less gracefully with an out-of-memory error. This reasoning clearly doesn't apply in several cases ─ notably TCO (in which case recursive calls don't grow the stack), stackless coroutines, or regular infinite loops that don't involve function calls ─ but a stack size limit doesn't affect those cases anyway.  
> **username_11** (2024-03-12): @Moonchild *"surely, the implementation should ensure it can recover equally gracefully from all sorts of memory exhaustion"* ─ that is not so simple. In Java for example, it is much easier to recover from a `StackOverflowError` than it is to recover from an `OutOfMemoryError`, because when the former is caught the stack has already been unwound, whereas when the latter is caught, no memory has necessarily been reclaimed and any new allocation could cause another error.  
> **username_12** (2024-03-13): stack overflow is a type of out-of-memory condition, and there is no reason to treat it nonuniformly.  if you can recover more gracefully from stack overflows than from other out-of-memory conditions, then you should improve your handling of other out-of-memory conditions  
> **username_12** (2024-03-13): there exist languages and implementations that have made suboptimal design choices.  no one disputes this  
> **username_11** (2024-03-13): @Moonchild I just explained the reason to treat it non-uniformly - in one case, the fact that you caught the exception means that memory has been reclaimed, in the other, it hasn't. In a garbage-collected language, you cannot simply reclaim heap allocations which there are still live references to just because you ran out of memory ─ that's not the result of a suboptimal design choice.  
> **username_12** (2024-03-13): in common lisp, or in general any language with an effect handler or condition system, 'catching' an 'exception' happens _before_ the stack is unwound, and this is quite generally useful.  for example, if an allocation—whether 'stack' or 'heap'—fails, then you could attempt to handle this by evicting entries from some cache, making space for the new allocation, and then transparently recovering  
> **username_12** (2024-03-13): and I already proposed the use of a backup heap  
> **username_3** (2024-03-13): Fun fact, in C# -- unlike some languages -- catching a stack overflow exception after unwinding the stack does not mean that suddenly you've got your stack back and everything is happy. Stack overflow exceptions are rethrown after being handled if I recall correctly.  
> **username_11** (2024-03-13): @Moonchild Then in Common Lisp, both types of error are equally difficult to handle, since your handler must ensure not to make any new allocation. If like most languages you don't need to keep regular stack frames alive after they have exited with an exception, then you can make stack overflows easier to handle, but you can't do the same for heap overflows.  
> **username_11** (2024-03-13): @EricLippert *"you are putting a high value on a particular principle: that some "wrong" programs that cannot be detected at compile time should be reliably detected at runtime"* ─ That is not a principle I've stated here. My argument is that runaway recursion is going to cause a runtime error regardless, so it's better for the program to fail without first allocating all the memory the program is allowed to allocate.  
> **username_3** (2024-03-13): Anyway, getting back to the design considerations, I'm still not sure I'm understanding the difference you're getting at, and I think it's because we're coming at the design question from sort of opposite viewpoints. My viewpoint is: bounded recursion on what you call "normal calls" is a *bad* thing that we accept because we trade it for *good performance for typical programs*. Your viewpoint seems to be that bounded recursion is a *good* thing because *erroneous programs should fail fast*.  
> **username_3** (2024-03-13): Ah our comments passed each other there. :) To be clear I'm not arguing that any of these principles are right or wrong, but rather that we should understand what the principles are that we're trading off between. Thanks for clarifying.  
> **username_14** (2024-03-13): @kaya3 "The stack should have a limited size because it can be exhausted very quickly" is circular reasoning.  
> **username_11** (2024-03-13): @user253751 No it isn't. The stack can be exhausted very quickly by runaway recursion regardless of what the limit is; and the speed at which it is exhausted is irrelevant to my argument except to say that overflowing faster is *better*. Also please do not put quotation marks around things which are not quotes.  
> **username_3** (2024-03-13): Well hold on, there's no prima facia reason why a stack should be exhausted quickly by a runaway recursion. A 64 bit architecture could reserve a billion trillion byte stack no problem and hitting the guard page is going to take a while.  (You couldn't on *Windows* due to limitations of the virtual memory manager, but other operating systems are not Windows.)  
> **username_11** (2024-03-13): @EricLippert I'm not interested in hypothetical scenarios like that, not least because (as I said) my argument doesn't actually depend on the phrasing "very quickly" at all. user253751 is just plucking something out of context. If runaway recursion would *slowly* overflow the stack (while using up more of the machine's available memory) then that makes it even more beneficial to impose a moderate limit on the stack depth so that that doesn't happen.  
> **username_15** (2024-03-14): @EricLippert - A function that recurses into itself twice (consider a family tree parser, or even a JSON generator/parser) each round will make 2^64 calls in just 64 steps. Now, your 64bit CPU only has 2^64 addresses (not necessarily bytes because thre are CPUs where each address point to a 2,4 or 8 bytes of RAM) and in 64 steps that funciton will definitely use up more than all available memory. Just because YOUR family does not have 2^64 people in it does not mean some junior dev cannot accidentaly procedually create one in code.  
> **username_16** (2024-03-15): @slebetman not sure what point you're making, but such a function won't need more than 64 stack frames. It'll only use up lots of memory if it allocates memory that continues living after each recursive call has returned, in which case, I guess it's probably on the heap?  
---
### Answer by username_17 on 2024-03-13. Score: 5
Stack limits permit a virtual machine to handle stack overflows within the language. If you don't provide one, then the consequences of a stack overflow can only be handled by the underlying language. This is analogous to the difference between providing exception handling or merely requiring everyone to call exit() to terminate a program if an exceptional behavior occurs.

If it's at all remotely possible that others might implement their own version of the virtual machine, defining this behavior in the language is likely preferable. Otherwise every implementation may have their own quirky behaviors. "Unspecified behavior" is a powerful tool for language creation, but it's also a crutch that leads to lots of incompatible behaviors.
> **Comments:**
> **username_3** (2024-03-13): This is an excellent point but I'll note that a stack limit just makes it *easier* to handle such user overflows. VM authors can handle user-code-induced stack faults in a variety of ways, none of which are pleasant, even in managed code. I wrote the stack overflow code for JScript in 1994 that had to work on both Windows 3.1 and Windows 95 without ever crashing Internet Explorer, so you kids today with your rock music can get off my lawn.  
> **username_3** (2024-03-13): Correction, 1996, not 1994, I was an intern in 1994!  
---
### Answer by username_12 on 2024-03-12. Score: 5
In the face of language implementations where the stack cannot have unbounded size, algorithms which could otherwise be cleanly expressed become contorted, and must use mechanisms like explicit stacks or continuation-passing style, obscuring the flow of control and computation. This is not very nice.

> a stack that may grow to infinity (for example, with a non-optimized recursion that never ends) takes up a lot of memory and might slow down computer operation (if we take an extreme case)

If you need a lot of memory, then you need a lot of memory; the question is simply where and how you allocate it. I could as easily say:

> a heap that may grow to infinity takes up a lot of memory and might slow down computer operation (if we take an extreme case)
> **Comments:**
> **username_18** (2024-03-13): I have little to add to this. Recursive implementations are often the most straightforward. There is no inherent reason these "should" instead be using loops or continuations when they can use a suitable call stack just as well; it's just complicating the implementation. I feel all the people who argue that recursion should be crippled may be leaning too heavily on the imperative side of things. What would they say if I limited their loops to 16k iterations, or their arrays to 16k elements "in case you have an infinite loop or an array that is getting too large"?  
---
### Answer by username_8 on 2024-03-15. Score: 0
Yes, you should limit the stack size (as well as all other data structures, i.e. heap or whatever you have), unless it is for some reason incredibly hard to do (e.g. huge overhead in processing time).

No, you do not *have* to make the user (programmer) care too much about it. You can achieve this by setting the default limit to an "unreachable" maximum (i.e., 2^64-1 or whatever is a convenient big number - many programming languages/libraries have a constant like MAX\_LONG or something like that).

Yes, you should make this user-configurable. You do not know all use-cases for your application in the future, and an application that uses potentially unlimited memory can be hard to maintain. For example, when deploying a container in Kubernetes, you always declare a maximum RAM limit outside of the executable, in the Kubernetes declaration for your deployment. You also try to get away with as little RAM as possible to allow the orchestrator to distribute the deployments amongst a given amount of nodes efficiently.

When your application exceeds that amount of RAM, it will immediately and unavoidably be force-killed by Kubernetes. If you have a way to set your maximum stack size, the programmer can make an educated guess and set that maximum sufficiently small to avoid his app being killed in this manner. Of course he then can run out of stack space by reaching that limit internally, but your programming language can then spit out a meaningful error message, giving the programmer a working chance to fix the issue.

This is just an example; the same applies of course if your program is simply started on some user's PC. Nobody wants any random program to potentially grab all memory and bring the PC to swap (or kill *other* random programs just because they unfortunately requested more memory after yours had filled the available RAM fully).
---
