1

I'm wondering if it was theoretically possible for a compiler to determine maximum stack depth at compile time if a limitation was placed on the program. The limitation being that you can't use recursion or cyclic calls. With cyclic calls I don't mean loops but function calls (a -> b, b -> a). The program flow would then have to follow an directed acyclic graph basically.

Under these circumstances, can every program still be written or are there programs that can only work without above limitations?

18
  • 2
    Unfortunately it is not clear what you mean by "recursion" here and how can you "not use it". Every machine code can literaly be written without a single call. That's because "call" is nothing else than a fancy "jump". But can you write code without "jump" instruction? Except for trivial programs, that's impossible. But then you remove a lot more than just "recursion", you also remove all loops and ifs. In fact: recursion and iteration are equivalent. Thus: can you rewrite every program without iteration? No, that is not possible.
    – freakish
    May 15 at 13:47
  • 1
    @glades A loop is a cycle.
    – JimmyJames
    May 15 at 14:16
  • 4
    @glades You should clarify because all loops are cycles
    – JimmyJames
    May 15 at 14:21
  • 9
    @glades If loops are allowed, then I think the answer is a trivial 'yes' given that a language can be Turing complete without supporting recursion.
    – JimmyJames
    May 15 at 14:27
  • 6
    The question title appears to be asking different question than the body. The title asks "can you write every program..." (for which the answer is likely yes) and the question body asks if the compiler can determine there is no recursion or cyclic calls. These are very different problems to solve. May 15 at 18:39

9 Answers 9

9

I think it is clear we are talking about a programming language environment where all code is organized inside functions with some local scope, all functions exist at compile time and the executing environment is using a call stack which is used to deal with the function calls.

In that case, "no direct or indirect recursive function calls" simply means the call graph is a tree. When one stops the program at any point in time (for example, with a debugger), one can see the call stack as a sequence of function calls, and no function must occur twice within that sequence, otherwise it would be a recursion.

Hence, a trivial compile-time determinable upper limit for the call stack size for such a program is the total number of functions within the program. When the only kind of allowed function calls are static ones, which can be determined at compile time, there is a better bound, namely the depth of the call tree. This can be derived easily from the information which function calls which other function.

Unfortunately, as soon as you allow dynamic function calls, it cannot be determined reliably at compile time whether a program will do recursive calls at run time or not. Most major programming languages of today have mechanisms for making dynamic function calls, deciding which function to call based on certain run-time criteria. Functions or function references may be passed around as parameters to other functions. This allows to write functions which can call any other function in the program including itself (or not), and one cannot easily find out at compile time if there is some restriction on the set of "any other functions" which forbids recursion (or not). I don't have a formal proof at hand, but I am convinced this makes determination if a program will make recursive calls a equivalent to the halting problem.

Another issue I see is the following. As you probably know, any recursive program can be converted to a non-recursive one. In general, you have to introduce some own stack structure for this. Such a converted program may have a compile-time determinable upper bound on the call stack size after the conversion, but now the custom stack can grow arbitrarily. Hence, though the call stack size may be limited, the total size of required memory or memory limits will not change. (Side note: in reality, such a conversion can make a lot of sense for programming environments where the call stack size cannot be changed dynamically, but custom stack sizes can.)

3
  • At least one C-dialect implementation I've used assumes that a call via function pointer is capable of calling any function whose signature matches the function pointer, but no other functions. Having a function pointer and all functions that should be viewed as "reachable" through it return a structure type that is used for no other purpose may break any cycles that might otherwise arise. This is a practical technique in a real implementation I've used.
    – supercat
    May 15 at 21:16
  • 1
    @supercat: This is called defunctionalization. Indeed, it's known that CPS transformation followed by defunctionalization will convert general recursion into iteration.
    – Corbin
    May 15 at 22:08
  • Presumably the sketch of the proof of halting-equivalence: Suppose we have an oracle for RECURSIVE. Given a TM, create a non-recursive TM simulator and run it with that TM as input, where after halting it immediately calls an infinitely-recursive function. This decides halting
    – Kaia
    May 16 at 0:34
8

The strict hierarchy of tasks that are computable under one theoretical model of computation vs. another really only exists "in the limit", i.e. when you allow unlimited resources. There are problems that can be solved with a deterministic finite-state automaton, and there are problems that can't no matter how many states you allow.

In real life all resources are limited, so technically all programming paradigms are equivalent in power. However, some make the same task much, much smaller and simpler.

For instance, exploring a labyrinth is pretty simple with recursion and a call stack; you can still write essentially the same program without recursion, but you will have to essentially re-implement the stack functionality yourself, which is almost always going to be a lot less efficient than what the compiler would have given you. This is why choosing the right paradigm matters even for real-life problems.

10
  • 3
    That's interesting since I did that once, I used an artificial preallocated stack. It's totally possible and even faster since you avoid function calls.
    – glades
    May 15 at 14:15
  • Instantiation of local variables within a called function is called a "stack frame" because in theory it has certain characteristics analogous to the stack data structure.
    – rwong
    May 15 at 14:32
  • 7
    Do you have any source for the "almost always going to be a lot less efficient" claim? My understanding is that this is situational, and that an simple example like path finding can be faster with an explicit stack.
    – JonasH
    May 15 at 14:49
  • @JonasH only if you know more or less how big the stack is going to be. A priori. With dynamic allocations I highly doubt it is ever faster.
    – freakish
    May 15 at 15:24
  • @freakish The call stack is fixed sized anyway, at least on the systems I have used. So that seem the most fair to use for comparison. If you have an no idea about the stack depth you will need dynamic allocations.
    – JonasH
    May 16 at 6:48
1

Use a compiler to translate your program into assembler. Then write a simulator that can simulate assembler programs. Then replace the assembler code with a huge array of static data.

1

The max call stack depth for a program without recursion would be the number of functions in the program.

It is always possible to rewrite recursive functions to be non-recursive with the help of a data structure like a linked list.

So the immediate answer is yes, you can rewrite any program to have a fixed-size call stack or eliminate the call stack altogether. But it comes at the prize of introducing another data structure of unbounded size.

0

Take a read of the Church Turing Thesis, in short all recursion can be replaced with iteration. Now that your limitation is removed, the question is simply can a compiler determine max stack usage.

The answer to that is unfortunately no. You could write a simple program that loops while random bool is true, the body of the loop containing a push to the stack. There's no way to know if your random bool is true every iteration for eternity.

You could do what GCC does and flag functions as static, bounded, or dynamic. But you may never be able to determine max stack usage of all programs.

To answer your specific questions:

  1. Can every program still be written without recursion or cyclic calls? Yes, all recursion can be replaced with iteration.
  2. Is it possible for a compiler to determine maximum stack depth at compile time? No, not all programs are deterministic.
2
  • Thanks for the link. Considering loops in the traditional sense of a higher order programming language (not on assembly or instruction basis), the loop would never end in the sense, but the stack would also not grow since within the constraints of a programming language (like C for example), the recurring instantiation of a bool within the loop body would occupy the same space in memory. So even if a program is not "effectively computable" does this really mean that space complexity must also be unknown?
    – glades
    May 16 at 12:14
  • @glades "a push to the stack" could mean something like a linked list, each iteration of the loop adds to the linked list. Note that many languages (eg C) do not have garbage collection, so you could endlessly (and meaninglessly) malloc and it won't be cleared when you leave the scope of the loop iteration.
    – jgn
    May 17 at 8:10
0

With a normal programming language, it's theoretically possible to write a static analyzer that determines a program's maximum stack usage, with the caveat that for some programs, the analyzer will answer “I don't know”.

Proof that it's possible: “always answer ’I don't know‘” is a correct (if boring) solution. Proof that the caveat is necessary if there is a way to write programs that overflow the stack: for any static analyzer, there exists a subprogram undecidable() such that the analyzer cannot decide whether it returns true or false. The analyzer cannot analyze the stack usage of if undecidable() then cause_stack_overflow() else do_nothing().

So the interesting questions are:

  1. Are there programming languages that are still Turing-complete (i.e. that can express everything we think of as (sequential) computation), but don't have a stack as such?
  2. If you want memory usage analysis to always be possible, what computing power do you lose?
  3. Can stack usage analysis be practical?

Programming without a stack

Arbitrary computations require the ability to write programs that can take arbitrarily long and use arbitrary amounts of memory. That memory doesn't have to be organized as a stack, however. Suppose you have a programming language with a stack (whatever the stack exactly is — typically at least a function call stack). Let's write an interpreter for it in the form of a while loop that executes one instruction at a time. If the interpreter needs to remember information about past instructions (for example a point to jump back to), it allocates an object in its heap. The interpreter itself doesn't have any function calls. Thanks to this interepreter, you now have a programming language that's executed without a stack.

Of course, if the original language had something like function calls, the abstract structure of its call stack still exists in the interpretation. But now it consists of links between heap objects, not directly a stack structure in memory.

What is theoretically necessary is the ability for memory usage to grow over the execution of the program, not that this growth involes a stack structure. Practically though, most programming languages have something like function calls, so they have a function call stack. This is because [functions]https://en.wikipedia.org/wiki/Function_(computer_programming)) (or subroutines, procedures, however you want to call it) are a very convenient way to have some composability, where you can write a piece of code and reuse it. If you've ever tried programming in an esoteric programming language without composability, you probably felt the pain.

What I've shown informally here is that imperative programming with heap allocation is as powerful (in terms of computability) as functional programming with recursion. The converse is true: both are common ways of achieving Turing completeness.

Programming in bounded memory

We've seen that you can “hide” a stack in some memory that isn't organized as a stack. Can we forbid that as well? What happens if we prevent programs from using arbitrary amounts of memory?

If a programming language only allows programs to use a fixed amount of memory, then all the programs are running on a finite automaton. The theoretical computing power of finite automata is very restricted. All it can do is recognize whether inputs match a regular expressions. Even very simple things such as determining whether a string has balanced parentheses become impossible.

Of course, in practice, we run programs on computers that have a finite amount of memory. But we don't reason about the finite memory as such, because it's intractable and extremely ad hoc. When we wonder “does my program work correctly?”, we don't want to get into the details that some particularly convoluted input only works if the computer has at least that many GB or RAM, and only if such-and-such program isn't running at the same time, and only if the heap wasn't fragmented by some previous processing, etc. (The exception is some high-reliability systems where we're willing to give up flexibility for certainty, which I'll come back to later.) So practical reasoning about programs involves theoretical models where if you run out of RAM, you just add more.

Coming back to theory, we've seen that if you impose that every program must use no more than some fixed amount of memory, your computing model is limited to finite automata. But you can have programs whose memory usage is statically analyzable, yet not statically bounded. For example, a common pattern is that a program will use a predictable amount of memory, but the amount depends on the input. If you follow this pattern that a program's resource usage can be unbounded but must be predictable, you get primitive recursive functions. Primitive recursion allows nesting function calls and loops, but you have to announce the number of calls or iterations in advance. That number can itself be a runtime calculation, but that calculation has to be bounded as well, and so on.

Not all computation can be done with primitive recursion. Turing completeness requires primitive recursion plus some form of unbounded iteration, such as a while loop or unbounded recursion. However, a lot of algorithms are primitive recursive because the number of iterations can be bounded by the size of some data structure.

Bounding stack usage in practice

In embedded programming, it's common to run programs in very small stacks. It's also sometimes inconvenient to detect stack overflow. Or even if a stack overflow can be detected, you can't recover from it, you can only halt the system. If this is a high-reliability system, you definitely don't want to do that. And so in embedded development, it's fairly common to run a static checker to ensure that the program will not overflow the stack. This is a whole-program check that of course depends on the exact platform you're deploying to and the details of how the compiler optimizes your program.

In order for the stack usage analysis to be practical, recursion is forbidden. If you have a problem that lends itself to a stack, such as searching for a value in a tree, you have to manage memory manually. If this involves heap allocation, you have to handle out-of-memory errors explicitly. Function pointers and dynamic dispatch are forbidden or at least restricted to what your analyzer supports.

Such static checkers exist for languages typically used in low-level programming. For example gcc -fstack-usage works for C, C++ and other languages supported by GCC. I don't know how practical it is with C++ where dynamic dispatch tends to happen far more often than in C.

-1

Brainfuck can be crammed into a single main procedure with a single dispatch loop, and everything can theoretically be compiled to Brainfuck. Memory usage is unbounded in the Turing-complete limit, but stack usage is constant and there are no calls aside from those used for I/O. The answer is yes.

3
  • 1
    The answer to what question is yes? The OP asked several and there appears to be a lot of confusion. In unbounded brainfuck it's still impossible to predict in all generality how much memory will be used and how long the loops will run!
    – Stef
    May 15 at 22:10
  • @Stef: The question is simple, although it should have been asked on CS Theory. It doesn't have to do with "how long the loops will run", it has to do with stack depth and the graph of continuations. It just happens to be the case that both of those things are trivial from the perspective of a Brainfuck interpreter. See Weiher 2020 and this article and discussion for deeper insight.
    – Corbin
    May 16 at 1:20
  • As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.
    – Community Bot
    May 16 at 18:23
-1

Pigeonhole principle

I think this question is being asked so broadly and vaguely that it's ceasing to be useful as an actual code metric.

The direct answer here is that if you disallow cyclic calls, then the Pigeonhole Principle effectively puts an upper limit on your stack size. You could not possible have a stack with more levels than there are methods in your codebase.

What are you asking?

can every program still be written

It depends on what you mean by "every program" and whether you're expecting that you're expecting them to map one-to-one or not.

For example, recursion allows you to solve any maze, and you don't need to know the size and scope of the maze when building your program. For a given maze size, you could effectively figure out how many recursions there would be in your code and hand-write all of them. It's not efficient, but it can theoretically be done.

But do you consider this a valid rewrite of the program, given that we're now limited to this size of maze and we can't solve bigger mazes? We could move the goalposts and hand-write more recursions non-recursively, but there's always going to be some kind of upper limit to your code.

We could consider an upper boundary of machine resources, and write a program that deals with such resources. For example, the limits of memory inherently limit the size of the maze that we can process, so we could hand-write enough recursions in order to accommodate that upper limit maze.
But still I wonder if you consider this a solution, because a recursive program would effectively be capable of solving bigger mazes if you give it more hardware resources, without needing to rewrite or even recompile the code.

The one limitation that even a recursive program has is the size of its data structures. An integer can only be so big, so even your recursive program is going to break at these sizes, even though up until now we've never broken the recursive program (even though we've suggested rewriting the non-recursive program several times now).

So is that your upper limit? If it is, then I have a sneaky suspicion that the amount of hand-written recursions is already going to yield a binary so huge that it itself runs into resource constraints to be executed, which is a whole different level of problems to solve.

Conclusion

So, what it boils down to is what you're asking:

Can we build a non-recursive program that follows a specific runtime's callstack of a recursive program?

Yes. Run it recursively, record the callstack, copy/paste to your heart's content.

Can we build a non-recursive program that is capable of solving dynamically sized problems just like a recursive program can?

No, because hand-writing your recursion levels inherently limits you to the finite amount of hand-writing you've done.

That being said, recursive programs don't run on infinite resources or data types with infinite capacity either, so infinity is not a real world consideration in the first place. Since this is a theoretical question, the onus is on you (the asker) to define where you draw the line of what's sufficiently equivalent between recursive and non-recursive programs.

8
  • All recursion can be rewritten as loops plus dynamically allocated memory
    – slebetman
    May 16 at 2:48
  • @slebetman: That's just recursion the long way round. If you define recursion to only refer to method calls and not a loop that cycles back on itself, then yeah, but that's a really foisted definition based on the letter of the law, not its spirit. Hence my first paragraph, the practicality of the topic has dissipated if you accept near-infinite complexity in the pursuit of avoiding a different but decidedly more trivial complexity.
    – Flater
    May 16 at 3:03
  • But all function-to-itself calls (also know as recursion) can be rewritten as for loops (or while loops if you want) regardless of complexity. Trivially recursive functions can be rewritten as loops. Non-trivial recursive functions can also be rewritten as loops. Near-infinite complex recursive functions can also be rewritten as loops.
    – slebetman
    May 16 at 3:11
  • No, because hand-writing your recursion levels inherently limits you to the finite amount of hand-writing - this statement is completely untrue. You can malloc the memory you need into an infinitely expanding array to make your loop not finitely limited.
    – slebetman
    May 16 at 3:12
  • The fact that recursion and iteration (loops) are equivalent is so fundamental in computing theory that it's usually covered within the first year of college. I really don't understand how people can forget this fact. It's like forgetting that anything multiplied by 1 equals itself.
    – slebetman
    May 16 at 3:16
-1

I'm wondering if it was theoretically possible for a compiler to determine maximum stack depth at compile time

No, this is not possible. The call depth usually depends on the input data, so in the general case, you would always have to assume "worst case" regarding the input (i.e., arbitrary size). So in the general case, without any sort of "annotation" or constraints on the input, or further information (on a higher level than what a compiler usually works with), a compiler does not have enough information.

If you want a concrete, albeit somewhat pathological example, think of the Ackermann function, which a general compiler has no chance of guessing the number of calls, and hence the depth of the stack (see this question for the complexities involved for even small values).

can every program still be written or are there programs that can only work without above limitations?

Yes, every recursive program can be written to work without a call stack; as long as your programming language is Turing complete, which it will be if it supports WHILE loops, you can (as a human) transform every recursive program into other code that uses very basic control statements only.

If you do this, you will be using (in the general case) some kind of data structure which has the same overall function as the original call stack - it will of course also, in theory, need to grow without limit. You can see an example of this in the above Wikipedia page on the Ackermann function, which is trivially transformed into a "term rewriting system", which itself is a WHILE loop without any actual function calls.

Hence, by avoiding recursive function calls you can get past hard limits of the actual call stack; you cannot get past the problem that you may eventually run out of memory. But if you are in a context where the RAM available for general data structures is much larger than the separate call stack, this can absolutely be an applicable solution.

2
  • 1
    With the Ackermann function, you can’t calculate the maximum stack depth, it’s even impossible to write down how many bytes you need to write down the maximum stack size. Or how many bytes you need to write down how many bytes you need (repeat 100 times) … to write down a limit for the stack frame size.
    – gnasher729
    May 16 at 11:13
  • That was my point, @gnasher729 (i.e., a concrete counter-example to a compiler being able to pre-calculate max stack depth). Was your comment meant to expand on that, or do you feel that the way I formulated it gave the impression that I meant something else?
    – AnoE
    May 16 at 12:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.