CAR and CDR
In computer programming, car i// and cdr (i// or i//) are primitive operations on cons cells (or "non-atomic S-expressions") introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.
Thus, the expression
(car (cons x y)) evaluates to
(cdr (cons x y)) evaluates to
When cons cells are used to implement singly linked lists (rather than trees and other more complicated 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.
Lisp was originally implemented on the IBM 704 computer, in the late 1950s. The 704 hardware had special support for splitting a 36-bit machine word into four parts: an "address part" and "decrement part" of fifteen bits each, and a "prefix part" and "tag part" of three bits each.
- car (short for "Contents of the Address part of Register number"),
- cdr ("Contents of the Decrement part of Register number"),
- cpr ("Contents of the Prefix part of Register number"), and
- ctr ("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.
LXD JLOC,4 CLA 0,4 PDX 0,4 PXD 0,4
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.
The alternative names
rest, which date back at least to 1959, are sometimes preferred to
cdr have the advantage that short compositions of the functions 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. This is because
2 is the first item of the rest of
(1 2 3). Similarly,
(caar '((1 2) (3 4))) is the same as
(car (car '((1 2) (3 4)))); its value is
1. Most Lisps set a limit on the number of composed forms they support; Common Lisp and Scheme both provide forms with up to four repetitions of the a and d. However, further compositions can easily be defined (if not used) by the user.
Other computer languages
Many languages (particularly functional languages and languages influenced by the functional paradigm) use a singly linked list as a basic data structure, and provide primitives or functions similar to
cdr. These are named variously
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 Haskell, for example,
snd when dealing with a pair type. Exact analogues of
cdr are thus rare in other languages.
- A Fortran-Compiled List-Processing Language
- A Fortran-Compiled List-Processing Language; HTML transcription
- Portions from NILS' LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html
- McCarthy, John (1979-02-12). "History of Lisp".
- McCarthy, J., Erratum to Memo 8, Recursive Functions of Symbolic Expressions and Their Computation By Machine, dated 13 March 1959, retrieved 19 September 2008.
- Russel, S. (undated, c. late 1950s) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
- Faase, Frans (2006-01-10). "The origin of CAR and CDR in LISP".
- Graham, Paul (1996). ANSI Common Lisp. Prentice Hall. ISBN 0-13-370875-6.
- Barski, Conrad (2010). Land of Lisp : learn to program in Lisp, one game at a time!. San Francisco, CA: No Starch Press, Inc. ISBN 978-1-59327-281-4.