Why the answer contains a `false`?

Help! Predicate
,
1

My SWI-Prolog knowledge base contains the following three facts:

data(catalog1, mike, deposit, 100).
data(catalog1, bob, deposit, 150).
data(catalog2, mike, deposit, 200).

The query is:

?- data(catalog1, mike, deposit, X).
X = 100 ;
false.

The 1st question:

Why the answer contains a false ? It seems that SWI-Prolog leaves a choice point, but I don’t know where it is. I can use ?- data(catalog1, mike, deposit, X), ! to workaround, but is this necessary?

Also, an interesting fact is that if I remove the 2nd or 3rd fact, then it’s OK.

data(catalog1, mike, deposit, 100).
data(catalog1, bob, deposit, 150).

?- data(catalog1, mike, deposit, X).
X = 100.

data(catalog1, mike, deposit, 100).
data(catalog2, mike, deposit, 200).

?- data(catalog1, mike, deposit, X).
X = 100.

P.s. There is a similar question on stackoverflow, but I can’t reproduce that problem in current SWI-Prolog v8.4.1.

The 2nd question:

For a knowledge base like the above, is it necessary to always create a auxiliary predicate to get value (as a Prolog convention) ?

For example,

data_deposite_get(Catalog, Person, Deposit) :-
   data(Catalog, Person, deposit, Deposit), !.

?- data_deposite_get(catalog1, mike, X).
X = 100.

Thanks.

2

Related: How to find unexpected choicepoints?

Can prevent unwanted backtracking with:

once(data(catalog1, mike, deposit, X)).

That data_deposite_get/3 is probably useful, but not necessary.

1 Like
3

I think prolog false means just no more solution remains, at least, for the query.

2 Likes
4

I think the OP’s main question refers to the choice point. However, I cannot reproduce one of the examples. If I remove the 2nd clause,

data(catalog1, mike, deposit, 100).
% data(catalog1, bob, deposit, 150).
data(catalog2, mike, deposit, 200).

I don’t get a semicolon. So I think everything is fine. The behavior is consistent with “first-argument-indexing”.

5

Fact indexing can be subtle: First-argument indexing - not taking effect

Just to confirm, the false just means “no further solutions found”, after checking for further solutions.

1 Like
6

First-argument indexing

@mgondan1 @brebs

Thank you for telling me this keyword, which is exactly what I am looking for.

I will look into it.

7

SWI-Prolog’s indexing is described here: SWI-Prolog -- Manual Note that this is not set in stone. The only “portable” indexing is on the first argument for integers, atoms and terms (terms based on the name and arity (number of arguments). SWI-Prolog does more and will likely do even more in the future. So, maybe future versions will make such calls deterministic.

2 Likes
8

Just watched a nice video on Youtube Argument Indexing in Prolog - YouTube which introduced many techniques to avoid choice point and guarantee complete generality and deterministic when possible.

9

There are different choice points though, arising by different mechanisms and with varying levels of the annoyance factor.

I noticed you liked an old post of mine. There, the premise is, I know I am writing “procedural” or “functional” code in Prolog and if there is a choice point, I probably messed up somewhere during the coding.

A completely different case is something like:

?- member(a, [a, b]).
true ;
false.

Here, the choice point is benign and unless you do something very funky, it won’t change the meaning of your program. Additionally, avoiding such choice points easily becomes a tar pit of wasted effort.

And to correct a misunderstanding, by just repeating the comment by @kuniaki.mukai : there is no “false” in any answer. On the top level (interactive by design!) you get “more solutions might be available” prompt, and when you ask, you get “no more solutions” as “false”. The solution does not contain “false”.

10

I wrote a Prolog program that avoids these benign choice points using cuts. In hindsight it was a total mistake, but as a noobie I didn’t understand the (lack of) consequences of these choice points.

Now that I am going back to this ~1.5 year old code I am considering putting in some time to cleanse my code of these cuts.

I do wish that SWI-Prolog’s tabling was able to prevent more of these useless choice points as it would have saved me from some confusion. Is there a trade-off in the tabling being more advanced?

11

You might want to try the new “single sided unification” (the => operator). Here’s a link to an example and also to the manual: Example of refactoring code to SSU

1 Like
12

I think there are two kinds of choice points:

  1. Benign choicepoints.
  2. Unnecessary choicepoints which can be avoided.

In your example, the choicepoint is benign, because the meaning of the built-in member/2 is that even if the X has been found, it will still keep looking for the next.

For example:

?- member(X, [a, b, a]).
X = a ;
X = b ;
X = a.

Notice that there are two X = a.

This is why ?- member(a, [a, b]). returns a false, because it attempts to looking for the next a.

Consider:

?- member(a, [a, b, a, c]).
true ;
true ;
false.

P.s. Someone might not like the built-in member/2 since the duplicate answers. Nevertheless, the member/2 is well-defined and it is logical pure.

However, there is the 2nd type of choicepoints (i.e. unnecessary choicepoints).

For example:

memberd(X, [E|Es]) :-
  (   X = E
  ;   dif(X, E),
      memberd(X, Es)
  ).

The meaning of the memberd/2 is that as soon as the X is found, the program terminates (no duplicates):

?- memberd(X, [a, b, a]).
X = a ;
X = b ;
false.

So ideally, ?- memberd(a, [a, b]). should return true., but

?- memberd(a, [a, b]).
true ;
false.

The false is due to an unnecessary choicepoint and it should be avoided.

For example,

:- use_module(library(reif)).
memberd(X, [E|Es]) :- 
  if_( X = E % (=)/3 
     , true
     , memberd(X, Es) 
     ). 

?- memberd(a, [a, b]).
true.

In the video of https://youtu.be/FZLofckPu4A (09:20), the author said that

Some optimizations are possible only if no choicepoints remain.
Example: tail call optimization

So ideally we should eliminate unnecessary choicepoint if it possible. The choicepoint (which causes false) in the topic thread is apparently unnecessary.

More details see: Indexing dif/2

Edit:

I said “the program terminates” which might be not precise, because X could be a variable. I mean that as soon as the X is found, the program won’t look for the next the same X (so no duplicates). For ?- member(a, [a, b])., we just consider X is ground, so the meaning is not changed.

13

You can get arbitrarily clever in detecting situations where choicepoints aren’t needed, but there’s an overheard for doing this check.
(I’m reminded of iterative deepening vs breadth-first search – iterative deepening repeats some computations but can be an overall win because of the book-keeping that’s avoided (depth-first also has low book-keeping overhead, but has the possibility of infinite loops) … but the choice between depth-first, breadth-first, iterative deepening, or other search strategies depends very much on the problem.)

14

Yes, I have seen those arguments before. Just remember that this takes lazy evaluation (through backtracking) and throws it away.

And yes, sometimes there is a conflict between backtracking and recursion. In practice I have noticed that it is usually straight-forward to resolve this conflict on a case-by-case basis. You can, after all, use conditionals and even a cut. At the very bottom of it, this is what the “indexing dif/2” paper does anyway.

15

I’ve bumped into this working with a fact database and wanting to assert that certain fact “prefixes” are unique. I was hoping (based on original example) that something like $(data(catalog1, mike, deposit, 100)) would work for this, but it fails with non determinism error. Is there a simpler way to achieve this than than having to count the solutions and asserting that count is 1?

16

$/1 asserts a goal leaves no choicepoint. That is stronger than a goal having only one answer. The quickest way to find goals with multiple answers is probably call_nth/2 as in

call_nth(Goal, 2).

If that succeeds, you have a problem :slight_smile: You may want to look at deterministic/1 as an early fast check. The docs suggests call_cleanup/2 as a more portable alternative. deterministic/1 is faster though.

17

Unique to what extent? :grinning:

E.g. is this acceptable or not:

my_silly_pred(X) :-
	member(X, [1, 1]).

Result:

?- my_silly_pred(X).
X = 1 ;
X = 1.

Could (maybe) call it unique, because:

?- setof(X, my_silly_pred(X), Xs).
Xs = [1].