🚀 go-pugleaf

In article <10588@topaz.RUTGERS.EDU> chomicki@topaz.RUTGERS.EDU 
(Jan Chomicki) quotes Francois-Michel Lang 
<lang%omega.PRC.Unisys.COM@cis.upenn.edu>:

>   In other words, xor(G1,G2) produces
>     -- all and only solutions of G1 if one exists, XOR
>     -- all and only solutions of G2 if one exists
>
>   The closest I've come to getting this one is 
>
>    my_xor(X,_) :-
>       call(X), !,
>       (true ; call(X)).
>    my_xor(_,Y) :- call(Y).
>
>    but the problem here is that backtracking into the first clause
>    won't recognize the first solution to the goal X.
>

The problem is worse than that.  Any instantiations which take place in
the first call(X) will persist after the cut.  These may be incompatible
with other solutions of X.  A better version might be:

my_xor(P, _) :-
	\+( \+( P )), !,
	call(P).
my_xor(_, P) :-
	call(P).

In this case, any instantiations within the goal P will be undone by the 
``double negation''.  

Alternatively one can copy the first goal, to ensure that no variable
in P is instantiated as a result of determining that the goal has at
least one solution;  i.e. replace the first clause by
my_xor(P, _) :-
	copy(P, NewP),
	call(NewP), 
	!,
	call(P).

where copy/2 could be
copy(X, _) :- assert(foo(X)), fail.
copy(_, Y) :- retract(foo(Y)).


Incidentally, prolog II has a built in procedure called, I think,
default/2, whose meaning is identical to my version of my_xor.  The
manual makes the mistake of claiming that ``default'' can't be
implemented using the control structures of prolog.  The example
here shows that it can be done, although somewhat inefficiently.

>
>2. Given a predicate
>
>      P :- A, B, C, D.
>
>   Is it possible to rewrite P to obtain the following behavior:
>   If the goal A initially succeeds, then
>      if B doesn't succeed, backtrack into A.  (This is quite normal.)
>   However, if A initially succeeds, and B does too,
>      then prevent backtracking into A.
>
>   In other words, if a given solution of A allows B to be solved,
>     then don't try to resatisfy A.
>   But if a given solution of A does not allow B to be solved,
>     then do try to resatisfy A.

The answer, due to Henk Zeevat (...!epistemi!henk), is very similar to
the last problem.  Basically we need to know that B has a solution, for
a given solution to A, but we don't in the first instance care what the
solution to B is.  So:

P :- A, \+( \+( B)), 
     !,
     B, C, D.

or equivalently

P :- copy(B, NewB),
     A, NewB,
     !,
     B, C, D.

Again, this suffers from a lack of efficiency, but seems to capture the
behaviour that you want.

Regards,

Jo

-- 
    ----------------------------------------------------------------------
    
    Jonathan Calder, University of Edinburgh, 
    		     Centre for Cognitive Science,
		     2 Buccleuch Place, 
		     Edinburgh, EH8 9LW,
		     Scotland
		     (+44) 31 667 1011 x6257

UUCP:    ...!ukc!cstvax!epistemi!jo
ARPA:	 jo%epistemi.ed.ac.uk@ucl.cs
JANET:	jo@ed.epistemi.ac.uk

Why don't we get together and form an institute