Up Next Tail

### 5.1 Introduction to Lists and Pairs

The pair is a fundamental PSL data type, and is one of the major attractions of LISP programming. A pair consists of a two-item structure. In PSL the first element is called the car and the second the cdr; in other LISPs, the physical relationship of the parts may be different. An illustration of the tree structure is given below as a box diagram; the car and the cdr are each represented as a portion of the box.

-----------------
|| Car  | Cdr  ||
-----------------

As an example, a tree written as ((A . B) . (C . D)) in dot-notation is drawn below as a box diagram.

-----------------
||   /  |  \   ||
----/-------\----
/         \
-----------------       -----------------
||  A   |   B  ||       ||  C   |   D  ||
-----------------       -----------------

The box diagrams are tedious to draw, so dot-notation is normally used. Note that a space is left on each side of the . to ensure that pairs are not confused with floats.

A list is a special case of a dotted pair structure. A list is either

1. NIL
2. A dotted pair whose car is an expression and whose cdr is a list.

List notation in general is a lot easier to read than the equivalent dotted pair notation.

(A . NIL)               = (A)
(A . B)                 = (A . B)
(NIL . NIL)             = (NIL)
(A . (B . NIL))         = (A B)
((A . NIL) . NIL)       = ((A))
((A . NIL) . (B . NIL)) = ((A) B)
(A . (B . C))           = (A B . C)

The following is an algorithm for writing a dotted pair structure in list notation.

1. Set a pointer Q to the beginning of the dotted pair structure and write a left parenthesis.
2. Write the list notation for the data structure pointed to by the car of Q and reset Q to the cdr of Q.
3. If Q is now the null pointer, then write a right parenthesis; otherwise, write a space, and if Q is an atom, write a period, a space, Q’s name, and a right parenthesis; otherwise write a space and go to step 2.

 Up Next Front