and separated by spaces. A list of the atoms "FOO", "43", and "BAR" would be written "(FOO 43 BAR)". Notice that the definition of a list is recursive. For example,
(DEFINE (SECOND X) (CAR (CDR X)))
is a list of three things: the atomic symbol DEFINE, a list of the two atomic symbols SECOND and X, and another list of two other things.
We can use S-expressions to represent algebraic expressions by using "Cambridge Polish" notation, essentially a parenthesized version of prefix Polish notation. Numeric constants are encoded as numeric atoms; variables are encoded as non-numeric atoms (which henceforth we will call atomic symbols); and procedure invocations are encoded as lists, where the first element of the list represents the procedure and the rest represent the arguments. For example, the algebraic expression "a*b+c*d" can be represented as "(+ (* a b) (* c d))". Notice that LISP does not need the usual precedence rules concerning whether multiplication or addition is performed first; the parentheses explicitly define the order. Also, all procedure invocations have a uniform syntax, no matter how many arguments are involved. Infix, superscript, and subscript notations are not used; thus the expression "Jp(x2+1)" would be written "(J p (+ (↑ x 2) 1))".
To encode a conditional expression
[p1 → e1; p2 → e2; ... ; pn → en]
(which means to evaluate the predicates pj in order until a true one is found, at which point the value of ej is taken to be the value of the conditional) we write the S-expression
(COND (p1 e1) (p2 e2) ... (pn en))
We can now encode sets of LISP recursion equations as S-expressions. For the equation
factorial[x] = [x=0 → 1; T → x*factorial[x-1]]
we write the S-expression
(DEFINE (FACTORIAL X)
(COND ((= X 0) 1)
(T (* X (FACTORIAL (- X 1))))))
(We could also have written
(DEFINE (FACTORIAL X) (COND ((=
X 0) 1) (T (* X (FACTORIAL (- X
1))))))
but we conventionally lay out S-expressions so that they are easy to read.)
