LGP-30 – A Drum Computer of Significance | Hacker News Reader

LGP-30 – A Drum Computer of Significance

masswerk.at

50 pointsmasswerk39 comments

From the company in "The story of Mel" http://www.catb.org/~esr/jargon/html/story-of-mel.html

Mel Kaye's hack was actually performed on an RPC-4000, so the story goes.

When I was doing my CS degree and had plenty of time in my hands for that sort of thing, I had a look at the manuals for the two systems and tried to follow Ed Nather's story.

It looks like Ed Nather misremembered the story (in his defense it had been several decades since he'd seen it) because the whole hack rested on the machine having an index register bit "between the address and the operation code in the instruction word", but the RPC-4000 had the index register bit ("index tag") at the end of the instruction word [1] and nothing between the current instruction and operand address, which is, I think, the natural reading of "operation code" and "address" respectively. There's also nothing between the operand address and the next instruction address. The RPC-4000 word looks like this:

  [COMMAND][OPERAND ADDRESS][NEXT ADDRESS][X]
  |0     4||5    11|12   17||18 24|25  30||31|
                   |              |
             TRACK | SECTOR  TRACK|SECTOR

What Nather remembers could be an overflow of the NEXT ADDRES field, through the index tag, and into the COMMAND field. It depends on whether the RPC-4000 handled overflows by wrapping or saturation (I can't find that in the manual).

On the other hand, Nather's account states that the hack changed an instruction to a jump instruction- and the RPC-4000 does not have a jump instruction, because it doesn't need it: like Nather's story says, every instruction has its own GOTO- in the NEXT ADDRESS field.

Here's some alternative ways the hack could have played out, from what I can tell:

1. The hack used the "Branch control" facility.

The RPC-4000 had another facility, the "Branch control", an internal flip-flop with only one bit that was turned on when an arithmetic overflow was detected. Kaye could have used this instead of the index tag and Nather may have misremembered it as being the index tag.

2. The hack was actually done on the LGP-30

The hack might also have been possible to pull off on the LGP-30, that had two bits between the opcode and the operand address [2] and an uncontrolled jump instruction ("Unconditional transfer" in the manual). Kaye could have kept those two bits set and caused an overflow, as told in the story.

3. The hack was done on an RPC-4000 emulating an LGP-30.

Royal McBee had an emulator written for the RPC-4000, specifically to be able to run LGP-30 programs on the new machine [3]:

  My name is James William (Bill) Bryner ... In 1960 I was hired by Royal-McBee
  to write the assembler for the replacement to the LGP-30, the RPC-4000.

  Mel Kaye designed the RPC-4000 assembler. It was titled ROAR (Royal-McBee
  Optimizing Assembler Routine). Edward W. Dubbs and I programmed that
  assembler.  Following that, I wrote an LGP-30 simulator to run on the
  RPC-4000. This was meant to allow all programs written for the LGP-30 to be
  executed on the RPC-4000 without further programming. A drum computer
  simulating a drum computer is agonizingly slow!

I bet, the blackjack program that brought everyone to the Royal McBee booth would have been top of the line of the programs to be run on the RPC-4000. Perhaps, then, Nather was working on Mel Kaye's "port" of the original blackjack program, not on the RPC-4000 but on the LGP-30 emulator running on the RPC-4000. Judging from the descriptions of Mel Kaye's programs in Ed Nather's account, just having an emulator for the architecure would not necessarily mean that Kaye's programs would run without any changes on the RPC-4000.

I have no clear idea how any of the above could have worked. Just guessing.

_____________

[1] http://www.bitsavers.org/pdf/royalPrecision/RPC-4000/RPC-400...

[2] Here's an example from the LGP-30 manual, as in the article:

    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
                           (-------)   (----------)(------------)
                           order bits   track bits     sector bits
                             = bring       = 20           = 00
                                       ( address = 2000 )

[3] http://ed-thelen.org/comp-hist/lgp-30.html#Historical%20Note...

The LGP-30 version had a ‘cheat switch’. A paper-tape image is available¹ and I've disassembled it.

The LGP-30 has one conditional branch instruction, ‘T’, which normally tests the sign of the accumulator. But it has a variant form: if the sign bit of the instruction word is set (‘−T’), and the front panel TRANSFER CONTROL switch is set, then the branch is unconditionally taken.

This variant instruction form appears once in the game. In the normal case, a player using a simple strategy (take another card if ≤16) will quickly be in the hole. But if the TRANSFER CONTROL switch is set, they'll be ahead.

I don't have my notes handy, so my description of how this works may be slightly wrong.

The game has no seed for its pseudo-RNG; from a fresh load, if the player makes the same choices, the computer deals the same cards. (I can't think of any way to implement a changing seed on the LGP-30, other than asking the user to enter one.)

The game has a table of cards, indicating whether each card has been dealt or not. To deal, it pseudo-randomly selects a card, and checks whether it has been dealt already; if so, it tries again. (Yes, this is slow.) When all cards have been dealt, it clears the table to ‘open a new deck’.

When the program starts, it initializes the deck, unless the TRANSFER CONTROL switch is set. If the switch is set, the game starts with the deck table as loaded from paper tape. That (if I remember correctly) marks two aces as already used, and that is enough to skew the game play in the user's favour.

¹ ftp://ftp.informatik.uni-stuttgart.de/pub/cm/lgp30/

The "t" (test) instruction with the sign-bit option and the "Transfer Control" button are mentioned in the post as well (see operations). On the LGP-30 this would have been the only means of manipulating the control flow from the console in a sensible manner. (I didn't have a look into the RPC-4000 yet, so I really don't know, if there had been additional options.) So the way to implement an option would have been to have a zero or positive value in the accumulator and then have a test instruction with the sign-bit set. If the "Transfer Control" button was deployed, we would take the branch (unconditionally), if not, we'd fall through to the next instruction, since the condition 'AC negative' was not met.

Nice bit of digital archeology there- thanks!

While the story makes it quite clear that it is about the RPC-4000 (because of the next address encoded in the spare bits of the LGP-30 instruction format), your ideas regarding the LGP-30 in (2) may actually work. Instruction "u", unconditional transfer (jump), is 12 (%1010) and the next instruction code is "t" (13, %1011), which is "test" (branch if AC is negative). So a program may cleverly overflow (by adding to the gap in the instruction) from an unconditional transfer into a conditional one, which is then ignored as AC is zero or positive and the program "falls through"…

Similarly, we could overflow from "t" (test, conditional transfer) to "h" (store and Hold the contents of AC), but this doesn't make much sense, since we have a conditional branch instruction in place right from the beginning.

Thank you, Goblin Queen! I am persuaded by your logic.

Or without the irritating formating:

http://www.pbm.com/~lindahl/mel.html

This machine made ingenious, economical use of the technology available in the mid 1950s. Only 16 instructions. The ALU used all diode logic. The CPU only used a few tubes for flipflops to store control state.

The rotating magnetic drum provided all memory -- including CPU registers. A tiny oscilloscope on the front panel showed register contents as they rolled by the read heads!

How do you implement a whole ALU in diode logic? All i know about diode logic is what it says on the wikipedia page, but according to that, you can't implement a NOT gate, which i would have thought would make it very hard to implement anything of significance - even a half-adder requires a NOT!

At the RTL or Moore-machine level, a computer consists of some register state (the flip-flops) which changes, at each clock transition, to a deterministic function of its previous state and its input lines at the time. So you need a way to compute the new state as some arbitrary Boolean function of the previous state.

The flip-flops each have a Q output and an inverted Q̄ output, which comes for free due to the symmetric construction of the flip-flop from a pair of vacuum tubes and other components. You can form any arbitrary Boolean function of the flip-flop state from a sum of products of the Q and Q̄ variables; it's a simple matter of applying De Morgan's theorem and distributivity. (Or, for that matter, you can use a product of sums by doing it in negative logic.) The flip-flops can supply not just all the memory but also all the inversion, signal level restoration, glitch elimination, and amplification, none of which can be done with diode logic.

So, indeed, diode combinational logic is not capable of computing arbitrary Boolean functions of its input lines. But it is indeed capable of computing arbitrary Boolean functions of the flip-flops' state. And that is all that is needed.

The LGP-30 manual gives a complete description of how the computation works at the Boolean equation level, a description which I have not yet managed to grok.

If you're interested in this kind of thing, you might be interested in notes/non-inverting-logic.html in Dercuano: http://canonical.org/~kragen/dercuano-20190711.tar.gz. (Like most things in Dercuano, it's unfinished.)

Allegedly, there were just 15 flip-flops, which are reused a lot…

Here's I found a source for this: Stanley P. Frankel on the design of MINAC and the LGP-30 in IRE Transactions on Electronic Computers. (15 flip-flops, presenting both normal and inverted output to a logical network made of resistors and crystal diodes, providing basic monotonic Boolean functions like And, Or, and Xor.)

Stanley P. Frankel, “The Logical Design of a Simple General Purpose Computer” in: IRE Transactions on Electronic Computers, March 1957, pp. 5 [1]

[1] https://www.masswerk.at/nowgobang/misc/MINAC-IRE-March-1957....

Here's a photo (by Cory Heisterkamp) showing the logic networks from the Ed Thelen's website [1]: http://ed-thelen.org/comp-hist/images/Heistercamp-lgp.jpg

(The cards with the rest of the logic are behind and below the main network plane. Mind that this a Control Data model, so it's 1965 or later.)

[1] http://ed-thelen.org/comp-hist/lgp-30.html

This is awesome! Thank you! This should make the Boolean equations in the manual quite a bit easier to decipher.

XOR isn't monotonic — you can't make X ⊕ Y with diode logic given just X and Y, the way you can make X ∧ Y and X ∨ Y. However, you can make it given X, Y, X̄, and Ȳ. I'm not sure if you can make it with X, Y, and just one of X̄ or Ȳ.

Regarding XOR: This is sloppy quoting of Frankel, who writes about the monotonic functions "And and (nonexclusive) Or" – so, yes, inclusive Or only. However, as described, both the normal and the inverted (negated) outputs of the flip-flops ("toggles") are fed into the network, so there's X and Y and negated X and negated Y available.

Right, and as I explained at https://news.ycombinator.com/item?id=20488446, if you have negated versions of all the literals available, you can make not just XOR but any arbitrary Boolean function as a sum of products (or a product of sums, CNF), just like a PLD does.

Notably, you need XOR (single-bit add) for an ALU anyway… (So the somewhat weak exclusion of "exclusive" in Frankel's paper is a bit luxurious.)

"Luxurious"? I'm not sure what you intend to say. Do you perhaps mean "unnecessary" or "essential" or "very strong" or "very weak" or "well-thought-out"?

As I read it, he's pointing out that since the diodes and resistors can't do things like XOR, because it's not monotonic, it's necessary for "[e]ach input variable" to be "presented in duplicate".

Another example that is in some sense more fundamental than XOR is the MUX function b if a else c. If at some point b = 0 and c = 1, the output is the negation of A, which diodes and resistors alone cannot achieve.

"Luxurious" is a term from psychology, where it's used to describe "ornamental" behavior, which may be hinting at something deeper. ;-)

In the particular case, I just found it interesting, since the duplicate outputs are already well established, before the text "withdraws" to monotonic functions (for which both inputs are used). A bit of an understatement.

Edit: I think, "luxurious" as used this way is a great term, because it doesn't attempt to apply any classification. It's just pointing out that there's a somewhat independent process, which consumes energy.

Probably being bit-serial and storing the CPU registers on the drum helped a lot with this. Have you looked at the magnetostrictive-delay-line calculators from the mid-1960s, which used pulses of torsion in a coil of straight-annealed wire instead of a mechanical drum?

In fact, I just have "Electronic Computers" by S.H. Hollingdale and G.C. Toothill (Pelican / Penguin Books, 1965) besides me. While meant to be popular or introductory to the EE side of computing, this is a wonderful book full of such things! Highly recommended and cheap to pick up on various market places!

Thank you for the recommendation! It doesn't seem to be on Libgen or in the Archive's texts collection, and I doubt that I can find a paper copy here in Argentina. Maybe you could scan and upload it; it is presumably in the public domain if it was originally published in the US, since the authors probably did not bother to renew the copyright.

I picked mine up at abebooks.co.uk – it seems to have been quite popular in the UK at the time.

Regarding copyright: It was published in the UK. So for the moment EU copyright regulations, 70 years from the death of the author (I guess).

Ah, the LGP-30!

I've actually programmed one, back around 1980 or so, at the University of Calgary.

Some friends and I got a collection of computers to play a musical piece. The LGP-30's role was to do the percussion. It was a bit of a challenge to get it to output the rhythm (pounding on the flexowriter) at speed, but we eventually figured out how to get the program to go fast enough for this. Of course, we probably didn't know all the good tricks...

So it could be used as kind of drum computer in nowadays use of the term, too?

It's wonderful to see this investigation being done on such an important early computer; I've attempted to make my way through the logical equations in the carefully preserved manuals, but so far have not finished the job. The LGP-30 appears to be substantially simpler than later minicomputers, even the PDP-8, and I've long wanted to understand how it could work at all. This article should help me quite a bit.

Thank you, Norbert! You are a true hero.

It's also interesting to me that these sorts of posts have so much, and so better presented information than was available back in the day to those who had to maintain these machines.

For example I found this fascinating animation by kens more useful in understanding how the hydraulically powered 1403 printer worked than any training at the time http://righto.com/ibm1401/printchain.html.

One thing I was wondering, but is probably a bit too ephemeral to find out more about in primary sources: I have always been amused by the "DEC Chair", which came with all bigger PDPs. Some of the Royal McBee materials suggest (loosely so) that the LGP-30 came with its own chair as well and that this may have been a broader habit in the first few decades of computing, when computers were still voluminous and expensive. (However, I don't think that IBM did ever ship a chair with their equipment. But this is just a personal impression.) – Are there any personal memories?

Never heard of that, but the Cray-1 (not that I ever saw one) came with a magnificent circular seating arrangement around the machine itself https://www.computerhistory.org/revolution/supercomputers/10....

I can only imagine the rarefied conversations that would have taken place in such a setting.

>> I can only imagine the rarefied conversations that would have taken place in such a setting.

Yes, me too. Typical conversations you hear in data centers:

Alice: "I ...aid the... is... ...misf..."

Bob: "WHAT DID YOU SAY?"

Alice: "I ...AID THE ... ERF... MEF... NAH!"

The CDC 6600 (another fascinating design) came with an orange-red chair, matching some cabinet trim.

Also designed by Seymour Cray, but I have no idea whether he designed the upholstery as well.

This animation is great and really informative!

You are welcome! :-)

Regarding the PDP-8, have a look into "Computer Engineering" by Gordon Bell, Craig Mudge and John McNamara; DEC, 1978. (Quite common to find at a reasonable price, there are even some PDFs circulating, which may be found by your search engine of choice.)

Edit: Maybe also of interest, "Computer Structures: Reading and Examples" by Gordon Bell and Allen Newell (McGraw-Hill, Inc., 1971). For availability, see above.

Learned LGP-30 assembly language for my high-school's programming class back in 1973, but we didn't actually have one, or even access to one. The teacher had learned on a (real) LGP-30, and thought that we students ought to learn how CPUs really worked before graduating to a higher-level language (NEAT/3 for the NCR Century 100 that the school district did have). So, homeworks were handed in on paper, and the instructor would run them in his head.

One aspect of programming the LGP-30 is that, by convention, to call function FOO, the caller would store the return address at $FOO and then jump to $FOO+1, where the actual code for FOO started. Then, to return, FOO would do jump to the address in $FOO. So, no recursion was possible by default. (There was a single instruction that did "Store the already-incremented PC at a given location, and jump to just after that location", so it was all very efficient.)

This is really interesting, because this is how later machines did it (at least with sum call instructions). I was actually surprised that the Programming Manual suggested to insert the address directly at the final jump to return.

(Regarding recursion, you could emulate a stack by storing the top of stack in a particular address by convention, say 0000, and fix up the 'r' command on the fly to insert PC+2 at this location. Then, every subroutine would look up 0000 for the top of stack and fix up its final jump to return. However, this would seriously mess up the accumulator and you had to store any return values in another conventional address, etc...)

Hmmm; you’re closer to correct than I. Actual details are covered in http://ed-thelen.org/comp-hist/lgp-30-man.html#R3.16 where it explains that the “R” instruction would store away the address part of what was typically an unconditional branch. So, it was only by convention that this would be kept at $FOO, and that FOO would return by branching to $FOO. A super-smart compiler (they existed) would know the address of the last instruction of each routine, and be able to R into that location directly before calling (actually, just jumping) to $FOO.

One other cute thing was that all memory was on a spinning drum, and you could really speed up your program’s execution by placing variables at addresses that were just about to be under the read head when the current operation was being performed. Otherwise, everything had to wait for up to a whole drum rotation. Kind of the original “pipeline stall”.

In addition to influencing Lorenz and Licklider, the LGP-30 was also the machine first used by Kemeny and Kurtz at Dartmouth. Their experience with its interactive programming and their discovery that undergraduates could be enthusiastic and effective programmers inspired them to get a bigger/better computer and create BASIC.

Reply on news.ycombinator.com