2.6 Boolean values

There are two special symbols named nil and t. nil is used at the same time for the empty list and the Boolean value “false” . Any value other than nil is considered as “true” in conditional statements. In order to facilitate programming, the symbol nil has the preassigned constant value nil such that a quote here is superfluous. And for the same reason the symbol t evaluates to itself - this symbol can be used if the Boolean value “true” is needed explicitly, e.g. as a return value. But please keep in mind that any non-nil value can play this role. In contrast to algebraic mode the number zero does not represent the Boolean value “false”.

2.6.1 Pairs, lists

The central structure of LISP is the pair. The external representation of a pair of two objects is (obj1.obj2). Here the infix dot is used as print symbol as well as infix constructor. It is often useful to use a double box for representing a pair graphically, e.g. for (10.20):

            | 10 | 20 |  


o1.o2(infix) construct pair (o1.o2)
cons(o1,o2)same as 01.02
pairp(q)true if q is a pair
car(q)extract the first object from a pair
cdr(q)extract the second object from a pair

The pair is a very general construct - since its objects themselves can be pairs, arbitrary trees and data structures can be built. E.g. ((a.b).(c.d))

            | *  | * |  
            /        \  
           /          \  
        .-------.    .-------.  
        | a | b |    | c | d |  
        ‘-------’    ‘-------’

On the other hand, structures with many members lead to a very complicated representation if printed using the above notation. Therefore the list concept has been introduced which allows one to use a special class of pair trees in a simplified form:

So the list is a linear sequence of pairs, where the cars contain the “data” items, while the cdrs contain the reference to the successors. The last successor is nil, which signals the end of the linear list. For the graphical representation of linear lists horizontally aligned double boxes are useful, e.g. for (C B A)

        .-------.    .-------.    .-------.  
        | c | *-+--->| b | *-+--->| a |nil|  
        ‘-------’    ‘-------’    ‘-------’

or with omitting the final nil

        .-------.    .-------.    .-------.  
        | c | *-+--->| b | *-+--->| a | / |  
        ‘-------’    ‘-------’    ‘-------’

The list notation is much simpler than the dot notation - unfortunately the dots cannot be avoided completely because pairs with id’s or numbers in the cdr part occur and they play an important role.

Lists can be nested; an example is the internal representation of algebraic forms (see below) which uses linear lists; e.g. (x + 1)2 would be represented by lists as

     (expt (plus x 1) 2)

Here the top level list has three elements expt, (plusx1) and 2 where the second element itself is a linear list of length 3.

        .-------.    .-------.    .-------.  
        |expt| *+--->| * | *-+--->| 2 | / |  
        ‘-------’    ‘-|-----’    ‘-------’  
                      .-------.    .-------.    .-------.  
                      |plus| *+--->| x | *-+--->| 1 | / |  
                      ‘-------’    ‘-------’    ‘-------’

In this graph the cars contain the symbols or numbers or they point to substructures (downwards) while the cdrs point to the successors (to the right) until the end is reached.

As mentioned already there can be mixtures of both forms if one cdr is not nil: (A(B.C)D.E) - here the second element of the list is a pair (A.B), the third element is D and there is no fourth element - the list ends with a non nil symbol.

        .-------.    .-------.    .-------.  
        | a | *-+--->| * | *-+--->| d | e |  
        ‘-------’    ‘-|-----’    ‘-------’  
                      | b | c |  

The empty list () is identical to the symbol nil. Note that the REDUCE algebraic forms are LISP lists where all lists are terminated by a nil.

Functions on lists:

{o1,o2,..on}construct list (o1 o2⋅⋅⋅on)
list(o1,o2,..on)same as {o1,o2,..on}
o1.l1(infix) put o1 in front of list l1
pairp(q)true if q is a pair (or a list)
atom(q)true if q is NOT a pair/list
null(q)true if q = nil (=empty list)
car(q)extract the first object from a list
cdr(q)extract the part of the list behind 1st element
nth(q,n)extract the n-th element from list q
length(q)count the number of elements of list q
reverse(q)reverse a list q
append(a,b)append b to the end of a copy of a
member(a,l)test if a is equal to one member of l
memq(a,l)test if a is identical one member of l
delete(a,l)delete a from list l


Examples: let u be a variable with value (A(B.C)NIL(D)). Then

car(u)= A
cdr(u)=((B.C) NIL (D))
length cdr(u)=3
cddr(u)=(nil (D))
null cddr(u)=nil
null caddr(u)=t
null cddddr(u)= t

All data which are not pairs (or lists) are classified as atoms: symbols, numbers, strings, vectors(see below) and, just as in real world, they are not very atomic – there are tools to crack them.