“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
indirect jumpoperations. 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 aWe can see this in the LISP 1.5 assembly code:
TSX SUBR, 4where
SUBRis the location of the first instruction of the subroutine. The subroutine ends with its value in the AC and the instruction
TRA 1,4which returns control to the instruction after the
TSXthat set IR4. Note that any other program can be executed between this
TRA 1,4so long as the contents of IR4 are restored to the value set by the
TRAis 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
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