31 1024x768

This vcrsKMi of ihc path function is a simple translation of Ihc recursivc paih algo* rithni from Engliłh inio LISP and łus several **bugs" ihat nccd 10 be correct c<L li don. hmocr, capcurc thc esscntial stnicture of thc algorithm and sliould be cxaniincd beforc coniinuing to correct thc bugs. The lirst test in thc cond statement is ncccssary for a >uc-cessful coniplction of thc scarch algorithm. When thc equal State goal patiem marches. the rccursion stops and thc atom success is returncd. Ołhcrwisc, path generates thc fbur desccmlnnf nodes of thc scarch graph and then calls itsclf on cach of thc nodes in tum.

In panicul.tr. notc thc usc of thc or form to control cvaluation of its argument*. RccaB that an or cvaluatcs its argumentu in tum until one of them returns a non-nil va!uc. Whea ihis occurs. thc or terminates withoul cvahiating thc other arguments and return* this non-nil yuIuc as a rcsult. Thus. thc or not only is u sod as a logical operator but a bo provides a way of controlling branching within thc spacc to be searchcd. The or form u uscd herc instead of a cond bccausc thc valuc that is bcing tested and thc valuc that should be retumed if thc test is non-nil are thc same.

One problem with this detinition is that a moce function may return a valuc of nil if thc movc ma>’ not be madc or if it leads to an unsafc stale. To prcvcnt path from attempting to generale the childrcn of a nil State, it musi first chcck wliethcr thc currcnt siatę is nil. If it is. path should return nil.

The other issue that needs to be addresscd in thc implcmcntation of path is that of dctccting potaniał loops in the scarch spacc. If the abovc implcmcntation of path is run. thc farmer will soon (ind himsclf going back and forth alonc bctwccn the two banks of tbe rivcr; that is. thc algorithm will be stuck in an infinifc loop bctwccn idcutical States, botb of which it has already yisited. To prcvcnt this from happening, path is givcn a third parameter. been-list. a list of all thc States that have already bccn yisited. Each timc that path is callcd rccursivcly on a ncw stale of the world. thc parem stałe will be added to been-list. path uses thc member predicate to make surę thc currcnt Mato is not a incmber of been-list. i.c.. that it has noc already bccn yisited. This is donc by checking thc eunent state for membership in been-list beforc generał i ng its dcsccndants. path is now defuted:

(defun path (State goal been-list)

(cond ((nuli State) nil)

((equal State goal) (reverse (cons State been-list)))

((not (member state been-list -test *oqual))

(or (path (farmer-takes-self State) goal (cons state been-list))

(path (farmer-takes-wotf state) goal (cons state been-list))

(path (farmer-takes-goat siata) goal (eona State been-list))

(path (farmer-takes-cabbage state) goal (cons state been-list))))))

In thc abcnc implcmcntation. member is a Conunon LISP built-in function ihat bchavcs in csscntially thc same way as the my-member function defined in this chaptcr. The only dśfTcrcncc is thc inciusion of :test #‘equal in thc argument list. Unlike our "homc-grown” member function. thc Common LISP built-in form allows the program-mer to specify thc function that is uscd in testing for membership. This wrinklc inerease* thc flcxibility of thc function and should not enuse too much conccrn in this discussion.

Rather than having thc function return just thc atom success. it is better to have it return the actual solution path. Bccausc thc senes of States on thc solution path is already

PART VI / LANGUAGES FOR Al PROBLEM SOLVING

containcd in ihc beon-list. ihis litu is rctumed imicad. Bccame thc goal is not already on been-list. ii is conscd onio Ihc list. A Bo. bccausc thc list is commicicd in rewne order (willi thc start sinic as thc last element), the list it rcvcncd (oonstructcd in loene order osiog anolher LISP built-in function. reverse> prior to bcing rctumed.

Finally. bccausc the been-list parameter should be kept “hidden" from the u ser. a ocp-loel cal ling function may be w ritten that takes as arguments a start and a goal stale ndcalls path with a nil valuc ««i been-list

(defun sotve-fwgc (state goal) (path state goal nil))

Lei us comparc thc LISP vcrsion of thc farmer, wolf. goal. and cabbagc problem with the PROLOG solution presented in Section 14.3. Not only doc* the LISP program soIyc thc same problem, but it also scarches cxactly thc same state spacc as thc PROLOG vcnfcm. This underseores thc point that the state spacc conccptualization of a problem is independent of thc implcmcntation of a program for scarching that spacc. Bccausc both programs scarch thc same spacc. the two iraplcmentations bavc strong similaritics; thc difTercnccs tend to bc subtle but provide an interes*iog contrast bctwccn dcclamnc and procedura! programming stylcs.

States in thc PROLOG vcrsion are represented using a prcdicatc. state(e.e.e.e). and the LISP implcmcntation uses a list. Thesc two representation* are morę than syntactic wialions on one another. The LISP representation of state is defmed not only by its list $ynta.\ but also by thc access and move functions that coratitutc thc abstract data typc "state.** In thc PROLOG vcrston. States are pattems; their mcaning is determined by thc wav in which they match other pattems in PROLOG rules which could also bc lista.

The LISP vcrsion of path is sliglitly longcr than thc PROLOG %crsion. One rcason for this is that thc LISP vcrsion ni ust implcmcnt a scarch slratcgy. whcrcas ihc PROI.OG vcrsion takes advnntagc of PROLOG *s built-in scarch algorithm. The contro! algorithm is csplicit in thc LISP vcrsion bul is implicit in thc PROLOG version. Bccausc PROLOG is built on dcclnrativc representation and thcorcm-provmg tcchniqucs. thc PROLOG program is morę concise and has a flavor of dcscribing thc problem domain. without dircctly implcmcnting thc scarch algorithm. The price paid for this concisencss ts that much of thc program s behavior is hiddcn. determined by PROLOG* built-in śnfcrcnce strategie*. hognmmers may also fccl morc pressurc to make thc problem solution conform to PROLOG* represcntational formalism and scarch strategie*. LISP. on thc other hand. altowa sreater flcxibility for the programmer. The price paid herc is that the programmer cannot Ara on a built-in representation or scarch slratcgy and must implcmcnt it cxplicitly.

15.3 Higher-Order Functions and Abstraction_

One of thc most powcrftil tcchniqucs that LISP and other functional programming lan-guages provide is the ability to definc functions that take other functions as parameters or return tbem as rcsults. Thesc are callcd higher-onier functions and consrituic an ńmportant tool for proceduraI abstraction.

707

CHAPTER IS / AN MTROOUCTION TO USP