[cl-faq] car and cdr naming
Justin Heyes-Jones
justinhj at gmail.com
Fri Jan 13 08:03:17 CST 2006
On 1/13/06, Pascal Bourguignon <pjb at informatimago.com> wrote:
>
> 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.
> _______________________________________________
> cl-faq mailing list
> cl-faq at lispniks.com
> http://www.lispniks.com/mailman/listinfo/cl-faq
>
Thanks for the correction Pascal, but isn't car "contents of address of
register" rather than the name of that part of the register.
From the wikipedia entry it mentions car and cdr as being macros, so which
were they macros or subroutines?
I think that's an awesome amount of detail their but probably too much for
this question, since it is merely asking about the naming.
Condsidering from performance point of view you would expect macros.
We could break it out into a couple more questions and answer those though?
Perhaps ...
Can you tell me more about the CDR and CAR IBM 704 instructions?
What is a cons cell?
How are cons cells used to build more complex structures like pairs, trees
and lists?
Justin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.lispniks.com/pipermail/cl-faq/attachments/20060113/3b3c402b/attachment-0001.html
More information about the cl-faq
mailing list