[cl-faq] car and cdr naming

[Pascal Bourguignon]

Justin Heyes-Jones writes:
> Figured I'd answer this one...
> 
> \faq{
> \question{Why are CAR and CDR called that?}
> \answer{
> car and cdr are the fundamental accessors for the head of a list and
> the rest of a list. Their names come from the names of two assembler
> macros on the IBM 704 mainframe.

They were not assembler macros.



"CAR" and "CDR" are the name of two fields of the registers of the
704, 709, and 7090.



The 7090: An early Lisp Machine?
--------------------------------

Of course, we all know how CAR/CDR came from the address and decrement
part of 704/7090 instructions.  But tag bits where also present.  The
36-bit words could be considered as:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|opcod|    decrement ( 15-bit)      | tags|   address ( 15-bit)         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|s 1 2|3 4 5 6 7 8 9 0 1 2 3 4 5 6 7|8 9 0|1 2 3 4 5 6 7 8 9 0 1 2 3 4 5|
|0 0 0|0 0 0 0 0 0 0 1 1 1 1 1 1 1 1|1 1 2|2 2 2 2 2 2 2 2 2 3 3 3 3 3 3|
|     |                             |     |                             |
 
There are instructions to get or set each of the fields: the operation
code, the decrement, the tags and the address.

STO CLA  store and load a full word (CONS) in the 36-bit accumulator AC.
STP      store the prefix (ie. operation code, ie. "tags for CDR").
STD      store the decrement.
STT      store the tags ("tags for the CAR").
STA      store the address.

SXD LXD  store and load the decrement (CDR) in a 15-bit index register.
SXA LXA  store and load the address   (CAR) in a 15-bit index register.

PXA PDA  move decrement or address between AC (CONS) 
PXD PDX  and an index register.





In the source of LISP 1.5, the CAR and CDR were accessed directly with
these instructions.  For example:

 APPLY SXD ASS1,4
       TZE 1,4
       STO AST1                   F
       PDX 0,4
       SXA     ASS1,4             SAVE FUNCTION ALONG WITH INDEX REGISTE
       CLA 0,4                    CWR(F)
       PAX 0,4                    CAR(F)

...

 ASP4  LXD AST1,4                 F
       CLA ,4
       PDX ,4                     CDR(F)

...


Of course, since these were important fields of the CONS structures,
there was lisp-level procedures to extract them. Here are the two CAR
and CDR lisp procedures:


R      HED
       REM CAR
       REM
CARP   SXA     CARX,4
       PDX ,4
       CAL ,4
       PAX ,4
       PXD ,4
CARX   AXT     **,4                                                     PAGE 152
       TRA 1,4
 BFS1
       REM
CDRP   SXA     CDRX,4
       PDX ,4
       CLA ,4
       ANA BFDM
CDRX   AXT     **,4
       TRA 1,4
 BFDM  SYN     $DMASK
       REM
       REM

In addition, there was two LISP symbols, named CAR and CDR, whose SUBR
property pointed to the above CARP and CDRP procedures:

*                                                                       GPLI0096
)011           -1,,-*-1                                                 GPLI0097
               SUBR,,-*-1                                               GPLI0098
               -*-1,,-*-2                                               GPLI0099
       TXL     CARP,,1                                                  GPLI0100
               PNAME,,-*-1                                              GPLI0101
               -*-1               CAR                                   GPLI0102
               -*-1                                                     GPLI0103
       OCT     232151777777                                             GPLI0104
*                                                                       GPLI0105
)012           -1,,-*-1                                                 GPLI0106
               SUBR,,-*-1                                               GPLI0107
               -*-1,,-*-2                                               GPLI0108
       TXL     CDRP,,1                                                  GPLI0109
               PNAME,,-*-1                                              GPLI0110
               -*-1               CDR                                   GPLI0111
               -*-1                                                     GPLI0112
       OCT     232451777777                                             GPLI0113

(and similarly for RPLACA and RPLACD).


Therefore, CAR and CDR designate:

- two fields of the processor registers, which can be manipulated
  directly with the micro-instructions of the processor,

- two assembler subroutines that allow LISP programs to extract these
  register fields,

- two LISP symbols fbound to these assember subroutines.



> These macros were used to extract two memory addresses from a 36bit
        subroutines

> register. car is an abbreviation of contents of address of register
> whilst cdr is for contents of decrement of register.
> 
> The assembler macros ended up with a home in lisp itself since they
> formed the basic computer operations on the 704 to perform what we can
> refer to as first and rest.
> 
> car and cdr survive in modern common lisp mostly for nostalgia reasons
> and also because of an interesting set of abbreviations they allow. By
> forming new abbreviations such as cadr and caaddr we treat each a as a
> car and each d as a cdr.
> 
> So cadr is an abbreviated form of (car (cdr lst)) and caaddr is an
> abbreviation of (car (car (cdr (cdr lst)))
> 
> See wikipedia's entry for more
> http://en.wikipedia.org/wiki/Cdr
> }
> }


It might be useful to add a discussion 
of cons/null/car/cdr vs. list/endp/first/rest

cons, null, car and cdr implement the pair abstract data type.  We use
them when we consider a record of two elements (an assoc for example), or
when we build a higher level data structures, like a tree, a list or
whatever.

list, endp, first and rest implement the Lisp list abstract data type.
We use them when we consider lists of items.  


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

The world will now reboot.  don't bother saving your artefacts.