lee@mulga.oz (Lee Naish) (04/29/88)
In article <2217@ubc-cs.UUCP> voda@ubc-cs.UUCP (Paul Voda) writes: > >The one-solution construct in Trilogy is a tame version of the >cut of Prolog. >... until now I could not explain it logically >I have written a paper... I would like a copy. NU-Prolog has a logical one solution construct - existential quantification (see "Negation and Quantifiers in NU-Prolog", 3rd ICLP). The example I normally give is the following: connected(A, B) :- some Path path(A, B, Path). It states that two nodes are connected if there is some path between them. If A and B are ground at the time of the call, the effect is the same as once (it succeeds at most once, even if there are multiple paths between the two nodes). If A or B are not ground, "some Path" has no effect (all possible answers are returned). NU-Prolog also has a non-logical version of some which allows you to get the value of Path back. The particular path which is returned depends on the order in which clauses and subgoals are selected (and perhaps communication delays in a parallel system). I agree with Richard that a construct returning a/any/some solution if preferable to one which must return the first solution (which is a procedural concept). This form of one solution construct is useful whe you know that a predicate has only one solution when called in a particular mode: sort(L, Sorted) :- gSome Sorted (perm(L, Sorted), sorted(Sorted)). Another thechnique which people I think people use (sometimes unconciously) is to push existential quantification inside a computation. Suppose we start with the following predicate for finding the sum of elements in two lists (merge returns any merging of the two input lists). We know the sum is deterministic (hence the use of gSome) and we dont care about which merged list we get (hence the use of some). sum_lists(L1, L2, Total) :- gSome Total some L (merge(L1, L2, L), sum_list(L, Total)). Its possible to push the quantification inwards, since sum_list is deterministic and, more importantly, always succeeds: sum_lists(L1, L2, Total) :- gSome L merge(L1, L2, L), sum_list(L, Total). An advantage of this is that the choice points which merge creates are destroyed sooner. It is possible to push the "quantification" further inside merge, turning it into the familiar "don't care nondeterministic" version. The behaviour is the same, but choice points are removed almost as soon as they are created. This means less memory is used and there is more scope for parallelism. This brings us back to determinism... Determinism and modes are pretty closely linked. Given that you want something to be deterministic, you can sometimes restrict the modes to ensure it is (this can be useful for parallelism or coroutines). For conventional Prolog, I cant see much use in a "deterministic" declaration which does not give modes. Inferring determinism from modes is useful for changing the control component of programs. Also, given mode information, its possible to make things "more deterministic". Pushing gSome can be seen as one case of this, since gSome implicitly gives modes. Debray has done work on analysing modes and using if-then-else instead of multiple clauses and I have a tech report "Parallelizing NU-Prolog" which is also related. Lee Naish Department of Computer Science Melbourne University Parkville 3052 Australia