30 1024x768

wach ihe goat. The program musi lind a solulion palli Ihal doc* not eonem, any unsafc staics. Allhough ihis We" check msy be done at a number of dificrcm siages of Ihe program. ourupproach isloperform ii inihc mmc functions.Th.s is implementcdby uanga function callcd safe. which we abo dcfinc shorily. safe Has the following bchavior.

>    (_Safe '(www w))    ; salo siatę, return unchangtd

(w WWW)

>    (safo *(• w w o))    ; wolt eals goal. return nil.

nl

>    (safo '(w w e o))    ; goat oals cabbago. return nl.

nil

safe is uscd in cach nun c function to filier out the unsafc States. Thus. any nunc that nun cs to an unsafc stale will return nil inslead of that stale. The rccursivc paih algorithm can check for ihis nil and usc it to prune that stale. In a sense. we arc using safe to impie-roent a production system style condirion-check prior to determining if a nunc nile can be applied. Using safe. a finał definrtion of the four nowe functions is ne*t:

(defun farmer-takes-self (State)

(safe (make-stato (opposite (farmor-side State))

(wolf-sido stale)

(goat słde State)

(cabbage-side State))))

(defun farmor-takos-woif (State)

(cond ((oqual (farmer-side stale) (woif-side State))

(safe (make-state (opposite (farmer-side State))

(opposite (wolf-sida State))

(goat-sido State)

(cabbage-side State))))

(tnfl)))

(defun farmor-takes-goat (stale)

(cond ((oqual (farmer-side State) (goat-sido State))

(safe (make-state (opposite (farmer-side State))

(wolf-side stale)

(opposite (goat-side stale))

(cabbage-side State))))

(tnll)))

(defun farmer-takos-cabbago (State)

(cond ((egual (farmer-side State) (cabbage-side State))

(safe (make-state (opposite (farmer-side State))

(wolf-sido stale)

(goat-side stale)

(opposite (cabbage-side stale)))))

<tn«)))

Notc that the las! three move functions inelude a conditional test to dctcrminc whether the farmer and the prospcctńc possenger arc on the same sidc of the rivcr. If they arc not. the functions return nil. The movc definitions usc the siato nianipulation functions already presented and a function opposite. which retums the opposite of a givcn sidc:

PART VI / LANGUAGES FOR Al PROBLEM SOLVING

(defun opposite (side)

(cond ((equal side ’e) ’w)

((oqual side *w)'«)))

LISP providcs a numbcr of dilYercnt prcdkatet for cquality. tbc most strwgeta. eq, _u irue orfy if its argument* e\aluatc to the same object, i.c^ point to tbe same mcmory loatton. equal is less strict: it rcquircs that its argument* bc ^nucńcalty idcntical. as im

>(setq 11 '(123))

(123)

>    (setq I2 '(1 2 3))

(123)

>(cqual 1112) t

>(eq 1112) nil

>    (sotq 13II)

(123)

>(*q no)

t

We dcfinc safe using a cond (o check for the iwo unsafc conditions: (I) ihe farmer on the opposite bank from Ihe wolf and ihe goat and (2) the farmer on the opposite tank from the goat and the cnbbagc. If the State is safe, it is returoed unehanged; ochcrwHe. safe retums nil:

(defun safe (State)

(cond ((and (equal (goat-side State) (wolf-side stali)) ;«*MUgo« (not (equal (farmer-side State) (wolf-*ids State)))) nl)

((and (oqual (goat-side State) (cabbage-side State)) ; goat sals cabbago (not (equal (farmer-side State) (goat-sMs State)))) nil)

(t state)))

palh implcmcnts the backiracking scarch of the state space. It tafces as arguments a szale and n goal and first checks to sec whether they arc equal. indicating a successful ter-■nation of the scarch. If they arc not equal, palh generates all four of the nrighborinj

stale* in the state spacc graph. calling itsdf rccursheły on och of ifcoc sagbboriog siaies

in tom łotry to find a path from (hem to a goal. Transłating ihis sśnpic dcfinmoo dirccth imo LISP yiclds:

(defun path (state goal)

(cond ((equal state goal) 'success)

(t (or (path (farmer-takes-seff sfate) goal)

(path (farmor-takes-wolf state) goal)

(path (farmor-takes-goat state) goal)

(path (farmer-takes-cabtage state) goal)))))

CMAPTER15/AW WTROOOCnOMł°U» 705