Page:AIM-453.djvu/7

From Wikisource
Jump to navigation Jump to search
This page has been proofread, but needs to be validated.
Steele and Sussman
5
The Art of the Interpreter

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