Prolog: How to tell if a predicate is deterministic or not

Question

So from what I understand about deterministic predicates:

Deterministic predicate = 1 solution

Non-deterministic predicate = multiple solutions

Are there any type of rules as to how you can detect if the predicate is one or the other? Like looking at the search tree, etc.

Answer 1

There is no clear, generally accepted consensus about these notions. However, they are usually based rather on the observed answers and not based on the number of solutions. In certain contexts the notions are very implementation related. Non-determinate may mean: leaves a choice point open. And sometimes determinate means: never even creates a choice point.

Answers vs. solutions

To see the difference, consider the goal length(L, 1). How many solutions does it have? L = [a] is one, L = [23] another... but all of these solutions are compactly represented with a single answer substitution: L = [_] which thus contains infinitely many solutions. In any case, in all implementations I know of, length(L, 1) is a determinate goal.

Now consider the goal repeat which has exactly one solution, but infinitely many answers. This goal is considered non-determinate.

In case you are interested in constraints, things become even more evolved. In library(clpfd), the goal X #> Y, Y #> X has no solution, but still one answer. Combine this with repeat: infinitely many answers and no solution.

Further, the goal append(Xs, Ys, []) has exactly one solution and also exactly one answer, nevertheless it is considered non-determinate in many implementations, since in those implementations it leaves a choice point open.

In an ideal implementation, there would be no answers without solutions (except false), and there would be non-determinism only when there is more than one answer. But then, all of this is mostly undecidable in the general case.

So, whenever you are using these notions make sure on what level things are meant. Rather explicitly say: multiple answers, multiple solutions, leaves no (unnecessary) choice point open.