12

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.

8
  • 14
    A particular implementation might need 36 bits. But as you can see here you could run LISP on an 8-bit machine. Jul 19 at 14:21
  • For what it's worth, AutoLisp (a Lisp implementation that ran inside of AutoCAD) ran perfectly fine (if slow) on a 286 running on extended memory MS-DOS. I did a lot of AutoLisp work at the end of the 80s.
    – Flydog57
    Jul 20 at 20:52
  • Not unless LISP cropped up only after 36-bit computing. Are you suggesting there was no LISP before that? Jul 20 at 22:37
  • Not a duplicate, but adding a link for anyone wondering why 36-bit computers existed in the first place.
    – dan04
    Jul 20 at 23:38
  • 1
    @RobbieGoodwin The first LISP implementation was on the IBM 704, which was indeed a 36-bit computer (the same was true of FORTRAN). There was no simple progression from lower bit-ness to higher bit-ness in computing, no matter what the marketing for microcomputers tries to tell you :)
    – Luaan
    Jul 29 at 5:37

2 Answers 2

33

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:

  • CAR - pointing to the list item and
  • CDR - pointing to the next list entry

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.

  • 3 bits Prefix qualifier (CPR)
  • 15 bits Decrement address (CDR)
  • 3 bits Tag qualifier (CTR)
  • 15 bits Address address (CAR)

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:

  • 3 bit Prefix, the instruction
  • 15 bit Decrement, an index to be used (*3)
  • 3 bit Tag, selecting one or more index registers to be used
  • 15 bit Address

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.

10
  • Do you have a source for "In fact, the very first LISP implementation consisted of just two macros called CAR and CDR"? That seems very strange to me as a modern lisper. I can believe cons cells were the only way to compose data, but (a) those are not usually macros, and (b) there would usually be some primitive/scalar types under that, e.g. to represent numbers in a reasonable way (the ATOM you describe).
    – amalloy
    Jul 20 at 0:37
  • 1
    @amalloy I think Raffzahn means “assembly language macros”. But CAR and CDR were merely subroutines in the original Lisp, and they can be found on pages 151 and 152 of this listing of the interpreter's source code from 1961.
    – texdr.aft
    Jul 20 at 1:13
  • 1
    @amalloy The first implementation was done in Assembly - what else - and CAR/CDR were, as texdr.aft says, a assembly language macros. In fact, there were 4, but only these two survived in name. An ATOM was simply a whole 36 bit word pointed to by CAR.There were no other ATOM types than those words.
    – Raffzahn
    Jul 20 at 4:51
  • 1
    I wanted to correct your statement "Its not about address length but encoding. In fact, the usable address space for 36 bit Lisp implementations was only 15 bit, good for 32 KiWords." Perhaps true for the (early) 704 implementation you describe, but not in general. I refer you to "Data Representation In PDP-10 MacLISP" (Steele, 1977) which describes two different implementations of MacLISP on the -10 both using full 18-bit addresses for cell/symbol pointers etc., and using auxiliary data type tables.
    – davidbak
    Jul 22 at 17:30
  • (That paper has an interesting companion, "Fast Arithmetic in MacLISP" (Steele, 1977), and IMO both are well worth reading even today for interesting examples on how to use your ISA to the max! And for use of the powerful indirect address feature of the -10 ISA, which has been discussed, with admiration, here at Retrocomputing. And also because they're written by Guy L. Steele, Jr., who always always writes about complicated things with such extreme clarity you'd think they were actually simple!)
    – davidbak
    Jul 22 at 17:33
10

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.”

6
  • 1
    It was actually Steve Russell who did the implementation. Paper by McCarthy. For the DEC connection, Alan Kotok (a PDP-6 designer) was friendly with MIT LISPers and influenced the machine design in that direction, including the halfword instructions. Jul 20 at 1:35
  • @another-dave And, found a quote by Kotok confirming it.
    – Davislor
    Jul 20 at 1:53
  • 7 Index registers were only found on the 7094. Story told is that the trailing '4' is about these 4 additional registers. All other 709x has 3, like the 704.
    – Raffzahn
    Jul 20 at 14:24
  • 2
    The little extension cabinet on the 7094 console sure is a kludge, though. Jul 20 at 15:34
  • @another-dave love that classification :))
    – Raffzahn
    Jul 20 at 19:18

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.