19 1024x768

>(♦14 5)

19

>(♦1234)

10

>(•(♦34)7)

0

> (• (♦ 2 5) (• 7 (/ 217)))

28

>(■(♦23)5)

I

>(>(•56) (+45))

|

>(abc)

Error Jrwalkf function: a

Sewrnl of ihc cxamplcs abovc havc argumenis Iha! are thcmsclvcs lists. for exampfe (• (♦ 3 4) 7). This indicaics thc composilion of functions, in ihis casc "subtract 7 from the result of adding 3 to 4”. The word "rcsult'' is emphasized herc to indicatc that thc funclion • is not passed thc s*cxprcssion “(+ 3 4)" as an argument but rather thc rcsult of cwluaiing that cxprcssion.

In cvaluating a funclion. LISP lirst evaluatcs its arguments and then applics thc function indicatcd by thc lirst element ofthc c\prcssion to thc results of these evaluatioos. If thc arguments are themselvcs function cxprcssions. LISP applics Ihis rulc recursively to their cvaluation. Thus. LISP allows nested function calls of arbitrary depth. It is imponant to remember that. by dcfault. LISP cvuluutcs cvcrything. LISP uses thc convcntion that nunibcrs alway* evaluate to thcmsclvcs. If, for cxamplc. 5 is typed into thc LISP interpreter. LISP will respond with 5. Symbols. such as x. may have a valuc botatd u them. If u symbol is bound. the binding is retumed when the symbol is evaluatcd (one wy in which symbols becomc bound is in a function cali: sec Section 15.1.2). If a symbol is unbound. it is an error to ewluatc that symbol.

For wampie, in cwluaiing thc expression (+ (* 2 3) (' 3 5)). LISP first waluaies the arguments. (* 2 3) and (* 3 5). In csaluating (“ 2 3). LISP eva!uates thc arguments 2 and 3. which return their respeethe arithmetie v.ilucs: these values are multiplicd to yiełd 6 Similariy. (* 3 5) ewliuies to 15. These results are then passed to thc top-lcvcI additk*. which is oaluated. retuming 21. A diagram of this evaluation appears in Figurę 15.1.

In addition to arithmetie operations. LISP ineludes a large number of functions tłu! operate on lists. These include functions to construct and combinc lists. to access ckmem* of lists. and to test vańou$ propenie*. For examplc. list takes any number of arguments and constnicts a list of thosc clcmcnts. nth takes a number and a list as arguments and returm the indicatcd element of thc list. By convention. nth begins counting with 0. Examplcs of these and other lisi manipulation functions include:

>(Kst12345)

(1234S)

>(nth0'(8bcd))

i

PART VI / LAMGUAGES FOR Al PROBLEM SOLVlNG

(•23)    (*35)

2    3

3    5

Figurę 15.1 Tree diagram of the evaluation of a slmpt* LISP function.

>    (nth 2 (list 12 3 4 5))

3

>    (nth 2 *«a 1) (b 2) (c 3) (d 4)))

(c3)

>    (length *(a b c d))

4

>    (member 7'(1 234 5)) nil

>    (nuli ( )) l

\Vc discuss list-handling functions in greaicr dctaił in Scction IS.I.5. The eonccpts of this scction are summarized in thc fol łowing definition.

DEFINITION

&-EXPRESSION

An s-cxprcssion is defined rccursivcły:

1.    An atom is an s-expression.

2.    If 6,. S₂.____S. are s-expressions,

then so is thc list (s, s, ... s_n).

A list is a nonatomic s-cxpression.

A form is an s-cxprcssion that is intended to be cvaluat©d- If it is « HsL thc lirst element is treated as thc function name and thc sub«qucnt element* are oahuled to obinin thc function arguments.

In cvaluating an s-expression:

If thc s-cxpressioo is a number. return thc value of thc number.

683

CHARTER 1S / AN blTROOWCnON TO U3R