Where did the stack go?

[This post doesn't describe things the way I'd like to. Please see the subsequent post.]

The IBM 704 didn't have a stack.

This was not unusual at the time. Although stacks were known about for years before, low-level languages did not make much use of them. Early FORTRAN certainly didn't need a stack, so IBM didn't bother with a hardware implementation.

Not having a stack does make it a bit of a challenge to program. For example, when you call a subroutine, where does the return address go?

The IBM 704 had an instruction TSX (Transfer and Set Index) that was designed for subroutine linkage. TSX would do two things. First, it loaded a register with the two's-complement value of the program counter. (The IBM 704 was much better at subtraction than addition. The two's complement of the program counter made it easier to dispatch because subtracting a two's complement number gives the same result as adding the uncomplemented number.) Second, it loaded the program counter with the subroutine address. Loading the program counter would cause an unconditional jump to the subroutine.

There was obviously a data path from the instruction register to the program counter — that's how the target address got from the instruction stream to the program counter. Likewise, there was a data path from the program counter to the register set. However, there doesn't appear to be a data path from the register set back in the other direction. So we can use the TSX instruction to call a subroutine, but once there we need to do a nasty trick to get back. That trick is to end the subroutine with an unconditional jump (opcode TRA). When we enter the subroutine, we expect the return address to be in one of the registers (by convention, LISP used register 4). The first thing the subroutine does is to save the return address in the target field of the TRA instruction. This modifies the code so that the unconditional jump at the end takes us back to where the subroutine is called.

But what if the subroutine needs to be re-entrant?

Ultimately, you need a stack (or a heap). There are several options for implementing one. The obvious idea of allocating a block of memory and keeping a pointer to the top of stack was not obviously the best idea. Without dedicated hardware, operations like push and pop become quite expensive. You have to fetch the stack pointer from memory, perform an addition or subtraction, do an indirect memory reference, and write the new stack pointer back to memory. (And if you thought the x86 didn't have enough registers, the IBM 704 had only 3 index registers.)

Another method is to use a linked list as a stack. This is not obviously a bad idea. Once the linked list is created at program initialization time, pushing and popping can be done via pointer chasing. This avoids having to use the ALU for adding and subtracting the stack pointer. Furthermore, you didn't have to guess how much stack space to reserve. with only 32,000 words of memory, you didn't want to waste any on unused stack reserve. For these reasons, both IPL and LISP I used a ‘push-down list’ to implement re-entrant subroutines.