A pair (sometimes called a dotted pair) is a record structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr. The car and cdr fields are assigned by the procedures set-car! and set-cdr!.

Pairs are used primarily to represent lists. A list can
be defined recursively as either the empty list or a pair whose
cdr is a list. More precisely, the set of lists is defined as the smallest
set `X` such that

- The empty list is in
`X`. - If
`list`is in`X`, then any pair whose cdr field contains`list`is also in`X`.

The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two-element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.

The empty list is a special object of its own type (it is not a pair); it has no elements and its length is zero.

Note:The above definitions imply that all lists have finite length and are terminated by the empty list.

The most general notation (external representation) for Scheme pairs is
the “dotted” notation (`c1` . `c2`) where
`c1` is the value of the car field and `c2` is the value of the
cdr field. For example (4 . 5) is a pair whose car is 4 and whose
cdr is 5. Note that (4 . 5) is the external representation of a
pair, not an expression that evaluates to a pair.

A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces. The
empty list is written `()` . For example,

(a b c d e)

and

(a . (b . (c . (d . (e . ())))))

are equivalent notations for a list of symbols.

A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:

(a b c . d)

is equivalent to

(a . (b . (c . d)))

Whether a given pair is a list depends upon what is stored in the cdr
field. When the `set-cdr!`

procedure is used, an object can be a
list one moment and not the next:

(define x (list 'a 'b 'c)) (define y x) y ==> (a b c) (list? y) ==> #t (set-cdr! x 4) ==>unspecifiedx ==> (a . 4) (eqv? x y) ==> #t y ==> (a . 4) (list? y) ==> #f (set-cdr! x x) ==>unspecified(list? x) ==> #f

Within literal expressions and representations of objects read by the
`read`

procedure, the forms `'`<datum>,
```<datum>, `,`<datum>, and
`,@`<datum> denote two-element lists whose first elements are
the symbols `quote`

, `quasiquote`

, `unquote`

, and
`unquote-splicing`

, respectively. The second element in each case
is <datum>. This convention is supported so that arbitrary Scheme
programs may be represented as lists.
That is, according to Scheme's grammar, every
<expression> is also a <datum> (see section see External representation).
Among other things, this permits the use of the read procedure to
parse Scheme programs. See section External representations.

— procedure: **pair?**` obj`

Pair? returns

#tifobjis a pair, and otherwise returns#f.(pair? '(a . b)) ==> #t (pair? '(a b c)) ==> #t (pair? '()) ==> #f (pair? '#(a b)) ==> #f

— procedure: **cons**` obj1 obj2`

Returns a newly allocated pair whose car is

obj1and whose cdr isobj2. The pair is guaranteed to be different (in the sense of eqv?) from every existing object.(cons 'a '()) ==> (a) (cons '(a) '(b c d)) ==> ((a) b c d) (cons "a" '(b c)) ==> ("a" b c) (cons 'a 3) ==> (a . 3) (cons '(a b) 'c) ==> ((a b) . c)

— procedure: **car**` pair`

Returns the contents of the car field of

pair. Note that it is an error to take the car of the empty list.(car '(a b c)) ==> a (car '((a) b c d)) ==> (a) (car '(1 . 2)) ==> 1 (car '()) ==>error

— procedure: **cdr**` pair`

Returns the contents of the cdr field of

pair. Note that it is an error to take the cdr of the empty list.(cdr '((a) b c d)) ==> (b c d) (cdr '(1 . 2)) ==> 2 (cdr '()) ==>error

— procedure: **set-car!**` pair obj`

Stores

objin the car field ofpair. The value returned by set-car! is unspecified.(define (f) (list 'not-a-constant-list)) (define (g) '(constant-list)) (set-car! (f) 3) ==>unspecified(set-car! (g) 3) ==>error

— procedure: **set-cdr!**` pair obj`

Stores

objin the cdr field ofpair. The value returned by set-cdr! is unspecified.

— library procedure: **caar**` pair`

— library procedure:**cadr**` pair`

— :** ...**

— library procedure:**cdddar**` pair`

— library procedure:**cddddr**` pair`

— library procedure:

— :

— library procedure:

— library procedure:

These procedures are compositions of car and cdr, where for example caddr could be defined by

(define caddr (lambda (x) (car (cdr (cdr x))))).Arbitrary compositions, up to four deep, are provided. There are twenty-eight of these procedures in all.

— library procedure: **list?**` obj`

Returns

#tifobjis a list, otherwise returns#f. By definition, all lists have finite length and are terminated by the empty list.(list? '(a b c)) ==> #t (list? '()) ==> #t (list? '(a . b)) ==> #f (let ((x (list 'a))) (set-cdr! x x) (list? x)) ==> #f

— library procedure: **list**` obj ...`

Returns a newly allocated list of its arguments.

(list 'a (+ 3 4) 'c) ==> (a 7 c) (list) ==> ()

— library procedure: **length**` list`

Returns the length of

list.(length '(a b c)) ==> 3 (length '(a (b) (c d e))) ==> 3 (length '()) ==> 0

— library procedure: **append**` list ...`

Returns a list consisting of the elements of the first

listfollowed by the elements of the otherlists.(append '(x) '(y)) ==> (x y) (append '(a) '(b c d)) ==> (a b c d) (append '(a (b)) '((c))) ==> (a (b) (c))The resulting list is always newly allocated, except that it shares structure with the last

listargument. The last argument may actually be any object; an improper list results if the last argument is not a proper list.(append '(a b) '(c . d)) ==> (a b c . d) (append '() 'a) ==> a

— library procedure: **reverse**` list`

Returns a newly allocated list consisting of the elements of

listin reverse order.(reverse '(a b c)) ==> (c b a) (reverse '(a (b c) d (e (f)))) ==> ((e (f)) d (b c) a)

— library procedure: **list-tail**` list k`

Returns the sublist of

listobtained by omitting the firstkelements. It is an error iflisthas fewer thankelements. List-tail could be defined by(define list-tail (lambda (x k) (if (zero? k) x (list-tail (cdr x) (- k 1)))))

— library procedure: **list-ref**` list k`

Returns the

kth element oflist. (This is the same as the car of(list-taillistk).) It is an error iflisthas fewer thankelements.(list-ref '(a b c d) 2) ==> c (list-ref '(a b c d) (inexact->exact (round 1.8))) ==> c

— library procedure: **memq**` obj list`

— library procedure:**memv**` obj list`

— library procedure:**member**` obj list`

— library procedure:

— library procedure:

These procedures return the first sublist of

listwhose car isobj, where the sublists oflistare the non-empty lists returned by(list-taillistk)forkless than the length oflist. Ifobjdoes not occur inlist, then#f(not the empty list) is returned. Memq uses eq? to compareobjwith the elements oflist, while memv uses eqv? and member uses equal?.(memq 'a '(a b c)) ==> (a b c) (memq 'b '(a b c)) ==> (b c) (memq 'a '(b c d)) ==> #f (memq (list 'a) '(b (a) c)) ==> #f (member (list 'a) '(b (a) c)) ==> ((a) c) (memq 101 '(100 101 102)) ==>unspecified(memv 101 '(100 101 102)) ==> (101 102)

— library procedure: **assq**` obj alist`

— library procedure:**assv**` obj alist`

— library procedure:**assoc**` obj alist`

— library procedure:

— library procedure:

Alist(for “association list”) must be a list of pairs. These procedures find the first pair inalistwhose car field isobj, and returns that pair. If no pair inalisthasobjas its car, then#f(not the empty list) is returned. Assq uses eq? to compareobjwith the car fields of the pairs inalist, while assv uses eqv? and assoc uses equal?.(define e '((a 1) (b 2) (c 3))) (assq 'a e) ==> (a 1) (assq 'b e) ==> (b 2) (assq 'd e) ==> #f (assq (list 'a) '(((a)) ((b)) ((c)))) ==> #f (assoc (list 'a) '(((a)) ((b)) ((c)))) ==> ((a)) (assq 5 '((2 3) (5 7) (11 13))) ==>unspecified(assv 5 '((2 3) (5 7) (11 13))) ==> (5 7)Rationale:Although they are ordinarily used as predicates, memq, memv, member, assq, assv, and assoc do not have question marks in their names because they return useful values rather than just#tor#f.