Why is the behaviour of SWI-Prolog seemingly inconsistent?

1
votes

Trying to understand the cut-fail combination in Prolog, I found the following example and started to play with it:

enjoys(vincent,X)  :-  big_kahuna_burger(X),!,fail. 
enjoys(vincent,X)  :-  burger(X). 

burger(X)  :-  big_kahuna_burger(X). 
burger(X)  :-  big_mac(X). 
burger(X)  :-  whopper(X). 


big_kahuna_burger(b). 
big_mac(a).  
whopper(d).

I've tried two different queries.

In query 1: enjoys(vincent,b), the result is that SWI-Prolog outputs false which is the expected behavior and it stops, doesn't ask me whether I want for it to search for more solutions.

In query 2: enjoys(vincent,a), first SWI-Prolog outputs true which again is expected, but then it gives me the option to click "next" and it tries to find another solution, then outputs false.

Why did it give me the option to check for another solution during the second query but not in the first one?

2
prologprolog-toplevel
If it returns false, that means it exhaustively searched, so that means in no way there is a solution, hence after a false, no solutions can be found anymore. - Willem Van Onsem
Then why didn't it return false in the frist query also? - BarbuDorel
false is not a solution, false means it did an exhaustive search, and failed to find anything. Most Prolog systems print false (or no) to show that the query has ended. - Willem Van Onsem
In the first example, since there are no solutions, it has no reason to prompt you to search further. It's already determined there are no solutions. In the second example, the successful logic path that finds a solution leaves a choice point which is a point in the rules in which Prolog can continue exploring to find additional solutions. Not finding any further solutions, it says "false". - lurker
@marc-s I had to rollback your edit because besides fixing one trivial typo it broke the question in several ways. Prolog does not "return" options as part of its query user interactions, it indeed "gives" them to users, just like the OP initially wrote. It's best to not interfere in situations where you're not sufficiently equipped to judge the outcome, wouldn't you agree? For instance I'd never attempt to improve any semi-coherent post in e.g. sql-server tag, ever. Cheers. - Will Ness

2 Answers

3
votes

In short: because false means that after an exhaustive search, no (extra) solutions could be found.

Why did it give me the option to check for another solution during the second query but not in the first one?

Because if it outputs false, that means it failed to find a solution after an exhaustive search. Hence it means "I did not find any solutions (anymore).". Therefore after a false, it makes no sense to search for extra solutions.

In case it proposes a solution however, that does not (per se) means that all solutions are exhausted. So it can propose extra solutions. Depending on the optimizations the Prolog interpreter has, it sometimes can know in advance that there are no extra solutions. If that is not the case, it thus prints the solution, and then pauses. The user can then request extra solutions.

For example if we write:

foo(a, 1).
foo(a, 2).
foo(b, 3).
foo(c, 4).

then querying with foo(b, 3) will, in SWI-Prolog at least, and in probably most interpreters, only say true, and then know that it is done. Because SWI-Prolog will analyze the functor/constant of the first argument, and thus knows in advance that, if the first argument is grounded, there are no other foo/2s with b as first argument.

1
votes

Your first query hits the cut, which signals to Prolog to abort any further attempts at searching for solutions. Then it hits false which makes the query fail and report false to the user, and then since the cut has already pruned all possibility for further search, Prolog stops.

An unsophisticated implementation could very well attempt a search after the cut, even if futile, only to just immediately discover the cut on backtracking, and then finally stop.

In your second query, big_kahuna_burger(a) fails, and the cut is avoided. The future search space isn't pruned.

burger(a)  :-  big_kahuna_burger(a).

fails, but

burger(a)  :-  big_mac(a).

succeeds, and there's still

burger(a)  :-  whopper(a).

to try.

So Prolog fully expects a possibility to find some if it searches some more. Just like our "unsophisticated" implementation would do even in the first case.

To stop there would require of the implementation to look ahead and check future outcomes in advance, detecting that whopper(a) is indeed destined to fail. But this is too costly to do always, and is done only in few very specific cases, if any.

I think this is referred to as "indexing". Searching for "indexing Prolog" gives quite a few hits.