CAR and CDR

Introduced in the Lisp programming language, car (pronounced /ˈkɑr/, just like the English word "car") and cdr (/ˈkʌdər/ or /ˈkʊdər/) are primitive operations upon linked lists composed of cons cells. 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 x, and (cdr (cons x y)) evaluates to y.

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.

Etymology

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 15 bits each and a "prefix part" and "tag part" of three bits each.

Precursors to Lisp included functions:

• 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.

The 704 assembler macro for cdr was

LXD JLOC,4
CLA 0,4
PDX 0,4
PXD 0,4[1]

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.^[2]

Continued acceptance

The alternate names first and rest, which date back at least to 1959,^[3] are sometimes preferred to car and cdr. However, car and 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 (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.

Other languages

Some other languages also use the singly-linked list as a basic data structure.

• ML usually uses pattern matching de-construct lists, but also provides functions "List.hd" and "List.tl".

• Haskell usually uses pattern matching de-construct lists, but also provides functions "head" and "tail".

• Clojure has functions "first" and "rest," which are equivalent to car and cdr.

• Erlang uses pattern matching, where the pattern "[H|T] = List" extracts the head into "H" and tail into "T" of the list "List"

• XQuery has the function subsequence which has three arguments, the sequence, the starting item count and optionally the number of items to be returned. So CAR is subsequence($in, 1, 1) and CDR is subsequence($in, 2). When the second argument is omitted the remainder of the sequence is returned.

References

1. ^ Portions from NILS' LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html
2. ^ McCarthy, John (1979-02-12). "History of Lisp". http://www-formal.stanford.edu/jmc/history/lisp/lisp.html. 
3. ^ McCarthy, J., Erratum to Memo 8, Recursive Functions of Symbolic Expressions and Their Computation By Machine, dated March 13, 1959, retrieved September 19, 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". http://www.iwriteiam.nl/HaCAR_CDR.html. 
• Graham, Paul (1996). ANSI Common Lisp. Prentice Hall. ISBN 0-13-370875-6.