Is a call stack required for robust computer architecture?

Question

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.

Answer 1

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

Answer 2

I do not think robustness is an issue here. Functionality is, in the most literal sense.

Forget implementation details for a moment and consider what a call stack is, really. It allows you to call sub-programs (functions) and return from them, continuing where you left off. That is, it provides the possibility to split up a problem into smaller parts, to create functional building blocks.

This is such a fundamental feature in a general purpose problem solving machine that one without it would be hard to imagine. It would be useless because there would be no way to create anything complex.

Answer 3

What you call "robust" is a matter of preference.

Stacks are useful, but it is not necessary for the architecture to define them directly.
A program can always make their own stacks if they want them.

Having hardware support for something makes it faster, but less flexible.

Architectures with call stacks make function calls fast, but not very fast since there is usually work to do with argument transfers.

On the other hand you are locked into a Last-In-First-Out world for function calls and returns. If you want to use coroutines, the stack no longer helps you.

The hardware we have affect the programs we write. And the programs we write affect the hardware we want. In the end, what we have seems "necessary", even if it is just one choice of many.

Answer 4

You don't need call stacks necessarily on any level be it the programming language level or the hardware level.

From a computer architecture perspective there doesn't need to be hardware support for a blessed stack (e.g. a special stack pointer register, instructions for loading and storing values relative to this stack, etc.) in order to implement a language with semi-arbitrary function call nesting like C or Scheme. You can implement your own with a register, register-offset addressing and manually incrementing and decrementing the register you have designated the "stack pointer". Call stack support in the instruction set is there for compactness of machine code.

From a programming language perspective the stack is just an implementation detail. The C standard doesn't call it a stack, it refers to stack variables as 'automatic' (because their storage is automatically deallocated when you leave the scope they were defined in). The standard calling convention in popular operating systems is to use the stack so that's what people assume has to be done.

Languages with first class continuations don't operate like there's a stack, conceptually. Forth implementations typically use two stacks. CPSd code conceptually uses no stack. There's lots of ways to do it, from heap-allocated branching "stacks" used to implement continuations and coroutines through to bog standard C.