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 (obj₁.obj₂). 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):

Functions:

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

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:

• in a pair with second element nil the dot and the nil are omitted: (A.nil) = (A).
• for a pair with another pair as second element one bracket pair and the dot are omitted: (B.(A)) = (B A), (C.(B A)) = (C B A).

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)

or with omitting the final nil

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)² would be represented by lists as

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

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.

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

Remarks:

• All of the above functions are non destructive: an input list remains as it has been before - the value of each access function is a reference to the corresponding part of the structure.
• The access functions can operate only if the desired elements are really there; e.g. if nth with 4 is applied to a 3 element list produces an error, and car or cdr applied to any symbol or number (including nil) will fail.
• Nested calls of car and cdr can be abbreviated by combining the a’s and d’s between c and r up to four inner a/d letters. E.g. cadr(u) = car(cdr(u)) - this is the direct access to the second element, caddr returns the third element and cadddr the fourth element.
• Although the functions first, second, third, rest known from algebraic mode operate in some REDUCE implementations in symbolic mode as synonyms of car, cadr, caddr, cdr, they should not be used here as this is the case in all REDUCE versions.
• The functions member and memq not only test the membership: if a is member of the list l, member (or memq) returns the (first) pair which contains a as its car. E.g. memq(′b,′(a b c)) returns (b c). This can be used either if you want to replace this item in the list, or if you want to process the part after the search item. The function memq looks for a member of the list which is eq to the object, while member uses equal as test (see discussion of equality below). If applicable, memq is substantially faster than member.
• Delete produces a copy of the top level pair sequence leaving out the first occurrence of the search item: the original list is not changed, and a possible second occurence of the search item in the list is not removed. delete(′a,′(0aba)) will result in (0ba) where the part (ba) is the original tail of the input list while the pairs in front of the original first a are new.

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

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.