2

I (Prolog absolute beginner) try to make sense out of prolog. Here's a Santa example in swi-prolog:

gives(santa,leonard,book).
gives(santa,adrian,game).
gives(santa,adrian,smartmax).

likes(leonard,lego).
likes(adrian,lego).
likes(adrian,book).

age(leonard,6).
age(adrian,4).

jealous(C1,C2) :- aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2,
  true.

jealous(C1,C2) :- findall(G, 
    (owns(C2,G), 
     likes(C1,G), 
     not(owns(C1,G))
    ), 
    Gifts),
  length(Gifts,NGifts),
  NGifts > 0,
  true.

This works as expected:

?- jealous(adrian,leonard).
true.

However, when I reverse the order of the two jealous-predicates in the code:

?- jealous(adrian,leonard).
true ;
false.

That's pretty weird: I thought the jealous-clauses would behave as an 'or': whenever one of the results is true, there shouldn't be any further processing. So I'm wondering: how to I make this so that it really behaves as an 'or': if any of the jealous-rules is true, it should return true, in all other cases, it's false. I don't want 'the next results'. I need only 1 result: true or false.

What am I doing wrong? (Probably a few things, so please, enlighten me :) ).

Thx.

false
  • 10,264
  • 13
  • 101
  • 209
Kurt Sys
  • 31
  • 6
  • There's a choice point in your implementation. That means Prolog has other options to explore after the first success (true). Your `;` entry tells Prolog to go back to the choice point and check for more solutions. It doesn't find any more, so it then responds with false. This is normal Prolog behavior. – lurker Dec 04 '19 at 22:49
  • Well, that choice point depends on the order of the clauses I define... I can't see why Prolog would go back in some cases, and not in others. However, seems I may have found a solution: https://stackoverflow.com/questions/25346189/prolog-disjunction. – Kurt Sys Dec 04 '19 at 22:49
  • This is another example: https://stackoverflow.com/questions/42209223/prolog-true-false-output-of-member-predicate – lurker Dec 04 '19 at 22:51
  • yeah, true... I understand the `;`, I can't figure out why Prolog wants to continue whenever it found a `true`. But apparently, that's normal behaviour :p. – Kurt Sys Dec 04 '19 at 22:52
  • There is such a thing as writing a "deterministic" predicate in Prolog that does not leave a choice point. It can be very challenging to do so without losing generality (e.g., if you use a cut). – lurker Dec 04 '19 at 23:01
  • Dangling choice points are harmless but slightly unaesthetic and seem to cause new users of Prolog quite a bit of grief. Rather than stressing about it, you should probably just ignore them, since as @lurker points out, interventions you attempt in your first few days of using Prolog are likely to cause you harm you won't notice until much later (backwards correctness issues, for instance). Remember, nondeterminism is an _advantage_ of Prolog; you want predicates that generate, and you will usually follow them up with predicates that filter. – Daniel Lyons Dec 05 '19 at 06:41

1 Answers1

1

With the clauses as ordered, Prolog's search attempts first to match the first clause:

jealous(C1,C2) :- aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2.
  % the final true is unnecessary

that clause counts that adrian has 2 gifts and leonard 1, therefore N1 < N2, it fails here. Prolog backtracks, the whole clause fails and the algorithm attempts the second one, which succeeds:

?- jealous(adrian,leonard).
true.

At this point all clauses have been attempted, there is no other alternative path to try to resolve the query and so it ends here.

If the clauses are reversed, the successful one is tried first, and the resolution given:

?- jealous(adrian,leonard).
true

But a second clause exists which hasn't been tried yet, and so the search algorithm offers you the option of returning to exhaust this second option. Which you do:

;
false.

The second clause is attempted and fails as before, but it does so after the first has already resolved the query.

The difference in behaviour is also due to how the algorithm optimises its record of choice points. Backtracking is resource intensive, and Prolog algorithms optimise this by discarding deterministic solutions from the stack of choice points. That is, if there is a statement somewhere

NGifts > 0

clearly if NGifts is known there's only one possible solution (doesn't matter which), and backtracking at this point will not return with an alternative proof. So this statement is discarded from the choice stack as it is deterministic - its only solution has been explored.

When the clauses are ordered as in your questions, by the time both have been investigated and the solution is given, there is no choice point in the stack and the theorem prover exits. But if you swap them, a solution is found in the first clause before the second is attempted, therefore the existence of a second jealous clause leaves a choice point to explore, which is proposed to you.

If you need to control this behaviour, and do not need to identify cases where little boys are doubly jealous of each other, you can force Prolog to 'cut' out choice points:

jealous(C1,C2) :-
  findall(G, 
    (owns(C2,G), 
     likes(C1,G), 
     not(owns(C1,G))
    ), 
    Gifts),
  length(Gifts,NGifts),
  NGifts > 0,
  !. % cut: if this clause gets so far, later clauses do not need to be explored

jealous(C1,C2) :-
  aggregate_all(count, gives(santa,C1,X), N1), 
  aggregate_all(count, gives(santa,C2,X), N2),
  N1 < N2.

Which makes the behaviour of both programs identical in this example. I leave the 'be careful with cuts' discussion to comments and other questions.

boisvert
  • 3,679
  • 2
  • 27
  • 53
  • Nice explanation! Being careful with cuts, I get that one, since it depends heavily on the order of the clauses. Would it make more sense to use 'once' in the queries? – Kurt Sys Dec 05 '19 at 18:03
  • @KurtSys the problem (with both cut and once) is that it affects the workings of Prolog as a theorem prover. Logic programming (as a field) is supposed to allow you to think of the problem to solve independently of the algorithm execution. If you need 'once', or a cut, then your program is reliant on execution order, and so it's not a statement of your problem, rather it is a program to solve it. – boisvert Dec 05 '19 at 19:06
  • Right, I get that... (it felt wrong that the order is important). The `jealous`-clauses are not a problem statement, but a program solving the problem. I can see that. So, where should I put them, if they shouldn't be in the clauses? (Or how would I write the 'problem statement' better? – Kurt Sys Dec 05 '19 at 19:15
  • @KurtSys look for ways to simplify code, move complicated code to isolate ugly computations in separate rules or clauses, and name rules according to what you intend them for. Actually, your first clause doesn't need all the counting stuff. All you need is the owns/likes/not owns. If you get several "proofs" of jealousy, then rethink: each proof is a reason to be jealous, added to a tally that measures how bad the jealousy is. So NGifts is a kind of jealousy metric. – boisvert Dec 05 '19 at 19:26
  • totally makes sense to me now. It's up to the user to choose what to do with all the 'true' proofs (or, if one adds a metric, to do something with all the metrics). However, that leaves me with another question: can I bind all the proofs in one list? So far, `N1 – Kurt Sys Dec 05 '19 at 21:53
  • ... got it fixed adding a 'measure of jealousy' to each clause. I really like that idea/solution. And I 'extracted' the actual program (how to answer specific questions, such as 'how jealous is X on Y') into another file. Nice. Thx! – Kurt Sys Dec 05 '19 at 23:00