38

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.

9
  • 9
    You might find this video interesting: Reverse Polish Notation and The Stack - Computerphile.
    – Fred
    Dec 12, 2022 at 12:01
  • 8
    Do you mean stack as in CPU hardware stack? Or software stack as data structure?
    – Justme
    Dec 12, 2022 at 12:07
  • 6
    @Justme - I'd suppose the concept is what matters. After you have the idea, it's somewhat immaterial whether you bake it into software or into germanium.
    – dave
    Dec 12, 2022 at 13:11
  • 9
    Function pointers are possible without a stack. FORTRAN II permitted the dummy argument of a subroutine to be used as a function call within the subroutine; this makes the dummy argument a 'function pointer'. It's just an indirect call at the machine code level. However, I see no ability to retain such pointers in a way that would give arbitrary call patterns, which I suppose to be your point.
    – dave
    Dec 12, 2022 at 13:57
  • 5
    cs.stackexchange.com/q/156040/755
    – D.W.
    Dec 12, 2022 at 19:18

4 Answers 4

49

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

10
  • 2
    Right, that’s the Sequentielle Formelfibersetzung paper, isn’t it? Dec 12, 2022 at 11:11
  • 2
    @PaŭloEbermann thanks, I copy-pasted it from the Springer scan of Dijkstra’s paper. Dec 13, 2022 at 4:57
  • 3
    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). Dec 13, 2022 at 7:01
  • 1
    It is just more references for your answer and not an own answer, so please include it! Dec 13, 2022 at 12:42
  • 2
    @Raffzahn Sorry, I wasn't clear - I was asking about the original Sequentielle Formelübersetzung paper.
    – dave
    Dec 13, 2022 at 17:44
22

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.

1
  • 2
    Bauer and Samelson developted the idea of a modern stack in 1951..54, filed patent in 1957. Dijkstra was of course as well involved in the Algol development, albeit only later on.
    – Raffzahn
    Dec 12, 2022 at 10:56
18

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.


20
  • 1
    Re, "since BURY and UNBURY are routines..." I have not read the report, but are you certain that BURY and UNBURY were not intended as macros? Dec 12, 2022 at 23:51
  • 1
    @SolomonSlow - "macro" seems to presuppose the existence of an assembler, or similar processor, on a machine that had not yet even been started. And wouldn't an assembler need a way to call subroutines?
    – dave
    Dec 13, 2022 at 0:15
  • 2
    @Raffzahn - oops; thanks.
    – dave
    Dec 13, 2022 at 0:17
  • 5
    When interpreting that paper (and many of that years) it's important that many of the concepts are discussed on a rather theoretical level, not really about concrete/existing machines or how exactly something is to be implemented. routine can mean anything from a machine instruction over some copied code (macro) to dedicated sub routines.
    – Raffzahn
    Dec 13, 2022 at 0:34
  • 3
    @rcgldr - (1) countless machines of the 1950s to 1970s used "save return address in first word, return indirect". (2) a linked list of save areas, removed in reverse order, is a stack regime.
    – dave
    Dec 13, 2022 at 12:42
6

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

3
  • 4
    A voice in my head says that it's not right in any imaginable way to upvote this, but it feels right. +1
    – Raffzahn
    Dec 16, 2022 at 3:17
  • 2
    @Raffzahn - Ignore that voice.
    – davidbak
    Dec 21, 2022 at 17:45
  • Famous discussion of non-spherical geometry in The Mikado as well.
    – davidbak
    Dec 21, 2022 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .