Call Stack Necessity in Robust Computer Architecture

Architectureenterprise-architecturefunctionsturing-completenessvirtual machine

I am not too familiar with the computer architecture terminology yet so please bear with me. I seem to understand that von Neumann architectures are more robust ("universal Turing machines") as opposed to Harvard architectures, but don't know too much about the details yet.

After spending the past few nights looking into the Call Stack, I am still confused. I also have seen a few papers here and there (just scanning the abstracts for the moment), such as Programming Without a Call Stack, and others, which makes me wonder if there are any systems / architectures for defining a virtual machine without a call stack. I don't really know what it would look like, but maybe there are some things to check out. I am not talking about simple machines, like those from the pre-1960's era which didn't have recursion and so didn't need call stacks I guess. I am talking about fully robust / complete computer architectures which use something other than a call stack.

Best Answer

... which makes me wonder if there are any systems / architectures for defining a virtual machine without a call stack

Continuation Passing Style enables tail call optimization for all function invocations — thus, no stack is needed; however, heap memory is most likely used to hold the closures capturing references to local variables.

CPS is used as an intermediate form (e.g. in a virtual instruction set) in some compilers to represent explicit flow of control, especially what happens in exceptions and exception handling.


The stack is a very efficient data structure: the top of the stack is almost certainly in the data cache, and, allocation and deallocation are super quick (i.e. one instruction).  The stack is a necessary part for C programs, so it is unlikely that a modern computer would be made without explicit support for a stack.

However, to be clear, MIPS and RISC V do not have a separate hardware-dedicated stack pointers or push and pop instructions — software simply uses one of the many general purpose registers that way.

Related Topic