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.

Fred
  • 680
  • 4
  • 19
BipedalJoe
  • 829
  • 3
  • 10
  • I guess the motivation was the ability to run recursive programs, and the condition was to have enough memory available. You can see the transition in ISAs and calling conventions, e.g. the PDP-8 (1965) still used memory on the call site, while the Burroughs B5000 (1961, a much bigger machine) already used a stack. – dirkt Dec 12 '22 at 10:38
  • 9
    You might find this video interesting: Reverse Polish Notation and The Stack - Computerphile. – Fred Dec 12 '22 at 12:01
  • 8
    Do you mean stack as in CPU hardware stack? Or software stack as data structure? – Justme Dec 12 '22 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 '22 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 '22 at 13:57
  • 5
    https://cs.stackexchange.com/q/156040/755 – D.W. Dec 12 '22 at 19:18
  • 2
    Let's note that math has always naturally supported recursion, and that concept was simply brought to computing software & hardware, so rather than suddenly invented/discovered, had to be developed in computer terms, which meant materializing a physical stack that was already postulated by math. – Erik Eidt Dec 12 '22 at 21:55
  • Simple data structures like a stack or queues are simple enough and have common enough use cases that I don't think anyone can specifically claimed to have "invented" it; it's likely have multiple re-discoveries. At best, we can find the earliest documented evidence of it being used in a prominent program, or application in a specific field, or people who popularized it, but it'd have to have been independently invented dozens of time by early programmers still learning on their own. – Lie Ryan Dec 13 '22 at 02:49
  • 1
    Stack as in call stack or more generally? – user3840170 Dec 13 '22 at 08:15

4 Answers4

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

Raffzahn
  • 222,541
  • 22
  • 631
  • 918
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.

Stephen Kitt
  • 121,835
  • 17
  • 505
  • 462
  • 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 '22 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.

dave
  • 35,301
  • 3
  • 80
  • 160
  • 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? – Solomon Slow Dec 12 '22 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 '22 at 00:15
  • 2
    @Raffzahn - oops; thanks. – dave Dec 13 '22 at 00: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 '22 at 00:34
  • There were no stored-program computers existing at the time of the ACE Report. The First Draft EDVAC Report was written the year before, but the EDVAC itself would not be done until 1949. – dave Dec 13 '22 at 00:42
  • @another-dave, would you prefer the word "template?" or maybe "boilerplate?" or "example?" – Solomon Slow Dec 13 '22 at 00:55
  • @SolomonSlow, Having found out what TS1 holds - the address of the most recent jump instruction - it's clear that BURY at least is an actual subroutine, since it needs to be jumped to (ok, you could inline it and still jump to it, but I'm pretty sure that's not intended. Turing talks of 'subsidiary instruction tables' or 'subsidiary operations', and it seems clear to me that it's the modern subroutine (though with only global variables!). – dave Dec 13 '22 at 01:17
  • Depending on what classifies as early, for some machines from the 1960's a call would store the return address in the first word of a sub-routine, then branch to the second word. The subroutine would do an indirect jump using it's first word to return. This allowed nested subroutines, but not reentrant subroutines (without additional code to save return addresses). IBM 360 main frame used a caller supplied save area for registers, where R13 pointed to the save area, R14 was the return address, R15 was the program counter. Using a pool of save areas allowed for recursion. – rcgldr Dec 13 '22 at 01:58
  • Sure, but the ACE report was written before there existed stored-programmed computers; the subroutine call did not yet exist as even a proposed machine instruction; and AFAIK no-one had yet thought of indirect addressing. – dave Dec 13 '22 at 02:08
  • @rcgldr: How does "self-modified link" work in Pegasus programming? has details about such a machine, storing a return address next to the callee's machine code (or effectively into, cross-modifying code.) Related Q&As: Is it possible to implement subroutine call without a stack nor indirect addressing? (and comments on the OP's What is a minimal example of why it is not possible to predict call pattern of functions?) – Peter Cordes Dec 13 '22 at 04:16
  • @PeterCordes - IBM 1130 and CDC 3000 series computers used that calling method: storing the return address in the first word of a function, then branching to the second word. I don't know what other machines used that calling sequence. – rcgldr Dec 13 '22 at 08:03
  • @PeterCordes - call without a stack or indirect addressing: IBM 360 and IBM mainframes that support that API use a save area. R13 points to the save area for the 16 registers, R14 contains the return address. R15 contains the base address of the function. If the function doesn't call other functions, a return effectively is a move R14 to R15 (PC). Otherwise, R14 is stored into the caller supplied save area, and a new save area is used (it could be dynamically allocated), to call the next function. The location of R13 in save areas can be used as a reverse link chain of save areas. – rcgldr Dec 13 '22 at 08:08
  • The first time I saw a stack was a software implementation for the PDP-1, in 1963. I didn't understand what I was looking at. The software made use of a seemingly worthless instruction, cal, to implement pushj. The popj routine was reached by a jmp instruction. The next machine I worked on was the PDP-6, a precursor to the PDP-10. It had four stack instructions. – Walter Mitty Dec 13 '22 at 12:35
  • 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 '22 at 12:42
  • I wouldn't be surprised if Ada Lovelace made use of a last-in-first-out data structure in her algorithm for calculating Bernoulli numbers. This was over a century before the first electronic computer. – Walter Mitty Dec 13 '22 at 12:42
  • @WalterMitty - the PDP-6 had just about every possible method of calling a subroutine known to man, as I'm sure you are aware. – dave Dec 13 '22 at 12:43
  • Yeah. Implement them all, and let the programmers figure out wchich ones are useful. However, without the infulence of TMRC, they might not have bothered with PUSH, POP, PUSHJ, and POPJ. – Walter Mitty Dec 13 '22 at 12:49
  • @another-dave - As commented before, the IBM 1130 was one of those machines that saved return in first address, but there was a version of APL, a recursive language, that ran on the IBM 1130. The IBM 360 and I think the 370, had something similar for interrupts: in low memory there were pairs of double words, the first used to save the current context (including return address), the second used to switch context (branch address). – rcgldr Dec 13 '22 at 14:07
  • 1
    @rcgldr APL\1130 was (very tediously) interpreted, so call/return used the interpreter's convention, not the hardware's. – John Doty Dec 13 '22 at 18:32
  • @JohnDoty - my point there was it was a software stack (the machine didn't have a hardware stack). Hoare's original implementation of quick sort also used a software stack, which he called a "nest" at the time, also on a machine that didn't have a hardware stack. IBM 360 programs used dynamic allocation for save areas, or did a one time allocation to create a pool of save areas to allow reentrant (recursive) functions. – rcgldr Dec 13 '22 at 20:43
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").

dave
  • 35,301
  • 3
  • 80
  • 160