Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
CAR and CDR
open-in-new
<h2 id="etymology">Etymology</h2> <p>Lisp was originally implemented on the <a href="/facts/IBM_704/bKkwXYb3">IBM 704</a> computer, in the late 1950s. </p><p>The popular explanation that <i>CAR</i> and <i>CDR</i> stand for "Contents of the Address Register" and "Contents of the Decrement Register"<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> does not quite match the IBM 704 architecture; the IBM 704 does not have a programmer-accessible address register and the three address modification registers are called "index registers" by IBM. </p><p>The 704 and its successors have a <a href="/facts/36-bit/P0V83YtM">36-bit</a> <a href="/facts/Word_(computer_architecture)/2e5umRaj">word</a> length and a 15-bit <a href="/facts/Address_space/EscyYKkP">address space</a>. These computers had two <a href="/facts/Instruction_(computer_science)/8p8vwUeE">instruction</a> formats, one of which, the Type A, had a short, 3-bit, <a href="/facts/Operation_code/UaLMp56C">operation code</a> prefix and two 15-bit <a href="/facts/Field_(computer_science)/jt622EDb">fields</a> separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a decrement or count. The tag specified one of three <a href="/facts/Index_register/pdhWVmHA">index registers</a>. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement".<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>: p. 8 The 704 hardware had special instructions for accessing the address and decrement fields in a word.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>: p. 26 As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>: Intro. </p><p>Thus, "CAR" is "Contents of the Address <i>part</i> of the Register". The term "register" in this context refers to "memory location".<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>Precursors<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> to Lisp included functions: </p> <ul><li>car ("contents of the address part of register number"),</li> <li>cdr ("contents of the decrement part of register number"),</li> <li>cpr ("contents of the prefix part of register number"), and</li> <li>ctr ("contents of the tag part of register number"),</li></ul> <p>each of which took a machine address as an argument, loaded the corresponding word from memory, and extracted the appropriate bits. </p> <h3>704 macros</h3> <p>The 704 <a href="/facts/Assembly_language/7XuV0cla">assembler</a> <a href="/facts/Macro_(programming)/7abAsm1o">macro</a> for car was:<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p> LXD JLOC 4 # C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C CLA 0,4 # C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list PAX 0,4 # C( Address of AC ) → C( C ) # Loads the Address of AC into Index Register C PXD 0,4 # C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC <p>The 704 assembler macro for cdr was:<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> </p> LXD JLOC 4 # C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C CLA 0,4 # C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list PDX 0,4 # C( Decrement of AC ) → C( C ) # Loads the Decrement of AC into Index Register C PXD 0,4 # C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC <p>A machine word could be reassembled by <i>cons</i>, which took four arguments (<i>a</i>,<i>d</i>,<i>p</i>,<i>t</i>). </p><p>The prefix and tag parts were dropped in the early stages of Lisp's design, leaving CAR, CDR, and a two-argument CONS.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h3>Compositions</h3> <p><a href="/facts/Function_composition/r5Pvnmth">Compositions</a> of car and cdr can be given short and more or less pronounceable names of the same form. In Lisp, (cadr '(1 2 3)) is the equivalent of (car (cdr '(1 2 3))); its value is 2. Similarly, (caar '((1 2) (3 4))) (pronounced /ˈkeɪɑːr/) is the same as (car (car '((1 2) (3 4)))); its value is 1. Most Lisps, for example <a href="/facts/Common_Lisp/mq1pRbSF">Common Lisp</a> and <a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a>, systematically define all variations of two to four compositions of car and cdr. </p> <h2 id="other-computer-languages">Other computer languages</h2> <p>Many languages (particularly <a href="/facts/Functional_programming/cdxqPEIM">functional</a> languages and languages influenced by the functional <a href="/facts/Programming_paradigm/7LwgRpB3">paradigm</a>) use a <a href="/facts/Linked_list/Ik4JTgJW">singly linked list</a> as a basic data structure, and provide primitives or functions similar to car and cdr. These are named variously first and rest, head and tail, etc. In Lisp, however, the cons cell is not used only to build linked lists but also to build pair and nested pair structures, i.e. the cdr of a cons cell need not be a list. In this case, most other languages provide different primitives as they typically distinguish pair structures from list structures either typefully or semantically. Particularly in typed languages, lists, pairs, and trees will all have different accessor functions with different type signatures: in <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a>, for example, car and cdr become fst and snd when dealing with a pair type. Exact analogues of car and cdr are thus rare in other languages. <a href="/facts/Clojure/3JRNxKXx">Clojure</a> uses first instead of car and next or rest instead of cdr. <a href="/facts/Logo_(programming_language)/Wh4sdwAh">Logo</a>, on the other hand, uses first instead of car and butfirst instead of cdr. </p> Notes <ul><li><a href="/facts/Steve_Russell_(computer_scientist)/gVNlFx9j">Russell, Steve</a>. <a href="ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf">"Writing and Debugging Programs"</a> (PDF). RLE and MIT Computation Center. <i>CSAIL Publications and Digital Archive</i> (Memo). <a href="/facts/AI_Memo/xDgy0VQl">AI Memo</a>, no. 6. <a href="/facts/Cambridge%2c_Massachusetts/k9UMIJ7U">Cambridge</a>, Massachusetts. <a href="/facts/OCLC_(identifier)/Yqad8waq">OCLC</a> <a href="https://search.worldcat.org/oclc/35415961">35415961</a>. Retrieved July 20, 2017.[<i>dead ftp link</i>] (To view documents see Help:FTP)</li> <li>Faase, Frans (2006-01-10). <a href="http://www.iwriteiam.nl/HaCAR_CDR.html">"The origin of CAR and CDR in LISP"</a>.</li> <li><a href="/facts/Paul_Graham_(computer_programmer)/Wu4kYTGr">Graham, Paul</a> (1996). <a href="https://archive.org/details/ansicommonlisp00grah"><i>ANSI Common Lisp</i></a>. Prentice Hall. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-13-370875-2.</li> <li>Barski, Conrad (2010). <i>Land of Lisp : learn to program in Lisp, one game at a time!</i>. San Francisco, CA: No Starch Press, Inc. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-59327-281-4.</li> <li><a href="/facts/John_McCarthy_(computer_scientist)/ajKU4SdD">McCarthy, John</a> (1960). <a href="http://jmc.stanford.edu/articles/recursive/recursive.pdf">"Recursive functions of symbolic expressions and their computation by machine, Part I."</a> (PDF). <i>Communications of the ACM</i>. 3 (4). ACM New York, NY, USA: 184–195. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F367177.367199">10.1145/367177.367199</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1489409">1489409</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>See, for example, Mitchell, John C. (2003), Concepts in Programming Languages, Cambridge University Press, pp. 28–29, ISBN 9781139433488, Section 3.4, Innovations in the Design of Lisp. The reference identifies the IBM 704 and correctly explains the address and decrement part of a cons cell, but then it omits the "part of" in McCarthy's explanation. <a href="9781139433488" target="_blank">9781139433488</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>704 - electronic data-processing machine http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf <a href="http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf" target="_blank">http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>704 - electronic data-processing machine http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf <a href="http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf" target="_blank">http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>McCarthy, John (1979-02-12). "History of Lisp". <a href="/wiki/John_McCarthy_(computer_scientist)" target="_blank">/wiki/John_McCarthy_(computer_scientist)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>McCarthy (1960, pp. 26–27) discusses registers on the free list and in garbage collection. - McCarthy, John (1960). "Recursive functions of symbolic expressions and their computation by machine, Part I." (PDF). Communications of the ACM. 3 (4). ACM New York, NY, USA: 184–195. doi:10.1145/367177.367199. S2CID 1489409. <a href="http://jmc.stanford.edu/articles/recursive/recursive.pdf" target="_blank">http://jmc.stanford.edu/articles/recursive/recursive.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985), LISP 1.5 Programmer's Manual (second ed.), Cambridge, Massachusetts: MIT Press, ISBN 978-0-262-13011-0, page 36, describes cons cells as words with 15-bit "address" and "decrement" fields. <a href="978-0-262-13011-0" target="_blank">978-0-262-13011-0</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>A Fortran-Compiled List-Processing Language <a href="http://dl.acm.org/citation.cfm?id=321022" target="_blank">http://dl.acm.org/citation.cfm?id=321022</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>A Fortran-Compiled List-Processing Language; HTML transcription <a href="http://www.informatimago.com/articles/flpl/flpl.html" target="_blank">http://www.informatimago.com/articles/flpl/flpl.html</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Portions from NILS' LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html <a href="https://archive.today/20041021220505/http://t3x.dyndns.org/LISP/QA/carcdr.html" target="_blank">https://archive.today/20041021220505/http://t3x.dyndns.org/LISP/QA/carcdr.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>MIT AI Lab Memo 6 https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf <a href="https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf" target="_blank">https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>CODING for the MIT-IBM 704 COMPUTER http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf <a href="http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf" target="_blank">http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Portions from NILS' LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html <a href="https://archive.today/20041021220505/http://t3x.dyndns.org/LISP/QA/carcdr.html" target="_blank">https://archive.today/20041021220505/http://t3x.dyndns.org/LISP/QA/carcdr.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>MIT AI Lab Memo 6 https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf <a href="https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf" target="_blank">https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>CODING for the MIT-IBM 704 COMPUTER http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf <a href="http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf" target="_blank">http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>McCarthy, John (1979-02-12). "History of Lisp". <a href="/wiki/John_McCarthy_(computer_scientist)" target="_blank">/wiki/John_McCarthy_(computer_scientist)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> </ol>