lang@bigburd.UUCP (04/03/87)
I have a few comments to make about the various solutions to the two control structure problems that were posted by Jan Chomickia while back. I am the original source of these problems. The problem with most (all?) of the solutions that I have seen to the xor problem is the following: One easy way to write xor is something like xor(Goal1,_) :- call(Goal1). xor(Goal1,Goal2) :- \+ Goal1, call(Goal2). The problem with this solution is that if Goal1 does not succeed, it has to be called twice before trying Goal2, and, in our application, this is computationally prohibitive. As for the P :- A, B, C, D. problem, I didn't make this clear in my original posting, but I do want to allow multiple solutions of B. I hope this helps. ---------------------------------------------------------------------------- Francois-Michel Lang Daytime phone: (215) 648-7490 Paoli Research Center, Unisys Corporation lang@bigburd.PRC.unisys.COM Dept of Comp. & Info Science, U of PA lang@cis.upenn.edu ----------------------------------------------------------------------------
wup@rpics.UUCP (04/06/87)
Concerning xor(G1,G2)... A "logic programming" approach is xor(G1,G2) :- G1,not(G2). xor(G1,G2) :- not(G1),G2. To be efficient in computation, one may want to be somewhat imperative in the "programming", I propose the following... xor(G1,G2) :- not(G1),G2. xor(G1,_) :- G1. This takes into account the possible "side effects" G1 and G2 may have. Peter Y.F. Wu wup@csv.rpi.edu
micha@ecrcvax.UUCP (04/06/87)
From the efficiency point of view, a solution with nonstandard cuts (see Lee's note) is the best one, I even think that it is not too complicated to include the soft cut into WAM, if one has the source of the system (this is however rarely the case). When it is too expensive to repeat the execution, the only remaining possibilities are assert or record or a special cut (I guess that the strings proposed by Jan Chomicki are slightly less efficient than assert). The second predicate is more general than the first one: for the xor/2 predicate it is enough to get rid of one choice point, for the other it is necessary to erase several successive choice points which are not at the stack top. (Btw, this is yet another reason to split the environment and choice point stack, it is then easier and the space can be better reclaimed.) There was a concept of remote cuts which allows to mark a place and then to cut all choices up to this point; this, however works only when thay are at the stack top. So the most efficient thing here would be a generalized structure which marks the beginning and the end of an area and then performs the cut, the default for the end being the stack top. With this one the two problems could be rewritten as xor(A, B) :- cutstart(label), xor1(A, B). xor1(A, _) :- cutend(label), call(A), cut(label). xor1(_, B) :- call(B). P :- cutstart(label), A, cutend(label), B, cut(label), C, D. Note that the xor/2 does not seem to be very straightforward, however the auxiliary procedure does not slow it down. This primitive is really powerful, all the cut types can be defined using it (although some of them not quite easy): usual cut: p(X) :- ..., !, ... p(X) :- cutstart(label), p'(X). p'(X) :- ..., cut(label), ... soft cut: p(X) :- ..., softcut, ... p(X) :- cutstart(label), p'(X). p'(X) :- cutend(label), ..., cut(label), ... Keith Hughes' snips: p(X) :- ..., [! A, B, C !], ... p(X) :- ..., cutstart(label), A, B, C, cut(label), ... remote cut: p(X) :- ..., mark(label), ... q(Y) :- ..., cut(label), ... p(X) :- ..., cutstart(label), ... q(Y) :- ..., cut(label), ... The exact semantics, mainly concerning backtracking and label management would have to be polished as well as the syntax. The question is now, is it useful/necessary/sound to include such a primitive into Prolog? It does not seem to be more nonlogical than the usual cut and as we have seen, there really are cases where it would be useful (Francois-Michel, I'm sorry that this is of no use for you now). --Micha
bd@zyx.UUCP (Bjorn Danielsson) (04/08/87)
In article <276@ecrcvax.UUCP> mcvax!unido!ecrcvax!micha (Micha Meier) writes: >From the efficiency point of view, a solution with nonstandard cuts >(see Lee's note) is the best one, ... I suggest a somewhat simpler (and less general) syntax for delayed cuts: delayed_cut(Goal) should work just like ordinary cut, except that the actual cutting is delayed until Goal has succeeded. P :- A,!,B. would be the same as P :- A,delayed_cut(true),B. P :- A,soft_cut,B. would be the same as P :- delayed_cut(A),B. The solutions to Francois-Michel Lang's problems would be: xor(A,B) :- delayed_cut(A) ; B. P :- A, delayed_cut(B), C, D. % Assuming P has no more clauses. -- Bjorn Danielsson, ZYX, +46 8 653205, ...mcvax!enea!zyx!bd