Car and cdr

From Free net encyclopedia

Template:Lowercase

"CADR" redirects here. This was also the name of the second version of MIT's Lisp machine

For other meanings, see CAR and CDR.

Introduced in the Lisp programming language, car and cdr (IPA [kədər] or [kudə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)) 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 704 assembler macro for cdr was

LXD JLOC,4

CLA 0,4

PDX 0,4

PXD 0,4Template:Ref

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 allow up to eight repetitions of the a and d in these composed forms, making certain kinds of pure list manipulation considerably easier, as with improbably complex forms like (caddaaaddr ...), which evaluates to the same thing as, but is much easier to type and read than, (car (cdr (cdr (car (car (car (cdr (cdr ...)))))))).

Use in conversation

cdr is sometimes used colloquially in conversation (notably at MIT), usually in the expression "cdr down". For example:

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.

References

• Russel, S. (undated, c. late 1950's) Writing and Debugging Programs. MIT Artificial Intelligence Laboratory Memo 6.
• {{cite book

   | last = Graham
   | first = Paul
   | authorlink = Paul Graham
   | title = ANSI Common Lisp
   | publisher = Prentice Hall
   | year = 1996
   | id = ISBN 0133708756 }}

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