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.