4

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.

4
  • Useful computers without call stack... Quantum computers ?
    – Christophe
    Nov 28, 2019 at 22:28
  • Pre-1960s machines weren't even remotely simple. Nov 29, 2019 at 2:23
  • 1
    I would expect a two-stack architecture before a zero-stack architecture. With two-stack, I mean a system where the stack for local variables is separate from the return address stack. Besides buffer safety, it could help the branch predictor.
    – MSalters
    Nov 29, 2019 at 12:09
  • @msalters FORTH typically has a control stack and a data stack.
    – Miles Rout
    Dec 3, 2019 at 18:44

4 Answers 4

13

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

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.

4
  • The Parrot VM doesn't have a stack. I wouldn't call it useless. Back when it was still actively developed, there were (partial) implementations of Perl, Perl6, ECMAScript, Ruby, Python, PHP, Java, C, Lua, several Lisps, several Schemes, Prolog, and many other languages (in various stages of completeness) for it. Its failure was not due to its lack of a call stack, it was over-ambition to be "the VM to end all VMs". Nov 29, 2019 at 9:19
  • @Jörg W Mittag Some of the languages you mention I know to support some kind of subroutine mechanism. That makes me say they must use some kind of call stack. You may mean there is no stack in the traditional sense, with a stack pointer and Push and Pop instructions, but I specifically called that an implementation detail. Can you please explain how subroutine calls work for those implementations without what you would consider to be a call stack? Nov 29, 2019 at 13:31
  • 2
    The Parrot VM used Continuations allocated on the heap. I would consider this significantly different from a stack. 1) A stack is linear, whereas continuations can branch, e.g. to implement complex non-local control flow such as resumable exceptions, symmetric coroutines, agents, actors, etc. 2) A stack normally sits outside the program, whereas (at least in Parrot), continuations were just objects like any other object that could be manipulated just like any other object, which opens up a world of powerful runtime meta programming. (Some environments such as many Smalltalks have reified … Nov 29, 2019 at 13:42
  • 1
    … stacks that can be manipulated through reflection, but those are rare.) 3) A stack is typically thought of as a) fixed in size and b) small, whereas the number of continuations is unlimited. Nov 29, 2019 at 13:43
0

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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