In the very early days (the earlier the better! Babbage maybe?) when something like a stack was developed, what motivated it originally?
I am aware that these days it makes many features possible, such as function pointers and impossible-to-predict function call patterns, but I do not know what motivated stack originally. I like to understand things from their evolution, it makes it easier.
The Stack, as we know it today, was developed by Friedrich Bauer and Klaus Samelson as part of their work on the Munich PERM and ALGOL. ALGOL-58 was in turn the first language to use a stack. They patented it in 1957.
The development was driven by the need for local storage, as ALGOL is essentially the language that brought us structured programming and compound statements, like most languages today use. Having a stack is essential to implement those concepts.
Noteworthy: While they also described a push stack, the primary means they thought of was a rather abstract linked list, providing storage per execution level. The all covering hardware stack is a minimalist version, only good for the most basic need of subroutine calling and register save.
It was the time when a 'compiler' were still called 'Automatic Programming', as real programming only happened on bare metal, using a primitive form of Assembler at most :))
Further information provided by Philipp Wendler:
The book Software Pioneers contains a reprint of the original paper and an article by Friedrich L. Bauer that talks about the history of the stack ("From the Stack Principle to ALGOL"). A video of Bauer's talk about this paper is available online for free (with English subtitles).
Given your reference to function pointers and function call patterns, I imagine you’re interested in call stacks. As far as I’m aware, these were first documented in Edsger W. Dijkstra’s 1960 paper, Recursive Programming.
Before the use of stacks, subroutines which needed local memory typically had an area of memory set aside for them. This had two consequences, which Dijkstra’s paper set out to address: memory was wasted (unless all subroutines were used simultaneously), and subroutines couldn’t be made re-entrant (i.e. a subroutine couldn’t call itself or call any other subroutine which might end up calling it again). The paper describes call stacks, their relevance to recursive programming, and their possible use in ALGOL 60.
Alan Turing, in his 1946 Report on the ACE described the need for a means to save the return addresses of all active subroutine calls, and to return from such calls in the proper sequence. His routines for subroutine entry and exit were named BURY and UNBURY.
The return addresses are arranged as a stack. In modern terms, we'd say 'push return address and jump to subroutine', and 'pop address and jump to it'. Or, for the PDP-10 programmers, PUSHJ and POPJ :-).
In Turing's report, he describes the routines thus:
BURY:
The content of TS 1 with 1 added is transferred to the position indicated in TS 31, and 1 is added to the reference in TS 31. We then proceed to carry out the instruction in TS 1.
UNBURY:
The minor cycle whose position is given in TS 31 is taken to be position of the next instruction.
In what we might call 'ACE pseudocode' (see slide 28) the routines are
BURY:
M[TS3l] ← TSl + 1; TS3l ← TS31 + 1; go to M[TSl]
UNBURY:
go to M[TS31 ← TS31 - 1]
The TS are temporary storage registers, M is memory; TS1 holds the address of the most-recently executed 'type B' (jump) instruction. So we have here a block of memory being used as a stack of return addresses, with TS31 as the stack pointer.
This of course is not a stack of activation records: it only holds return addresses, not local variables, and thus provides no support for recursive activation.
For what it's worth, this is much like the Subroutine Jump Nesting Store (SJNS) on the English Electric KDF9, which is a 16-deep stack of return addresses. Algol 60 implementations on KDF9 therefore used a software stack for Algol procedure calls (and other blocks), with the SJNS being used 'under the covers' for the implementation internals.
As to motivation: early computers did not yet have subroutine call and return instructions; subroutines were still being invented. Nor was indirect addressing a thing. Since one subroutine can call another, which calls another, you have to track the return addresses and use them in the correct reverse order. Thus the LIFO or stack has appeal.
Stacks were invented by the research team of Gilbert and Sullivan, assisted by John Wellington Wells, in their presentation The Sorcerer, published in 1877, in which they described the wide-ranging utility of the last-in-first-out structure:
If anyone anything lacks, He'll find it all ready in stacks,
(The team also popularized other data structures. For example, see The Mikado: "I've got a little list").
