3 ms·

How can you predict how much stack you need? Isn't this basically the halting problem?

• phkahler 5y ago
  With the exception of recursion, static analysis can answer that question.
• Verdex 5y ago
  As far as I know, there aren't any languages which provide a way to do this out of the box. If a language wants to provide an environment where no stack overflows can happen, then it needs to provide a runtime where the stack programs use is transplanted over to the heap as it gets too large (or maybe it just starts out there). At this point the answer is that you only need a stack big enough to hold your runtime (which you can engineer to be sufficiently small always). Of course you can imagine a language where your function signature includes how much stack space it takes up. The stack size being recursively calculated by looking at all the functions your function calls etc. If recursion is included, then you're correct that this would require solving the halting problem. The obvious solution would be to just not allow recursion. Although, if you also consider languages like Idris (which are technically sometimes not turing complete) you can setup a termination checker and then certain rules can give you an upper bound on how long a recursive function will run (and therefore how much stack it takes up).
• deleted 5y ago
  [deleted]