lee@mulga.oz (Lee Naish) (03/17/88)
In article <1798@sics.se> seif@sics.se (Seif Haridi) writes: > >if(+P,+Q,+R) is similar to (P -> Q ; R) construct except that it allows the >generation of all possible solutions for P. Several Prologs have similar constructs and I think all Prologs *should*. From a logical point of view, quite often we want to do something like some X (p(X, Y), q(X, Z)) ; (not some X p(X, Y), r(Z)) The standard (p(X, Y) -> q(X, Z) ; r(Z)) doesnt work because some solutions to the first disjunct may be lost (it may also bind Y, cutting off the second disjunct when it shouldn't). A solution to the first problem is to use (\+ p(X, Y) -> r(Z) ; p(X, Y), q(X, Z)) Unfortunately, this calls p/2 twice. In NU-Prolog, you can write (if some X p(X, Y) then q(X, Z) else r(Z)) This can return multiple answers to p/2 (without calling it twice) and also delays until Y is ground (solving the second problem). How is it implemented? Not with any destructive assignment. It is translated into a call to xyzzy(Y, Z), where xyzzy/2 is defined as follows (more or less): ?- xyzzy(Y, _Z) when ground(Y). % delay until Y is ground xyzzy(Y, Z) :- p(X, Y), $soft_cut, q(Y, Z). xyzzy(Y, Z) :- r(Z). Soft cut removes the choice point for xyzzy but does not touch choice points created by the execution of p. It is as easy to implement as cut, if not easier. If the quantified variable, X, did not occur in the "then" part, normal cut could be used instead of soft cut. This is discussed in Naish, L., "Negation and Quantifiers in NU-Prolog", Proceedings Third ICLP, London, LNCS 225, Springer. While I am on the subject, I may as well launch into some "random musings, part 1". <<REST HERE IF TIRED>> Its a pity cut was ever invented. It combines two operations which should be separate. They are soft cut (clobbers the parent choice point) and the "once" construct of DEC-10 (which clobbers all choice points created by the execution of a call). p :- q, r, !, s. is equivalent (exactly) to p :- once (q, r), soft_cut, s. Why should the two operations be separated? * Soft cut is for negation. * Once is for existential quantification. For example, if we assume that the first argument of p/2 is ground at the time of calling (we could ensure this by delaying, testing, compile time analysis, or praying very hard) p(X, Y) :- once q(X, Z), r(X, Y). p(X, Y) :- s(X, Y). is a correct implementation of p(X, Y) :- some Z q(X, Z), r(X, Y). p(X, Y) :- s(X, Y). and p(X, Y) :- q(X, Z), soft_cut, r(X, Y). p(X, Y) :- s(X, Y). is a correct implementation of p(X, Y) :- q(X, Z), r(X, Y). p(X, Y) :- all Z not q(X, Z), s(X, Y). Thats enough for now. Stay tuned for part 2, which may mention commit, removing choice points as soon as possible and "semi-completeness" (defined in "Proving properties of committed choice logic programs", appearing in JLP some time). lee