Welcome to the last part of the Prolog Crash Course. Today we will talk about Cuts and Negations.
This post is based on this tutorial.
What is a "Cut"?
In the previous posts, we saw several examples of Prolog's backtracking behaviour. In some examples, we needed a lot of steps to travel the whole search tree. This can be inefficient, for example in cases where we know that there is only a single legitimate solution and no need to search further.
The cut operator T is designed to control the backtracking behaviour in order to increase efficiency. Let's look at an example.
We define a predicate maxi/3: the first two arguments define a range of numbers, and the third argument is equal to the maximum value of these two. In other words, this fact should return T:
: (? (maxi 5 1 5))
-> T
while these ones are NIL:
: (? (maxi 2 3 2))
-> NIL
: (? (maxi 2 3 5))
-> NIL
Of course we can also query the maximum:
: (? (maxi 2 3 @Max))
@Max=3
-> NIL
Now let's define maxi. We want to compare two numbers @X and @Y. To do this, we can call a PicoLisp function. The corresponding clause has three parts:
- the
^symbol in the CAR, - the PicoLisp program body in the CDDR,
- the variable to which the result is unified in the CADR.
(be maxi (@X @Y @Y)
(^ @ (<= @X @Y)) )
(be maxi (@X @Y @X)
(^ @ (> @X @Y)) )
We don't really care for the result as such, this is why the variable @ is anonymous.
Prolog tests two cases: first if @X <= @Y, and then if @X>@Y. Where is the problem?
Our definition is not wrong, but it is unefficient. If the first clause already returns T, there is actually no need to test for the second condition. The first and second clause are mutually exclusive. In this case, the cut operator comes in handy.
With the following notation, we can tell Prolog to stop if the first clause evaluates to T:
(be maxi (@X @Y @Y)
(^ @ (<= @X @Y))
T)
This type of cut is called a green cut, because there is no influence on the program output itself if you remove the cut symbol T.
On the other hand, red cuts are cuts that causes a program change. These cuts can be dangerous and need to be tested well.
Negation as a failure
There are two kinds of negations in formal logic. Strong negation means that a statement is considered as false only if it can be proven to be false. On the other hand, weak negation means that if a statement cannot be proven true, it is considered as false. Latter one is also called negation as a failure.
(In Prolog, this is implemented as **negation as failure* operator and can be written as \+)*.
Why do we need it? We can implement it to describe "except" statements, such as: "Mary likes all animals except insects". In Pilog, we can implement it using the cut operator and the built-in predicate (fail):
# Mary likes all animals except insects.
(be likes (Mary @X)
(insect @X)
T
(fail) )
(be likes (Mary @X)
(animal @X) )
where animals are:
(be animal (@X) (insect @X))
(be animal (@X) (pet @X))
(be animal (@X) (cattle @X))
(be insect (Spider))
(be pet (Cat))
(be pet (Dog))
(be cattle (Cow))
Let's test it:
: (? (likes Mary Cat))
-> T
: (? (likes Mary Spider))
-> NIL
Congratulations, with this post we have finished the Pilog introduction. In the next posts, we will see how we can embed it into PicoLisp and use it for database queries.
Top comments (0)