We shall introduce some elementary functions of S-expressions. To distinguish the functions from the S-expressions themselves, we shall write function names in lower case letters, since atomic symbols consist of only upper case letters. Furthermore, the arguments of functions will be grouped in square brackets rather than parentheses As a separator or punctuation mark we shall use the semicolon.
The first function that we shall introduce is the function cons. It has two arguments and is in fact the function that is used to build S-expressions from smaller S-expressions.
Examples
cons[A;B]=(A . B)
cons[(A . B);C]=((A . B) . C)
cons[cons[A;B];C]=((A . B) . C)
The last example is an instance of composition of functions. It is possible to build any S-expression from its atomic components by compositions of the function cons.
The next pair of functions do ]ust the opposite of cons. They produce the subexpressions of a given expression.
The function car has one argument. Its value is the first part of its composite argument, car of an atomic symbol is undefined.
Examples
car[(A . B)]=A
car[(A . (Bl . B2))]=A
car[((Al . A2) . B)]=(A1 . A2)
car[A] is undefined
The function cdr has one argument. Its value is the second part of its composite argument. cdr is also undefined if its argument is atomic.
Examples
cdr[(A . B)]=B
cdr[(A . (B1 . B2))]=(B1 . B2)
cdr[((A1 . A2) . B)]=B
cdr[A] is undefined
car[cdr[(A . (B1 . B2))]]=B1
car[cdr[(A . B)]] is undefined
car[cons[A;B]]=A
Given any S-expression, it is possible to produce any subexpression of it by a suitable composition of car's and cdr's. If x and y represent any two S-expressions, the following identities are true:
car[cons[x;y]]=x
cdr[cons[x;y]]=y
The following identity is also true for any S-expression x such that x is composite (non-atomic):
cons[car[x];cdr[x]]=x
The symbols x and y used in these identities are called variables. In LISP, variables are used to represent S-expressions. In choosing names for variables and functions, we shall use the same type of character strings that are used in forming atomic symbols, except that we shall use lower case letters.
A function whose value is either true or false is called a predicate. In LISP, the values true and false are represented by the atomic symbols T and F, respectively. A LISP predicate is therefore a function whose value is either T or F.
The predicate eq is a test for equality on atomic symbols. It is undefined for non-atomic arguments.
Examples
eq[A;A]=T
eq[A;B]=F
eq[A,(A . B)] is undefined
eq[(A . B);(A . B)] is undefined
The predicate atom is true if its argument is an atomic symbol, and false if its argument is composite.
Examples
atom[EXTRALONGSTRINGOFLETTERS]=T
atom[(U . V)]=F
atom[car[(U . V)]]=T