Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!decwrl!labrea!sri-unix!quintus!ok From: ok@quintus.uucp (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: The meaning of "declarative" Message-ID: <648@quintus.UUCP> Date: 8 Nov 88 09:46:10 GMT References: <818@etive.ed.ac.uk> <590@dcl-csvax.comp.lancs.ac.uk> <859@etive.ed.ac.uk> <256@aipna.ed.ac.uk> <41315@linus.UUCP> <602@quintus.UUCP> <41581@linus.UUCP> Sender: news@quintus.UUCP Reply-To: ok@quintus.UUCP (Richard A. O'Keefe) Organization: Quintus Computer Systems, Inc. Lines: 85 In article <41581@linus.UUCP> bwk@mbunix (Kort) writes: >A tip of the hat to Richard for his well-penned remarks. >I am amazed at the power of Prolog to solve a problem in >combinatorial logic without being given an explicit method. >But I am also disheartened by the difficulty of untangling >the effects of reordering the clauses. Purr purr... >When a bright student solves a brain-teaser, the order in which >the clues are stated does not strongly affect the method of >solution. In Prolog, resequencing the clues can have dramatic >effects on the search order. I find this phenomenon bewildering. Well, I'm not a student any more, but even when I was, the order of the clues had a pretty strong effect on me. (...rrup rrup) Why should it be bewildering that an intelligent-but-slow organism which spends some time thinking about the problem and a totally-stupid-but-fast programming language interpreter should act differently? Let's look at the monkey-and-bananas program which started this discussion. It's just a depth-first search, where states have the form state(MonkeyHoriz,MonkeyVert,BoxVert,HasBananas). initial_state(state(atdoor,onfloor,atwindow,hasnot)). move( state(middle,onbox,middle,hasnot), grasp, state(middle,onbox,middle,has)). move( state(P,onfloor,P,H), climb, state(P,onbox,P,H)). move( state(P1,onfloor,P1,H), push(P1,P2), state(P2,onfloor,P2,H)). move( state(P1,onfloor,Q,H), walk(P1,P2), state(P2,onfloor,Q,H)). depth_first_monkey(Moves) :- initial_state(State), depth_first_monkey(State, Moves). depth_first_monkey(state(_,_,_,has), []). depth_first_monkey(State1, [Move|Moves]) :- move(State1, Move, State2), depth_first_monkey(State2, Moves). Note that this state space is just about as bad for depth-first search as it can possibly be: for any P,H, push(P,P) is a possible action which transforms state(P,onfloor,P,H) to itself, and similarly for any P,Q,H, walk(P,P) is a possible action which transforms state(P,onfloor,Q,H) to itself. Or if you're smart enough to avoid trivial loops, push(P,Q);push(Q,P) and walk(P,Q);walk(Q,P) are loops. Loops are BAD NEWS for depth-first search. There is an easy way of fixing this, and while it looks like a hack it is actually a principled strategy which competes well with breadth-first search. That is ITERATIVE DEEPENING. To keep this message short: iterative_deepening_monkey(Moves) :- list(Moves), depth_first_monkey(Moves). list([]). list([_|L]) :- list(L). I suggest that you consult a good AI text to find out when iterative deepening is appropriate. In this particular case, the iterative deepening version works well no matter how you shuffle the rules. This is actually a problem where working backwards is a good idea: there is only one move which can possibly yield the final state, only one move which can yield that state, and not too many before that. What one really wants is a "smart" program which notes for example that any sequence Walk*{Push;Walk*}* can be collapsed to either Walk or Walk?Push;Walk?, that no action can follow a 'grasp', and that no other action than 'grasp' can follow 'climb', so that the only "interesting" sequences are {Walk | Walk? Push Walk?} {Climb Grasp?}? -- This is why I have never really got interested in things like the Zebra puzzle: by the time you have figured out a cunning way to represent the search space and the rules there is nothing left to write in Prolog.