Zero Push Zero
It has taken me fifty years to realize that this puzzle is a fable, a story with a lesson.
First the puzzle is stated: On a PDP-10 computer, clear memory and then execute a PUSH instruction placed at memory location zero.
What happens ?
The simple answer is that:
A one instruction computer program, copies itself twenty times,
and dies hanging the machine in an infinite loop.
The lesson is: Unlike the LISP-Eval-LISP story, or the Function 91 story,
the indirect addressing self reference in this case is a mistake leading to failure.
It was caused either by engineering laziness or design hubris.
I wish to elaborate the story at some length.
The longer technical explaination is that:
Exactly twenty instruction cycles later,
the computer will enter an infinite addressing loop at memory location octal 023
attempting to execute the instruction PUSH @22(2) while index register 2 contains the value 1.
The atsign "@ " is the indirect addressing bit.
The numeral 2, within parentheses, specifies index register two.
That 20th PUSH is attempting to fetch a word of data to place into its stack,
The infinite loop is that the PDP-10 addressing computation
requires adding the address field from the instruction word, 000022,
to the value of the specified index register #2 which is a 1,
then fetching an indirect address, because the indirect bit of the instruction was on,
but now the addressed word is location 023 which is the same as the instruction word as just explained.
The address field is still 000022 with index register 2 still at value 1 and the indirect bit is still on.
The stack control register at zero contains a final value of 261023000023 as octal 36 bits wide.
The execution trace goes as follows:
Location Instruction PDLPTR
step#1. 0 / PUSH 0,0 0/261001000001 stores 261000000000 into m
step#2. 1 / PUSH 0,0 0/261002000002 stores 261001000001 into m
step#3. 2 / PUSH 0,1 0/261003000003 stores 261000000000 into m
step#4. 3 / PUSH 0,0 0/261004000004 stores 261003000003 into m
step#5. 4 / PUSH 0,3 0/261005000005 stores 261000000000 into m
step#6. 5 / PUSH 0,0 0/261006000006 stores 261005000005 into m
step#7. 6 / PUSH 0,5 0/261007000007 stores 261000000000 into m
step#8. 7 / PUSH 0,0 0/261010000010 stores 261007000007 into m
step#9. 10 / PUSH 0,7 0/261011000011 stores 261000000000 into m
step#10. 11 / PUSH 0,0 0/261012000012 stores 261011000011 into m
step#11. 12 / PUSH 0,11 0/261013000013 stores 261000000000 into m
step#12. 13 / PUSH 0,0 0/261014000014 stores 261013000013 into m
step#13. 14 / PUSH 0,13 0/261015000015 stores 261000000000 into m
step#14. 15 / PUSH 0,0 0/261016000016 stores 261015000015 into m
step#15. 16 / PUSH 0,15 0/261017000017 stores 261000000000 into m
step#16. 17 / PUSH 0,0 0/261020000020 stores 261017000017 into m
step#17. 20 / PUSH 0,17 0/261021000021 stores 261000000000 into m
step#18. 21 / PUSH 0,0 0/261022000022 stores 261021000021 into m
step#19. 22 / PUSH 0,@21(1)
== PUSH 0,0 0/261023000023 stores 261022000022 into m
step#20. 23 / PUSH 0,@22(2) !! INFINITE addressing loop at 023
The PUSH instruction first retrieves a word of DATA from its effective address,
then increments both halves of the PDLPTR,
then stores the data into right half (PDLPTR).
For example, the index register #1 detail of the penultimate step #19,
I had not appreciate until February 2018,
that the execution of PUSH 0,@21(1)
which gets logged as yet another "PUSH 0,0" is slightly more complex:
because 021 is indexed by 0, and then indirects thru 021 which is 0;
fore shadowing by two microseconds the disaster at step#20.
On the first early levels, the initial riddle,
when heard and if taken seriously,
might give one a deep understanding of computer addressing mechanism;
as well as simply the steps in executing the PUSH instruction,
The PUSH and POP instructions in the 1960s were a novel innovation.
The PUSH and POP semantics might be attributed to the stacks of dinner plates as an MIT student cafeteria
frequented by a couple of MIT hobby Railroad club members,
who then coined the names of the computer opcodes in the design transition
from research TX0 into TX2, and again for commercial PDP1 into PDP6.
When did you first hear "PUSH" and "POP", "KILL" and "YANK", "CUT" and "PASTE" ? How old are you now ?
How far did you live from Harvard Square ? or from the corner of Page Mill and I-280 ?
Then I reflect on Why this design?, is it a good design, is it pragmatic YES, is it aesthetic NO.
Then reflect on respecting authority,
did Ed Fredkin, Gordan Bell and Alan Kotok really know what they were doing here ?
Did they reflect on an infinite address computation ?
do we now reflect on self-programming, self-inspection, self-modifing code ?
I vaguely recall, that I first heard this puzzle,
I was standing near the coffee at the Prancing Pony, in the D.C.Power Building,
Some one asked me "What do you think a PUSH zero in zero does ?".
If you were a young PDP-10 super computer programmerm wanna-be, in the 1970s
You would think "whoa! Where is the stack pointer?"
Ah, oh, um, the stack pointer is the instruction itself,
Sick, sick, but it is a challenge puzzle for super programmers to solve
and prove-worthy of epic hero status like a cybernautic Achilles.
Why isn't the left half of the accumlator negative something ?
No, that doesn't matter for a puzzle problem.
What word gets pushed ? um the content of the accumulator zero itself !
Where does that word go ? um into memory slot #1 from memory slot #0. kinky.
What is the next instruction ? the same push as was in zero, but incremented on both the left and right side by 1.
Maybe after more coffee, the pot of drip coffee was hours old, with a half inch of unattactive sludge at the bottom;
which would require starting a new pot,
requiring cleaning the previous pot, per the posted rules,
an so on per the usual 1960s graduate student reseach lab sites.
So now, You see that the stack pointer is incrementing
just in time to write a new PUSH instructions into each of the sixteen accumulators, in lock step,
and then something messy is likely to happen as the index register field overflows into the indirect bit field.
THEN, I, as well as you, will set this silly puzzle aside (decades will pass by)
This puzzle will on occasion pop up (intentional pun) and be mentioned, en passant,
at conversations down the years, at a BBQ here, or while standing around at a Hackers gathering or conference there;
while waiting for the catering to overload the buffet tables,
and now decades later at memorial services or reunion dinners.
I once attribute this puzzle, wrongly to the famous HAKMEM file, (MIT AIM memo #229)
or to the famous Hackers Dictionery, or to an individual famous hacker, was it Poole, Minsky or Gosper ?
It was not Earnest, McCarthy or even Knuth.
Was it Kotok or Bell or Fredkin ?
On the PDP-10 simulators I have maintained,
I simply hate the infinite address computation of the original DIGITAL hardware,
AND so I implement the two black holes: INDIRECT addressing and XCT[XCT] as truncated at two deep.
I have NOT found a single fragment of historical software ever hitting these low-bar limits.
Login in as either BGB or REG, run RAID, enter the PUSH instruction,
0 § Stanford-ALT-mode-character ⎇ Ⓢ
hello but the post mortem gets clobbered. You need to use the Google devTool setting a breakpointer
or be satisfied with using the .E examine command.
Example of deep indirect addressing
Here is stub for an example program to exercise four levels of PDP-10 indirect addressing.
The addressing stop value at z lacks the indirect bit.
The effective address daisy chain from w, to x, to y, to fetch the contents of z; works but is pointless.
Displacement by an index register, in some mid addressing fetch,
also seems pointless since everything is based on an elaborate read-only table.
Lets try implementing four dimensional Tic-Tack-Toe with 3x3x3x3 little squares.
z: xwd 777757,777777
sa: move @w