🚀 go-pugleaf

I'm forwarding (with a permission from the originator) a message that
has been circulating by E-mail for some time. It looks like an
interesting challenge.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

From: Francois-Michel Lang <lang%omega.PRC.Unisys.COM@cis.upenn.edu>
Date: Tue, 17 Mar 87 17:05:54 EST

A number of us at SDC have been experimenting with some Prolog
control structures which we have so far been unable to implement
cleanly--i.e., without using the database.

Any ideas about how to hack either of these?

1. A predicate xor(G1,G2) which has the following behavior:
   First, goal G1 is called.
   If G1 succeeds, xor(G1,G2) succeeds, and can be re-satisfied
      on backtracking as often as G1 can be.  When G1 can't be
      re-satisfied, xor fails.
   If G1 fails, G2 is called.
   If G2 succeeds, xor(G1,G2) succeeds, and can be re-satisfied
      as often as G2 can be.

   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.


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.


These structures may seem a bit odd, but we do have a good reason
for wanting to use them!


If either of you has any ideas about these structures,
I'd love to hear about it, and so would the rest of us NL people!

--Francois

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Posted by:
-- 
Jan Chomicki (chomicki@aramis.rutgers.edu)	Phone: (201) 932-3999
Dept.of Computer Science, Rutgers University, New Brunswick, NJ 08903
Usenet: {...harvard,pyramid,seismo,nike}!rutgers!aramis!chomicki
Arpanet: chomicki@aramis.rutgers.edu