Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
CAR and CDR
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Programming language construct in Lisp}} {{other uses|CAR (disambiguation)|CDR (disambiguation)|CADR (disambiguation)}} In [[computer programming]], '''CAR''' (<code>car</code>) {{IPAc-en|k|Ιr|audio=en-us-car.ogg}} and '''CDR''' (<code>cdr</code>) ({{IPAc-en|Λ|k|Κ|d|Ιr|audio=US-Lisp-CDR2.ogg}} or {{IPAc-en|Λ|k|Κ|d|Ιr|audio=US-Lisp-CDR.ogg}}) are primitive operations on [[cons]] cells (or "non-atomic [[S-expression]]s") introduced in the [[Lisp (programming language)|Lisp programming language]]. A cons cell is composed of two [[Pointer (computer programming)|pointer]]s; the ''car'' operation extracts the first pointer, and the ''cdr'' operation extracts the second. Thus, the expression <code>(car (cons ''x'' ''y''))</code> evaluates to <code>''x''</code>, and <code>(cdr (cons ''x'' ''y''))</code> evaluates to <code>''y''</code>. When cons cells are used to implement [[singly linked list]]s (rather than [[tree (data structure)|trees]] and other more complicated [[data structure|structures]]), the ''car'' operation returns the ''first'' element of the list, while ''cdr'' returns the ''rest'' of the list. For this reason, the operations are sometimes given the names ''first'' and ''rest'' or ''head'' and ''tail''. == Etymology == Lisp was originally implemented on the [[IBM 704]] computer, in the late 1950s. The popular explanation that ''CAR'' and ''CDR'' stand for "Contents of the Address Register" and "Contents of the Decrement Register"<ref>See, for example, {{Citation |last=Mitchell |first=John C. |title=Concepts in Programming Languages |publisher=Cambridge University Press |year=2003 |isbn=9781139433488 |url=https://books.google.com/books?id=7Uh8XGfJbEIC&pg=PA29 |pages=28–29}}, 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.</ref> 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. The 704 and its successors have a [[36-bit]] [[word (computer architecture)|word]] length and a 15-bit [[address space]]. These computers had two [[instruction (computer science)|instruction]] formats, one of which, the Type A, had a short, 3-bit, [[operation code]] prefix and two 15-bit [[Field (computer science)|field]]s 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 [[index register]]s. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement".<ref name="edpm704">704 - electronic data-processing machine [http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/704/24-6661-2_704_Manual_1955.pdf]</ref>{{rp|p. 8}} The 704 hardware had special instructions for accessing the address and decrement fields in a word.<ref name="edpm704"/>{{rp|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.<ref name=mccarthy>{{cite web | last = McCarthy | first = John | author-link = John McCarthy (computer scientist) | date = 1979-02-12 | title = History of Lisp | url = http://www-formal.stanford.edu/jmc/history/lisp/lisp.html }}</ref>{{rp|Intro.}} Thus, "CAR" is "Contents of the Address ''part'' of the Register". The term "register" in this context refers to "memory location".<ref>{{harvtxt|McCarthy|1960|pp=26–27}} discusses registers on the free list and in garbage collection.</ref><ref>{{Citation |last1=McCarthy |first1=John |last2=Abrahams |first2=Paul W. |last3=Edwards |first3=Daniel J. |last4=Hart |first4=Timothy P. |last5=Levin |first5=Michael I. |title=LISP 1.5 Programmer's Manual |publisher=MIT Press |location=Cambridge, Massachusetts |year=1985 |edition=second |isbn=978-0-262-13011-0 |url=https://archive.org/details/lisp15programmer00john }}, page 36, describes cons cells as words with 15-bit "address" and "decrement" fields.</ref> Precursors<ref name="flpl">[http://dl.acm.org/citation.cfm?id=321022 A Fortran-Compiled List-Processing Language]</ref><ref name="flpltranscription">[http://www.informatimago.com/articles/flpl/flpl.html A Fortran-Compiled List-Processing Language; HTML transcription]</ref> to Lisp included functions: *<code>car</code> ("contents of the address part of register number"), *<code>cdr</code> ("contents of the decrement part of register number"), *<code>cpr</code> ("contents of the prefix part of register number"), and *<code>ctr</code> ("contents of the tag part of register number"), each of which took a machine address as an argument, loaded the corresponding word from memory, and extracted the appropriate bits. ===704 macros=== The 704 [[assembly language|assembler]] [[macro (programming)|macro]] for <code>car</code> was:<ref name="assm" /><ref name="acm" /><ref name="MIT704"/> <syntaxhighlight lang="asm"> 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 </syntaxhighlight> The 704 assembler macro for <code>cdr</code> was:<ref name="assm">Portions from NILS' LISP PAGES- [https://archive.today/20041021220505/http://t3x.dyndns.org/LISP/QA/carcdr.html http://t3x.dyndns.org/LISP/QA/carcdr.html]</ref><ref name="acm">MIT AI Lab Memo 6 [https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf https://web.archive.org/web/20170706114352/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf]</ref><ref name="MIT704">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 http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/computer_center/Coding_for_the_MIT-IBM_704_Computer_Oct57.pdf]</ref> <syntaxhighlight lang="asm"> 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 </syntaxhighlight> A machine word could be reassembled by ''cons'', which took four arguments (''a'',''d'',''p'',''t''). The prefix and tag parts were dropped in the early stages of Lisp's design, leaving CAR, CDR, and a two-argument CONS.<ref name=mccarthy /> ===Compositions=== [[Function composition|Compositions]] of <code>car</code> and <code>cdr</code> can be given short and more or less pronounceable names of the same form. In Lisp, <code>(cadr '(1 2 3))</code> is the equivalent of <code>(car (cdr '(1 2 3)))</code>; its value is <code>2</code>. Similarly, <code>(caar '((1 2) (3 4)))</code> (pronounced {{IPAc-en|Λ|k|eΙͺ|Ιr}}) is the same as <code>(car (car '((1 2) (3 4))))</code>; its value is <code>1</code>. Most Lisps, for example [[Common Lisp]] and [[Scheme (programming language)|Scheme]], systematically define all variations of two to four compositions of <code>car</code> and <code>cdr</code>. ==Other computer languages== Many languages (particularly [[Functional programming|functional]] languages and languages influenced by the functional [[Programming paradigm|paradigm]]) use a [[Linked list|singly linked list]] as a basic data structure, and provide primitives or functions similar to <code>car</code> and <code>cdr</code>. These are named variously <code>first</code> and <code>rest</code>, <code>head</code> and <code>tail</code>, 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 <code>cdr</code> 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 [[Haskell (programming language)|Haskell]], for example, <code>car</code> and <code>cdr</code> become <code>fst</code> and <code>snd</code> when dealing with a pair type. Exact analogues of <code>car</code> and <code>cdr</code> are thus rare in other languages. [[Clojure]] uses <code>first</code> instead of <code>car</code> and <code>next</code> or <code>rest</code> instead of <code>cdr</code>. [[Logo (programming language)|Logo]], on the other hand, uses <code>first</code> instead of <code>car</code> and <code>butfirst</code> instead of <code>cdr</code>. ==References== {{reflist}} ;Notes *{{Cite FTP |url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-006.pdf |url-status=dead |title=Writing and Debugging Programs |last=Russell |first=Steve |author-link=Steve Russell (computer scientist) |department=RLE and MIT Computation Center |series=[[AI Memo]], no. 6 |location=[[Cambridge, Massachusetts|Cambridge]], Massachusetts |type=Memo |oclc=35415961 |server=CSAIL Publications and Digital Archive |access-date=July 20, 2017}} * {{cite web | last = Faase | first = Frans | date = 2006-01-10 | title = The origin of CAR and CDR in LISP | url = http://www.iwriteiam.nl/HaCAR_CDR.html }} * {{cite book | last = Graham | first = Paul | author-link = Paul Graham (computer programmer) | title = ANSI Common Lisp | publisher = Prentice Hall | year = 1996 | isbn = 978-0-13-370875-2 | url = https://archive.org/details/ansicommonlisp00grah }} * {{cite book|last=Barski|first=Conrad|title=Land of Lisp : learn to program in Lisp, one game at a time! |year=2010|publisher=No Starch Press, Inc.|location=San Francisco, CA|isbn=978-1-59327-281-4}} * {{cite journal |last=McCarthy |first=John |author-link=John McCarthy (computer scientist)|title=Recursive functions of symbolic expressions and their computation by machine, Part I.|journal=Communications of the ACM|volume=3|issue=4|year=1960|pages=184β195|url=http://jmc.stanford.edu/articles/recursive/recursive.pdf|publisher=ACM New York, NY, USA|doi=10.1145/367177.367199|s2cid=1489409}} [[Category:Lisp (programming language)]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation
(
edit
)
Template:Cite FTP
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite web
(
edit
)
Template:Harvtxt
(
edit
)
Template:IPAc-en
(
edit
)
Template:Other uses
(
edit
)
Template:Reflist
(
edit
)
Template:Rp
(
edit
)
Template:Short description
(
edit
)