Stories

Let's ask the waiter

In the 1970s, at a Chinese restaurant just across El Camino from the Stanford Campus. A waiter approaches a round table seating eight or nine Silicon Valley corporate technology employees from a company like I.B.M. or Digital Equipment. They are chattering loudly:

        What's the size of the cache on our new model ?

        What's the fish of the day ?

        Let's ask the waiter.

   The cache size on you new model is eight kilobytes,
   and the fish of the day is halibut Schezwan.

Russian for XING

John McCarthy asked me to help car pool six Russian visitors from the airport to Stanford. We met the Russians, with their baggage carts, at the international terminal outside customs. They were jet lagged and it was late in California. The three senior academic experts went with Professor McCarthy Two lesser ranking computer experts got in the back seat of my car, a Datsun 510, a talkative Russian, who I assume was an escort, since he was reasonably fluent in English, but knew nothing about computer programming. Our conversation, started with how could a mere graduate student afford such a nice Japanese car, and proceeded to Caliofornia Road signs such as what does "XING" mean.

Better Red than expert

Mao Zedong, 毛泽东 1893 to 1976, was still alive when a delegation of Chinese academics visited our lab. The high point of the robotics demonstration was the hand-eye arm writing in Chinese with a paint brush "Better Red than Expert".

要红不要专

Librascope Auction Story

Librascope was decommissioned on 1 November 1976, per the minutes of the weekly System Meeting at SAIL. SYSTEM.MTG[D,LES]

Librascope: Rest in peace. Decided that the maintenance effort required is no longer worth the performance gain. We will either give it away or scrap it - LES.

$151 to David Shaw, $150 to Geoff Goodfellow (SRI), $130 to Vic Scheinman, and $129 to L. Earnest. They are all fools who lose control at auctions. Les

LISP eval LISP

The computer programming language named LISP, was invented by John McCarthy. The startling, LISP in LISP, fragment in a golden frame is:

 apply[fn;x;a] =
      [atom[fn] → [eq[fn;CAR] → caar[x];
                   eq[fn;CDR] → cdar[x];
                   eq[fn;CONS] → cons[car[x];cadr[x]];
                   eq[fn;ATOM] → atom[car[x]];
                   eq[fn;EQ] → eq[car[x];cadr[x]];
                   T → apply[eval[fn;a];x;a]];
       eq[car[fn];LAMBDA] →
                    eval[caddr[fn];pairlis[cadr[fn];x;a]];
       eq[car[fn];LABEL] → apply[caddr[fn];x;
                           cons[cons[cadr[fn];caddr[fn]];a]]]
  eval[e;a] =
      [atom[e] → cdr[assoc[e;a]];
       atom[car[e]] → [eq[car[e];QUOTE] → cadr[e];
                       eq[car[e];COND] → evcon[cdr[e];a];
                       T → apply[car[e];evlis[cdr[e];a];a]];
       T → apply[car[e];evlis[cdr[e];a];a]]
  evcon[c;a] = [eval[caar[c];a] → eval[cadar[e];a];
               T → evcon[cdr[c];a]]
  evlis[m,a] = [null[m] → NIL;
               T → cons[eval[car[m];a];evlis[cdr[m];a]]]
  pairlis[x;y;a] = [null[x] → a;
                   T → cons[cons[car[x];car[y]];
                               pairlis[cdr[x];cdr[y];a]]]
  assoc[x;a] = [equal[caar[a];x] → car[a];
                         T → assoc[x;cdr[a]]]
  

The significance and worship of the gold framed code is well documented, search for LISP as the Maxwell equations of software. For me the fragment is a piece of intellectual catnip that sets off both fond memories and renewed insights.

My coming of age story has a large gap. I simply do not recall when I first saw LISP. Likely it was at some point in the early 1960s when I must have read that LISP was at the frontier of computer programming and Artificial Intelligence, and so I appended it to my fantasy self image without actually bothering to learn it or use it prior to 1969. In January 1969 however, after a brief 1968 flirtation with particle physics at SLAC, I moved to SAIL and immediately had to cram study LISP to catch up with my self image and my new academic advisers, John McCarthy and Tony Hearn.

Even before I was in high school, I was fascinated with electronic brains, and somehow acquired and read, perhaps in 1958, the 1953 book Faster Than Thought, editor B.V.Bowen, available on Archive.org, with the front plate picture, The Countess of Lovelace, Ada Augusta and a picture of Charles Babbage after page 12. I took the one-bit adder diagram, on page 53, as a DIY project using relays for logic gates.

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[1]
step#2.    1 / PUSH 0,0   0/261002000002 stores 261001000001 into m[2]
step#3.    2 / PUSH 0,1   0/261003000003 stores 261000000000 into m[3]
step#4.    3 / PUSH 0,0   0/261004000004 stores 261003000003 into m[4]
step#5.    4 / PUSH 0,3   0/261005000005 stores 261000000000 into m[5]
step#6.    5 / PUSH 0,0   0/261006000006 stores 261005000005 into m[6]
step#7.    6 / PUSH 0,5   0/261007000007 stores 261000000000 into m[7]
step#8.    7 / PUSH 0,0   0/261010000010 stores 261007000007 into m[10]
step#9.   10 / PUSH 0,7   0/261011000011 stores 261000000000 into m[11]
step#10.  11 / PUSH 0,0   0/261012000012 stores 261011000011 into m[12]
step#11.  12 / PUSH 0,11  0/261013000013 stores 261000000000 into m[13]
step#12.  13 / PUSH 0,0   0/261014000014 stores 261013000013 into m[14]
step#13.  14 / PUSH 0,13  0/261015000015 stores 261000000000 into m[15]
step#14.  15 / PUSH 0,0   0/261016000016 stores 261015000015 into m[16]
step#15.  16 / PUSH 0,15  0/261017000017 stores 261000000000 into m[17]
step#16.  17 / PUSH 0,0   0/261020000020 stores 261017000017 into m[20]
step#17.  20 / PUSH 0,17  0/261021000021 stores 261000000000 into m[21]
step#18.  21 / PUSH 0,0   0/261022000022 stores 261021000021 into m[22]
step#19.  22 / PUSH 0,@21(1)
            == PUSH 0,0   0/261023000023 stores 261022000022 into m[23]
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.

Running zero-push-zero on the javascript SAILDART emulator, Login in as either BGB or REG, run RAID, enter the PUSH instruction, .L 1.BGB .R RAID linefeed PUSH enter 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.

title infour
w: @x
x: @y
y: @z
z: xwd 777757,777777
sa: move @w
    move @[@[@[@[01234567]]]]
    exit
end sa
comment ⊗
a: b(1)
b: c(2)
c: d(3)
d: e(4)
⊗