CAR and CDR

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 popular explanation that CAR and CDR stand for "Contents of the Address Register" and "Contents of the Decrement Register" does not quite match the IBM 704 architecture; the IBM 704 does not have a programmer-accessible address register and the three address modification registers are called "index registers" by IBM.

The 704 and its successors have a 36-bit word length and a 15-bit address space. These computers had two instruction formats, one of which, the Type A, had a short, 3-bit, operation code prefix and two 15-bit fields separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a decrement or count. The tag specified one of three index registers. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement". The 704 hardware had special instructions for accessing the address and decrement fields in a word. As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.

Thus, "CAR" is "Contents of the Address part of the Register". The term "register" in this context refers to "memory location".

Precursors to Lisp included functions:

• car ("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.

704 macros

The 704 assembler macro for car was:

<span id="mwaw"></span><span class="nf" id="mwbA">LXD</span><span class="w" id="mwbQ"> </span><span class="no" id="mwbg">JLOC</span><span class="w" id="mwbw"> </span><span class="mi" id="mwcA">4</span><span class="w" id="mwcQ"> </span><span class="c1" id="mwcg"># C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C</span> <span class="nf" id="mwcw">CLA</span><span class="w" id="mwdA"> </span><span class="mi" id="mwdQ">0</span><span class="p" id="mwdg">,</span><span class="mi" id="mwdw">4</span><span class="w" id="mweA"> </span><span class="c1" id="mweQ"># C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list</span> <span class="nf" id="mweg">PAX</span><span class="w" id="mwew"> </span><span class="mi" id="mwfA">0</span><span class="p" id="mwfQ">,</span><span class="mi" id="mwfg">4</span><span class="w" id="mwfw"> </span><span class="c1" id="mwgA"># C( Address of AC ) → C( C ) # Loads the Address of AC into Index Register C</span> <span class="nf" id="mwgQ">PXD</span><span class="w" id="mwgg"> </span><span class="mi" id="mwgw">0</span><span class="p" id="mwhA">,</span><span class="mi" id="mwhQ">4</span><span class="w" id="mwhg"> </span><span class="c1" id="mwhw"># C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC</span>

The 704 assembler macro for cdr was:

<span id="mwkg"></span><span class="nf" id="mwkw">LXD</span><span class="w" id="mwlA"> </span><span class="no" id="mwlQ">JLOC</span><span class="w" id="mwlg"> </span><span class="mi" id="mwlw">4</span><span class="w" id="mwmA"> </span><span class="c1" id="mwmQ"># C( Decrement of JLOC ) → C( C ) # Loads the Decrement of location JLOC into Index Register C</span> <span class="nf" id="mwmg">CLA</span><span class="w" id="mwmw"> </span><span class="mi" id="mwnA">0</span><span class="p" id="mwnQ">,</span><span class="mi" id="mwng">4</span><span class="w" id="mwnw"> </span><span class="c1" id="mwoA"># C( 0 - C( C ) ) → C( AC ) # The AC register receives the start address of the list</span> <span class="nf" id="mwoQ">PDX</span><span class="w" id="mwog"> </span><span class="mi" id="mwow">0</span><span class="p" id="mwpA">,</span><span class="mi" id="mwpQ">4</span><span class="w" id="mwpg"> </span><span class="c1" id="mwpw"># C( Decrement of AC ) → C( C ) # Loads the Decrement of AC into Index Register C</span> <span class="nf" id="mwqA">PXD</span><span class="w" id="mwqQ"> </span><span class="mi" id="mwqg">0</span><span class="p" id="mwqw">,</span><span class="mi" id="mwrA">4</span><span class="w" id="mwrQ"> </span><span class="c1" id="mwrg"># C( C ) → C( Decrement of AC ) # Clears AC and loads Index Register C into the Decrement of AC</span>

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.

Compositions

Compositions of car and cdr 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. Similarly, (caar '((1 2) (3 4))) (pronounced ) is the same as (car (car '((1 2) (3 4)))); its value is 1. Most Lisps, for example Common Lisp and Scheme, systematically define all variations of two to four compositions of car and cdr.