Nobody invented the stack

A function calls another function, which calls another, and each one needs somewhere to keep its own things while it waits for the one below to finish. When the innermost one is done its little world evaporates and control goes back up. Last in, first out, like a pile of plates. The arrangement is called a stack, and every program you have ever run has been standing on one.

It is the least surprising idea in computing. It is also one that had to be invented three separate times, in three countries, by people who had never heard of each other, over about fifteen years. Nobody handed it down. Everybody just kept finding it.

The reason it is not obvious is that the earliest computers managed without it, badly. Calling a subroutine, which is what a function was called before anybody called it a function, meant writing down where to come back to. The machine had exactly one place to write that: a single slot belonging to that subroutine. Which works perfectly, once.

Call the same subroutine again before the first call has finished, and the second call writes its return address into that one slot, on top of the first one. The address the first call needed in order to get home is now gone. It will return to the wrong place, or to the same place forever. So a routine could not call itself, and could not call anything that might eventually loop round and call it again, because it had nowhere to put the second note. Recursion was not merely discouraged. It was structurally impossible.

Alan Turing gets there first, on paper, in his 1945 proposal for the Automatic Computing Engine. He sets out a pair of operations for putting return addresses somewhere they cannot be overwritten, and taking them back off again in reverse. He called them BURY and UNBURY, which is a better pair of names than anything the field has used since. The machine he designed them for was then built, by other people, to a different design. This happened to Turing constantly and is a much longer story than this one.

Twelve years later, in Munich, Friedrich Bauer and Klaus Samelson were working on something that looks unrelated: how to make a machine work out an algebraic expression with brackets in it. Their answer was to postpone every operation you cannot do yet, keeping them in order, and then take them back in reverse. Same shape, different problem. They filed a patent for it in 1957.

In the same year, on the other side of the world, Charles Hamblin got there from a third direction. Hamblin was an Australian philosopher and logician, and his problem was brackets too, but he wanted to abolish them. Ordinary arithmetic needs them to say what to do first. His fix was to put the numbers first and the operation last. Two plus three becomes two three plus. Nothing is ambiguous, and no brackets are needed. It is called reverse Polish notation, and a certain kind of calculator still uses it.

To work through a sum written that way you need somewhere to hold the numbers while you wait for the operation that will consume them. Hamblin called that a running accumulator, which is a lovely name for a stack.

Three people, three problems, three countries, one answer. None of them was copying, and not one of them called it a stack.

The word came last, and from somebody else again. Edsger Dijkstra used it around 1960, while building the first compiler for ALGOL 60. ALGOL is the ancestor most languages you have used are descended from, and nobody writes it any more, which is the usual reward for going first. The Oxford English Dictionary's earliest citation for the computing sense of stack is his. So the thing was invented three times across fifteen years, and named once, afterwards, by somebody who had turned up to use it.

There is a tidy version of this, which is that ideas turn up everywhere at once when their time has come. It does not fit. Turing was twelve years ahead of the other two, and nothing about 1957 made the answer easier to find than 1945 had. Nobody was waiting for a moment. They were walking into the same wall from three directions, and the wall had always been there. Nesting is everywhere: in brackets, in grammar, in one job interrupting another. Anything that has to come back out in the reverse of the order it went in wants a stack, and once you have seen that, you cannot unsee it.

Which is why most people meet a stack only on the day it breaks. It gets a fixed amount of memory, so a function that calls itself and never stops will fill it, one buried return address at a time, until there is no room for the next one. The program then dies with the two words everybody in this trade has read a thousand times, and has probably typed into a search box: stack overflow.