22

We all know and love that function calls are usually implemented using the stack; there are frames, return addresses, parameters, the whole lot.

However, the stack is an implementation detail: calling conventions may do different things (i.e. x86 fastcall uses (some) registers, MIPS and followers use register windows, and so on) and optimizations can do even other things (inlining, frame pointer omission, tail-call optimization..).

Sure, the presence of convenient stack instruction on many machines (VMs like JVM and the CLR, but also real machines like x86 with their PUSH/POP etc.) make it convenient to use it for function calls, but in some cases it is possible to program in a way in which a call stack is not needed (I am thinking about Continuation Passing Style here, or Actors in a message passing system)

So, I was beginning to wonder: is it possible to implement function call semantics without a stack, or better, using a different data structure (a queue, perhaps, or an associative map?)
Of course, I understand that a stack is very convenient (there is a reason why it is ubiquitous) but I recently bumped into an implementation that made me wonder..

Do any of you know if it has ever been done in any language/machine/virtual machine, and if so which are the striking differences and shortcomings?

EDIT: My gut feelings are that different sub-computation approaches can use different data structures. For example, lambda calculus is not stack based (the idea of function application is captured by reductions) but I was looking at a real language/machine/example. That's why I am asking...

Lorenzo Dematté
  • 678
  • 1
  • 5
  • 14
  • [Clean](http://clean.cs.ru.nl) uses a graph and a graph rewrite machine, which is in turn implemented using a three-stack machine, but with different content than usually. –  Dec 08 '15 at 18:38
  • For virtual machines, a linked list can be used. Each node of the list is a frame. Since the hardware stack is used by the VM, this is allows frames to exist on the heap without the overhead of `realloc()`. – shawnhcorey Dec 03 '16 at 15:50

3 Answers3

22

Depending on the language, it may not be necessary to use a call stack. Call stacks are only necessary in languages that allow recursion or mutual recursion. If the language does not allow recursion, then only one invocation of any procedure may be active at any moment, and local variables for that procedure may be statically allocated. Such languages do have to make provision for context changes, for interrupt handling, but this still does not require a stack.

Refer to FORTRAN IV (and earlier) and early versions of COBOL for examples of languages that do not require call stacks.

Refer to the Control Data 6600 (and earlier Control Data machines) for an example of a highly-successful early supercomputer that did not provide direct hardware support for call stacks. Refer to the PDP-8 for an example of a very successful early minicomputer that did not support call stacks.

As far as I know, the Burroughs B5000 stack machines were the first machines with hardware call stacks. The B5000 machines were designed from the ground up to run ALGOL, which required recursion. They also had one of the first descriptor-based architectures, which laid groundwork for capability architectures.

As far as I know, it was the PDP-6 (which grew into the DEC-10) that popularized call stack hardware, when the hacker community at MIT took delivery of one and discovered that the PUSHJ (Push Return Address and Jump) operation allowed the decimal print routine to be reduced from 50 instructions to 10.

The most basic function call semantics in a language that allow recursion require capabilities that match nicely with a stack. If that's all you need, then a basic stack is a good, simple match. If you need more than that, then your data structure has to do more.

The best example of needing more that I have encountered is the "continuation", the ability to suspend a computation in the middle, save it as a frozen bubble of state, and fire it off again later, possibly many times. Continuations became popular in the Scheme dialect of LISP, as a way to implement, among other things, error exits. Continuations require the ability to snapshot the current execution environment, and reproduce it later, and a stack is somewhat inconvenient for that.

Abelson & Sussman's "Structure and Interpretation of Computer Programs" goes into some detail on continuations.

John R. Strohm
  • 18,043
  • 5
  • 46
  • 56
  • 3
    That was a great historical insight, thank you! When I asked my question, I had indeed continuations in mind, especially continuation-passing style (CPS). In that case, a stack is not only inconvenient, but probably not necessary: you do not need to remember where to return, you provide a point where to continue your execution. I wondered if other stack-less approaches where common, and you gave some very good ones I was not aware of. – Lorenzo Dematté Jun 07 '13 at 14:16
  • Slightly related: you correctly pointed out "if the language does not allow recursion". What about language with recursion, in particular functions that are not tail-recursive? Do they need a stack "by design"? – Lorenzo Dematté Jun 07 '13 at 14:18
  • "Call stacks are only necessary in languages that allow recursion or mutual recursion" - no. If a function can be called from more than one place (e.g. both `foo` and `bar` may call `baz`), then the function needs to know what to return to. If you nest this "who to return to" information, then you end up with a stack. It doesn't matter what you call it or if it's supported by the CPU's hardware or something you emulate in software (or even if its a linked list of statically allocated entries), it's still a stack. – Brendan Jun 07 '13 at 14:49
  • @Brendan not necessarily (at least, that's the whole purpose of my question). "Where to return to" or better "where to go next" does it need to be a stack, i.e. a LIFO structure? Could it be a tree, a map, a queue or something else? – Lorenzo Dematté Jun 08 '13 at 13:05
  • For example, my gut feelings are that CPS just needs a tree, but I am not sure, nor I know where to look at. That's why I am asking.. – Lorenzo Dematté Jun 08 '13 at 13:06
  • @LorenzoDematté: A simple approach is to simply have a statically-allocated variable associated with each method to identify where execution should go after the method executes. – supercat Jun 26 '14 at 01:22
  • @supercat that does not work with recursion – Lorenzo Dematté Jun 26 '14 at 03:51
  • @LorenzoDematté: Precisely. That was how the CDC 6600 Return Jump (RJ) subroutine call worked. "RJ xxx" stored a jump to PC+1 in xxx and then jumped to xxx+1. When the subroutine finished, it jumped to xxx, which jumped back to the calling routine. This works fine for nonrecursive languages like FORTRAN, but it doesn't work for recursive languages like PASCAL. PASCAL had to implement a call stack in software. – John R. Strohm Jun 26 '14 at 12:31
  • I should add that the PDP-8 JMS xxx (JuMp to Subroutine at xxx) instruction stored the return address at address xxx and jumped to xxx+1. To return, the programmer coded an indirect jump through location xxx. Same basic idea as the 6600, no stack. – John R. Strohm Dec 08 '15 at 14:39
  • Given that recursion is [limited](https://stackoverflow.com/questions/1825964/c-c-maximum-stack-size-of-program) to ~10,000, then you could consider a function f = f1,...,f10,000 and have the function just call one to the next. Then for recursion perhaps a stack wouldn't even be needed. – Lance Apr 24 '18 at 03:38
  • @LancePollard, See pixelbeat's answer to the question you linked. Also, think about the cost in memory of making 10,000 copies of the one routine, that keep the call order intact. – John R. Strohm Apr 24 '18 at 04:09
  • Even if the language doesn't support recursion, and thus local variables can be allocated statically, we still need to remember during runtime the addresses from which each function was called, in order to return correctly from call chains of arbitrary lengths. Doesn't this still need a stack, at least for the return addresses? – Aviv Cohn Apr 20 '20 at 09:18
  • @AvivCohn: No. Read the other comments. Read specifically the descriptions of the CDC 6600 RJ instruction and the PDP-8 JMS instruction. HAVING SAID THAT, it is abundantly clear in the Real World that supporting general recursion is a Good Thing, and, for that, you do need something with call stack semantics. You either support recursion directly, or the programmer gets to simulate it. (The code to do this is MESSY. If you can find it, read the CDC 6600 STARTRK game PHOTON subroutine, and look at the simulated recursion for 8-way connectivity for nova triggering.) – John R. Strohm Apr 20 '20 at 12:12
  • @AvivCohn: It is worth mentioning that Urs Ammann's PASCAL compiler for the CDC 6x00 (6600, 6400) generated code to simulate a call stack so that the language could support recursion. I read his library support routines (I wasn't up to reading his compiler) and wondered why he didn't use the RJ instruction and conventions, and then I realized that his approach allowed recursion, which RJ didn't. – John R. Strohm Apr 20 '20 at 12:15
6

It's not possible to implement function call semantics without using some sort of stack. It's only possible to play word games (e.g. use a different name for it, like "FILO return buffer").

It is possible to use something that doesn't implement function call semantics (e.g. continuation passing style, actors), and then build function call semantics on top of it; but this means adding some sort of data structure to track where control is passed when the function returns, and that data structure would be a type of stack (or a stack with a different name/description).

Imagine you have many functions that can all call each other. At run-time, each function must know where to return to when the function exits. If first calls second then you have:

second returns to somewhere in first

Then, if second calls third you have:

third returns to somewhere in second
second returns to somewhere in first

Then, if third calls fourth you have:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

As each function is called, more "where to return" information must be stored somewhere.

If a function returns, then its "where to return" information is used and is no longer needed. For example, if fourth returns back to somewhere in third then the amount of "where to return to" information would become:

third returns to somewhere in second
second returns to somewhere in first

Basically; "function call semantics" implies that:

  • you must have "where to return" information
  • the amount of information grows as functions are called and is reduced when functions return
  • the first piece of "where to return" information stored will be the last piece of "where to return" information discarded

This describes a FILO/LIFO buffer or a stack.

If you attempt to use a type of tree, then every node in the tree will never have more than one child. Note: a node with multiple children can only happen if a function calls 2 or more functions at the same time, which requires some sort of concurrency (e.g. threads, fork(), etc) and it would not be "function call semantics". If every node in the tree will never have more than one child; then that "tree" would only be used as a FILO/LIFO buffer or a stack; and because it's only used as a FILO/LIFO buffer or a stack it's fair to claim that the "tree" is a stack (and the only difference is word games and/or implementation details).

The same applies to any other data structure that could conceivably used to implement "function call semantics" - it will be used as a stack (and the only difference is word games and/or implementation details); unless it breaks "function call semantics". Note: I would provide examples for other data structures if I could, but I can't think of any other structure that is slightly plausible.

Of course how a stack is implemented is an implementation detail. It could be an area of memory (where you keep track of a "current stack top"), it could be some sort of linked list (where you keep track of "current entry in list"), or it could be implemented in some other way. It also doesn't matter if hardware has built-in support or not.

Note: If only one invocation of any procedure may be active at any moment; then you can statically allocate space for "where to return to" information. This is still a stack (e.g. a linked list of statically allocated entries used in a FILO/LIFO way).

Also note that there are some things that do not follow "function call semantics". These things include "potentially very different semantics" (e.g. continuation passing, actor model); and also includes common extensions to "function call semantics" like concurrency (threads, fibres, whatever), setjmp/longjmp, exception handling, etc.

Brendan
  • 3,895
  • 21
  • 21
  • By definition, a stack is a LIFO collection: Last in, first out. A queue is a FIFO collection. – John R. Strohm Jun 07 '13 at 16:02
  • So is a stack the only acceptable data structure? If so, why? – Lorenzo Dematté Jun 08 '13 at 13:07
  • @JohnR.Strohm: Fixed :-) – Brendan Jun 09 '13 at 00:57
  • 2
    For languages without recursion (direct or mutal), it's possible to statically-allocate for each method a variable which will identify the place from which that method was last called. If the linker is aware of such things, it can allocate such variables in a fashion which will be no worse than what a stack would do *if every statically-possible execution path were actually taken*. – supercat Jun 26 '14 at 01:24
4

The toy concatenative language XY uses a call-queue and a data stack for execution.

Every computation step simply involves dequing the next word to be executed and in the case of builtins, feeding it's internal function the data stack and call-queue as arguments, or with userdefs, pushing the words composing it to the front of the queue.

So if we have a function to double the top element:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Then the composing functions + and dup have the following stack/queue typ signatures:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

And paradoxically, double will look like this:

double [X Y] -> [X dup^+^Y]

So in a sense, XY is stackless.

Kile Kasmir Asmussen
  • 141
  • 3
  • Wow, thanks! I will look into that... not sure it really applies to function calls but worth a look anyway – Lorenzo Dematté Jun 08 '13 at 13:08
  • 1
    @ Karl Damgaard Asmussen "pushing the words composing it to the front of the queue" "pushing front" Isn't that a stack? –  Dec 08 '15 at 13:20
  • @guesttttttt222222222 not really. A callstack stores return pointers, and when the function returns, the callstack is popped. The execution queue stores only pointers to functions, and when executing the next function, it is expanded to its definition and pushed to the front of the queue. In XY the execution queue is actually a deque, since there are operations that work on the back of the execution queue as well. – Kile Kasmir Asmussen Dec 26 '15 at 11:56