chomicki@topaz.UUCP (03/31/87)
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.edudebray@arizona.UUCP (04/02/87)
Regarding the probloems posed by chomicki@topaz.RUTGERS.EDU (Jan Chomicki): > 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. > Assuming no side effects, the following works on most Prologs: xor(G1,G2) :- not(not(call(G1))) -> call(G1) ; call(G2). > 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. > Again, assuming no side effects, the following will work on most Prologs: P :- ( not(not( (A,B) )) -> (A -> B) ; (A, B) ), C, D. A comment in passing regarding these solutions and something the original poster said: > 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. Apparently a lot of people have a tendency to resort to "assert" or "record" at the drop of a hat (I can see complaints that my solutions above compute the first solution twice: once in the satisfiability test not(not( ... )), once in the actual call). What's often ignored is that "assert" and "record" are *expensive*, and may end up being costlier than recomputing the solutions. I, personally, have found only two or three situations where I'd say "assert" was really necessary. I think a little more care in coding could in most cases result in code which, in avoiding asserts, would improve in speed, understandability _and_ portability. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray
debray@arizona.UUCP (04/02/87)
I'd proposed the following solutions to Chomicki's problems: > Assuming no side effects, the following works on most Prologs: > > (1) xor(G1,G2) :- not(not(call(G1))) -> call(G1) ; call(G2). > > (2) P :- ( not(not( (A,B) )) -> (A -> B) ; (A, B) ), C, D. > The following simplifications should now be obvious: (1) xor(X,Y) :- not(call(X)) -> call(Y) ; call(X). (2) P :- ( not( (A -> B) ) -> (A, B) ; (A -> B) ), C, D. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray
lee@mulga.UUCP (04/02/87)
In article <10588@topaz.RUTGERS.EDU> chomicki@topaz.RUTGERS.EDU (Jan Chomicki) writes: >From: Francois-Michel Lang <lang%omega.PRC.Unisys.COM@cis.upenn.edu> >Any ideas about how to hack either of these? > >1. A predicate xor(G1,G2) You need "soft cut" for this: xor(G1, _) :- call(G1), $soft_cut. % (this is what its called in MU-Prolog) xor(_, G2) :- call(G2). When soft cut is called, it removes the choice point of the parent call (xor in this case) but no others. It is pretty easy to implement this when you are writing a Prolog system, but difficult afterwards. It is not a standard construct and has no standard name. I'm not sure how many Prolog systems have it. It is useful for a version of "if" which can return multiple answers to the condition (see L. Naish, "Negation and Quantifiers in NU-Prolog", 3rd ICLP, 1986). For this reason, NU-Prolog and recent versions of MU-Prolog have soft cut implemented internally. I guess LM-Prolog does also, since it has a retrying version of "if". >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. P :- A, B, !, C, D. % if there are no more clauses, or P :- once (A, B), C, D. % if you Prolog system has once/1 Does what you said. It also prevents multiple solutions to B, which you may want (this was not said in the original posting). If you dont want to remove choice point from the execution of B, I cant think of how to do it in Prolog systems I know of (ancestor cut is not flexible enough). Lee Naish CSNET: lee@mulga.oz ARPA: munnari!lee@seismo UUCP: {seismo,mcvax,ukc,prlb2,ubc-vision}!munnari!lee {decvax,vax135,eagle,pesnta}!mulga!lee
wagner@iaoobelix.UUCP (04/02/87)
/***** iaoobelix:comp.lang.pro / topaz!chomicki / 5:28 pm Mar 31, 1987*/ > 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 ... > 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 The above `xor' predicate seems to be identical with something called `default(X,Y)' (if I remember it right) available in Prolog-II. `default(X,Y)' behaves like X if there is at least one solution for X, otherwise it behaves like Y. There are some other Prologs implementing this (e.g I saw one on the Macintosh). Juergen Wagner, USENET: ...seismo!unido!iaoobel!wagner ("Gandalf") or ...!pyramid!iaoobel!wagner Mail: Juergen Wagner Fraunhofer-Institut IAO Rosenbergstr. 28 D-7000 Stuttgart 1 Federal Republic of Germany Phone: + 49 711 6648-205
jo@epistemi.UUCP (04/02/87)
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
micha@ecrcvax.UUCP (04/02/87)
Both of the required predicates can be defined using one predicate succeeds(X) that succeeds if X does, without binding variables and leaving choice points (if X has some side effects, I doubt you can define it without assert). The xor(A, B) can be defined as xor(A, _) :- succeeds(A), !, A. xor(_, B) :- B. and the other one P :- A, succeeds(B), !, B, C, D. Not to forget the definition of succeeds/1: succeeds(X) :- not(not(X)). or alternatively succeeds(X) :- replace_vars(X, Y), Y, !. where replace_vars(X, Y) makes a copy of X with fresh variables. This has, of course the disadvantage that the predicate is called twice, first in succeeds(X) and then the proper call, the problem is similar to writing setof/3 in pure Prolog - you can make it but it is not very efficient. --Micha
schaefer@ogcvax.UUCP (04/03/87)
In article <ecrcvax.275> mcvax!unido!ecrcvax!micha (Micha Meier) writes: >[...] >Not to forget the definition of succeeds/1: > succeeds(X) :- not(not(X)). >or alternatively > succeeds(X) :- replace_vars(X, Y), Y, !. >where replace_vars(X, Y) makes a copy of X with fresh variables. >[...] >--Micha The replace_vars predicate can be implemented as: replace_vars(X,Y) :- copy1(X,Y,T), !. copy1(X,Y,Tbl) :- var(X), member((X,Y),Tbl). copy1(X,X,Tbl) :- atomic(X). copy1([H|T],[H1|T1],Tbl) :- copy1(H,H1,Tbl), copy1(T,T1,Tbl). copy1((F,S),(F1,S1),Tbl) :- copy1(F,F1,Tbl), copy1(S,S1,Tbl). copy1(X,Y,Tbl) :- not atomic(X), X =.. [F|R], copy1(R,R1,Tbl), Y =.. [F|R1]. member((X,Y),[(X1,Y)|R]) :- X == X1. member(E,[E1|R]) :- var(E1), E1 = E. member(E,[_|R]) :- member(E,R). -- Bart Schaefer Dept. of CS&E CSNET: schaefer@Oregon-Grad Oregon Graduate Center UUCP: {ihnp4,seismo,sun}!verdix \ 19600 NW Von Neumann Dr {hplabs,ucbvax,decvax}!tektronix !ogcvax!schaefer Beaverton, OR 97006
bd@zyx.UUCP (04/04/87)
In article <10588@topaz.RUTGERS.EDU> chomicki@topaz.RUTGERS.EDU (Jan Chomicki) writes: >From: Francois-Michel Lang <lang%omega.PRC.Unisys.COM@cis.upenn.edu> > >Any ideas about how to hack either of these? > >1. A predicate xor(G1,G2) which has the following behavior: > (...) A "real" exclusive-or should be equivalent to: G1, not(G2) ; not(G1), G2. The xor defined in the question is rather like: G1 ; \+ G1, G2. So one solution is: xor(G1,G2) :- G1 ; \+ G1, G2. This has the disadvantage that G1 is called twice. A more efficient solution is possible if (as Lee Naish pointed out) you have a retrying "if": xor(G1,G2) :- if(G1, true, G2). % if G1 then true else G2 >2. Given a predicate > > P :- A, B, C, D. > > Is it possible to rewrite P to obtain the following behavior: > (...) 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. Assuming that P has no more clauses, a possible solution might be: P :- A(X), B(X,_), !, B(X,Y), C, D. The variable X represents the solutions of A. Here too we have the disadvantage that B is called twice. We also have the requirement that the variables that represent the solutions of B for a given solution of A are easily identifiable. This may or may not be the case. -- Bjorn Danielsson, ZYX, +46 8 653205, ...mcvax!enea!zyx!bd