WIXLIB

SYNTAX AND MEANING OF PROLOG PROGRAMS2.5 Example:monkeyand bananaThe monkeyand bananaproblemis often usedasa simpleexampleof problemsolving.our Prologprogramfor thisproblemwill showhow the mechanismsofmatchingand backtrackingcan be usedin suchexercises.We will developtheprogramin the non-proceduralway, andthenstudyits proceduralbehaviourindetail. The programwill be compactand illustrative.We will usethe followingvariationof the problem.Thereis a monkeyatthe door into a room. tn the middle of the room a bananais hangingfrom theceiling. The monkey is hungry and wants to get the banana,but he cannotstretchhigh enoughfrom the floor. At the window of the room there is a boxthe monkeymay use.The monkeycan perform the followingactions:walk onthe floor, climb the box, push the box around (if it is alreadyat the box) andgraspthe bananaif standingon the box directly under the banana.Can themonkey get the banana?One importanttask in programmingis that of finding a representationofthe problem in terms of conceptsof the programminglanguageused.In ourcasewe canthink of the 'monkeyworld' asalwaysbeingin somestatethat canchangein time. The currentstateis determinedby the positionsof the objects.For example,the initial stateof the world is determinedby:(1) Monkey is at door.(2) Monkey is on floor.(3) Box is at window.(4) Monkey doesnot have banana.It is convenientto combineall of thesefour piecesof information into onestructuredobject.Let uschoosethe word'state' asthe functorto hold the fourcomponentstogether. Figure 2.12 showsthe initial state repreSentedas astructuredobject.Our problemcanbe viewedasa one-persongame.Let us now formalizethe rules of the game.First, the goal of the gameis a situationin which themonkeyhasthe banana;that is, any statein which the lastcomponentis 'has':state(-) -, -, has)stateatdooronflooratwindowhasnotFigure2.12 The initial stateofthe monkeyworld representedas a structuredobject.The four componentsare: horizontalpositionof monkey,verticalpositionof monkey,positionof box, monkeyhasor hasnot the banana.

PROLOG PROGRAMMING FOR ARTIFICIAL INTELLIGENCESecond,what are the allowed movesthat changethe world from one state toanother?There are four types of moves:(1) graspbanana,(2) climb box,(3) pushbox,(4) walk around.Not all moves are possiblein every possiblestate of the world. For example,the move 'grasp'is only possibleif the monkeyis standingon the box directlyunder the banana(which is in the middle of the room) and doesnot havethebananayet. Such rules can be formalized in Prolog as a three-placerelationnarnedmove:mov{ Statel, M, State2)The three argumentsof the relation specify a move thus:Statgl --------) State2MStatel is the state before the move. M is the move executed and State2is thestateafter the move.The move 'grasp', with its necessarypreconditionon the statebefore themove, can be definedby the clause:move( state( middle, onbox, middle, hasnot),grasp,state(middle, onbox, middle, has) ).Vo Before moveVo MoveVo After moveThis fact says that after the move the monkey has the banana, and he hasrernained on the box in the middle of the room.In a similar way we can expressthe fact that the monkey on the floor canwalk from any horizontal position Pl to any position P2. The monkey can dothis regardlessof the position of the box and whether it has the bananaor not.All this can be defined by the following Prolog fact:move( state( Pl, onfloor, B, H),walk( Pl, P2),state( P2, onfloor, B, H) ).Vo Walk from PL to PZNote that this clause saysmany things, including, for example:othe move executedwas 'walk from some position Pl to some position P2'othe monkey is on the floor before and after the move;

SYNTAX AND MEANING OF PROLOG PROGRAMS51MOYC McangetcangethasFigure2.13 Recursiveformulationof canget.oothe box is at some point B which remained the same after the move;the 'has banana' status remains the same after the rnove.The clause actually specifiesa whole set of possible moves because it isapplicableto any situationthat matches the specified state before the move.Sucha specificationis thereforesometimesalso called a move schema.Due tothe conceptof Prolog variablessuch schemas can be easily programmed inProlog.The other two types of moves, 'push' and 'climb', can be similarlyspecified.The main kind of questionthat our programwill haveto answeris: Canthe monkey in someinitial state S get the banana?This can be formulated asapredicatecanget(S)where the argumentS is a state of the monkey world. The program for cangetcan be basedon two observations:(1)For any stateS in which the monkeyalreadyhasthe banana,the predicate cangetmust certainly be true; no move is neededin this case.Thiscorrespondsto the Prolog fact:cange( state(-, -, -, has) ).(2)In other casesone or more movesare necessary.The monkeycan get thebananain any state51 if there is somemoveM from state51 to somestate52, suchthat the monkeycan then get the bananain state52 (in zero ormore moves).This principleis illustratedin Figure2.I3. A Prologclausethat correspondsto this rule is:canget(Sl) :move( 51, M, S2),canget( S2).This completesour programwhich is shownin Figure2.14.The formulation of canget is recursive and is similar to that of thepredecessorrelation of Chapter 1 (compare Figures 2.I3 and 1.7). This principle is usedin Prolog againand again.

52PR.OLOGPROGRAMMING FOR ARTIFICIAL INTELLIGENCE% Legal movesmove( state( middle, onbox, middle, hasnot),grasp,state( middle, onbox, middle, has) ).Vo Grasp bananamove( state( P, onfloor, P, H),climb,state( P, onbox, P, H) ).Vo Climb boxmove( state( Pl, onfloor, Pl, H),push( Pl, P2),state( P2, onfloor, P2, H) ).Vo Pushbox from Pl to P2move( state( Pl, onfloor, B, H),walk( Pl, P2),state( P2, onfloor, B, H) ).Vo Walk from Pt to P2Vo canget(State):monkeycan get bananain Statecanget( state( -, -, -, has) ).Vo can 1: Monkey already has itcanget( Statel) :move( Statel, Move, State2),canget( State2).Vo can 2: Do some work to get itVo Do somethingVo Get it nowFigure2.14 A programfor the monkeyandbananaproblem.- We have developedour monkey and bananaprogram in the non-procedural way. Let us now study its procedural behaviour by consideringttrefollowing question to the program:?- canget(state( atdoor, onfloor, atwindow, hasnot)).Prolog'sansweris'yes'. The processcarriedout by Prologto reachthis answerproceeds,accordingto the proceduralsemanticsof Prolog,througha sequenceof goal lists. It involves some searchfor right moves among the possiblealternativemoves.At somepoint this searchwill take a wrongmoveleadingtoa deadbranch.At this stage,backtrackingwill help it to recover.Figure2.15illustratesthis searchprocess.To answerthe question Prolog had to backtrackonce only. A rightsequenceof moves was found almost straight away. The reason for thisefficiency of the program was the order in which the clausesabout the moverelationoccurredin the program.The order in our case(luckily) turnedout tobe quite ordingto therules of the game,the monkey could just as easilytry to walk here or there

SYNTAX AND MEANING OF PROLOG aspclimbpushwalk( I push(P2,P2')P2',onfloor,P2',hasnot)state(grasp climb walk pushstate(P2',onboxlPz)hasnot)graspP2' middlestate(middle,onbox,middle,has)Figure2.15 The monkey'ssearchfor the banana.The searchstartsat the top node andproceedsdownwards, as indicated. Alternative moves are tried in the left-to-rishtorder. Backtrackingoccurred once only.without ever touching the box, or aimlesslypush the box around. A morethoroughinvestigationwill reveal,asshownin the followingsection,that theordering of clausesis, in the caseof our program, in fact critical.2.6 Orderof clausesand goals2.6.1 Dangerof indefiniteloopingConsiderthe followingclause:p:-p.Thissaysthat 'p is trueif p is true'.Thisis declarativelyperfectlycorrect,but

54PROLOG PROGRAMMING FOR ARTIFICIAL INTELLIGENCEprocedurallyis quite useless.In fact, such a clausecan causeproblemstoProlog.Considerthe question:'!- p.Usingthe clauseabove,the goalp is replacedby the samegoalp; this will be inturn replacedby p, etc. In sucha caseProlog will enter an infinite loop notnoticingthat no progressis beingmade.This example is a simple way of getting Prolog to loop edin someof our previousexampleprogramsif we changedthe order of clauses,or the order of goals in theclauses.It will be instructiveto considersomeexamples.In the monkeyand bananaprogram,the clausesaboutthe moverelationwere ordered thus: grasp, climb, push, walk (perhaps.unclimb' should beaddedfor completeness).Theseclausessaythat graspingis possible,climbingis possible,etc. Accordingto the proceduralsemanticsof prolog, the order oiclausesindicatesthat the monkey prefersgraspingto climbing, climbing topushing,etc. This order of preferencesin fact helpsthe monkeyto solvetheproblem.But what couldhappenif the orderwasdifferent?Let us assumethatthe 'walk' clauseappearsfirst. The executionof our original goal of theprevioussection?- canget(stat{ atdoor, onfloor, atwindow, hasnot)).would this time produce the following trace. The first four goal lists (withvariablesappropriatelyrenamed)are the sameas before:(1)canget( state( atdoor, onfloor, atwindow, hasnot) )The second clause of canget ('c anz') is applied, producing:(2)move( state( atdoor, onfloor, atwindow, hasnot), M,, S2,),canget( s2')By the move walk( atdoor, PZ') we get:(3)canget( state(Pz', onfloor, atwindow, hasnot) )using the clause 'can?'again the goal list becomes:(4)move( state( P2', onfloor, atwindow, hasnot), M', s2"),canget( s2")Now the difference occurs. The first clause whose head matches the first goalabove is now 'walk' (and not 'climb' as before). The instantiation is

SYNTAX AND MEANING OF PROLOG PROGRAMS5552" state(P2", onfloor, atwindow, hasnot).Therefore the goal list becomes:(5)canget(state(P2", onfloor, atwindow, hasnot))Applying the clauseocan?'weobtain:(6)move(state(P2", onfloor, atwindow,hasnot),M"' , 52"'),canget(s2"')Again, 'walk' is now tried first, producing:(7)canget(state(P2"' , onfloor, atwindow, hasnot))Let us now comparethe goals(3), (5) and (7). They are the sameapart fromofonevariable;thisvariableis, in turn, P', P" andP"'. As we know, the successa goaldoesnot dependon particularnamesof variablesin the goal.This meansthat from goal list (3) the executiontrace showsno progress.We can see,infact, that the sametwo clauses,'can2' and 'walk', are usedrepetitively.Themonkey walks around without ever trying to use the box. As there is noprogressmade this will (theoretically) go on for ever: Prolog will not realizethat there is no point in continuingalongthis line.This exampleshowsProlog trying to solvea problem in sucha way that asolutiortis never reached,althougha solutionexists.Suchsituationsare notunusualin Prolog programming.Infinite loopsare, also,not unusualin otherprogtamming languages.What l'sunusualin comparisonwith other languagesis that the declarativemeaning of a Prolog program may be correct, but theprogram is at the same time procedurally incorrect in that it is not able toproducean answerto a question.In suchcasesPrologmaynot be ableto satisfya goal becauseit tries to reachan answerby choosinga wrong path.A natural questionto ask at this point is: Can we not make somemoresubstantialchangeto our programso as to drasticallypreventany dangeroflooping?Or shallwe alwayshaveto rely just on a suitableorderingof clausesandgoals?As it turnsout programs,especiallylargeones,wouldbe too fragileif they just had to rely on some suitableordering. There are severalothermethodsthat precludeinfinite loops, and theseare much more generalandrobustthan the orderingmethoditself.Thesetechniqueswill be usedregularlylater in the book, especiallyin those chaptersthat deal with path finding,problemsolvirrgand search.2.6.2 Program variations through reorderlng of clauses and goalsAlready in the exampleprogramsof Chapter 1 there was a latent dangerofproducinga cyclingbehaviour.Our programto specifythe predecessorrelation