1

I have a little question about the negation as failure in Prolog language:

This is a question more theoretical than practical because I have clear how this example work.

so I have the following Prolog program:

/* Fatti che specificano quali esseri sono degli animali: */
animal(cat).
animal(dog).
animal(frog).
animal(horse).
animal(viper).
animal(boa).
animal(python).

/* Fatti che specificano quali esseri sono dei serpenti: */
snake(viper).
snake(boa).
snake(python).

/* X è un serpente, fallisce ed impedisce il backtracking quindi
   il predicato likes(mary,X) risulta essere falso: */
likes(mary,X) :- snake(X),
                 !,
                 fail.

/* Se X è un animale allora a mary piace: */
likes(mary, X) :- animal(X).

In Prolog I can't simply say something like: "Mary loves every animals, BUT NOT THE SNAKES" and I have to formulate it in this way: "If X is a snake, then Mary don't love it. Otherwise, if X it is an animal, mary love it"

The precedent program do exactly this thing, by the rule:

likes(mary,X) :- snake(X),
                 !,
                 fail.

Prolog check if it is true that X it is a snake, imposes the cut to avoid backtracking and force a failure of the predicate.

In this way if snake(X) is TRUE the program force the failure also of the head prediate likes(mary,X) and imposing backtracking avoid the possibility to execute the other rule in the program (that answer true because a snake is also an animal)

My question is: it seems me that this use of Prolog falls outside from the logical and declarative paradigm and in some way fall in some sort of procedural paradigm

Because:

  1. I have to impose an order of the 2 predicate (so in some way I am saying: if the first fail, try the second).
  2. But even more I am saying that: if the first rule match (X it is a snake) then execute a forced failure and imposes no backtracking.

This seems to me more near to a procedural meaning that a classical logical meaning...

Is it that? Is it that in these cases, Prolog uses a procedural behavior to overcome a limitation of the logic?

logi-kal
  • 7,107
  • 6
  • 31
  • 43
AndreaNobili
  • 40,955
  • 107
  • 324
  • 596

3 Answers3

4

I disagree with 'limitations of the logic'.

The same would be

likes(mary,X) :- not(snake(X)) , animal(X).

Because Prolog uses a depth-first-search some things can be expressed in an shorter way that then depends on the depth-first-search backtracking algorithm.

x :- a, !, b.
x :- c.
x :- d.

is the same as

x :- a, b.
x :- not(a), c.
x :- not(a), d.
User
  • 14,131
  • 2
  • 40
  • 59
  • 1
    I would add that Andrea is right in the sense that you _can_ use procedural behavior in Prolog to do things that are hard to do declaratively--though I agree with you that this is not an example of something hard to do declaratively. – Daniel Lyons Apr 08 '13 at 20:28
  • 6
    Consider writing that as `likes(mary, X) :- animal(X), \+ snake(X).`, and recall that `(\+)/1` (which is an ISO standard predicate, whereas `not/1` is not) is sound if its argument is ground. With this definition, you can even ask the most general query `?- likes(X, Y).` and get a correct result. – mat Apr 08 '13 at 21:41
  • Yes, this solves the clause ordering problem, even when "a" is non-ground at runtime and doesn't have side effects. But practially it induces an overhead and it doesn't solve the goal ordering problem when "a" is non-ground at runtime. –  Nov 13 '15 at 21:52
1

Programs that make use of cut (!) are most of the time sensitive to the ordering of goals and clauses in their meaning and not only in their termination, so they are often not declarative.

The negation as failure (\+) ecapsulates in a certain way the cut. It is defined and even implemented by most Prolog systems as follows:

\+ X :- X, !, fail.
\+ _ .

Although it hints a logical meaning and thus declarativity, the negation as failure is still sensitive to ordering of goals. Here is an example. Assume we have the following database:

p(a).
q(b,c).

Then the following query produces X=a as a solution:

?- p(X), \+ q(X,Y).
X = a.

But if the arguments of the conjunction (,)/2 switch side, a different result is obtained:

?- \+ q(X,Y), p(X).
false.

Ergo, negation as failure is not declarative per se. For ground term flow of arguments, negation as failure sneeks in an existential quantifiers. So a query of the form:

 ?- A(X), \+ B(X,Y).

Has essentially the meaning that it quantifies the fresh variables Y inside the negation:

 ?- A(X), ~ exists Y B(X,Y).

So in the above example where conjunction is switched, the set of fresh variables in the negation as failure changes, thats why different solutions are obtained.

Bye

0

In short, yes, it is procedural.

Negation as failure uses a cut, and cuts are procedural concepts. You cannot use negation as failure in a declarative way - it is not possible.

It is worth mentioning that not all uses of cuts throw declarativeness out of the window - some of them just increase efficiency. But unfortunately, this is not the case with negation as failure - declarativeness goes out the window.

(Prolog is just a procedural prover disguised as a declarative language lol)

Bob
  • 61
  • 1
  • 6