No stack? No problem.

“We have no badges. In fact, we don't need badges. I don't have to show you any stinking badges...”
                 — The Treasure of the Sierra Madre, B. Travern

---

I really blew it with that last post. Mea maxima culpa.

---

The IBM 704 didn't have a stack.
This was not unusual at the time. Most computer languages at the time had no need of a stack at all. Algol, however, was a different story. Friedrich L. (Fritz) Bauer had, a few years earlier, invented the stack in order to support recursive descent evaluation of expressions. This appeared to be the best way to support the recursion and block structure that ALGOL required. As Alan Perlis notes:

It was ALGOL 60 that really pointed a finger at, focused on the absolute necessity of learning how to define, control and manipulate stacks. ALGOL 60 would have been impossible to adequately process in a reasonable way without the concept of stacks. Though we had stacks before, only in ALGOL 60 did stacks come to take a central place in the design of processors.
         —Alan J. Perlis, Transcripts of Presentation

Not having a stack can make it a bit of a challenge to program, but Steve “Slug” Russell invented a different technique. The assembly code of LISP I was written in continuation-passing style. (Russell did not name this technique; the phrase “continuation-passing style” seems to have been coined by Sussman and Steele in 1975.)

When a program is converted to continuation-passing style, all control transfer can be expressed with jump and indirect jump operations. This does not eliminate the need for temporary storage — any piece of re-entrant or recursive code will need to save and restore values in use as it calls subroutines — but it allows you to separate the control flow from the temporary storage management.

Closed subroutines in LISP are given a standard calling sequence. The arguments of the subroutines are placed in order in the AC, the MQ, and locations called ARG3 and ARG4.

After the arguments have been provided, the subroutine is entered by a TSX SUBR, 4 where SUBR is the location of the first instruction of the subroutine. The subroutine ends with its value in the AC and the instruction TRA 1,4 which returns control to the instruction after the TSX that set IR4. Note that any other program can be executed between this TSX and the TRA 1,4 so long as the contents of IR4 are restored to the value set by the TSX before the TRA is executed. A subroutine restores all index registers it uses to the value they had on entering the subroutine.
                 — S. Russell, Artificial Intelligence Project — RLE and MIT Computation Center, Writing and Debugging Programs — Memo 6

We can see this in the LISP 1.5 assembly code:

       REM
       REM APPEND(L1,L2)=
       REM (L1=0 YIELDS L2,1 YIELDS CONS(CAR(L1),APPEND(CDR(L1),L2))
A      HED
APPEND TNZ APNP1
       XCA
       TRA 1,4       ** Invoke continuation (return)

 APNP1 SXD AS1,4     ** Store continuation in memory
       TSX $SAVE,4   ** Call SAVE subroutine
       TXL     $END2,,CWR1+2      SAVE 2 ITEMS
       PDX 0,4
       CLA 0,4
       STO CWR1
       ANA DECM
       TSX APPEND,4  ** Recursive call to APPEND
       XCA
       LXA CWR1,4
       PXD 0,4
       TSX UNSAVE,4  ** Call UNSAVE to restore temps
       LXD AS1,4     ** Restore continuation to register
       TRA $CONS     ** Tail call CONS