Exclamation mark in Prolog

Question

Given the following facts and predicates:

sound(time1).
sound(time2).
sun(time3).
relax(X):-sound(X),!,sun(X).
relax(_):-sun(_).

When executing relax(S). I'd expect to get S=time1 due to the !, that says (correct me if I'm wrong), that if 'X' is satisfied , then stop the backtracking.

Here is the trace:

3 ?- trace.
true.

[trace] 3 ?- relax(S).
   Call: (6) relax(_G1831) ? creep
   Call: (7) sound(_G1831) ? creep
   Exit: (7) sound(time1) ? creep
   Call: (7) sun(time1) ? creep
   Fail: (7) sun(time1) ? creep
   Fail: (6) relax(_G1831) ? creep
false.

So why does Prolog also checks sun(time1), even though that it met the exclamation mark after being satisfied by sound(X) (because sound(time1) is a fact).

This has nothing to do with functional programming and isn't appropriate for the programming-languages tag either... don't add tags just because you feel like it. — l4mpi, Feb 25 '13 at 11:53

score 41 · Answer 1 · answered Apr 03 '16 at 16:35

To clarify this even more, if somebody still struggles how exclamation operator works (like i did), here is an example:

sound(time3).
sound(time1).
sun(time1).
relax(X):-sound(X),!,sun(X).

For this certain example, if you ask Prolog for ?-relax(S). this results into false. We can describe Prolog working like this:

Prolog searches for asked predicate (relax(SOMEVARIABLE unifiable with S)) in our example).
Prolog finds predicate relax(X). Variables X and S are now bound.
Prolog starts to evaluate clauses:
- sound(X)
  - Prolog searches the file for fact which satisfies sound(X).
  - it finds the fact sound(time3). and unifies it with our variables X=S=time3.
- !
  - Prolog continues to next clausule which is operator ! so he will not backtrack back behind this operator.
- sun(X)
  - Prolog searches the file for the fact which satisfies sun(X). X is already bound so it searches for sun(time3) which does not exists.
Conclusion
- at this point, if there was no ! operator Prolog would return (backtrack) to sound(X) and it would reassign variable X=S as X=S=time1. Which would eventually result into true since fact sun(time1) exists.
- Prolog returns false because he could not match relax(S) for any rule.

In opposition like I said in 4. without ! operator it results into success.

sound(time3).
sound(time1).
sun(time1).
relax(X):-sound(X),sun(X).

Feel free to correct me if I am wrong at some point.

I found this explanation to be much clearer than the accepted answer, thank you! — Dan, Jan 24 '17 at 16:54

Sufian Latif · Accepted Answer · 2013-02-25T12:24:24.733

30

The ! sign prevents backtracking of the clauses to the right of it to the left, it's like a one-way gate so that it won't backtrack beyond the cut.

When sound(time1) is true, the next clause sun(time1) will be evaluated, and only then prolog will find that sun(time1) is false (by searching the knowledge base, it doesn't actually know that it's a fact).

Then, because of the cut, prolog won't try values time2 and time3 in the first clause.

More about cut:

Prolog evaluates the clauses of a predicate left to right. It binds a value to a variable in the leftmost clause. If the clause is true, it moves to the next one. If it's false, prolog tries other values as well.

If any of the clauses cannot be satisfied by any value, it would be false, and so will be the whole predicate (because the clauses are joined by AND).

The whole thing works as a depth-first traversal of a tree, where the clauses are the nodes and the edges represent different values of its variable. If the traversal finds a clause to be false, it would return to its preceding clause and try a different value.

Here comes the cut. If you put a cut (!) between two clauses, it would mean that if the clause after a cut becomes false, trying new values will go on ONLY IF the evaluation runs AFTER the cut. It means the values of the variables used before the cut are locked, and they cannot be changed when the evaluation crosses the cut.

edited Feb 25 '13 at 12:24

answered Feb 25 '13 at 11:23

Sufian Latif

13,086
3
33
70

So what you're saying is that there is no difference between `relax(X):-sound(X),!,sun(X).` and `relax(X):-sound(X),sun(X),!.` ? prolog would try only the current 'X' and then fail ... ? – JAN Feb 25 '13 at 11:53
@ron Of course there is a difference between the two, which is the location of the cut. The first version might give you the answer multiple times if `sun(X)` can be solved more than once - e.g. if you add `sun(time1).` and `sun(X) :- sound(X).` to your predicates and then ask for `relax(S)`. The second version will always result in one (or no) answer. You are correct though that it won't make a difference for your current set of predicates. – l4mpi Feb 25 '13 at 11:58
@l4mpi:OK ,so that's the weird part : why does prolog check beyond the `!` in `relax(X):-sound(X),!,sun(X).` ? If prolog found that `relax(time1)` is a fact , won't the `!` tell it not to check anything else , and in addition not to check also `sun(time1)` ? – JAN Feb 25 '13 at 12:20
3

@ron you misunderstood what the cut does. It does not stop evaluation, it just means that all choice points accumulated until `!` are discarded. When `sound(X)` is reached, possible soulutions are `time1` and `time2`. The prolog interpreter chooses the first one (`time1`) and creates a choice point it can backtrack to if the rest of the clause fails, so it can re-evaluate with `time2`. The `!` does nothing except discarding this choice point. Prolog now evaluates the rest of the predicate, but can't backtrack before the `!` and test with `time2` anymore. – l4mpi Feb 25 '13 at 12:37
@ron Prolog can __check__ beyond a cut (left to right), but cannot __backtrack__ beyond a cut (right to left) - that's why a cut is like a one-way gate. – Sufian Latif Feb 25 '13 at 12:51

score 5 · Answer 3 · answered Feb 25 '13 at 11:23

5

It will still try to satisfy the rest of the rule, it just won't backtrace to before the exclamation mark. That is, if sun(X) fails, it won't backtrace and try to match a different object to sound(X), but fail to match that rule entirely.

answered Feb 25 '13 at 11:23

Junuxx

14,011
5
41
71

Exclamation mark in Prolog

3 Answers3

Linked