18 1024x768

ftinctional programming. combined \vith a rich set of high-levcl tools for building synj. bolic dala structures such as predtćaies, frames. nętworks. and objccts. is rcsponsiblc for LISPs popularity in the Al community. USP is widcly uscd as a languagc for implcmcnt-ing Al tools and modcls, particularły in the research community. wherc its high-1evcl func-tionality and rich dcwlopmcnt cmironmcnt make it an ideał languagc for building and testing prototype Systems.

In (his chaptcr we introducc the syntax and semanties of Common LISP, with particu-lar emphosis on the fcalures of the languagc that make it useful for Al programming: the usc of lists to create symbolic data structurcs. and the implemcntation of interpreter* and scareh algorithms to manipulate thesc structurcs. Examplcs of LISP programs that we devcłop in this chaptcr indude scareh engines. panem matchcrs. theorem provers, rak-based expert system shells. semantie nętworks. algorithms for leaming. and objcct-ori-ented simulations. It is not our goal to prosidc a complctc introduclion to LISP: a number of esccllcnt tcxts (see the cpiloguc to this chaptcr) do this in far greater detail ihaa om spiec allows. Instcad. we focus on using LISP to implcmcnt the reprcscntation languagc* and algorithms of artittciai imelligencc programming.

15.1 LISP: A Brief Overview

15.1.1 Symbolic Exprcssions, the Syniactic Basis of LISP

The syntactic elcmcnts of the LISP programming languagc arc symbolic expressions, also known as s-cspnrssions. Both programs and data arc rcpresented as s-exprcssions: an s-cxprcssion mny be cither an atom or a list. LISP aioms arc the basie syntactic units of the languagc and include both numbers and symbols. Symbolic aioms arc composed oflettm. numbers. and the following non-alphanumeric charactcrs:

F.xampłcs of USP aioms indude:

3.1416

100

jK:

hyphenated-name

‘śomo^tobal*

nil

A lisi is a sequencc of cither aioms or other lists scpąrated by blanks and cnclosed in parentheses. Example$ of lists indude:

(1234)

(tom mary John joyce)

(a (bc)(d (•!)))

PART VI / LANOUAGES FOR Al PROBLEM SOLVING

Notę that lists may bc clcmcnts of lists. This nesting may be arbitrarily dccp and alKws u* to crcatc symbol structurcs of any desircd form and complcxity. The empcy list. ”( )". plays a spccial role in the construction and manipulation of LISP data structurcs and is given the spccial namc nil. nil is the only s-cxpression that is considcrcd to be both an atom and a list. Lists arc cxtrcmcly flexiblc tools for constructing rcprcscntational struć-tores. For cxnmplc. we can usc lists to represent cxpressions in the prcdicatc calcu! us:

(on block-1 tablo)

(likos bill X)

(and (likes georgo kata) (likes bill merry))

NVc usc this syntax to represent prcdicatc calculus cxprcssions in the unińcation algo-ritłmt of this chaptcr. The ncxt two cxampies suggest ways in which lists may bc uscd to msptemcnt the data structurcs nccdcd in a databasc Application. Scction 15.1.5 dcscribcs ifae implcmcntation of a si nipie data rctricval system using these representations.

((2467 (lovelac© «da) programmer) (3592 (babbage Charles) computer-designer)) ((key-1 valu©-1) (key-2 valuo-2) (key-3 value-3))

An important fen turę of LISP is its usc of LISP syntax lo represent programs as uell as data. For cxomplc. the lists.

r 79)

(-(♦34) 7)

may be interpreted as arithmetie cxprcssions in a prcfix noćation. This is exactly how LISP trciilS these exprcssions. witla (“ 7 9) represent ing the product of 7 and 9. When LISP is śmokcd on the Computer, the u ser enters an intcractive dialog uc with the LISP interpreter. The interpreter prints a prompt (in the examplcs in this tcxt: >), rcads ehe user input. anempts to evaluatc that input. and. if successful. prints the result. For cxample:

>(•79)

63

>

Herc. the user enters (* 7 9) and the LISP interpreter responds with 63. i.c.. the iu/w asso-ciaicd with that cxprcssion. LISP then prints another prompt and waits for morę user input. This cyclc is known as the ncad-eral-print toop and is the heart of the LISP interpreter.

When givcn a list. the LISP cvaluator attempts to interpret the ftr>t demem of the list « the namc of a function and the rcmaining clcmcnts as its arguments. Thus. the y-espression (f x y) is equivalcnt to the morę traditional mathematical function notataon f(x.y). The value prinicd by LISP is the result of applying the function to its arguments. LISP cxprcssions that mny bc mcaningfully cvaluated arc cattcd Jorms. If the user enters aa cKprcssion that may not be correctly cvaluatcd. LISP prints an error messa gc and allows the user to trące and correct the problem. A sample LISP session appears be Iow;

681

CHAPTER 15/AN INTRCX>UCTlON TO USP