22

From Ed Nather's hacker-epic "The Story of Mel" (using the original paragraph-formatting to save space in this question):

The firm manufactured the LGP-30, a small, cheap (by the standards of the day) drum-memory computer, and had just started to manufacture the RPC-4000, a much-improved, bigger, better, faster — drum-memory computer.
[...]
Perhaps my greatest shock came when I found an innocent loop that had no test in it. No test. None. Common sense said it had to be a closed loop, where the program would circle, forever, endlessly. Program control passed right through it, however, and safely out the other side. It took me two weeks to figure it out.

The RPC-4000 computer had a really modern facility called an index register. It allowed the programmer to write a program loop that used an indexed instruction inside; each time through, the number in the index register was added to the address of that instruction, so it would refer to the next datum in a series. He had only to increment the index register each time through. Mel never used it.

Instead, he would pull the instruction into a machine register, add one to its address, and store it back. He would then execute the modified instruction right from the register. The loop was written so this additional execution time was taken into account -- just as this instruction finished, the next one was right under the drum's read head, ready to go. But the loop had no test in it.

The vital clue came when I noticed the index register bit, the bit that lay between the address and the operation code in the instruction word, was turned on-- yet Mel never used the index register, leaving it zero all the time. When the light went on it nearly blinded me.

He had located the data he was working on near the top of memory -- the largest locations the instructions could address -- so, after the last datum was handled, incrementing the instruction address would make it overflow. The carry would add one to the operation code, changing it to the next one in the instruction set: a jump instruction. Sure enough, the next program instruction was in address location zero, and the program went happily on its way.

A programmer's manual for the Royal Precision LGP-30 computer is available here. It does not seem to have an "index register"; it does have what it calls a "counter register" but that's just a traditional "program counter"/"instruction pointer." Which also means that the LGP-30 definitely did not have the "every instruction followed by a GO TO" feature that Ed Nather attributes to its successor the RPC-4000. The lack of an "index register" is also indicated by how the LGP-30 manual uses instruction modification to do load-from-consecutive-indices in a loop, in this section of the manual.

The Internet Archive has an RPC-4000 manual which does indicate the presence of a "next address" field and an "index tag field" (in the lowest-order bit). Ed Nather's story talks about "a jump instruction," which the RPC-4000 doesn't have; but if you were to increment a command word whose index bit was set, you'd end up overflowing into the "next address" field, which could probably be made to do something similar, maybe?

Can anyone provide an example of an "infinite loop" that uses anything resembling Mel's technique to break the loop?


There's some previous discussion on Hacker News here. Commenter "kps" points to an FTP site where you can download an LGP-30 simulator (written in Pascal): ftp://ftp.informatik.uni-stuttgart.de/pub/cm/lgp30/simulator/lgp30sim.zip
and a blackjack game (ASCII dump of the machine code): ftp://ftp.informatik.uni-stuttgart.de/pub/cm/lgp30/papertapes/Games/bkjck.tx
If it's possible to "disassemble" that blackjack game, that at least would be very interesting, even if it might not answer the question because the LGP-30 wasn't much like the RPC-4000.

9

I recently ended up looking into this myself, including reading the programming manuals for both machines mentioned.

Some quirks of the RPC-4000 include that the last few addressable tracks of the drum have special fast-access features which change the way the data is laid out. The last track actually has fewer usable locations due to this, so it would be very odd to find an array of any significant size there; you would use it for temporary variables instead. Additionally the opcode that would have to be incremented to become a conditional-branch instruction - a compare - seems a bit unlikely to be used in a loop with no apparent conditional branch to begin with.

I think it more likely that the strange loop construct actually existed in a version of the blackjack program written for the LGP-30 or one of its immediate descendants (more immediate than the RPC-4000, that is). The opcode numbers are more logical for this purpose, and if the two don't-care bits between the operand and the opcode fields are set, incrementing the former could indeed carry into the latter.

The narrator thus appears to be a bit unreliable. One reasonable explanation, though, is that he tried to compare the two implementations of the same game to figure out where the bug might be, and got his memory of this confused after so many years had elapsed since then.

| improve this answer | |
  • 1
    There's no direct evidence for this, but it's possible that Mel Kaye wrote BlackJack for the LGP-30; someone wrote a LGP-30 emulator for the RPC-4000; the emulator was imperfect and BlackJack cheated backwards under the emulator; and Ed Nather was tasked with fixing this vital application. It's easy to believe that failing to find a bug in a Mel program under an LGP-30 emulator running on a RPC-4000 could lead to some confusion when recalling events decades later. – A. I. Breveleri Jan 11 at 21:44
  • @A.I.Breveleri The story does specifically say that the blackjack program was rewritten for the RPC-4000. Simply running it under an emulator doesn't seem to fit that narrative. – Chromatix Jan 11 at 21:50
  • 5
    And remember that the point of Ed's story was never to expose the technical quirks of porting BlackJack from the LGP-30 to the RPC-4000. Ed was trying to convey the enormous intellectual effort required to squeeze any decent performance out of one of those primitive clunkers, and how one particular genius who thoroughly mastered the required techniques seemed to be operating on a completely different plane of existence. – A. I. Breveleri Jan 11 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.