Prolog: how to determine if a predicate is deterministic or not

Question

So, from what I understand about deterministic predicates:

Deterministic predicate = 1 solution

Non-deterministic predicate = several solutions

Are there any rules regarding how you can determine if a predicate is one or the other? For example, looking at a search tree, etc.

Thanks a lot!

Answer 1

There is no clear, generally accepted opinion about these concepts. However, they are usually based more on the observed answers, rather than on the number of decisions. In certain contexts, concepts are very related to implementation. Uncertain may mean: leaves the selection point open. And sometimes certain means: they never even create a point of choice.

Answers and Decisions

To see the difference, consider the goal length(L, 1) . How many solutions does he have? L = [a] is one, L = [23] other ... but all these solutions are compactly represented using one answer substitution: L = [_] , which, therefore, contains infinitely many solutions. In any case, in all the implementations that I know of, length(L, 1) is the defining goal.

Now consider the goal of repeat , which has exactly one solution, but infinitely many answers. This goal is considered vague.

If you are interested in limitations, everything becomes even more developed. In library(clpfd) target X #> Y, Y #> X has no solution, but another answer. Combine this with repeat : infinitely many answers and no solution.

In addition, the append(Xs, Ys, []) target append(Xs, Ys, []) has exactly one solution, as well as exactly one answer, however, it is considered undefined in many implementations, since in these implementations it leaves an open choice point.

In an ideal implementation, there would be no answers without solutions (other than false ), and there would be no determinism if there were more than one answer. But then all this is in most cases insoluble.

So, whenever you use these concepts, make sure at what level things are meant. Rather, I will explicitly say: multiple answers, multiple solutions, do not leave (unnecessary) the choice point open.

Answer 2

You need to understand the difference between det, semidet and undet, this is more than just the number of solutions.

Since there is no loop control operator in Prolog, a loop (not recursion) is constructed as a sequence predicate (undet), and then the loop body. You can also store solutions with some findall-group predicates as a list and a loop later with the member / 2 predicate.

So, any part of your program is either part of a loop construct or part of a regular thread. Thus, there is a difference in the development of the predicates det and undet almost in the intended use. If you can work with a sequence, you can always turn it off and comment on it. There is a good extension of the unit test in the swi prolog that can verify that your predicate is always the same in the det / semidet / undet tool (semidet is used to use the same way as undet, but as the head of the "if" construct).

So, the difference is in the pre-project, and this question should not arise with existing predicates. It is good practice to always comment on the intended use in a comment, for example.

 % member(?El, ?List) is undet.