Car and cdr
Encyclopedia
car and cdr (ˈ or ˈ) are primitive operations on cons
cells (or "non-atomic S-expression
s") 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
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.
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:
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
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.
of the functions can be given short and more or less pronounceable names of the same form. In Lisp,
and Scheme both provide forms with up to four repetitions of the a and d.
as a basic data structure, and provide primitives or functions similar to
Cons
In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...
cells (or "non-atomic S-expression
S-expression
S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...
s") introduced in the Lisp programming language
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
. 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
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
(rather than trees
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
and other more complicated structures
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
), 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 704IBM 704
The IBM 704, the first mass-produced computer with floating point arithmetic hardware, was introduced by IBM in 1954. The 704 was significantly improved over the IBM 701 in terms of architecture as well as implementations which were not compatible with its predecessor.Changes from the 701 included...
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 wasLXD 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.
Continued acceptance
The alternate namesfirst and rest, which date back at least to 1959, are sometimes preferred to car and cdr. However, car and cdr have the advantage that short compositionsFunction composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
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 LispCommon Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
and Scheme both provide forms with up to four repetitions of the a and d.
Other computer languages
Many languages (particularly functional languages and languages influenced by the functional paradigm) use a singly linked listLinked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
as a basic data structure, and provide primitives or functions similar to
car and cdr. These are named variously first and rest, head and 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, car and cdr become fst and snd when dealing with a pair type. Exact analogs of car and cdr are thus rare in other languages.