Came across a curious claim today about the PDP-6:
First, 36 bits was the standard for scientific computing. This extended word length also accommodated LISP, a new language developed for work in artificial intelligence
Is there any particular reason you can't do LISP in 18-bits? The address space was still 18-bits, so it's not memory size.
Is there any particular reason you can't do LISP in 18-bits?
No, as already commented, LISP can of course be done with any machine word size. It's just that a 36 bit word could hold all elements of a "CONS" (aka a pair), the core management object of LISP, on the computer LISP was developed for (*1).
On a 36 bit machine, any access to a list will always retrieve a CONS at once, whereas on an 18 bit machine two fetches are necessary. More so, a 36 bit register always holds a complete CONS, making a CONS atomic within the underlying hardware, all without further ado.
The address space was still 18-bits, so it's not memory size.
It's not about address length but encoding. In fact, the usable address space for 36 bit Lisp implementations was only 15 bits, good for 32 KiWords. This was quite fine in 1958 where even a top-end computer like the IBM 704 maxed out at 32 KiWords (*2).
A basic element of a list, a CONS, consists of two pointers:
A pointer needs to be qualified, as it may point to another list (CONS), or a leaf (ATOM). A few bits are needed to be added to each pointer.
Now, the original LISP was developed on an IBM 704, a computer with 36 bit word size and 15 bit address size, which not only gave room nicely to hold two 15 bit address pointers plus the needed qualifiers, but also had instructions for easy access of these fields.
In fact, LISP is much more tied to the 704 machine structure than one may expect, as these 4 fields are what a type A instruction looks like:
This looks quite like a CONS, doesn't it? This was noted by the developers of the first implementation. More so as the 704 offered instructions to directly read or write (*4) each of these fields within a register. Almost as if the 704 was purposely constructed to support Lisp (*5).
Lisp was implemented using a set of Assembly language macros (*6) to access the fields within a CONS element: CPR, CDR, CTR and CAR. The macro to create a CONS-word from its fields was called CONS (*7). Everything else was constructed from there. CAR and CDR survived into later Lisp lingo as shorthand for the elements of a CONS.
_Update: When looking for some links to improve this, I found that the Wiki article about CAR and CDR offers a pretty detailed explanation of the origin.
Using this structure made CONS atomic machine words and not only allowed easy access and use of both pointers, but was also quite compact and performant. Later, non 704/709x based, 36 bit implementations had to use shift and masking operations to do the same. This lost the performance advantage, but still kept the atomic nature of a CONS.
And yes, all of this can be of course be done on an 18 bit machine. Except now a CONS will cover two (18 bit) words, effectively halving the available memory as now only even addresses are valid - or each and every access will need to include a shift operation to turn a CONS address into a memory address (*8).
Like so often it's not about an implementation being impossible, or the difference being huge, but the little advantage that will pay out big when done often enough - like with every access or iteration.
*1 - And was still good for quite some time after.
*2 - 32 KiWords may seem not much today, but it was exceptional at the time. For the 704, magnetic core memory was built from one or more 737 Magnetic Core Storage Unit, each delivering a whopping 4096 Words in a shell roughly the size of one of today's 19" racks (plus two racks for the controller). It would take 8 such units to populate a 15 bit address range. Not sure how many users/universities could have afforded such a large configuration.
Very early computing had much more in common with micro pioneers and their single boarders than one often imagines - high flying ideas, like Lisp, and puny hardware barely able to implement the basic version of that idea :)
*3 - Called Decrement as index values would be subtracted from a base address
*4 - Tag write was never implemented
*5 - Which may as well be part of the impression that Lisp is especially good on 36 bit (704) type machines.
*6 - The first implementation was in Assembly, what else?
*7 - Assembly can mimic other high level languages quite closely ... accepting a somewhat bent syntax might help :=).
*8 - Which might be not as much of an additional burden as the address had to extracted by masking anyway.
There have been many implementations of Lisp for machines with registers narrower than 36 bits (most commonly, for 32-bit machines). It’s a high-level language that can be implemented in many different ways.
However, Steve Russell originally implemented the interpreter for John McCarthy’s Lisp on an IBM 704 computer with three different types of register. The 36-bit registers could be efficiently decomposed into a pair of 15-bit fields, with six bits left over for tags. Russell recalls:
The 704 family (704, 709, 7090) had "Address" and "Decrement" fields that were 15 bits long in some of the looping instructions. There were also special load and store instructions that moved these 15-bit addresses between memory and the index regiseters ( 3 on the 704, 7 on the others )
We had devised a representation for list structure that took advantage of these instructions.
Because of an unfortunate temporary lapse of inspiration, we couldn't think of any other names for the 2 pointers in a list node than "address" and "decrement", so we called the functions CAR for "Contents of Address of Register" and CDR for "Contents of Decrement of Register".
After several months and giving a few classes in LISP, we realized that "first" and "rest" were better names, and we (John McCarthy, I and some of the rest of the AI Project) tried to get people to use them instead.
Alas, it was too late! We couldn't make it stick at all. So we have CAR and CDR.
As the 704 has 36 bit words, there were 6 bits in the list nodes that were not used. Our initial implimentation did not use them at all, but the first garbage collector, comissioned in the summer of 1959, used some of them as flags.
Atoms were indicated by having the special value of all 1's in car of the first word of the property list. All 0's was NIL, the list terminator.
He added that the A field was used for the head of a list node and the D field for its tail on the theory that the head would be used more often, and would be one clock cycle faster that way. (In a comment, Raffzahn tells me that Russell misremembered which models had three registers and which had seven.)
Lisp soon moved to the DEC PDP-10, a successor to the PDP-6 that also had 36-bit words that could be decomposed into two parts. This allowed software relying on this feature of the IBM 704 to be ported to the DEC PDP-6 or PDP-10. Alan Kotok, a MIT alumnus who was friends with many of the Lisp hackers at MIT and one of the designers of the PDP-6, recalled, “facilitating a good Lisp implementation was an important consideration.”
