(sec:3.3)= # Negation as failure # The following program computes the maximum of two integers: ```{swish} swish:3.3.1 --- query-id: swishq:3.3.x --- ``` `>=` and `=<` are built-in predicates with meaning 'greater than or equal' and 'less than or equal', respectively[^8_]. Declaratively, the program captures the intended meaning, but procedurally there are two different ways to solve queries of the form `?-max(N,N,M)`. The reason for this is that the bodies of the two clauses are not exclusive: they both succeed if the first two values of the `max` predicate are equal. We could of course remove one of the equality symbols, but suppose that we use a cut instead: ```{swish} swish:3.3.2 --- query-id: swishq:3.3.x --- ``` With a red cut, this program can only be understood procedurally. The question is: does the procedural meaning correspond to the intended meaning? Perhaps surprisingly, the answer is no! For instance, the query ```{swish-query} swishq:3.3.x ?-max(5,3,3). ``` succeeds: the cut is never reached, because the literal in the query does not unify with the head of the first clause. The second program is in fact a very bad program: the declarative and procedural meanings differ, and **neither** of them captures the intended meaning. ```{exercise} ex:3.4 ``` +++ The procedural meaning of the program would be correct if its use is restricted to queries with uninstantiated third argument. It illustrates a very common use of cut: to ensure that the bodies of the clauses are mutually exclusive. In general, if we have a program of the form ```pProlog p:-q,!,r. p:-s. ``` its meaning is something like ```pProlog p:-q,r. p:-not_q,s. ``` How should `not_q` be defined, in order to make the second program work? If `q` succeeds, `not_q` should fail. This is expressed by the following clause: ```pProlog not_q:-q,fail. ``` where `fail` is a built-in predicate, which is always **false**. If `q` fails, `not_q` should succeed. This can be realised by the program ```pProlog not_q:-q,!,fail. not_q. ``` The cut in the first clause is needed to prevent backtracking to the second clause when `q` succeeds. +++ This approach is not very practical, because it only works for a single proposition symbol, without variables. We would like to treat the literal to be negated as a parameter, as in ```Prolog not(Goal):- /* execute Goal, */ !,fail. not(Goal). ``` The problem now is to execute a goal which is passed to the predicate `not` as a term. Prolog provides two facilities for this. One is the built-in predicate `call`, which takes a goal as argument and succeeds if and only if execution of that goal succeeds. The second facility[^9_] is merely a shorthand for this: instead of writing `call(Goal)`, one may simply write `Goal`, as in ```{swish} swish:3.3.2_2 ``` This is a slight abuse of the syntax rules, because a variable (a term) occurs in a position where only atoms are allowed. As long as the variable is instantiated to a goal before it is reached, this will, however, cause no problem (if it is not correctly instantiated, Prolog will generate an error-message). Predicates like `not` and `call` are called *meta-predicates*, that take formulas from the same logical language in which they are written as arguments. As we will see in later chapters, meta-predicates play an important role in this book. +++ We illustrate the operation of `not` by means of the following propositional program: ```pProlog p:-q,r. p:-not(q),s. s. ``` and the query `?-p`. The SLD-tree is shown in {numref}`fig:3.9`. The first clause for `p` leads to a failure branch, because `q` cannot be proved. The second clause for `p` is tried, and `not(q)` is evaluated by trying to prove `q`. Again, this fails, which means that the second clause for `not` is tried, which succeeds. Thus, `not(q)` *is proved by failing to prove* `q`! Therefore, this kind of negation is called *negation as failure*. ```{figure} /src/fig/part_i/image038.svg --- name: 'fig:3.9' width: 32% --- SLD-tree with `not`. ``` +++ {numref}`fig:3.9` shows, that Prolog tries to prove `q` twice. Consequently, the program with `not` is slightly less efficient than the version with cut: ```pProlog p:-q,!,r. p:-s. s. ``` which leads to the SLD-tree shown in {numref}`fig:3.10`. Here, `q` is tried only once. However, in general we prefer the use of `not`, because it leads to programs of which the declarative meaning corresponds more closely to the procedural meaning. ```{figure} /src/fig/part_i/image040.svg --- name: 'fig:3.10' width: 27% --- Equivalent SLD-tree with cut. ``` +++ In the following program, `:-not(q)` fails because `:-q` succeeds: ```pProlog p:-not(q),r. p:-q. q. r. ``` The SLD-tree for the query `?-p` is shown in {numref}`fig:3.11`. Since `q` succeeds, `fail` ensures that `not(q)` fails. The cut is needed to ensure that everything following the `not` is pruned, even if it contains a success branch. ```{figure} /src/fig/part_i/image042.svg --- name: 'fig:3.11' width: 40% --- `:-not(q)` fails because `:-q` succeeds. ``` +++ The implementation of `not` illustrated above can lead to problems if variables are involved. Take a look at the following program: ```{swish} swish:3.3.3 ``` ```{exercise} ex:3.5 ``` +++ Consider the query ```{swish-query} swishq:3.3.3a ?-bachelor(X). ``` for which the SLD-tree is depicted in {numref}`fig:3.12`. According to negation as failure, Prolog tries to prove `not(married(X))` by trying `married(X)` first. Since this succeeds for `X = fred`, the cut is reached and the success branch to the right (representing the correct answer { `X` → `peter` }) is pruned. Thus, `:-not(married(X))` fails because `:-married(X)` succeeds for one value of `X`. That is, `not(married(X))` is interpreted as 'it is false that somebody is married', or equivalently, 'nobody is married'. But this means that the clause ```Prolog bachelor(X):-not(married(X)),man(X). ``` is interpreted as '`X` is a bachelor if nobody is married and `X` is a man', which is of course not as intended. ```{figure} /src/fig/part_i/image044.svg --- name: 'fig:3.12' width: 55% --- There are no bachelors?! ``` ````{infobox} --- title: Negation as failure vs. logical negation --- Negation as failure is not the same as logical negation: if we cannot prove `q`, we know that `q` is not a logical consequence of the program, but this does not mean that its negation `:-q` is a logical consequence of the program. Adopting negation as failure is similar to saying 'I cannot prove that God exists, therefore I conclude God does not exist'. It is a kind of reasoning that is applicable in some contexts, but inadequate in others. Logical negation can only be expressed by indefinite clauses, as in the following program: ```pProlog p:-q,r. p;q:-s. s. ``` Semantically speaking, if we don't have enough information to conclude that a formula $F$ is true or false, the truth value of its logical negation will also be undecided, but `not`$(F)$ will be true. This property of negation as failure can be very useful when dealing with exceptions to rules: if we don't know that something is an exception to a rule, we assume that it's not, so we only have to list the exceptions and not the normal cases. This approach will be extensively discussed in {numref}`Chapter %s` on reasoning with incomplete information. ```` +++ Thus, if `G` is instantiated to a goal containing variables at the time `not(G)` is called, the result may be not in accordance with negation as failure. *It is the programmer's responsibility to avoid this*. A simple remedy that will often work is to ensure the grounding of `G` by literals preceding `not(G)` in the body of the clause, i.e. ```{swish} swish:3.3.3a --- query-id: swishq:3.3.3a --- ``` ```{exercise} ex:3.6 ``` +++ Thus, we see that changing the order of the literals in the body of a clause does not only affect the order in which answers to a query are found, but it may also change the set of answers! Of course, this is very much against the spirit of declarative programming, because the declarative interpretation of a clause does not depend on the order of the literals. Therefore, some Prolog interpreters provide a mechanism which defers the evaluation of `not(G)` until `G` is ground. However, with standard Prolog it is the programmer's duty to ensure that `not` is never called with a non-ground argument. +++ Let's summarise the points made about negation in Prolog. It is often used to ensure that only one of several possible clauses is applicable. The same effect can be achieved by means of cut, but in general we prefer the use of `not`, although it is somewhat less efficient[^10_]. `not` is supplied by Prolog as a meta-predicate (i.e. a predicate which takes formulas from the same logical language in which it is written as arguments). It is only a partially correct implementation of negation as failure, since it does not operate correctly when its argument is a goal containing variables. [^8_]: Written this way to distinguish them from the arrows `=>` and `<=`. [^9_]: This is not allowed by every Prolog interpreter. [^10_]: Since efficiency is an implementation issue, it is suggested that `not` is replaced by `!` only in the final stage of program development.