14

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?

8
  • 6
    I disagree that a stack would have saved memory, as the inline parameter passing approach is very efficient (a word of data per parameter, and no code at all, e.g. no stack pushes); it works well for FORTRAN. The downside is no recursion (but FORTRAN didn't offer recursion back then). One extra word per function for the return address is rather minimal. (The PDP-8 wasted words here and there with that page scheme anyway.)
    – Erik Eidt
    Apr 26, 2021 at 16:03
  • 3
    Re: "it causes programs to use more memory," you're assuming the fungibility of "memory." Core memory is cheaper than DTL transistor registers, which is what you'd be exchanging here. Apr 26, 2021 at 16:17
  • 4
    Re: "Did the designers consider a stack and decide it wasn't worth the cost?" Short of finding primary design documents and discussions, I think you're calling for speculation. Perhaps a book like Bell et al's "Computer Engineering: A DEC View of Hardware Systems Design" has the answer, but beyond that, I think you'd need to be digging around in old DEC archives, which are probably long since turned to CO₂ and organic byproducts by now. Apr 26, 2021 at 16:24
  • 3
    @WarrenYoung As a general idea and vehicle for automatic optimization, tail calls weren't fully and formally explored until Steele and co. in the 1970s, but I've seen it done by hand in machine-coded functions in Lisp interpreters from the 1960s.
    – texdr.aft
    Apr 26, 2021 at 16:34
  • 3
    p.217 from the above-referenced book: "This straightforward subroutine call mechanism, although inexpensive to implement, requires reentrant and recursive subroutine calls to be interpreted by software rather than by hardware. A stack for subroutine linkage, as in the PDP-11..." This doesn't answer the question, being a retrospective view, but it does show that it's an intentional tradeoff of design complexity (hence machine cost) versus advantages to the software developer. Apr 26, 2021 at 16:57

2 Answers 2

25

Without detailed documentation on the PDP-8 design process, we cannot say for sure. I suspect that while they may have briefly considered it, it was never a serious prospect.

The PDP-8 is just the PDP-5 redesigned electronically. The PDP-5 was introduced in 1963 as an even-more-reduced version of a computer compared to the PDP-1 and PDP-4. The PDP-1/4 did not have a stack either.

The PDP-8 had only 12 bit words instead of 18, 3 bits of opcode per instruction instead of 5, and so on. Among the things sacrificed were hardware subtraction, a more sophisticated IO system, a larger address space, hardware to assist multiplication/division, and instructions like bitwise XOR and OR.

In short, they took everything out that they could. Anything else (10 bit word? No bitwise operations at all? No addition?) would drastically slow it down, require huge code for common operations, or simply make it too small (memory-wise).

It is approximately the minimal viable general-purpose computer. While addition might be necessary, stacks are not. Like subtraction, stack access can be simulated on a PDP-8 with just a couple of instructions average. (See some RISC machines that still do this today with no hardware stack.)

In '63 when the PDP-5 was released, hardware stacks were rare in general. DEC had never released a computer using them. The PDP-6 would come out about a year later, as the first. Stacks showed up on some fancy mainframes from other manufacturers around then, and, importantly, were usually a feature intended to support high level languages.

While this is another educated guess, I think supporting high level languages was likely not a design requirement for the PDP-5 and -8. In fact, I suspect the designers would have been quite surprised to learn the architecture, a decade later, would be hosting fairly complete compilers for languages like FORTRAN 66 and COBOL. At the outset, they barely squeezed a limited subset (no subroutines!) of FORTRAN II into the machine.

It was mostly intended to be a laboratory computer, or factory industrial controller, or some kind of embedded processor for control and monitoring tasks. Software like word processing systems and sophisticated compilers were something that became desirable and obvious only once it had been shipping for a while.

In conclusion, between the necessary additional hardware for a stack going directly against the main design goal, stacks being easily simulated with short routines, and the non-obviousness at design time of needing to support high-level languages in the ALGOL style, I doubt it was seriously considered.

3
  • 3
    "I suspect the designers would have been quite surprised...it would be hosting fairly complete compilers for languages like FORTRAN 66..." Not to mention that part of the OP's question rests on the idea that TCO and such is even possible when the compiler itself must run in that 4k field architecture. You aren't going to have much luck applying late-1970s to early-1980s research-grade optimization tech to a compiler that must run on a mid-1960s computer design. It was a minor miracle to get a non-optimizing compiler into that space! Apr 26, 2021 at 19:04
  • 4
    @WarrenYoung Well, I was thinking more in terms of handwritten assembly; I was doing TCO by hand on a 6502 back when I had no idea that optimization had a formal name :) You are right of course that squeezing an optimizing compiler into a PDP-8 is a nontrivial challenge.
    – rwallace
    Apr 26, 2021 at 20:32
  • 5
    Absolutely the case. Look at the use cases. Hardware stack - esp for subroutine call/return - wasn't as interesting back then as it is now. FORTRAN and assembler didn't need it. Instrumentation/laboratory/industrial control programming - main use cases for PDP-8 - didn't need it. Nobody was running large programs, nobody was running the available languages (ALGOL family) that used a stack for its execution model. Look at the use cases for this little machine.
    – davidbak
    Apr 27, 2021 at 15:12
7

I'm going to say no.

The PDP-8 was chiefly designed for compatibility with the PDP-5, and this machine also had no hardware stack.

There is not enough room in the instruction space to add push and pop instructions either.

4
  • 1
    I'm afraid I must completely disagree that there is no room in the instruction space for the extra instructions. With its one accumulator, the PDP-8 would need only 6 stack instructions (per stack), and they do not take arguments. - The last few models of the PDP-8 line used the Harris IM6120 CPU which implemented two stacks and simply defined 12 previously unused CPU-class (62xx) op codes to control them. Apr 28, 2021 at 1:20
  • @A.I.Breveleri being IOT instructions, they don't really belong in the CPU, do they? I take it those IM6120 instructions essentially use the IO subsystem to get at the accumulator. They even could use a completely different memory bank.
    – Lorraine
    Apr 28, 2021 at 3:19
  • 1
    Whatever you want to call them, there were plenty of unused op codes in those two ranges. Advances in electronic technology over the PDP-8 series lifetime gradually made these codes less expensive to use. - Even without such advances, a stack would have needed only one device code, and there were always lots of those. Apr 28, 2021 at 4:40
  • If anything, I would think that at the time the PDP-8 was being designed (the IM6120 was much later), some theoretical stack facility would have been realized as an optional external hardware. Something which could have been adapted for the PDP-5 and maybe -9 etc.
    – Lorraine
    Apr 28, 2021 at 4:47

You must log in to answer this question.

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