What is a "Test succeeded with choicepoint" warning in PL-Unit, and how do I fix it?

Question

I'm writing a prolog program to check if a variable is an integer. The way I'm "returning" the result is strange, but I don't think it's important for answering my question.

The Tests

I've written passing unit tests for this behaviour; here they are...

foo_test.pl

:- begin_tests('foo').
:- consult('foo').

test('that_1_is_recognised_as_int') :-
    count_ints(1, 1).

test('that_atom_is_not_recognised_as_int') :-
    count_ints(arbitrary, 0).

:- end_tests('foo').
:- run_tests.

The Code

And here's the code that passes those tests...

foo.pl

count_ints(X, Answer) :-
  integer(X),
  Answer is 1.

count_ints(X, Answer) :-
  \+ integer(X),
  Answer is 0.

The Output

The tests are passing, which is good, but I'm receiving a warning when I run them. Here is the output when running the tests...

?- ['foo_test'].
%  foo compiled into plunit_foo 0.00 sec, 3 clauses
% PL-Unit: foo 
Warning: /home/brandon/projects/sillybin/prolog/foo_test.pl:11:
        /home/brandon/projects/sillybin/prolog/foo_test.pl:4:
        PL-Unit: Test that_1_is_recognised_as_int: Test succeeded with choicepoint
. done
% All 2 tests passed
% foo_test compiled 0.03 sec, 1,848 clauses
true.

• I'm using SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
• I have tried combining the two count_ints predicates into one, using ;, but it still produces the same warning.
• I'm on Debian 8 (I doubt it makes a difference).

The Question(s)

• What does this warning mean? And...
• How do I prevent it?

Answer 1

First, let us forget the whole testing framework and simply consider the query on the toplevel:

?- count_ints(1, 1).
true ;
false.

This interaction tells you that after the first solution, a choice point is left. This means that alternatives are left to be tried, and they are tried on backtracking. In this case, there are no further solutions, but the system was not able to tell this before actually trying them.

Using all/1 option for test cases

There are several ways to fix the warning. A straight-forward one is to state the test case like this:

test('that_1_is_recognised_as_int', all(Count = [1])) :-
    count_ints(1, Count).

This implicitly collects all solutions, and then makes a statement about all of them at once.

Using if-then-else

A somewhat more intelligent solution is to make count_ints/2 itself deterministic!

One way to do this is using if-then-else, like this:

count_ints(X, Answer) :-
        (   integer(X) -> Answer = 1
        ;   Answer = 0
        ).

We now have:

?- count_ints(1, 1).
true.

i.e., the query now succeeds deterministically.

Pure solution: Clean data structures

However, the most elegant solution is to use a clean representation, so that you and the Prolog engine can distinguish all cases by pattern matching.

For example, we could represent integers as i(N), and everything else as other(T).

In this case, I am using the wrappers i/1 and other/1 to distinguish the cases.

Now we have:

count_ints(i(_), 1).
count_ints(other(_), 0).

And the test cases could look like:

test('that_1_is_recognised_as_int') :-
    count_ints(i(1), 1).

test('that_atom_is_not_recognised_as_int') :-
    count_ints(other(arbitrary), 0).

This also runs without warnings, and has the significant advantage that the code can actually be used for generating answers:

?- count_ints(Term, Count).
Term = i(_1900),
Count = 1 ;
Term = other(_1900),
Count = 0.

In comparison, we have with the other versions:

?- count_ints(Term, Count).
Count = 0.

Which, unfortunately, can at best be considered covering only 50% of the possible cases...

Tighter constraints

As Boris correctly points out in the comments, we can make the code even stricter by constraining the argument of i/1 terms to integers. For example, we can write:

count_ints(i(I), 1) :- I in inf..sup.
count_ints(other(_), 0).

Now, the argument must be an integer, which becomes clear by queries like:

?- count_ints(X, 1).
X = i(_1820),
_1820 in inf..sup.

?- count_ints(i(any), 1).
ERROR: Type error: `integer' expected, found `any' (an atom)

Note that the example Boris mentioned fails also without such stricter constraints:

?- count_ints(X, 1), X = anything.
false.

Still, it is often useful to add further constraints on arguments, and if you need to reason over integers, CLP(FD) constraints are often a good and general solution to explicitly state type constraints that are otherwise only implicit in your program.

Note that integer/1 did not get the memo:

?- X in inf..sup, integer(X).
false.

This shows that, although X is without a shadow of a doubt constrained to integers in this example, integer(X) still does not succeed. Thus, you cannot use predicates like integer/1 etc. as a reliable detector of types. It is much better to rely on pattern matching and using constraints to increase the generality of your program.

Answer 2

First things first: the documentation of the SWI-Prolog Prolog Unit Tests package is quite good. The different modes are explained in Section 2.2. Writing the test body. The relevant sentence in 2.2.1 is:

Deterministic predicates are predicates that must succeed exactly once and, for well behaved predicates, leave no choicepoints. [emphasis mine]

What is a choice point?

In procedural programming, when you call a function, it can return a value, or a set of values; it can modify state (local or global); whatever it does, it will do it exactly once.

In Prolog, when you evaluate a predicate, a proof tree is searched for solutions. It is possible that there is more than one solution! Say you use between/3 like this:

For x = 1, is x in [0, 1, 2]?

?- between(0, 2, 1).
true.

But you can also ask:

Enumerate all x such that x is in [0, 1, 2].

?- between(0, 2, X).
X = 0 ;
X = 1 ;
X = 2.

After you get the first solution, X = 0, Prolog stops and waits; this means:

The query between(0, 2, X) has at least one solution, X = 0. It might have further solutions; press ; and Prolog will search the proof tree for the next solution.

The choice point is the mark that Prolog puts in the search tree after finding a solution. It will resume the search for the next solution from that mark.

The warning "Test succeeded with choicepoint" means:

The solution Prolog found was the solution the test expected; however, there it leaves behind a choice point, so it is not "well-behaved".

Are choice points a problem?

Choice points you didn't put there on purpose could be a problem. Without going into detail, they can prevent certain optimizations and create inefficiencies. That's kind of OK, but sometimes only the first solution is the solution you (the programmer) intended, and a next solution can be misleading or wrong. Or, famously, after giving you one useful answer, Prolog can go into an infinite loop.

Again, this is fine if you know it: you just never ask for more than one solution when you evaluate this predicate. You can wrap it in once/1, like this:

?- once( between(0, 2, X) ).

or

?- once( count_ints(X, Answer) ).

If someone else uses your code though all bets are off. Succeeding with a choice point can mean anything from "there are other useful solutions" to "no more solutions, this will now fail" to "other solutions, but not the kind you wanted" to "going into an infinite loop now!"

Getting rid of choice points

To the particular example: You have a built-in, integer/1, which will succeed or fail without leaving choice points. So, these two clauses from your original definition of count_ints/2 are mutually exclusive for any value of X:

count_ints(X, Answer) :-
  integer(X), ...

count_ints(X, Answer) :-
  \+ integer(X), ...

However, Prolog doesn't know that. It only looks at the clause heads and those two are identical:

count_ints(X, Answer) :- ...

count_ints(X, Answer) :- ...

The two heads are identical, Prolog doesn't look any further that the clause head to decide whether the other clause is worth trying, so it tries the second clause even if the first argument is indeed an integer (this is the "choice point" in the warning you get), and invariably fails.

Since you know that the two clauses are mutually exclusive, it is safe to tell Prolog to forget about the other clause. You can use once/1, as show above. You can also cut the remainder of the proof tree when the first argument is indeed an integer:

count_ints(X, 1) :- integer(X), !.
count_ints(_, 0).

The exactly same operational semantics, but maybe easier for the Prolog compiler to optimize:

count_ints(X, Answer) :-
    (   integer(X)
    ->  Answer = 1
    ;   Answer = 0
    ).

... as in the answer by mat. As for using pattern matching, it's all good, but if the X comes from somewhere else, and not from the code you have written yourself, you will still have to make this check at some point. You end up with something like:

variable_tagged(X, T) :-
    (   integer(X) -> T = i(X)
    ;   float(X)   -> T = f(X)
    ;   atom(X)    -> T = a(X)
    ;   var(X)     -> T = v(X)
    % and so on
    ;   T = other(X)
    ).

At that point you can write your count_ints/2 as suggested by mat, and Prolog will know by looking at the clause heads that your two clauses are mutually exclusive.

I once asked a question that boils down to the same Prolog behaviour and how to deal with it. The answer by mat recommends the same approach. The comment by mat to my comment below the answer is just as important as the answer itself (if you are writing real programs at least).