Introduced in the Lisp programming language, car (IPA ['kar], just like the English word "car") and cdr (IPA ['kʌ dər] or ['ku 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. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... The International Phonetic Alphabet (IPA) is a system of phonetic notation devised by linguists to accurately and uniquely represent each of the wide variety of sounds (phones or phonemes) used in spoken human language. ... The International Phonetic Alphabet (IPA) is a system of phonetic notation devised by linguists to accurately and uniquely represent each of the wide variety of sounds (phones or phonemes) used in spoken human language. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...

Thus, the expression (car (cons x y)) always evaluates to x, and (cdr (cons x y)) always 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.

Origin of the names car and cdr

Lisp was originally designed for the IBM 704 computer, in the late 1950s. On the 704, a cons cell was represented by a single 36-bit machine word containing two parts: an address part and a decrement part, each 15 bits long. The assembly functions used to extract either part of a machine word were called car (Contents of Address of Register) and cdr (Contents of Decrement of Register). The IBM 704, the first mass-produced computer with floating point arithmetic hardware, was introduced by IBM in April, 1956. ...

The 704 assembler macro for cdr was

LXD JLOC,4

CLA 0,4

PDX 0,4

PXD 0,4^[1]

Nowadays some people mostly use first and rest when programming Lisp due to their greater clarity. However, the words car and cdr have an advantage over these synonyms: they can be composed. 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. While it's not clear that a complex composed form such as (cadadr ...) is any easier for the untrained eye to parse than the spelled out equivalent (car (cdr (car (cdr ...)))) these composed forms can be convenient in certain idiomatic uses such as taking apart lists representing code. For instance given a lambda expression like the following: Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ... Scheme is a functional programming language and a dialect of Lisp. ... In computer science, the lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...

 (lambda (a b) (one-thing) (another-thing)) 

an experienced Lisper would read:

 (let ((p1 (caadr form)) (p2 (cadadr form)) (body (cddr form)) ...) 

as extracting the first and second parameters and then the list containing the body of the lambda expression. However this kind of "list destructuring" is common enough, especially when writing macros, that modern Lisps such as Common Lisp provide facilities for doing it directly. That code would be written in Common Lisp using the destructuring-bind macro like this:

 (destructuring-bind ((p1 p2) &body body) form ...) 

Use in conversation

cdr is sometimes used colloquially in conversation (notably at MIT), usually in the expression "cdr down". For example: Mapúa Institute of Technology (MIT, MapúaTech or simply Mapúa) is a private, non-sectarian, Filipino tertiary institute located in Intramuros, Manila. ...

Can you cdr down that list of restaurants to see if any are open at 3AM?

Note that this usage implies looking at each element in turn, which would actually be done by caring the result of repeated cdrs. See also cons. CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...

References

1. ^ Portions from NILS' LISP PAGES- http://t3x.dyndns.org/LISP/QA/carcdr.html

• Russel, S. (undated, c. late 1950's) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
• Graham, Paul (1996). ANSI Common Lisp. Prentice Hall. ISBN 0133708756.