Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Exclamation mark in Prolog

Tags:

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).

like image 971
JAN Avatar asked Feb 25 '13 11:02

JAN


People also ask

What does exclamation mark do in Prolog?

Prolog provides a predicate that performs this function. It is called the cut, represented by an exclamation point (!). The cut effectively tells Prolog to freeze all the decisions made so far in this predicate. That is, if required to backtrack, it will automatically fail without trying other alternatives.

What does the symbol mean in Prolog?

! symbol represents the cut . You can read more about cut here. Also, an example in prolog can be found here.

What does \+ mean in Prolog?

Because of the problems of negation-as-failure, negation in Prolog is represented in modern Prolog interpreters using the symbol \+ , which is supposed to be a mnemonic for not provable with the \ standing for not and the + for provable.

What is fail in Prolog?

As its name suggests, fail/0 is a special symbol that will immediately fail when Prolog encounters it as a goal. That may not sound too useful, but remember: when Prolog fails, it tries to backtrack . Thus fail/0 can be viewed as an instruction to force backtracking.


2 Answers

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:

  1. Prolog searches for asked predicate (relax(SOMEVARIABLE unifiable with S)) in our example).
  2. Prolog finds predicate relax(X). Variables X and S are now bound.
  3. 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.
  4. 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.

like image 94
Smarty77 Avatar answered Sep 18 '22 13:09

Smarty77


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.

like image 29
Sufian Latif Avatar answered Sep 19 '22 13:09

Sufian Latif