The PDP-8 was a remarkable exercise in minimalist computer design; some of the aspects of its design are discussed in detail at PDP-8 transistor count
One feature it did not have was a stack. Instead, when you called a subroutine, the return address would be saved in the first word of the subroutine. Of course, this meant it didn't support reentrancy (that is, if you needed reentrancy, you had to make your own arrangements, implement your own call stack in software). On the face of it, this is consistent with the overall design philosophy of eschewing luxury to save parts count and therefore cost.
But looking a bit more closely, the lack of a stack actually increases cost in some ways. In particular, it causes programs to use more memory, because a word has to be allocated for a return address for every subroutine in the program (as opposed to just the maximum call depth that will ever be used).
Furthermore, if you have a stack, you can use tail call optimization, where a call immediately followed by a return is replaced with a jump, saving a word of memory (and several cycles). Without a stack, you cannot do this.
In general, it's clear that the designers did care about code density, which in many ways is remarkably high; for example, a jump instruction to an arbitrary memory location takes two words, as expected – except two jump instructions in the same page to the same location, can share the operand word, for an amortized cost of 12 bits each. I have seen no other architecture that can do this.
And there was good reason to care about code density. Memory was expensive! Even with the basic 4096 12-bit words of memory in the PDP-8, this still amounted to a large percentage of the total system cost. For the low end of the market at which the machine was aimed, code density therefore could very well be more important than speed.
What exactly would it have cost to add a stack to the machine?
- A register for the stack pointer itself. This could have been just 7 bits; if there are two transistors needed to store a bit in discrete logic, that's an extra 14 transistors, about 1% of the total in the machine. (Plus corresponding other components, diodes, wires etc.) That would seem worthwhile for a likely saving of significantly more than 1% of memory.
- Opcode space not an issue, the call instruction would've taken the same number of bits, and there was spare opcode space for zero-operand instructions like RET, and a couple of instructions to push and pop the accumulator.
- Circuitry to increment and decrement the stack pointer. The machine already had a full-width adder. Decrement can be done by adding all ones.
- Control logic for the necessary sequence of operations. Does this add much complexity? Call would need to push the return address onto the stack before jumping to the destination. Then again, in the current design, call needs to jump to the destination, save the return address, then again increment the program counter. Doesn't look like a huge difference.
Overall it looks to me like a stack would achieve a modest improvement in code density at small extra hardware cost. Worth it? Hard to say. Looks like a tricky judgment call that would preferably need to be based on analysis of exactly what the hardware cost would be.
But this was in the early sixties. At that time, stacks and recursion were not in any way taken for granted the way they are now. Storing the return address in the first word of a subroutine was a perfectly normal way to do things!
So:
Did the designers consider a stack and decide it wasn't worth the cost? Or did they just go with return address stored in the first word of the callee because that was the way things were commonly done, and there was no particular reason to do otherwise? Is there anything written down by the designers that goes into detail about the options they considered? Or can anything be inferred from architectures that already existed, that the designers would have been familiar with; did any of those existing architectures have a stack?
