1.3 List Notation

The S-expressions that have been used heretofore have been written in dot notation. It is usually more convenient to be able to write lists of expressions of indefinite length, such as (A B C D E).

Any S-expression can be expressedin terms of the dot notation. However, LISP has an alternative form of S-expression called the list notation. The list $(m_{1}  m_{2}  \ldots   m_{n})$ can be defined in terms of dot notation. It is identical to $(m_{1}  .   (m_{2}  (\ldots   (m_{n}  .  NIL)\ldots )))$.

The atomic symbol NIL serves as a terminator for lists. The null list ( ) is identical to NIL. Lists may have sublists. The dot notation and the list notation may be used in the same S-expression.

Historically, the separator for elements of lists was the comma (,), however, the blank is now generally used. The two are entirely equivalent in LISP. (A, B, C) is identical to (A B C).

Examples

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

It is important to become familiar with the results of elementary functions on S-expressions written in list notation. These can always be determined by translating into dot notation.

Examples

        car[(A B C)]=A 
        cdr[(A B C)]=(B C) 
        cons[A; (B C)]=(A B C) 
        car[((A B) C)]=(A B) 
        cdr[(A)]=NIL 
        car[cdr[(A B C)]]=B

It is convenient to abbreviate multiple car's and cdr's. This is done by forming function names that begin with c, end with r, and have several a's and d's between them.

Examples

        cadr[(A B C)]=car[cdr[(A B C)]=B 
        caddr[(A B C)]=C 
        cadadr[(A (B C) D)]=C

The last a or d in the name actually signifies the first operation in order to be performed, since it is nearest to the argument.