Who first come up with the idea of the call stack?

Question

It's simple yet fast and effective because of the locality property. You also manage the memory, a finite resource, by adjusting just one pointer.

I think it's a brilliant idea.

• Who first come up with the idea of the call stack?
• Since when does computers have supporting instructions for stack?
• Is there any historically significant paper on it?

Answer 1

As far as I know, computers have used a call stack since its earliest days.

Stacks themselves were first proposed by Alan Turing, dating back to 1946. I believe that stacks were first used as a theoretical concept to define pushdown automatons.

The first article about call stacks I could find was written by Dijkstra on Numerische Mathematik journal, titled "Recursive Programming" (http://link.springer.com/article/10.1007%2FBF01386232).

Also note that the call stack is there mainly because of recursion. It may be difficult to actually know who really got the idea for the call stack in the first place, since it is pretty intuitive that a stack is needed if you want to support recursion. Consider this quote from Expert C Programming - Deep C Secrets, by Peter Van Der Linden:

A stack would not be needed except for recursive calls. If not for these, a fixed amount of space for local variables, parameters, and return addresses would be known at compile time and could be allocated in the BSS. [...] Allowing recursive calls means that we must find a way to permit multiple instances of local variables to be in existence at one time, though only the most recently created will be accessed - the classic specification of a stack.

This is from chapter 6, page 143 / 144 - if you like this kind of stuff, I highly recommend you to read it.

It is easy to understand that a stack is probably the right structure to use when one wants to keep track of the call chain, since function calls on hold will return in a LIFO manner.