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.

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

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.

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.