PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/23/86)
PROLOG Digest Monday, 25 Aug 1986 Volume 4 : Issue 41
Today's Topics:
Query - Fixed Points,
Implementation - Bagof,
Puzzle - Knights and Knaves
----------------------------------------------------------------------
Date: Thu 14 Aug 86 19:40:02-EDT
From: Paul G. Weiss <PGW@XX.LCS.MIT.EDU>
Subject: Fixed Points
The familiar non-trivial LISP fixed point is:
((lambda (X) (list X (list (quote quote) X)))
(quote (lambda (X) (list X (list (quote quote) X)))))
What can be done for Prolog? Ideally, I would like to find a
one-clause predicate fixed/1, with the property that fixed(Term)
is true of the Term which is the clause that defines fixed/1.
So far the best I can do is a pair of predicates foo/0 and b/1, each
of one clause such that typing "foo" at the ?- prompt causes the two
defining clauses to be written out. I am unhappy with this since it
uses write and writeq:
foo :- b((
b(X) :-
writeq((foo :- b(X))), write('. '), nl,
writeq(X), write('. '), nl
)).
b(X) :-
writeq((foo :- b(X))), write('. '), nl,
writeq(X), write('. '), nl.
Can such a predicate be defined ?
------------------------------
Date: 20 Aug 86 14:10:37 GMT
From: Ramesh Krishnamurti <mcvax!ukc!cstvax!edcaad!ramesh@seismo>
Subject: Dave Plummer's bagof query
In reponse to Dave Plummer's query, the way bag_of(X,P,B) works
in C-Prolog and hence (?) ought to in DEC-10 Prolog is to
find to all instances of X such that P is provable with the
condition that any variables in P not X are bound.
Thus for the program,
p(1,2).
p(1,1).
p(2,_).
p(3,_).
p(4,4).
bagof(X,p(X,Y),B) will, on backtracking, successively generate
the lists
[3,2,1] with Y bound to 2
[1] with Y bound to 1
[4] with Y bound to 4
Ideally, it should produce the lists
[3,2,1] with Y bound to 2
[3,2,1] with Y bound to 1
[4,3,2] with Y bound to 4
But thats asking too much of Prolog !
If you want the variables in P not in X to remain free then
they must be explicitly bound by an existential quantifier ^.
That is,
bagof(X,Y^p(X,Y),B) will generate the list
[4,3,2,1,1] with Y bound to _
If you don't want to be bothered with specifying the free
variables the following version of bagof works.
%-------------------------------------------------------------
bag(_,_,_):- asserta($bag(base,_)),
fail.
bag(X,P,B):- Pred,
asserta($bag(item,X)),
fail.
bag(_,_,B):- $gather([],B).
$gather(C,B):- retract($bag(Tag,X)),
!,
$gather(Tag,X,C,B).
$gather(base,_,B,B):- !.
$gather(item,X,C,B):- !,
$gather([X|C],B).
%-------------------------------------------------------------
However, for the database:
drinks(tom,lager).
drinks(dick,bitter).
drinks(harry,bitter).
drinks(bill,lager).
drinks(jack,lager).
drinks(bill,bitter).
bag(X,drinks(X,Y),B) will produce
B = [tom,dick,harry,bill,jack,bill] with Y bound to
whereas
bagof(X,drinks(X,Y),B) will successively produce
B = [jack,bill,tom] with Y = lager
B = [bill,harry,dick] with Y = bitter
Take your pick.
-- Ramesh
------------------------------
Date: 18 Aug 86 22:26:39 GMT
From: David Fiore <ucdavis!ucrmath!hope!fiore@Berkeley>
Subject: Knights and Knaves
This is an attempt at writting a Prolog program and I have come to a
point where I don't know why the program doesn't work and I have run
out of ideas on how to make it work. Could anyone help me out with
this?
Thank you,
-- David Fiore
/* This program is supposed to solve a logic puzzle I read in R.
Smullyn's book "What Is The Name Of This Book?". The problem
is as follows:
On a certain island in the pacific is an island
of knights and knaves. Now knights by nature allways
tell the truth, as far as they know it, while knaves
by nature allways tell lies, as far as they know it.
A visitor to the Island of Knights and Knaves comes
across three inhabitants of the island standing together
in a garden. We will call them Larry, Curly, and Moe.
The stranger says to Larry: "Are you a knight or a
knave?". Larry answers but, rather indistinctly, so the
stranger could not make out what Larry said. So the
stranger says to Curly: "What did Larry say?". Curly
says: "Larry said that he was a knave." At this point,
the third man Moe says: "Don't believe Curly, he's lying!"
The question is what are Curly and Moe?
It is immediately obvious that whatever Curly is, Moe is the
opposite. What is not immediately obvious to everyone is that
independant of Moe's statement, we can see that Curly is lying
because it is impossible for any inhabitant to claim to be a
knave. We can therefore deduce that Curly is a knave and Moe is
a knight.
*/
is_knight (X) :-
is_knave (X),!,false.
is_knight (X) :- /* Someone is a knight if he */
says (X, Y), Y. /* says something and that */
/* thing is true. */
is_knave (X) :-
is_knight (X), !, false.
is_knave (X) :- /* Someone is a knave is he */
says (X, Y), not (Y). /* says something and that */
/* thing is not true. */
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).
/* Says larry claims knavehood */
says (curly, says (larry, is_knave (larry))).
/* Says curly is a knave */
says (moe, is_knave (curly)).
------------------------------
End of PROLOG Digest
********************