PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/13/86)
PROLOG Digest Thursday, 14 Aug 1986 Volume 4 : Issue 37
Today's Topics:
Implementation - `->',
Puzzle - Farmer Summary
----------------------------------------------------------------------
Date: Tue, 12 Aug 86 10:12:33 pdt
From: Allen VanGelder <avg@diablo>
Subject: Programs with ->
In designing NAIL! (*) we came across the same confusion about ->
and ';' that was brought up by Saumya Debray and commented upon by
Fernando Pereira. We decided to add 'else' as an operator of lower
precedence than -> and stop overworking the semi-colon. Let's see
howthis works on Fernando's examples:
Prolog NAIL!
Source p :- a -> b; c. p :- a -> b else c.
Parse :- :-
/ \ / \
p ; p ->
/ \ / \
-> c a else
/ \ / \
a b b c
Equivalent to p :- q. p :- q.
q :- a, !, b. q :- a, b.
q :- c. q :- not a, c.
Source a -> b; c; d -> f; g a -> b else c; d -> f else g
a -> b; c; d -> f; g
a -> b; c; d -> f else g
a -> b else c; d -> f; g
a -> b else (c; d -> f else g)
Who knows how a programmer thinks the expression on the left reads?
Following the heuristic "the first semi-colon after -> is an 'else'"
yields the 1st line on the right. The heuristic "when you see a lot
of semi-colons, they are all or's" yields the second line on the
right. The 3rd and 4th lines provide other possible readings by
humans.
Actually, Prolog reads the 5th line. The subtle difference between
the 2nd and 5th lines is that when (a -> b) fails in Prolog, it
matters whether 'a' failed or 'b' failed. If 'b' failed, there is NO
backtracking to 'c' and/or (d -> e), while if 'a' failed, there IS
backtracking.
This certainly looks like an error-prone construction with semi-colon
having two English translations. As far as I can see, its only excuse
for being that way is that it was easy to implement by reducing it to
other Prolog primitives. But the main reason to HAVE if-then-else in
the language, as argued by Lee Naish, is that it represents a concept
that ISN'T easily expressible by other Prolog primitives.
* For information on NAIL!, see "Design Overview of the NAIL! System"
in Proceedings ICLP, July 86, London, or STAN-CS-86-1108 from Stanford
Univ. Computer Science Dept.
------------------------------
Date: 13 Aug 86 04:02:00 GMT
From: Mario O. Bourgoin <ucbcad!nike!ll-xn!mit-amt!mob@berkeley>
Subject: Farmer Puzzle
First, I would like to thank all the persons who answered my
request for help. Your advice and suggestions were most useful
in making this exercise a learning experience for me.
Thanks to:
- Dave Broderick. He was the first to send me a solution to the
Farmer problem. His program modeled the state as composed of
left and right riverbank lists and the problem as finding a
sequence of sequential addition/deletions from these lists to
reach the goal. As an example:
Start state: river(farmer+[fox,goose,grain],[]).
Goal state: river([],farmer+[fox,goose,grain]).
- Chrisj@basser.oz. He was the last to send me a solution to the
Farmer problem. I got it just as I was writing this article
and haven't had time to try it out yet. His answer is to the
Australian version of the problem, involving a Koala,
Eucalyptus leaves, a Dingo and of course a Farmer.
- Maarten van Emden mhvanemden. His reply was to send me a
problem set which included questions about moving from node to
node through a graph which was where my head space was at at
the time. This covered two methods to prevent program
looping: the depth-bound approach and the path record
approach. The problem set also included many questions which
brought home other points that were essential in cleaning up
my model of Prolog's behavior. This reply was without doubt
the most useful one.
- Ed Windes. He pointed out the problem of the path/2 procedure
being left-recursive and also mentioned the need for keeping a
record of visited states to prevent looping while walking
through the problem state graph.
- Wayne Cook and Suzanne Dietrich. Both made the suggestion that
already seen states be asserted and looked up as a means of
controlling looping. I had already used the technique in a
small classification expert system as a means of avoiding
solving for already discovered facts.
Truth Maintenance Systems (TMS) accomplish this caching in an
efficient way that allows easy checking of which facts are or
are not applicable to a situation. TMSs also replace
chronological backtracking with dependency directed
backtracking for greater search efficiency. Johan de Kleer
(Artificial Intelligence, Vol. 28, No. 1, 1986) of Xerox PARC
has designed an assumption based TMS which eliminates most
backtracking of all types. Maybe such systems will be
included in future versions of Prolog.
- Chuck Restivo. For being the moderator to this newsgroup and
sending my request for help to places that may not have been
reached otherwise.
------------------------------------------------------------------
On to the problem itself. There were three problems that prevented
the original program from finding _a_ solution to the Farmer
problem:
- There was a typo in the statement of the linked/2 procedure.
- The path/2 procedure was left recursive. While the solution
statement was logically correct, the left recursion caused
much unnecessary searching to find a solution. This was fixed
by replacing the left call to a call to linked/2.
- The path/2 procedure did not restrict alternate linked states
to those not yet encountered. This was fixed by adding a Path
variable to the input(?) list of the path/2 predicate making
it into a path/3 predicate.
While the last two fixes are not in theory essential to the
finding of a solution, not fixing them results in stack overflow
before a solution can be found. If Prolog refused to solve for
goals already encountered, this problem would not exist. A hash
table of calls would provide an efficient solution to the problem
of whether a state has been met already given a consistent
encoding of variable names. Can someone provide me with a reason
other than efficiency for why this is not done?
Ed Windes and Suzanne Dietrich pointed out that the linked/2
procedure did not produce all of correct linked states for the
state(1,1,1,1) input. This was due only to the typo in the
third and clause of the predicate. With this fixed, the predicate
is able to generate all of the linked states, albeit with much
redundancy.
There are two answers to the Farmer Puzzle. While with the above
fixes my program would manage to produce a correct solution,
resolution for alternate answers would repeat many of the
already encountered solutions. The number of repetitions has an
upper bound of 2^58 as near as I can calculate. The 58 was
obtained by counting the number of legal second states produced by
Prolog using linked/2 and subtracting the total number of
legal states from the result. Can someone substantiate this answer?
The problem is that both legal/1 and linked/2 are
loose characterizations of what they claim to represent so that they
reproduce previously given answers upon resolution. legal/1 for
example will produce 16 legal states while there are only 10
legal ones. 16 was obtained through figuring out the number of
states that legal/1 can produce. Can someone give me an
explanation or a pointer to an explanation as to how to calculate
the number of repeated resolutions to linked/2 or similar predicates?
Another problem of efficiency was that my statement of the problem
did not take advantage of Prolog's unification procedure for
stating similarity between elements of states. Taking advantage of
this feature eliminates the same(yes,_,_) predicate and associated
matching. This results in up to 2.5 times! fewer procedure calls.
This statistic was gathered by hand. Can someone point me to tools
that allow me to get statistics from Prolog? I use C-Prolog.
Better yet, can someone point me to theory that would allow me to
calculate the expected number of calls a particular problem
statement will require to generate all solutions?
----------------------------------------------------------------------
Here is the final solution:
/*
The problem solver keeps track of the current state as a
predicate of the form:
state(Farmer,Fox,Goose,Grain).
Where Farmer is abbreviated F, Fox is X, Goose is G and Grain is A.
Each place can take on a value of either 1 or 2, each number
representing a side of the river.
*/
/* Test for membership of an element in a list */
member(E,[E|_]).
member(E,[_|T]) :- member(E,T).
/* Define sides 1 and 2 as being opposite */
opposite(1,2).
opposite(2,1).
/*
A legal state is one where either the farmer is on the same side as
the goose or is on the same side as both the fox and the grain. In
the latter case, the condition that the farmer be on the opposite
side from the goose is necessary to prevent resolutions that repeat
states already covered by the first legal/1 definition.
*/
legal(state(F,_,F,_)).
legal(state(F,F,G,F)) :- opposite(F,G).
/* There are four cases for linked states:
Only the farmer changes sides */
linked(state(F1,X,G,A),state(F2,X,G,A)) :-
opposite(F1,F2),
legal(state(F2,X,G,A)).
/* The farmer and the fox change sides */
linked(state(F1,F1,G,A),state(F2,F2,G,A)) :-
opposite(F1,F2),
legal(state(F2,F2,G,A)).
/* The farmer and the goose change sides */
linked(state(F1,X,F1,A),state(F2,X,F2,A)) :-
opposite(F1,F2),
legal(state(F2,X,F2,A)).
/* The farmer and the grain change sides */
linked(state(F1,X,G,F1),state(F2,X,G,F2)) :-
opposite(F1,F2),
legal(state(F2,X,G,F2)).
/*
This is the top level predicate whose purpose is to establish
whether there is a non-circular path from the Start state to the
Goal state. Solution is that path. path/3 calls path/4 with a list
of the Start state as the germ of the already seen states list.
*/
path(Start,Goal,Solution) :-
path(Start,[Start],Goal,Solution).
/*
A path from State to Goal exists if State is linked with Goal.
Path is the list of states encountered up to now. Solution is Path
prepended with Goal.
*/
path(State,Path,Goal,[Goal|Path]) :-
linked(State,Goal).
/*
A path from State1 to Goal exists if there exists a State2 which
has not yet been encountered, which is linked with State1 and for
which a path exists to Goal. State2 is part of the list of states
encountered up to now and Solution is the list of states leading
from the original state to Goal.
*/
path(State1,Path,Goal,Solution) :-
linked(State1,State2),
not(member(State2,Path)),
path(State2,[State2|Path],Goal,Solution).
-- Mario O. Bourgoin
------------------------------
End of PROLOG Digest
********************