PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/06/86)
PROLOG Digest Monday, 8 Sep 1986 Volume 4 : Issue 47
Today's Topics:
Query - IF/Prolog,
Implementation - Fixed Points,
Puzzle - Knaves Knights and Knaves
----------------------------------------------------------------------
Date: Mon, 1 Sep 86 10:59:24 PDT
From: Mike Newton <newton@vlsi.caltech.edu>
Subject: IF/Prolog
Hello --
I just received IF/Prolog's information brochure and was
sufficiently interested to consider ordering it. Before
doing so, I would like to hear any comments from people
who have used it. [If I get enough interest I will
summarize the comments to this list]. Please either
send me net mail, or a post card to the below address
(with your phone number) and I will call you.
Any information would be appreciated!
-- mike
newton@cit-vax.caltech.edu
Caltech 256-80
Pasadena CA 91125
818-356-6771 (afternoons,nights)
------------------------------
Date: 30 Aug 86 06:48:13 GMT
From: Bjorn Danielsson <mcvax!enea!zyx!bd@seismo.css.gov>
Subject: Fixed Points
I have found a solution, but it requires an extra predicate
that interprets a "represented" clause and melts it into a
lower level of representation. Using an extra predicate
might seem like cheating, especially if you write something
like:
fixed(X) :- cheat(X). cheat((fixed(X) :- cheat(X))).
However, the extra predicate in my solution contains no
information about the problem. The program follows:
fixed(X) :- Y = (-z = (fixed(quote(-x)) :- quote(-y) = build_quote(-y),
-y,
melt(quote(-z),quote(-x)))),
Z = (fixed(-x) :- -y = quote(Y),
Y,
melt(-z,-x)),
melt(Z,X).
% melt(X,Y) interprets the representation X of a clause fragment,
% and unifies Y with the most general term it represents.
% -(foo) represents the variable _foo.
% quote(C) represents the constant C.
% build_quote(X) represents the term quote(Y), where X is a term
% that represents Y.
% Everything else has its usual meaning.
melt(X,Y) :- melt(X,Y,_).
melt(quote(X),X,_).
melt(build_quote(X),quote(Y),L) :- melt(X,Y,L).
melt(-X,V,L) :- member([X|V],L).
melt([A|B],[X|Y],L) :- melt(A,X,L), melt(B,Y,L).
melt([],[],_).
melt(A,X,L) :- A=..[F|B], melt(B,Y,L), X=..[F|Y].
melt(A,A,_).
member(X,[Y|Z]) :- X=Y; member(X,Z).
% End of program
-- Bjorn Danielsson
------------------------------
Date: 2 Sep 86 17:04:41 GMT
From: Jamie Andrews <ubc-vision!ubc-cs!andrews@uw-beaver.arpa>
Subject: Fixed Points
The original query was framed so loosely that even this
program works:
fixed(X).
I think Paul Weiss probably wanted to say "fixed(Term) is
true ONLY of Terms which are clauses defining a predicate
extensionally identical to fixed(Term)." Can the people
who proposed solutions prove that their solutions have
this property?
-- Jamie
------------------------------
Date: 3 Sep 86 21:06:09 GMT
From: David Fiore <ucdavis!ucrmath!hope!fiore@ucbvax.Berkeley>
Subject: Knights and Knaves
I am posting this message to thank all of you who have been
kind enough to answer my call for help on the Knights and Knaves
problem.
Special thanks to Paul Kamsteeg for your in depth analysis and
explanation of the problem. Even though I don't understand all
of what you wrote, what I did understand has been very helpful.
Thanks again to everyone who contributed.
-- David Fiore
------------------------------
Date: Thu, 4 Sep 86 13:08:20 pdt
From: Paul Kamsteeg <Univ. of Amsterdam, Netherlands>
Subject: Knights and Knaves
Dear David,
You have certainly picked an awkward problem for your
*first* Prolog exercise, since it contains at least three
features at which the inference machine of Prolog balks.
The first two are quite well-known limitations of Prolog.
The third one I have never seen mentioned as a problem
(which isn't saying much).
1. You cannot simply state bidirectional implications
(like a<=>b ) in Prolog as:
a:- b.
b:- a.
since this tends to loop, especially if a and b are untrue.
(More specifically, the only way it does not loop is if
there is a non-backreferential clause for a or b *prior*
to the two above in the database, *and* the clause is
guaranteed not to backtrack). You can see why: to prove a,
prove b; to prove b, prove a; to prove a, .... (etc).
The same thing happens, by the way, if you state:
a:- not(b).
b:- not(a).
since to "prove" not(b), Prolog has first to try proving b
(see below). A often used solution is, to make two "layers",
one to prove facts and one of facts that are already known,
as in:
a:- b, assert( known (a) ).
b:- known(a).
thereby resolving the circularity.
2. You cannot depend on Prolog to prove definite negatives,
unless you are absolutely certain you can prove *all*
positives. That is, Prolog uses "negation by failure" which
means that in Prolog succeeding of not(a) only means that a
was not provable, i.e. "I don't know that a" instead of "I
know that not a". The last interpretation only applies if
you are certain that if a were true, Prolog would have proven
it. If you have to use a three_valued logic (true, false,
unknown or in your case knight, knave, unknown) you have to
state the two definite cases (true, false) explicitly and
add clauses to state that they are mutually exclusive, e.g.:
true(a):- true( true(a) ).
true(a):- false( false(a) ).
false(a):- true( false(a) ).
false(a):- false( true(a) ).
or, alternatively:
opposite( a,b ).
opposite( b,a ).
true(X):- opposite(X,Y), false(Y),!, assert( known(X) ).
false(X):- opposite(X,Y), known(Y).
( *not* "false(X):- opposite(X,Y), true(Y)" since this would
again loop)
3. Prolog does not check of itself for logical inconsistencies.
It is perfectly legal to state:
a:- true(b), false(b).
even when true and false are declared to be mutually exclusive
as above. The clause would always fail, either by true(b) not
being provable, or by false(b) not being provable, but Prolog
would not know that it *has* to fail, and could therefore never
conclude "false(a)" *of itself*. To make use of these logical
inconsistencies, you have to make them explicit. I fear this is
not easily accomplished in a general way. For the Knights-and
-Knaves problem I have found a way but it is rather ad-hoc.
I have got a working solution which you can have (it's written
in C-Prolog so probably the syntax needs checking), but I guess
you rather would have a try yourself first. If you need my code
feel free to ask.
Now for your program:
/* First, you only have clauses to represent facts and
* inferences, but you have no way to start up the thing
* (shell, inference machine, top-call) */
is_knight (X) :-
is_knave (X),!,false.
/* The above clause could as well be deleted, since it
* *always* fails. So it does not do anything.
* PS: in C-prolog "false" should be "fail", but I guess
* in your Prolog it's legal syntax. Also, in C-Prolog you
* cannot have a space between functor and arguments, but
* again, in your Prolog ... */
is_knight (X) :- /* Someone is a knight if he */
says (X, Y), Y. /* says something and that */
/* thing is true. */
/* In C-Prolog, you cannot directly call a variable. You have
* to use call(Y) instead of just "Y". Maybe it's legal in
* your Prolog. */
is_knave (X) :-
is_knight (X), !, false.
/* loops together with the first clause of is_knight. See
above (1) */
is_knave (X) :- /* Someone is a knave is he */
says (X, Y), not (Y). /* says something and that */
/* thing is not true. */
/* In Prolog, not(Y) does not mean "definitely not Y". See
above (2) */
legal (X, Y) :-
Y, is_knight (X).
legal (X, Y) :-
not (Y), is_knave (X).
says (larry, Z):- /* We don't know what he said */
legal (larry, Z).
/* You try to state a fact (Larry says something and it's legal).
Instead you state a procedure (Larry says something *if* it's
legal, i.e. larry says anything it's legal for him to say).
Should be says(larry,Z)&legal(larry,Z). or something like that.
Better still to include the legal test in a
really_says predicate */
/* Says larry claims knavehood */
says (curly, says (larry, is_knave (larry))).
/* Says curly is a knave */
says (moe, is_knave (curly)).
Much succes in your new attack at the problem, and good luck,
-- Paul Kamsteeg
Univ. of Amsterdam, Netherlands
------------------------------
End of PROLOG Digest
********************