Up | Next | Tail |

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 ||

-----------------

|| 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 ||

----------------- -----------------

|| / | \ ||

----/-------\----

/ \

----------------- -----------------

|| 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

- NIL
- 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)

(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.

- Set a pointer Q to the beginning of the dotted pair structure and write a left parenthesis.
- Write the list notation for the data structure pointed to by the car of Q and reset Q to the cdr of Q.
- 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 |