semantics - Why double negation doesn't bind in Prolog

Question

Say I have the following theory:

a(X) :- + b(X).

b(X) :- + c(X).

c(a).

It simply says true, which is of course correct, a(X) is true because there is no b(X) (with negation as finite failure). Since there is only a b(X) if there is no c(X) and we have c(a), one can state this is true. I was wondering however why Prolog does not provide the answer X = a? Say for instance I introduce some semantics:

noOrphan(X) :- + orphan(X).

orphan(X) :- + parent(_,X).

parent(david,michael).

Of course if I query noOrphan(michael), this will result in true and noOrphan(david) in false (since I didn't define a parent for david)., but I was wondering why there is no proactive way of detecting which persons (michael, david,...) belong to the noOrphan/1 relation?

This probably is a result of the backtracking mechanism of Prolog, but Prolog could maintain a state which validates if one is searching in the positive way (0,2,4,...) negations deep, or the negative way (1,3,5,...) negations deep.

Answer 1

Let's start with something simpler. Say + X = Y. Here, the negated goal is a predefined built-in predicate. So things are even clearer: X and Y should be different. However, + X = Y fails, because X = Y succeeds. So no trace is left under which precise condition the goal failed.

Thus, + + X = Y does produce an empty answer, and not the expected X = Y. See this answer for more.

Given that such simple queries already show problems, you cannot expect too much of user defined goals such as yours.

In the general case, you would have to first reconsider what you actually mean by negation. The answer is much more complex than it seems at first glance. Think of the program p :- + p. should p succeed or fail? Should p be true or not? There are actually two models here which no longer fits into Prolog's view of going with the minimal model. Considerations as these opened new branches to Logic Programming like Answer Set Programming (ASP).

But let's stick to Prolog. Negation can only be used in very restricted contexts, such as when the goal is sufficiently instantiated and the definition is stratified. Unfortunately, there are no generally accepted criteria for the safe execution of a negated goal. We could wait until the goal is variable free (ground), but this means quite often that we have to wait way too long - in jargon: the negated goal flounders.

So effectively, general negation does not go very well together with pure Prolog programs. The heart of Prolog really is the pure, monotonic subset of the language. Within the constraint part of Prolog (or its respective extensions) negation might work quite well, though.