29 1024x768

Mouwcr. unlikc such strongly typcd languagcs as C or Pascal, whcre all cxprcs.\ioi» can bc checkcd for typc consistcncy bcforc run timc. in LISP ii is ihc tlała objccis iłiai arc typcd. raihcr ihan \ariaWc*. Any LISP symbol may bind lo any objccL This pnwidcs the programmcr u itli thc powcr of typing but also with u grcat dcal of flcxibiliiy in manipuht-ing objccis of difYcrcnt or even unknown types. For cxamplc. we niay bind any objęci to any variablc at run tinic. This means that we may dciine dala structurcs such as framcs. withotit fully spccifying thc types of thc valucs stored in them. To support this ftaiibility, LISP implcmcnts run-timc lypc chccking. So if wc bind a valuc to a symbol, and try to me this valuc in nn crroncous fashion at run-timc. thc LISP interpreter will dctcct an error.

>    (sotq x ’•)

a

>    (♦ x 2)

>    > Error: a la not a valid argument to ♦.

>    > While executing: *

Users may implcmcnt their own typc chccking using cithcr built-in or user-defoed lypc predicatcs. This allows thc dctcct ion and management of typc errors as nccded.

The prcccding pages arc not a complctc dcscription of LISP. Instead. they arc intendcd to cali Ihc rcadcr*s attention lo interesting fcaturcs of thc languagc that will be of usc in implcmcnting Al data structurcs and algorithms. Thcsc fcaturcs inelude:

1.    The naturalncss with which LISP supports a data abstraction approach to programming.

2.    The usc oflists to create symbol ic data structurcs.

3.    The usc of cond and rccursion to eon troi program llow.

4.    The rcc.ursivc naturę of list structurcs and thc rccursivc schcmcs invofvcd in their manipulation.

5.    The usc of quote and eval to eon troi function cvaluation.

6.    The usc of set and lot to control yariable bindings and side cfTects.

The rcmainder of this chaptcr builds on thcsc idcas to dcmonstmtc thc usc of LISP for typical Al programming tasks such as paltem matchcrs and scarch algorithms.

15.2 Search in LISP: A Functional Approach to the Farmer, Wolf, Goat, and Cabbage Problem

To introducc Al programming in LISP. wc ncxt represent and solve thc farmer, w>If» gcuL and cabbage problem:

A farmer with hu wolf, goat. and cabbage eonie to thc edge of u nvcr they wisli lo eros*. That is a bont at the rivcr‘s edge. but. of coursc. only thc farmer can row it. The boat also cm cany

PART VI / LANGUAGCS FOR Al PROBLEM SOLVING

only l»o thingi (inc fading ihc rower)ai a timc. If thc Mtfbcw left alonc »«th Ar foat. Ac •olf will eat thc gost; aimilarły. if thc gnat b Icft słone h ith Ac i-Atngr. Ac goc «fl cat Ac cabbage. Dcvi*c a scqucncc of crouings of thc mer so Aet *11 fowr charactcn arme uW> ca thc other sldc of thc mer.

This problem was fint presented in PROLOG in Sectaon 14.3. The LISP temoa searches the same spacc and has stmctural similaritics to thc PROLOG sohaion. hoaotr. il difTers in wnys that rclicet LISP’s impcramc functional orkntatkm. The USP solution icjichcs thc siatę spacc in a depth-fint fashion using a lisi of visited States to avo*d loops.

The hcart of the program is a set of functśons that deftne States of thc world a» an abstmet data typc. Thcsc functions hide the intemaU of siatę representalion Irom higher-lcvcl componcnts of the program. States arc represented as lista of Ibur demem*, w herc each element denotes thc location of the farmer, woli, goat. or cabbage. rcspcc-mch Thus. (o w e w) represenU the State in which the farmer (the fint demem) and the goat (thc third element) arc on thc cast bank and the w>lf and cabbage arc on the »oi. The tnsic functions defining thc stale data typc will be a constniclor. make-stale. wtnch takes as arguments thc locations of thc farmer, wolf. goat. and cabbage and retums a stale, and fouraccess functions. farmer-slde, wolf-side. goat-siće. and cabbage-skle. «hu h takc j stale and return thc location of an individual. Thcsc functions arc defined:

(defun make-state (fwgc) (Rat 1 w g c))

(defun farmer-sido (state)

(nth 0 stale))

(dofun wolf-side (stato)

(nth 1 state))

(defun goat-skfo (state)

(nth 2 state))

(defun cabbage-skle (state)

(nth 3 state))

The rest of the program is built on thcsc stale access and consirucnon fimetion*. In partkular. they arc used to implemeot the four possibic actions thc farmer may eakc: tomiog across the rivcr alonc or with cithcr thc wolf. goat. or cabbage.

Each movc uses thc access functions to tear a stale aport uho its componcnts. A function callcd opposite (to be defined shortfy) determines the new location of thc ■Ariduais that cross the rivcr. and make-state rcassembłes thcsc inco the new state. For eumplc, thc function farmer-takes-sełf may be defined:

(dofun farmer-takes-self (siato)

(make-state (opposite (farmer-sfde state))

(wolf-side State)

(goat-side State)

(cabbage-sldo state)))

Note that this flinclion returns thc new stare, regardless of wbether ii is safe or not. A ■cneisunsafc if thc farmer has Icft the goat alone with thc cabbage or icft the woff alonc

CHAPTER tS/ANlNTROOUCTłONTOLISP

703