PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/01/86)
PROLOG Digest Monday, 1 Sep 1986 Volume 4 : Issue 46
Today's Topics:
Puzzle - Knights and Knaves,
Implementation - Bagof & Fixed Points
----------------------------------------------------------------------
Date: 25 Aug 86 18:20:37 EDT
From: Jan Chomicki <CHOMICKI@RED.RUTGERS.EDU>
Subject: "Knights and Knaves": a solution
To solve the "Knights and Knaves" puzzle we construct a simple
theory of the island. Syntactically, the theory consists of
sentences:
"is(X,K)" and "says(X,A)"
where X is a person, K - his/her kind
(Knight or Knave) and A - a sentence. Only negation is allowed,
no conjunction etc. Hence every sentence looks like
"says(X1,says(X2,...says(Xn,is(Y,K))))",
with possibly interspersed negations. We are interested in the
models of this theory. Notice that the truth of a sentence
depends on who says it, and that's why it is enough to consider
the assignments to the predicate "is" of the form { is(larry,...),
is(curly,...), is(moe,...)} . My procedure true/2 determines the
truth of a sentence in a given model.
It is interesting to see that the models are only partially
determined. That's why the puzzle asks abour Curly and Moe, but
not about Larry.
I have also another solution of this puzzle which does not use "\+"
in the code. However, I had to make stronger assumptions about the
situation being modelled and the code is a bit longer.
/* "Knights and Knaves": a solution by Jan Chomicki. */
:-op(900,fy,[~]).
true(~A,T) :- \+ true(A,T).
true(is(X,K),T) :- member(is(X,K),T).
true(says(X,A),T) :- true(is(X,knight),T), !, true(A,T).
true(says(X,A),T) :- true(is(X,knave),T), !, \+ true(A,T).
solution([is(larry,A),is(curly,B),is(moe,C)]) :- oneof(A),oneof(B),
oneof(C).
oneof(knave).
oneof(knight).
member(X,[X|_]) :- !.
member(X,[Y|L]) :- X\==Y, member(X,L).
g(X) :- solution(X), true(says(curly,says(larry,is(larry,knave))),X),
true(says(moe,is(curly,knave)),X).
| ?- g(X).
X = [larry is knave,curly is knave,moe is knight] ;
X = [larry is knight,curly is knave,moe is knight] ;
no
------------------------------
Date: 22 Aug 86 09:53:11 GMT
From: Chris Moss <mcvax!ukc!icdoc!cdsm@seismo.css.gov>
Subject: Dave Plummer's bagof query
>Given the program:
>
>p(1,_). p(2,_). p(3,3). p(4,4).
>
>and the goal bagof(X, p(X,Y), S). Edinburgh DEC-10 Prolog
>returns,
>
>S = [1,2,3] X = _ Y = 3
>S = [4] X = _ Y = 4
>
>This behaviour doesn't agree with my reading of the
>documentation
Poplog produces the solutions:
S=[4] X =_1 Y=4
S=[3] X =_1 Y=3
S=[1,2] X=_1 Y=_2
which is _slightly_ more consistent.
The problem has been dealt with in:
Lee Naish: All solutions predicates in Prolog.
Techch Report 84/4, Dept of Comp. Sc., Univ of Melbourne.
He has a 'hard-line' solution which involves coroutining and
never returning variables if they can be subsequently bound.
-- Chris Moss
------------------------------
Date: Thu 28 Aug 86 13:53:54
From: Wlodek Drabent <enea!liuida!wdr@seismo.CSS.GOV>
Subject: Fixed Points
Here is a two-clause "fixed point" program:
fix( X, g(X) ) :- g( X ).
g(( fix( X, g(X) ) :- g( X ) )).
and an execution trace for it:
| ?- fix( X, Y ).
X = (fix(_162,g(_162)):-g(_162)),
Y = g((fix(_162,g(_162)):-g(_162))) ;
no
| ?- listing.
fix(_1,g(_1)) :-
g(_1).
g((fix(_1,g(_1)):-g(_1))).
yes
| ?-
The drawback of the program is that it accepts not only itself
but also every instance of itself. The second program is without
this disadvantage:
fix( X, (g(X,Y):-Y) ) :- g( X, Y ).
g(
( fix( X, (g(X,Y):-Y) ) :- g( X, Y ) ),
( var( X ), var( Y ), X\==Y )
) :- var( X ), var( Y ), X\==Y.
Here is an execution trace for the second program:
| ?- fix( X, Y ).
X = (fix(_163,(g(_163,_164):-_164)):-g(_163,_164)),
Y = (g((fix(_163,(g(_163,_164):-_164)):-g(_163,_164)),
(var(_163),var(_164),_163\==_164)):-var(_163),var(_164),_163\==_164)
yes
| ?- listing.
fix(_1,(g(_1,_2):-_2)) :-
g(_1,_2).
g((fix(_1,(g(_1,_2):-_2)):-g(_1,_2)),(var(_1)','var(_2)','_1\==_2)) :-
var(_1),
var(_2),
_1\==_2.
yes
-- Wlodek Drabent
------------------------------
Date: 31 Aug 86 12:24:39 GMT
From: Ran Ever-Hadani <techunix.BITNET!raan@ucbvax.Berkeley.EDU>
Subject: Answer to fixed-points query
In pure Prolog, it is not possible to construct a single clause,
self/1 with non-empty body that yields any answer to a query; it can
either fail or go into infinite loop. If the clause is Head:-Body
then the initial goal is Head, and no reduction can ever produce the
empty goal.
self/1 with no body is also not possible, since it will have to
contain itself.
The solution below is a procedure is self/2, which contains two
clauses and is true when fed these clauses as parameters.
self(Y,self(Y,0)) :- self(Y,0).
self((self(Y,self(Y,0)):-self(Y,0)),0).
This it not perfect, since if we ask ?- self(A,B). then apart from
A=.. clause1 .. B=.. clause2 .. which is the sollution we want,
we also get A=.. clause1 .. B=0 (by unifying directly to clause2).
This can only be avoided using a cut (which is not pure Prolog) as
shown in a slightly different version of self/2 below:
Script started on Sun Aug 31 14:58:20 1986
% cprolog
C-Prolog version 1.4a
| ?- [user].
|
| self(Y,self(Y,0)) :- self(Y,0), !.
|
| self((self(Y,self(Y,0)):-self(Y,0),!),0).
| ^D
user consulted 416 bytes 0.116667 sec.
yes
| ?- self(A,B).
A = self(_9,self(_9,0)):-self(_9,0),!
B = self((self(_9,self(_9,0)):-self(_9,0),!),0) ;
no
| ?- ^D
[ Prolog execution halted ]
%
Script done on Sun Aug 31 14:59:33 1986
-- Ran Ever-Hadani
------------------------------
End of PROLOG Digest
********************